Abstract
Belief Propagation (BP) is a cornerstone algorithm for node labeling in networked data, yet it suffers from convergence issues on graphs with loops and high computational costs. This paper introduces Linearized Belief Propagation (LinBP) and Single-pass Belief Propagation (SBP). By linearizing BP's update equations, the authors derive a closed-form matrix solution with guaranteed convergence. Empirical results demonstrate speedups of up to 600x over standard BP while maintaining over 99% accuracy, alongside seamless integration into relational databases.
Introduction
Inferring missing labels in large-scale networks—such as identifying fraudulent accounts in transaction graphs or political leanings in social networks—is a critical task. Belief Propagation (BP) is the standard iterative approach for this, but it faces two primary challenges: lack of guaranteed convergence on loopy graphs and significant computational overhead, especially for dynamic or massive datasets.
Methods
The core contribution of this work is the linearization of BP equations to overcome these hurdles.
Linearized Belief Propagation (LinBP)
By applying Maclaurin series expansions and centering belief values around a neutral state ($1/k$ for $k$ classes), the authors transform BP's multiplicative updates into a linear system. This results in a closed-form matrix equation that allows for exact convergence conditions and incorporates "echo cancellation" to prevent artificial score inflation in network loops.
Single-pass Belief Propagation (SBP)
SBP is a localized, non-iterative variant of LinBP. It propagates information across each edge exactly once, effectively labeling nodes based on their geodesic distance to known labels. This approach is particularly suited for rapid incremental updates in dynamic graphs.
SQL Implementation
A significant practical advantage of these linearized methods is their compatibility with standard relational algebra. Operations like JOIN and GROUP BY can implement the matrix-vector multiplications, enabling "database-native" inference without exporting data to external graph frameworks.
Experimental Setup
The methods were evaluated on:
- Synthetic Kronecker Graphs: Ranging from 243 to 1.5 million nodes, designed to mimic real-world network topology.
- DBLP Dataset: A citation network of ~36,000 nodes where researchers are classified into four computer science subfields.
Results
The linearized approaches show remarkable performance across several metrics.
Speed and Scalability
In Java-based tests, LinBP achieved speedups of up to 600x compared to standard BP. SBP further improved performance, running 10x faster than LinBP in SQL environments. Both methods scale linearly with the number of edges.
Fidelity and Convergence
Despite the linearization, LinBP maintains >99.9% accuracy relative to standard BP, while SBP maintains >98.6% accuracy. As shown in the comparative analysis, the standardized beliefs and standard deviations of the linearized variants closely track the original BP until the convergence limit is reached.
Discussion
While LinBP and SBP offer significant advantages, they currently rely on a pre-defined coupling matrix ($H$) that describes class interactions. Future work involves automatically learning this matrix from data. Additionally, while SBP is highly efficient, it can be more prone to ties in top-belief assignments compared to the iterative LinBP, though this is often manageable in practical applications.
Summary updated