Belief Propagation: An Asymptotically Optimal Algorithm for the Random Assignment Problem

Justin Salez, Devavrat ShahMath. Oper. Res 2009 · DOI

TL;DR

This paper demonstrates that the Belief Propagation (BP) algorithm can solve the random assignment problem in nearly optimal time, achieving an $O(n^2)$ complexity. This is a significant improvement over existing algorithms and worst-case bounds, suggesting BP is a powerful tool for large-scale optimization problems.

What Problem Does This Paper Address?

The random assignment problem involves finding a minimum-cost perfect matching in a complete bipartite graph where edge weights are drawn independently from a common distribution. While the optimal cost of this problem is known to converge to a specific value as the graph size grows, efficiently finding the assignment that achieves this cost has been a challenge. Existing algorithms, like Edmonds and Karp's, have a worst-case complexity of $O(n^3)$. The Belief Propagation (BP) algorithm, a decentralized heuristic, has shown promise but its theoretical convergence rate was not well understood, with a known worst-case upper bound suggesting a much higher complexity ($O(n^4)$). This paper aims to bridge this gap by providing a rigorous analysis of BP's performance on the random assignment problem, specifically focusing on its convergence rate and computational complexity.

Methods

The authors leverage the concept of local weak convergence to analyze the behavior of BP on large random graphs. The core idea is to show that the dynamics of BP on a growing random bipartite graph ($K_{n,n}$) can be accurately approximated by the dynamics of BP on a fixed, infinite random tree structure called the Poisson Weighted Infinite Tree (PWIT).

The proof proceeds in three main steps:

  1. Convergence of BP on $K_{n,n}$ to BP on PWIT: They establish that the BP algorithm's behavior on $K_{n,n}$ converges to its behavior on the PWIT as $n \to \infty$. This is achieved by carefully relabeling vertices and showing that the BP messages and decisions on $K_{n,n}$ converge to those on the PWIT.
  2. Analysis of BP on PWIT: They then analyze the dynamics of BP on the PWIT itself. This involves studying a recursive update rule on the tree and characterizing its fixed points and convergence behavior. A key technique here is the use of a "transform" to analyze the distribution of messages.
  3. Connecting PWIT solution to $K_{n,n}$ optimum: Finally, they use a known result (Theorem 6.1 by Aldous) that connects the stationary configuration of BP on the PWIT to the optimal assignment of the random assignment problem.

Datasets

Not discussed in the paper. The problem is defined on synthetically generated random graphs with i.i.d. edge weights.

Key Insights and Ideas

  • Local Weak Convergence as a Tool: The paper powerfully demonstrates how local weak convergence, specifically to the PWIT, can be used to analyze the asymptotic behavior of distributed algorithms like BP on large random graphs. This provides a framework for understanding complex systems by simplifying them to a fixed, infinite structure.
  • BP's Asymptotic Optimality: The most striking insight is that BP, despite its decentralized nature and heuristic origins, achieves an asymptotically optimal solution in $O(n^2)$ time. This is remarkable because $O(n^2)$ is the size of the input, meaning BP essentially processes each edge weight a constant number of times on average.
  • Bridging Theory and Practice: The work provides a rigorous theoretical justification for the observed good performance of BP in practice, which was previously only supported by simulations and less rigorous methods.
  • PWIT as a Canonical Model: The PWIT emerges as a fundamental structure for understanding the behavior of BP in problems with random edge weights, serving as a limiting object for large random graphs.

Key Results

  • The paper proves that the Belief Propagation algorithm finds an asymptotically optimal assignment for the random assignment problem.
  • The computational complexity of BP for this problem is shown to be $O(n^2)$ with high probability, assuming the edge weights satisfy certain regularity and light-tail properties.
  • This $O(n^2)$ complexity is asymptotically optimal, as it matches the lower bound for processing the input size.
  • This result significantly improves upon the previously known worst-case upper bound for BP convergence ($O(n^4)$) and is faster than Edmonds and Karp's $O(n^3)$ algorithm.

Limitations and Future Work

  • Assumptions on Edge Weights: The main result relies on specific assumptions about the cumulative distribution function (CDF) of the edge weights:
  • Regularity: The CDF must be continuous, and its derivative at zero must exist and be non-zero.
  • Light-tail property: The tail of the CDF must decay exponentially, i.e., $H(t) = 1 - O(e^{-\beta t})$ for some $\beta > 0$. While these assumptions cover common distributions like uniform and exponential, they exclude heavier-tailed distributions.

  • "Almost Optimal" Assignment: The paper focuses on finding an "almost optimal" assignment, where the expected fraction of non-optimal assignments converges to zero. While this can be modified to produce a valid matching, it's noted that local violations might occur.

  • Future Work: The authors express hope that the methodology used (replacing asymptotic analysis of algorithms on large graphs with their study on limiting infinite structures via local weak convergence) will be a powerful tool for understanding loopy BP in general. This suggests a broad applicability of their approach to other problems involving BP.

Summary updated

BibTeX
@article{salez2009belief,
  author = {Justin Salez and Devavrat Shah},
  title = {{Belief Propagation: An Asymptotically Optimal Algorithm for the Random Assignment Problem}},
  journal = {Math. Oper. Res.},
  year = {2009},
  doi = {10.1287/moor.1090.0380},
}
Figure