Stable Fixed Points of Loopy Belief Propagation Are Local Minima of the Bethe Free Energy

We extend recent work on the connection between loopy belief propagation and the Bethe free energy. Constrained minimization of the Bethe free energy can be turned into an unconstrained saddle-point problem. Both converging double-loop algorithms and standard loopy belief propagation can be inter- preted as attempts to solve this saddle-point problem. Stability analysis then leads us to conclude that stable (cid:12)xed points of loopy belief propagation must be (local) minima of the Bethe free energy. Perhaps surprisingly, the converse need not be the case: minima can be unstable (cid:12)xed points.