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

This paper considers a Bayesian approach to a semi-supervised learning problem, assuming that inputs come from a manifold. The paper shows that with the right graph structure on the input data, the resulting graph posterior distribution converges to the continuum limit as the size of unlabeled inputs grows. Further, when this consistency holds, carefully designed MCMC algorithms have a uniform spectral gap, independent of the number of unlabeled inputs.

Recommended citation: Nicolas Garcia Trillos, Zachary Kaplan, Thabo Samakhoana, Daniel Sanz-Alonso. (2020). "On the consistency of graph-based Bayesian semi-supervised learning and the scalability of sampling algorithms." Journal of Machine Learning Research. 21(28).