# Understanding the Behavior of Belief Propagation

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 155 references that are in the map.
- First posted on arXiv 5 Sep 2022.

## Builds on (most cited first, 13 of 13)

- [Statistical physics of inference: Thresholds and algorithms](https://mlsanity.com/paper/1511.02476/) (2015)
- [Loopy Belief Propagation for Approximate Inference: An Empirical Study](https://mlsanity.com/paper/1301.6725/) (2013)
- [Spectral Clustering of Graphs with the Bethe Hessian](https://mlsanity.com/paper/1406.1880/) (2014)
- [Fixed Points of Belief Propagation -- An Analysis via Polynomial Homotopy Continuation](https://mlsanity.com/paper/1605.06451/) (2016)
- [Belief Propagation in Conditional RBMs for Structured Prediction](https://mlsanity.com/paper/1703.00986/) (2017)
- [Self-Guided Belief Propagation -- A Homotopy Continuation Method](https://mlsanity.com/paper/1812.01339/) (2018)
- [Belief Optimization for Binary Networks: A Stable Alternative to Loopy Belief Propagation](https://mlsanity.com/paper/1301.2317/) (2013)
- [Approximating the Bethe partition function](https://mlsanity.com/paper/1401.0044/) (2013)
- [Revisiting Algebra and Complexity of Inference in Graphical Models](https://mlsanity.com/paper/1409.7410/) (2014)
- [Gauged Mini-Bucket Elimination for Approximate Inference](https://mlsanity.com/paper/1801.01649/) (2018)
- [Perturbed Message Passing for Constraint Satisfaction Problems](https://mlsanity.com/paper/1401.6686/) (2014)
- [Clamping Improves TRW and Mean Field Approximations](https://mlsanity.com/paper/1510.00087/) (2015)
- [On the Network Topology Dependent Solution Count of the Algebraic Load Flow Equations](https://mlsanity.com/paper/1512.04987/) (2015)

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

- [Exact Soft Analytical Side-Channel Attacks using Tractable Circuits](https://mlsanity.com/paper/2501.13748/) (2025)

## Abstract (arXiv)

Probabilistic graphical models are a powerful concept for modeling high-dimensional distributions. Besides modeling distributions, probabilistic graphical models also provide an elegant framework for performing statistical inference; because of the high-dimensional nature, however, one must often use approximate methods for this purpose. Belief propagation performs approximate inference, is efficient, and looks back on a long success-story. Yet, in most cases, belief propagation lacks any performance and convergence guarantees. Many realistic problems are presented by graphical models with loops, however, in which case belief propagation is neither guaranteed to provide accurate estimates nor that it converges at all. This thesis investigates how the model parameters influence the performance of belief propagation. We are particularly interested in their influence on (i) the number of fixed points, (ii) the convergence properties, and (iii) the approximation quality.