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

2017/10/20 by Nicolás García Trillos, Zachary Kaplan, Trillos, Nicolas Garcia +5 · 2 citations
Computer Science · #Bayesian Modeling and Causal Inference #Computation (stat.CO) #FOS: Computer and information sciences #FOS: Mathematics #Gaussian Processes and Bayesian Inference #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Probability (math.PR)

paper · pdf · doi:10.48550/arxiv.1710.07702

openalex publication_date 2017/10/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/31

Abstract

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.

Citations

• Convergence of Laplacian spectra from random samples
• Towards a theoretical foundation for Laplacian-based manifold methods
• Asymptotic behavior of ℓ_p-based Laplacian regularization in semi-supervised learning

Cited by

• Laplace Learning in Wasserstein Space
• Bayesian Inverse Problems on Metric Graphs

Related

• Unlabeled Data Help in Graph-Based Semi-Supervised Learning: A Bayesian Nonparametrics Perspective
• Large Data and Zero Noise Limits of Graph-Based Semi-Supervised Learning\n Algorithms
• Bayesian Graph Selection Consistency Under Model Misspecification
• Bayesian computation for high-dimensional Gaussian Graphical Models with spike-and-slab priors
• Scalable Monte Carlo for Bayesian Learning