On the consistency of graph-based Bayesian semi-supervised learning and the scalability of sampling algorithms

Nicolas Garcia Trillos; Zachary Kaplan; Thabo Samakhoana; Daniel Sanz-Alonso

This paper considers a Bayesian approach to graph-based semi-supervised learning. We show that if the graph parameters are suitably scaled, the graph-posteriors converge to a continuum limit as the size of the unlabeled data set grows. This consistency result has profound algorithmic implications: we prove that when consistency holds, carefully designed Markov chain Monte Carlo algorithms have a uniform spectral gap, independent of the number of unlabeled inputs. Numerical experiments illustrate and complement the theory.

On the consistency of graph-based Bayesian semi-supervised learning and the scalability of sampling algorithms

Abstract