The Linearization of Belief Propagation on Pairwise Markov Networks
This provides a faster and more reliable inference method for probabilistic graphical models, though it is incremental as it builds on existing linearization approaches.
The paper tackles the lack of convergence guarantees for Belief Propagation (BP) in cyclic graphs by generalizing prior linearization methods to approximate loopy BP on any pairwise Markov Random Field as a linear equation system, achieving comparable labeling accuracy to BP for graphs with weak potentials while speeding up inference by orders of magnitude.
Belief Propagation (BP) is a widely used approximation for exact probabilistic inference in graphical models, such as Markov Random Fields (MRFs). In graphs with cycles, however, no exact convergence guarantees for BP are known, in general. For the case when all edges in the MRF carry the same symmetric, doubly stochastic potential, recent works have proposed to approximate BP by linearizing the update equations around default values, which was shown to work well for the problem of node classification. The present paper generalizes all prior work and derives an approach that approximates loopy BP on any pairwise MRF with the problem of solving a linear equation system. This approach combines exact convergence guarantees and a fast matrix implementation with the ability to model heterogenous networks. Experiments on synthetic graphs with planted edge potentials show that the linearization has comparable labeling accuracy as BP for graphs with weak potentials, while speeding-up inference by orders of magnitude.