Introduction
Probabilistic inference is a cornerstone of network analysis, used to determine the likelihood of node states in complex systems. Belief Propagation (BP) is the standard iterative algorithm for this task. However, BP faces significant challenges in real-world "loopy" graphs, where it often fails to converge or becomes computationally prohibitive for massive datasets. This paper introduces a novel linearization of BP that transforms iterative message-passing into a system of linear equations, offering guaranteed convergence and substantial speedups.
Methodology: From Messages to Matrices
The core innovation lies in a mathematical "centering" technique. Rather than processing raw probabilities, the method centers edge weights (potentials) and node beliefs around a default value. By focusing on the residuals—the deviations from these defaults—and applying a Maclaurin series expansion, the author replaces the complex multiplications of standard BP with simple additions.
The resulting linear system is expressed as: $$\hat{\mathbf{y}} = \hat{\mathbf{x}} + \text{bias} + \text{propagation} - \text{echo cancellation}$$
A critical component is the "echo cancellation" term, which mathematically mitigates the feedback loops inherent in non-tree graphs. To ensure stability, the paper introduces a convergence parameter, $s$, derived from the spectral radius of the system's matrix.
As shown in the figure above, the parameter $s$ allows for fine-tuning the trade-off between speed and accuracy. By adjusting $s$, users can "weaken" potentials just enough to guarantee a stable solution while maintaining high inference quality.
Experimental Evaluation
The method was evaluated using synthetic graphs ($n=1000$) with planted edge potentials to provide a ground truth for accuracy measurements. The experiments varied parameters such as average degree ($d$), potential strength ($h$), and the fraction of labeled nodes ($f$).
Key Results
The linearized approach demonstrates a massive performance leap. It is approximately 100 times faster per iteration than standard BP, and because it converges more reliably, total speedups can reach 1000x. On a graph with 30 million edges, a single iteration takes less than two seconds.
In terms of accuracy, the linearized version performs nearly identically to standard BP for weak to medium potential strengths ($h$). As $h$ increases (representing stronger coupling between nodes), standard BP may achieve higher accuracy if it converges, but the linearized version remains stable and predictable.
Conclusion
By linearizing Belief Propagation, this work provides a scalable and robust framework for inference in heterogeneous networks. While accuracy may slightly degrade under extremely strong potentials, the gains in speed and convergence reliability make it an ideal choice for massive, real-world graph analysis. Future work may leverage this fast approximation to initialize standard BP or to explore theoretical bounds on BP's convergence.
Summary updated