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.

本文提出了一种基于解线性方程组的方法，用于近似解决循环因子带权 Markov 随机场的置信传播问题，并且这种方法能够同时享有完全收敛的保证和较快的矩阵实现、适应于异质网络的特点。实验结果表明，在节点权重较弱的网络图上，这种线性化的方法在保证准确性的同时大大加快了推断速度，达到了与 BP 相当的标签准确性。