  Belief propagation (BP) is a popular method for performing probabilistic
inference on graphical models. In this work, we enhance BP and propose
self-guided belief propagation (SBP) that incorporates the pairwise potentials
only gradually. This homotopy continuation method converges to a unique
solution and increases the accuracy without increasing the computational
burden. We provide a formal analysis to demonstrate that SBP finds the global
optimum of the Bethe approximation for attractive models where all variables
favor the same state. Moreover, we apply SBP to various graphs with random
potentials and empirically show 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.
