Belief Propagation for Min-cost Network Flow: Convergence & Correctness

David Gamarnik, Devavrat Shah, Yehua Wei

TL;DR

This paper proves that Belief Propagation (BP), a popular message-passing algorithm, can efficiently solve the min-cost network flow (MCF) problem. They show BP converges to the optimal solution in pseudo-polynomial time for MCF instances with unique optimal solutions and integral parameters. Furthermore, they introduce a randomized modification of BP that achieves a fully polynomial-time randomized approximation scheme (FPRAS) for MCF, even without the uniqueness assumption.

What Problem Does This Paper Address?

Message-passing algorithms, particularly Belief Propagation (BP), have become ubiquitous in various fields for solving complex optimization and inference problems. Despite their empirical success, a rigorous theoretical understanding of BP's convergence and correctness, especially for optimization problems, has lagged behind. This paper focuses on the capacitated min-cost network flow (MCF) problem, a cornerstone of operations research and optimization theory. The authors aim to bridge this gap by providing theoretical guarantees for BP's performance on MCF, a problem that has historically been challenging for BP in its general linear programming form.

Methods

The core of this paper lies in adapting and analyzing the Belief Propagation algorithm for the MCF problem.

  • BP Formulation for MCF: The authors first formulate the MCF problem as a factorized optimization problem, which is the standard input for BP. They define variable functions (representing arc costs) and factor functions (representing flow conservation constraints at nodes).
  • Piecewise Linear Convex Functions: A key technical contribution is showing that the "messages" exchanged between nodes in the BP algorithm for MCF are piecewise linear convex functions. This allows for efficient representation and computation of these messages, enabling a concrete implementation of BP.
  • Convergence Proof (Unique Solution): For MCF instances with a unique optimal solution and integral parameters, they prove that BP converges to this exact optimal solution in pseudo-polynomial time. This proof involves constructing "computation trees" and relating the BP process to solving MCF on these trees.
  • FPRAS via Randomized Modification: To overcome the limitation of requiring a unique optimal solution and to achieve polynomial time complexity, they introduce a randomized approach. By slightly perturbing the cost vector of the MCF problem with carefully chosen random values, they create a new problem that, with high probability, has a unique optimal solution and whose solution is a good approximation to the original problem's optimal solution. This leads to a Fully Polynomial-Time Randomized Approximation Scheme (FPRAS).

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and algorithmic development for a general optimization problem.

Key Insights and Ideas

  • BP's Applicability to MCF: The paper demonstrates that BP, despite its origins in graphical models, is a powerful tool for a fundamental optimization problem like MCF.
  • Piecewise Linear Convex Messages: The insight that BP messages in MCF are piecewise linear convex functions is crucial for efficient implementation and analysis. This allows for a structured way to handle the iterative updates.
  • Uniqueness as a Key for Exactness: The paper highlights that uniqueness of the optimal solution is a critical condition for BP to guarantee exact convergence in pseudo-polynomial time.
  • Randomization for FPRAS: The idea of using randomized cost perturbations to achieve both uniqueness and approximation is a clever way to extend BP's applicability to a broader class of MCF problems and achieve polynomial time complexity.
  • BP for Uniqueness Detection: A surprising finding is that BP can potentially detect the uniqueness of an optimal solution in a distributed manner, a property not immediately obvious from its message-passing nature.

Key Results

  • Pseudo-polynomial Time Convergence: BP converges to the unique optimal solution of an integral MCF problem in pseudo-polynomial time.
  • FPRAS for MCF: A randomized modification of BP yields an FPRAS for MCF, providing a $(1+\epsilon)$-multiplicative approximation in polynomial time with respect to $m, n,$ and $1/\epsilon$.
  • Efficient Message Updates: The paper provides an efficient procedure for updating and encoding the piecewise linear convex message functions.

Limitations and Future Work

  • Pseudo-polynomial vs. Polynomial Time: The exact convergence result for BP is in pseudo-polynomial time, which can still be slow if costs or capacities are large. The FPRAS addresses the polynomial time requirement.
  • Uniqueness Assumption: The exact convergence proof relies on the assumption of a unique optimal solution. The FPRAS circumvents this by introducing randomness.
  • General LP: The paper notes that BP does not converge for general linear programming problems, as shown by a counter-example. Identifying the broadest class of optimization problems solvable by BP remains an open problem.
  • Future Work: The authors suggest that their randomized decimation procedure, used for the FPRAS, could be a general method applicable to other combinatorial problems. They also point to the challenge of identifying the precise class of optimization problems for which BP is provably efficient.

Summary updated

Abstract

Message passing type algorithms such as the so-called Belief Propagation algorithm have recently gained a lot of attention in the statistics, signal processing and machine learning communities as attractive algorithms for solving a variety of optimization and inference problems. As a decentralized, easy to implement and empirically successful algorithm, BP deserves attention from the theoretical standpoint, and here not much is known at the present stage. In order to fill this gap we consider the performance of the BP algorithm in the context of the capacitated minimum-cost network flow problem - the classical problem in the operations research field. We prove that BP converges to the optimal solution in the pseudo-polynomial time, provided that the optimal solution of the underlying problem is unique and the problem input is integral. Moreover, we present a simple modification of the BP algorithm which gives a fully polynomial-time randomized approximation scheme (FPRAS) for the same problem, which no longer requires the uniqueness of the optimal solution. This is the first instance where BP is proved to have fully-polynomial running time. Our results thus provide a theoretical justification for the viability of BP as an attractive method to solve an important class of optimization problems.
BibTeX
@inproceedings{gamarnik2010belief,
  author = {David Gamarnik and Devavrat Shah and Yehua Wei},
  title = {{Belief Propagation for Min-cost Network Flow: Convergence \& Correctness}},
  booktitle = {SODA},
  year = {2010},
  doi = {10.1137/1.9781611973075.24},
}
Figure