Sufficient conditions for convergence of Loopy Belief Propagation

2012/07/04 by Joris M. Mooij, Mooij, Joris, Hilbert J. Kappen +1 · 2 citations
Computer Science · Engineering · #Advanced Wireless Communication Techniques #Algorithms and Data Compression #Artificial Intelligence (cs.AI) #Error Correcting Code Techniques #FOS: Computer and information sciences

paper · pdf · doi:10.48550/arxiv.1207.1405

openalex publication_date 2012/07/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We derive novel sufficient conditions for convergence of Loopy Belief Propagation (also known as the Sum-Product algorithm) to a unique fixed point. Our results improve upon previously known conditions. For binary variables with (anti-)ferromagnetic interactions, our conditions seem to be sharp.

Cited by

• Minima and Critical Points of the Bethe Free Energy Are Invariant Under Deformation Retractions of Factor Graphs
• Beyond Belief Propagation: Cluster-Corrected Tensor Network Contraction with Exponential Convergence

Related

• Message Error Analysis of Loopy Belief Propagation for the Sum-Product Algorithm
• Loopy Belief Propogation and Gibbs Measures
• Fast Convergence of Belief Propagation to Global Optima: Beyond Correlation Decay
• Convergence of Generalized Belief Propagation Algorithm on Graphs with Motifs
• Primal View on Belief Propagation