Convergence of Generalized Belief Propagation Algorithm on Graphs with Motifs
This addresses the problem of understanding and ensuring convergence in belief propagation for researchers in machine learning and related fields, but it is incremental as it builds on existing work with specific model constraints.
The paper tackles the convergence behavior of generalized belief propagation on graphs containing motifs like triangles and loops, showing that under specific initialization, it converges to the global optimum of the Bethe free energy for ferromagnetic Ising models.
Belief propagation is a fundamental message-passing algorithm for numerous applications in machine learning. It is known that belief propagation algorithm is exact on tree graphs. However, belief propagation is run on loopy graphs in most applications. So, understanding the behavior of belief propagation on loopy graphs has been a major topic for researchers in different areas. In this paper, we study the convergence behavior of generalized belief propagation algorithm on graphs with motifs (triangles, loops, etc.) We show under a certain initialization, generalized belief propagation converges to the global optimum of the Bethe free energy for ferromagnetic Ising models on graphs with motifs.