Abstract: 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 sufficientconditions 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.
Abstract: We derive sufficientconditions for the uniqueness of loopy belief propagation fixed points. These conditions depend on both the structure of the graph and the strength of the potentials and naturally extend those for convexity of the Bethe free energy. We compare them with (a strengthened version of) conditions derived elsewhere for pairwise potentials. We discuss possible implications for convergent algorithms, as well as for other approximate free energies.
Abstract: We derive novel conditions that guarantee convergence of the Sum-Product algorithm (also known as Loopy Belief Propagation
or simply Belief Propagation) to a unique fixed point, irrespective of the initial messages. The computational complexity of the
conditions is polynomial in the number of variables. In contrast with previously existing conditions, our results are directly
applicable to arbitrary factor graphs (with discrete variables) and are shown to be valid also in the case of factors containing
zeros, under some additional conditions. We compare our bounds with existing ones, numerically and, if possible, analytically.
For binary variables with pairwise interactions, we derive sufficientconditions that take into account local evidence (i.e. single
variable factors) and the type of pair interactions (attractive or repulsive). It is shown empirically that this bound outperforms