Abstract
Graph-based method is one important paradigm of semi-supervised learning (SSL). Its learning performance typically relies on excellent graph construction which, however, remains challenging for general cases. What is more serious, constructing graph improperly may even deteriorate performance, which means its performance is worse than that of its supervised counterpart with only labeled data. For this reason, we consider learning a safe graph construction for graph-based SSL in this work such that its performance will not significantly perform worse than its supervised counterpart. Our basic idea is that, given a data distribution, there often exist some dense areas which are robust to graph construction. We then propose to combine trustable subgraphs in these areas from a set of candidate graphs to derive a safe graph, which remains to be a convex problem. Experimental results on a number of datasets show that our proposal is able to effectively avoid performance degeneration compared with many graph-based SSL methods.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Argyriou, A., Herbster, M., Pontil, M.: Combining graph Laplacians for semi-supervised learning. In: Advances in Neural Information Processing Systems, Cambridge, MA, pp. 67–74 (2005)
Balsubramani, A., Freund, Y.: Optimally combining classifiers using unlabeled data. In: Proceedings of International Conference on Learning Theory, Paris, France, pp. 211–225 (2015)
Belkin, M., Niyogi, P.: Towards a theoretical foundation for Laplacian-based manifold methods. J. Comput. Syst. Sci. 74(8), 1289–1308 (2008)
Belkin, M., Niyogi, P., Sindhwani, V.: Manifold regularization: a geometric framework for learning from labeled and unlabeled examples. J. Mach. Learn. Res. 7, 2399–2434 (2006)
Blum, A., Chawla, S.: Learning from labeled and unlabeled data using graph mincuts. In: Proceedings of the 8th International Conference on Machine Learning, Williamstown, MA, pp. 19–26 (2001)
Bottou, L., Curtis, F.E., Nocedal, J.: Optimization methods for large-scale machine learning. ar**v preprint ar**v:1606.04838 (2016)
CarreiraPerpiñán, M.Á., Zemel, R.S.: Proximity graphs for clustering and manifold learning. In: Advances in Neural Information Processing Systems, Cambridge, MA, pp. 225–232 (2005)
Chapelle, O., Schölkopf, B., Zien, A. (eds.): Semi-Supervised Learning. MIT Press, Cambridge (2006)
Guo, L.-Z., Li, Y.-F.: A general formulation for safely exploiting weakly supervised data. In: Proceedings of the 32nd AAAI Conference on Artificial Intelligence, New Orleans, LA (2018)
Jebara, T., Wang, J., Chang, S.F.: Graph construction and b-matching for semi-supervised learning. In: Proceedings of the 26th International Conference on Machine Learning, Montreal, Canada, pp. 441–448 (2009)
Joachims, T.: Transductive learning via spectral graph partitioning. In: Proceedings of the 20th International Conference on Machine Learning, Washington, DC, pp. 290–297 (2003)
Krijthe, J.H., Loog, M.: Implicitly constrained semi-supervised least squares classification. In: Fromont, E., De Bie, T., van Leeuwen, M. (eds.) IDA 2015. LNCS, vol. 9385, pp. 158–169. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-24465-5_14
Li, Y.-F., Zhou, Z.-H.: Towards making unlabeled data never hurt. In: Proceedings of the 28th International Conference on Machine Learning, Bellevue, WA, pp. 1081–1088 (2011)
Li, Y.-F., Zhou, Z.-H.: Towards making unlabeled data never hurt. IEEE Trans. Pattern Anal. Mach. Intell. 37(1), 175–188 (2015)
Li, Y.-F., Wang, S.-B., Zhou, Z.-H.: Graph quality judgement: a large margin expedition. In: Proceedings of the 25th International Joint Conference on Artificial Intelligence, New York, NY, pp. 1725–1731 (2016)
Li, Y.-F., Kwok, J., Zhou, Z.-H.: Towards safe semi-supervised learning for multivariate performance measures. In: Proceedings of the 30th AAAI Conference on Artificial Intelligence, Phoenix, AZ, pp. 1816–1822 (2016)
Li, Y.-F., Zha, H.-W., Zhou, Z.-H.: Learning safe prediction for semi-supervised regression. In: Proceedings of the 31st AAAI Conference on Artificial Intelligence, San Francisco, CA, pp. 2217–2223 (2017)
Liang, D.-M., Li, Y.-F.: Lightweight label propagation for large-scale network data. In: Proceedings of the 27th International Joint Conference on Artificial Intelligence, Stockholm, Sweden (2018)
Liu, W., Wang, J., Chang, S.F.: Robust and scalable graph-based semisupervised learning. Proc. IEEE 100(9), 2624–2638 (2012)
Nesterov, Y.: Introductory Lectures on Convex Optimization. A Basic Course. Springer, Heidelberg (2003). https://doi.org/10.1007/978-1-4419-8853-9
Niu, G., du Plessis, M.C., Sakai, T., Ma, Y., Sugiyama, M.: Theoretical comparisons of positive-unlabeled learning against positive-negative learning. In: Advances in Neural Information Processing Systems, Barcelona, Spain, pp. 1199–1207 (2016)
Stewart, R., Ermon, S.: Label-free supervision of neural networks with physics and domain knowledge. In: Proceedings of 31th AAAI Conference on Artificial Intelligence, San Francisco, CA (2017)
Wang, F., Zhang, C.: Label propagation through linear neighborhoods. In: Proceedings of the 23rd International Conference on Machine Learning, Pittsburgh, PA, pp. 985–992 (2006)
Wang, F., Zhang, C.: Label propagation through linear neighborhoods. IEEE Trans. Knowl. Data Eng. 20(1), 55–67 (2008)
Wang, Y.-Y., Chen, S.-C., Zhou, Z.-H.: New semi-supervised classification method based on modified cluster assumption. IEEE Trans. Neural Netw. Learn. Syst. 23(5), 689–702 (2012)
Wei, T., Guo, L.-Z., Li, Y.-F., Gao, W.: Learning safe multi-label prediction for weakly labeled data. Mach. Learn. 107(4), 703–725 (2018)
Zhou, D., Bousquet, O., Navin Lal, T., Weston, J., Schölkopf, B.: Learning with local and global consistency. In: Advances in Neural Information Processing Systems, pp. 595–602. MIT Press, Cambridge (2004)
Zhu, X., Ghahramani, Z., Lafferty, J.: Semi-supervised learning using Gaussian fields and harmonic functions. In: Proceedings of the 20th International Conference on Machine learning, Washington, DC, pp. 912–919 (2003)
Zhu, X., Kandola, J., Ghahramani, Z., Lafferty, J.: Nonparametric transforms of graph kernels for semi-supervised learning. In: Advances in Neural Information Processing Systems, pp. 1641–1648. MIT Press, Cambridge (2005)
Zhu, X.: Semi-supervised learning literature survey. Technical report, University of Wisconsin-Madison (2007)
Zhou, Z.-H.: A brief introduction to weakly supervised learning. Natl. Sci. Rev. 5(1), 44–53 (2018)
Acknowledgement
The authors want to thank the reviewers for their helpful comments. This research was supported by the National Natural Science Foundation of China (61772262) and the Fundamental Research Funds for the Central Universities (020214380044).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer Nature Singapore Pte Ltd.
About this paper
Cite this paper
Liang, DM., Li, YF. (2018). Learning Safe Graph Construction from Multiple Graphs. In: Zhou, ZH., Yang, Q., Gao, Y., Zheng, Y. (eds) Artificial Intelligence. ICAI 2018. Communications in Computer and Information Science, vol 888. Springer, Singapore. https://doi.org/10.1007/978-981-13-2122-1_4
Download citation
DOI: https://doi.org/10.1007/978-981-13-2122-1_4
Published:
Publisher Name: Springer, Singapore
Print ISBN: 978-981-13-2121-4
Online ISBN: 978-981-13-2122-1
eBook Packages: Computer ScienceComputer Science (R0)
