Consistency of Fractional Graph-Laplacian Regularization in Semisupervised Learning with Finite Labels
Adrien Weihs, Matthew Thorpe · SIAM Journal on Mathematical Analysis · 2024
Abstract. Laplace learning is a popular machine learning algorithm for finding missing labels from a small number of labeled feature vectors using the geometry of a graph. More precisely, Laplace learning is based on minimizing a graph-Dirichlet energy, equivalently a discrete Sobolev [Formula: see text] seminorm, constrained to taking the values of known labels on a given subset. The variational problem is asymptotically ill-posed as the number of unlabeled feature vectors goes to infinity for finite given labels due to a lack of regularity in minimizers of the continuum Dirichlet energy in any dimension higher than one. In particular, continuum minimizers are not continuous. One solution is to consider higher-order regularization, which is the analogue of minimizing Sobolev [Formula: see text] seminorms. In this paper we consider the asymptotics of minimizing a graph variant of the Sobolev [Formula: see text] seminorm with pointwise constraints. We show that, as expected, one needs [Formula: see text], where [Formula: see text] is the dimension of the data manifold. We also show that there must be an upper bound on the connectivity of the graph; that is, highly connected graphs lead to degenerate behavior of the minimizer even when [Formula: see text].