Semi-Supervised Laplace Learning on Stiefel Manifolds
This addresses a specific bottleneck in semi-supervised learning for practitioners dealing with limited labeled data, representing a strong incremental improvement.
The paper tackles the degeneracy of Laplace learning algorithms at low label rates by reformulating graph-based semi-supervised learning as a nonconvex trust-region subproblem and developing sequential subspace optimization with a novel sample selection method. It demonstrates lower classification error compared to state-of-the-art methods across low, medium, and high label rates.
Motivated by the need to address the degeneracy of canonical Laplace learning algorithms in low label rates, we propose to reformulate graph-based semi-supervised learning as a nonconvex generalization of a \emph{Trust-Region Subproblem} (TRS). This reformulation is motivated by the well-posedness of Laplacian eigenvectors in the limit of infinite unlabeled data. To solve this problem, we first show that a first-order condition implies the solution of a manifold alignment problem and that solutions to the classical \emph{Orthogonal Procrustes} problem can be used to efficiently find good classifiers that are amenable to further refinement. To tackle refinement, we develop the framework of Sequential Subspace Optimization for graph-based SSL. Next, we address the criticality of selecting supervised samples at low-label rates. We characterize informative samples with a novel measure of centrality derived from the principal eigenvectors of a certain submatrix of the graph Laplacian. We demonstrate that our framework achieves lower classification error compared to recent state-of-the-art and classical semi-supervised learning methods at extremely low, medium, and high label rates.