Properly-weighted graph Laplacian for semi-supervised learning
It addresses a stability issue in semi-supervised learning for applications with limited labeled data, though it appears incremental as it builds on existing Laplacian regularization approaches.
The paper tackles the degeneracy of graph Laplacian methods in semi-supervised learning when labeled data is scarce, by proposing a properly-weighted Laplacian that ensures stability and convergence to a smooth solution in the large-sample limit.
The performance of traditional graph Laplacian methods for semi-supervised learning degrades substantially as the ratio of labeled to unlabeled data decreases, due to a degeneracy in the graph Laplacian. Several approaches have been proposed recently to address this, however we show that some of them remain ill-posed in the large-data limit. In this paper, we show a way to correctly set the weights in Laplacian regularization so that the estimator remains well posed and stable in the large-sample limit. We prove that our semi-supervised learning algorithm converges, in the infinite sample size limit, to the smooth solution of a continuum variational problem that attains the labeled values continuously. Our method is fast and easy to implement.