D-CIS Publication Database


Type of publication:Article
Entered by:WW
TitleOn the properties of the Bethe approximation and Loopy Belief Propagation on binary networks
Bibtex cite ID
Journal Journal of Statistical Mechanics: Theory and Experiment
Year published 2005
Volume 2005
Number 11
Pages 11012
ISSN 1742-5468
Keywords graphical models,approximate inference
We analyse the local stability of the high-temperature fixed point of the loopy belief propagation (LBP) algorithm and how this relates to the properties of the Bethe free energy which LBP tries to minimize. We focus on the case of binary networks with pairwise interactions. In particular, we state sufficient conditions for convergence of LBP to a unique fixed point and show that these are sharp for purely ferromagnetic interactions. In contrast, in the purely antiferromagnetic case, the undamped parallel LBP algorithm is suboptimal in the sense that the stability of the fixed point breaks down much earlier than for damped or sequential LBP; we observe that the onset of instability for the latter algorithms is related to the properties of the Bethe free energy. For spin-glass interactions, damping LBP only helps slightly. We estimate analytically the temperature at which the high-temperature LBP fixed point becomes unstable for random graphs with arbitrary degree distributions and random interactions.
Mooij, Joris
Kappen, Hilbert J.
Total mark: 5