Loopy Belief Propagation for Bipartite Maximum Weight b-Matching

Bert Huang, Tony JebaraAISTATS 2007

Introduction

Maximum weight $b$-matching is a fundamental problem in combinatorial optimization where each node in a graph must be matched with exactly $b$ neighbors to maximize the total edge weight. While standard matching ($b=1$) is well-understood, $b$-matching presents greater computational challenges, particularly when scaling to large datasets. Traditional combinatorial algorithms, though exact, are often difficult to parallelize and slow in practice.

This paper explores the use of Loopy Belief Propagation (BP) for solving $b$-matching on bipartite graphs. Although BP is typically used for approximate inference in graphical models and often fails to converge on graphs with cycles (loops), the authors demonstrate that for this specific class of problems, BP is guaranteed to converge to the globally optimal solution.

Methodology

To adapt BP for $b$-matching, the researchers formulated the problem as a probability distribution on a graphical model. They introduced two critical innovations to overcome the standard limitations of BP:

  1. Algebraic Message Compression: A naive implementation of BP for $b$-matching would require passing messages of length $\binom{n}{b}$, leading to exponential complexity. By exploiting the structure of the matching constraints, the authors proved that these messages can be compressed into a single scalar value. This reduces the update complexity per node to $O(bn)$.
  2. Convergence via Unwrapped Graphs: The core theoretical contribution is a proof of convergence using "computation trees" or unwrapped graphs. The authors show that if BP were to converge to a suboptimal solution, it would imply the existence of an improving alternating path in the original graph, contradicting the optimality of the matching in the computation tree. This analysis proves that BP converges to the correct global optimum in $O(n)$ iterations.
The computation tree (unwrapped graph) construction used to prove that BP converges to the global optimum despite loops in the original bipartite graph.

Experimental Evaluation

The algorithm was evaluated against the GOBLIN combinatorial library and $k$-Nearest Neighbors (k-NN) across several tasks:

  • Synthetic Data: Points sampled from spherical Gaussians, with test sets translated to test robustness against distribution shifts.
  • MNIST Digits: Classification of handwritten digits (3, 5, and 8).
  • MNIST with Backgrounds: Digits overlaid on complex textures (e.g., noise, wood, marble) to simulate non-IID conditions.

Key Results

Efficiency and Scalability

In empirical tests on random bipartite graphs, the BP-based solver was consistently hundreds of times faster than the GOBLIN library. While both methods share a similar theoretical complexity, the constant factors for BP are significantly smaller, and its structure allows for efficient parallelization.

Median running time comparison between the proposed BP approach and the GOBLIN library across different values of $n$ and $b$. BP maintains significantly lower runtimes as problem size increases.

Robustness in Classification

$b$-matching acts as a powerful regularizer by enforcing uniform connectivity, unlike k-NN which can be "greedy." On translated synthetic data, k-NN accuracy dropped to 65%, while $b$-matching maintained 100% accuracy. Similarly, on MNIST with complex backgrounds, $b$-matching outperformed k-NN, showing remarkable invariance to background noise and transformations.

Conclusion and Future Work

This work proves that Loopy BP is an exact and highly efficient solver for bipartite maximum weight $b$-matching. By combining theoretical guarantees with practical speedups, it offers a robust alternative to traditional combinatorial methods. Future research aims to extend these proofs to general (non-bipartite) graphs, where odd-length cycles currently pose a challenge for convergence, and to address scenarios with non-unique maximum weight matchings.

Summary updated

BibTeX
@article{huang2007loopy,
  author = {Bert Huang and Tony Jebara},
  title = {{Loopy Belief Propagation for Bipartite Maximum Weight b-Matching}},
  journal = {AISTATS},
  year = {2007},
}
Figure