Linearized and Turbo Belief Propagation

Wolfgang Gatterbauer, Stephan Günnemann, Danai Koutra, Christos FaloutsosarXiv 2014 · arXiv

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.

The matrix representation of LinBP, illustrating the components of the linearized equation including the echo cancellation term.

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.

Comparison of standardized beliefs (a-c) and standard deviation (d) for BP, LinBP, and SBP, showing high fidelity and convergence behavior.

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

Abstract

How can we tell when accounts are fake or real in a social network? And how can we tell which accounts belong to liberal, conservative or centrist users? Often, we can answer such questions and label nodes in a network based on the labels of their neighbors and appropriate assumptions of homophily ("birds of a feather flock together") or heterophily ("opposites attract"). One of the most widely used methods for this kind of inference is Belief Propagation (BP) which iteratively propagates the information from a few nodes with explicit labels throughout a network until convergence. One main problem with BP, however, is that there are no known exact guarantees of convergence in graphs with loops. This paper introduces Linearized Belief Propagation (LinBP), a linearization of BP that allows a closed-form solution via intuitive matrix equations and, thus, comes with convergence guarantees. It handles homophily, heterophily, and more general cases that arise in multi-class settings. Plus, it allows a compact implementation in SQL. The paper also introduces Single-pass Belief Propagation (SBP), a "localized" version of LinBP that propagates information across every edge at most once and for which the final class assignments depend only on the nearest labeled neighbors. In addition, SBP allows fast incremental updates in dynamic networks. Our runtime experiments show that LinBP and SBP are orders of magnitude faster than standard
BibTeX
@misc{gatterbauer2014linearized,
  author = {Wolfgang Gatterbauer and Stephan Günnemann and Danai Koutra and Christos Faloutsos},
  title = {{Linearized and Turbo Belief Propagation}},
  year = {2014},
  eprint = {1406.7288},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1406.7288},
}
Figure