# On the Consistency of Graph-based Bayesian Learning and the Scalability of Sampling Algorithms

arXiv: https://arxiv.org/abs/1710.07702 · HTML: https://mlsanity.com/paper/1710.07702/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Oct 2017.

## Built on by (most cited first, 5 of 5)

- [Optimization on Manifolds via Graph Gaussian Processes](https://mlsanity.com/paper/2210.10962/) (2022)
- [Rates of Convergence for Regression with the Graph Poly-Laplacian](https://mlsanity.com/paper/2209.02305/) (2022)
- [Laplace Learning in Wasserstein Space](https://mlsanity.com/paper/2511.13229/) (2025)
- [Mathematical Foundations of Graph-Based Bayesian Semi-Supervised Learning](https://mlsanity.com/paper/2207.01093/) (2022)
- [Manifold limit for the training of shallow graph convolutional neural networks](https://mlsanity.com/paper/2601.06025/) (2026)

## Abstract (arXiv)

A popular approach to semi-supervised learning proceeds by endowing the input data with a graph structure in order to extract geometric information and incorporate it into a Bayesian framework. We introduce new theory that gives appropriate scalings of graph parameters that provably lead to a well-defined limiting posterior as the size of the unlabeled data set grows. Furthermore, we show that these consistency results have profound algorithmic implications. When consistency holds, carefully designed graph-based Markov chain Monte Carlo algorithms are proved to have a uniform spectral gap, independent of the number of unlabeled inputs. Several numerical experiments corroborate both the statistical consistency and the algorithmic scalability established by the theory.