Counting fixed points in belief propagation on binary graph models

Counting the Fixed Points of Binary Belief Propagation: Generic Degree, Syzygies, and Real Solutions

Information Theory

Summary

Belief propagation is a method used to analyze networks where each connection can be on or off. The authors studied how many stable solutions, called fixed points, this method can have on such networks. They found a formula that counts these fixed points based on the network’s structure and gave two ways to understand this count using advanced mathematics. Their work also shows that for certain networks, the number of these fixed points relates directly to specific algebraic properties. They verified these findings using a formal proof system.

What this means in practice

  • For network algorithm developers: Identify guaranteed numbers of stable states in network inference methods to improve algorithm design and reliability.
  • For signal processing engineers: Use relations between network structure and fixed points to better understand behavior of message passing in sensor networks with binary states.

A theory result. No direct application yet.

Authors

Yusuke Watanabe

Abstract

How many fixed points does belief propagation have on a binary pairwise model? Over complex parameters, the admissible equations of a finite loopless multigraph form an algebraic family whose generic degree we determine: it is a graph state sum over edge sets without vertices of degree one, each vertex of positive degree contributing one less than its degree. We give two geometric realizations of this state sum. The first is the total Betti number of a universal edge-incidence ring constructed without parameters. Its full graded Betti table is the state sum, its Tor algebra is natural for noncontracting graph maps, the alternating numerator recovers the graph polynomial of Watanabe and Fukumizu, and an Artin reduction by a regular sequence realizes the one-variable specialization, corrected for tree components. The second lies in the actual family: at the strong-field boundary each state factor is a ramification index, and at sufficiently strong field the state charts exhaust the admissible complex fiber. For fixed nonzero real couplings, every Eulerian message-sign sector contains a real fixed point at every external field, and strong fields attain this lower bound: one admissible real fixed point per element of the binary cycle space and one positive fixed point. For graphs of maximum degree at most three, this minimum equals the number of minimal module generators of the edge-incidence ring. One state decomposition connects the complex degree, graded syzygies, and an attained minimum real count. The degree, selected ring and resolution statements, and the real counts are formalized in Lean 4.