Local stability of Belief Propagation algorithm with multiple fixed points
This work addresses convergence issues in BP for researchers in statistical physics and computer science, but it is incremental as it builds on existing stability analysis.
The paper tackles the problem of multiple fixed points and convergence in Belief Propagation (BP) algorithms for approximating marginal probabilities in Markov random fields, by deriving a new sufficient condition for local stability of a BP fixed point based on graph structure and belief values.
A number of problems in statistical physics and computer science can be expressed as the computation of marginal probabilities over a Markov random field. Belief propagation, an iterative message-passing algorithm, computes exactly such marginals when the underlying graph is a tree. But it has gained its popularity as an efficient way to approximate them in the more general case, even if it can exhibits multiple fixed points and is not guaranteed to converge. In this paper, we express a new sufficient condition for local stability of a belief propagation fixed point in terms of the graph structure and the beliefs values at the fixed point. This gives credence to the usual understanding that Belief Propagation performs better on sparse graphs.