Belief Propagation Converges to Gaussian Distributions in Sparsely-Connected Factor Graphs
Tom Yates, Yuzhou Cheng, Ignacio Alzugaray, Danyal Akarca, Pedro Mediano, Andrew Davison
Abstract
Belief Propagation (BP) is a powerful algorithm for distributed inference in probabilistic graphical models, however it quickly becomes infeasible for practical compute and memory budgets. Many efficient, non-parametric forms of BP have been developed, but the most popular is Gaussian Belief Propagation (GBP), a variant that assumes all distributions are locally Gaussian. GBP is widely used due to its efficiency and empirically strong performance in applications like computer vision or sensor networks – even when modelling non-Gaussian problems. In this paper, we seek to provide a theoretical guarantee for when Gaussian approximations are valid in highly non-Gaussian, sparsely-connected factor graphs performing BP (common in Spatial AI). We leverage the Central Limit Theorem to prove mathematically that variables’ beliefs under BP converge to a Gaussian distribution in complex, loopy factor graphs obeying our 4 key assumptions. We then confirm experimentally that variable beliefs become increasingly Gaussian after just a few BP iterations in a stereo depth estimation task.
BibTeX
@inproceedings{
yates2026belief,
title={Belief Propagation Converges to Gaussian Distributions in Sparsely-Connected Factor Graphs},
author={Tom Yates and Yuzhou Cheng and Ignacio Alzugaray and Danyal Akarca and Pedro A. M. Mediano and Andrew J. Davison},
booktitle={Forty-third International Conference on Machine Learning},
year={2026},
url={https://openreview.net/forum?id=FaGn04tvzq}
}