Graph construction and b-matching for semi-supervised learning

ABSTRACT

Graph based semi-supervised learning (SSL) methods play an increasingly important role in practical machine learning systems. A crucial step in graph based SSL methods is the conversion of data into a weighted graph. However, most of the SSL literature focuses on developing label inference algorithms without extensively studying the graph building method and its effect on performance. This article provides an empirical study of leading semi-supervised methods under a wide range of graph construction algorithms. These SSL inference algorithms include the Local and Global Consistency (LGC) method, the Gaussian Random Field (GRF) method, the Graph Transduction via Alternating Minimization (GTAM) method as well as other techniques. Several approaches for graph construction, sparsification and weighting are explored including the popular k-nearest neighbors method (kNN) and the b-matching method. As opposed to the greedily constructed kNN graph, the b-matched graph ensures each node in the graph has the same number of edges and produces a balanced or regular graph. Experimental results on both artificial data and real benchmark datasets indicate that b-matching produces more robust graphs and therefore provides significantly better prediction accuracy without any significant change in computation time.

REFERENCES

• 1: Bayati, M., Shah, D., & Sharma, M. (2005). Maximum weight matching via max-product belief propagation. Int. Symp. on Information Theory (pp. 1763--1767).
• 2: Mikhail Belkin , Partha Niyogi, Towards a theoretical foundation for Laplacian-based manifold methods, Journal of Computer and System Sciences, v.74 n.8, p.1289-1308, December, 2008 [doi>10.1016/j.jcss.2007.08.006]
• 3: Belkin, M., Niyogi, P., & Sindhwani, V. (2005). On manifold regularization. Int. Workshop on Artificial Intelligence and Statistics.
• 4: Avrim Blum , Shuchi Chawla, Learning from Labeled and Unlabeled Data using Graph Mincuts, Proceedings of the Eighteenth International Conference on Machine Learning, p.19-26, June 28-July 01, 2001
• 5: Chapelle, O., Schölkopf, B., & Zien, A. (Eds.). (2006). Semi-supervised learning. Cambridge, MA: MIT Press.
• 6: Chung, F. (1997). Spectral Graph Theory. American Mathematical Society.
• 7: Edmonds, J. (1965). Paths, trees and flowers. Canadian Journal of Mathematics, 17, 449--467.
• 8: Huang, B., & Jebara, T. (2007). Loopy belief propagation for bipartite maximum weight b-matching. Int. Workshop on Artificial Intelligence and Statistics.
• 9: Jebara, T., & Shchogolev, V. (2006). B-Matching for Spectral Clustering. The European Conf. on Mach. Learn. (pp. 679--686). Springer.
• 10: Maier, M., & Luxburg, U. (2009). Influence of graph construction on graph-based clustering measures. The Neural Information Processing Systems, 22, 1025--1032.
• 11: Roweis, S., & Saul, L. (2000). Nonlinear Dimensionality Reduction by Locally Linear Embedding. Science, 290, 2323--2326.
• 12: J. Salez , D. Shah, Optimality of belief propagation for random assignment problem, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.187-196, January 04-06, 2009, New York, New York
• 13: Fei Wang , Changshui Zhang, Label Propagation through Linear Neighborhoods, IEEE Transactions on Knowledge and Data Engineering, v.20 n.1, p.55-67, January 2008 [doi>10.1109/TKDE.2007.190672]
• 14: Jun Wang , Tony Jebara , Shih-Fu Chang, Graph transduction via alternating minimization, Proceedings of the 25th international conference on Machine learning, p.1144-1151, July 05-09, 2008, Helsinki, Finland [doi>10.1145/1390156.1390300]
• 15: J. Zhang , M. Marszałek , S. Lazebnik , C. Schmid, Local Features and Kernels for Classification of Texture and Object Categories: A Comprehensive Study, International Journal of Computer Vision, v.73 n.2, p.213-238, June 2007 [doi>10.1007/s11263-006-9794-4]
• 16: Zhou, D., Bousquet, O., Lal, T., Weston, J., & Schöölkopf, B. (2004). Learning with local and global consistency. The Neural Information Processing Systems (pp. 321--328).
• 17: Zhu, X. (2005). Semi-supervised learning literature survey (Technical Report 1530). Computer Sciences, University of Wisconsin-Madison.
• 18: Zhu, X., Ghahramani, Z., & Lafferty, J. (2003). Semi-supervised learning using gaussian fields and harmonic functions. Int. Conf. on Mach. Learn. (pp. 912--919).

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Pattern matching

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Graph and tree search strategies
  I.6 SIMULATION AND MODELING
      I.6.4 Model Validation and Analysis
      I.6.5 Model Development
          Subjects: Modeling methodologies

General Terms:
Algorithms, Design, Performance, Theory