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.