Guided Selection of Accurate Belief Propagation Fixed Points

Belief propagation (BP) and the Bethe approximation are two closely relatedconcepts that both suffer from the existence of multiple fixed points (or stationarypoints). We propose a modification of BP, termed self-guided belief propagation(SBP), that incorporates the pairwise potentials only gradually; this essentiallyselects one specific fixed point and increases the accuracy without increasing thecomputational burden. We apply SBP to various models with Ising potentials andshow that: (i) SBP is superior in terms of accuracy whenever BP converges, and (ii)SBP obtains a unique, stable, and accurate solution whenever BP does not converge.