Semi-supervised learning with regularized Laplacian

Abstract

We study a semi-supervised learning method based on the similarity graph and regularized Laplacian. We give convenient optimization formulation of the regularized Laplacian method and establish its various properties. In particular, we show that the kernel of the method can be interpreted in terms of discrete and continuous-time random walks and possesses several important properties of proximity measures. Both optimization and linear algebra methods can be used for efficient computation of the classification functions. We demonstrate on numerical examples that the regularized Laplacian method is robust with respect to the choice of the regularization parameter and outperforms the Laplacian-based heat kernel methods.

Keywords:

• semi-supervised learning
• graph-based learning
• regularized Laplacian
• proximity measure
• Wikipedia article classification

AMS Subject Classification:

• 68T01
• 68T05
• 15A16
• 15A45
• 97R40
• 05C50

Acknowledgments

We would like to thank the reviewers for very useful suggestions that helped to improve the presentation of the material.

Disclosure statement

No potential conflict of interest was reported by the authors.

Notes

1. Cf. the cosine law [21] and the inverse covariance mapping [22, Section 5.2].

2. http://download.wikimedia.org/enwiki/20100130

3. http://www.ams.org/mathscinet/msc/msc2010.html

Additional information

Funding

This work was partially supported by Campus France, Alcatel-Lucent Inria Joint Lab, EU Project Congas FP7-ICT-2011-8-317672, and Russian Science Foundation (RFBR) [grant numbers 16-11-00063, 3-07-00990].