Belief Propagation for Weighted b-Matchings on Arbitrary Graphs and its Relation to Linear Programs with Integer Solutions

We consider the general problem of finding the minimum weight $\bm$-matching on arbitrary graphs. We prove that, whenever the linear programming (LP) relaxation of the problem has no fractional solutions, then the belief propagation (BP) algorithm converges to the correct solution. We also show that when the LP relaxation has a fractional solution then the BP algorithm can be used to solve the LP relaxation. Our proof is based on the notion of graph covers and extends the analysis of (Bayati-Shah-Sharma 2005 and Huang-Jebara 2007}. These results are notable in the following regards: (1) It is one of a very small number of proofs showing correctness of BP without any constraint on the graph structure. (2) Variants of the proof work for both synchronous and asynchronous BP; it is the first proof of convergence and correctness of an asynchronous BP algorithm for a combinatorial optimization problem.

• Publication year

  2007

• Venue

  SIAM Journal on Discrete Mathematics

• Publication date

  2007-09-08

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1137/090753115arXiv 0709.1190
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Belief propagation for min-cost network flow: convergence & correctness

  2010influential reference
• Convergence of Min-Sum Message-Passing for Convex Optimization

  2010cited by this paper
• Optimality of belief propagation for random assignment problem

  2009cited by this paper
• Matching

  2009cited by this paper
• MAP Estimation, Message Passing, and Perfect Graphs

  2009cited by this paper
• On the exactness of the cavity method for weighted b-matchings on arbitrary graphs and its relation to linear programs

  2008cited by this paper
• A Message-Passing Paradigm for Resource Allocation

  2008cited by this paper
• Linear programming analysis of loopy belief propagation for weighted matching

  2007influential reference
• Message Passing for Max-weight Independent Set

  2007cited by this paper
• Loopy Belief Propagation for Bipartite Maximum Weight b-Matching

  2007cited by this paper
• Finding long cycles in graphs

  2007cited by this paper
• Convergence of the Min-Sum Algorithm for Convex Optimization

  2007cited by this paper
• Equivalence of LP Relaxation and Max-Product for Weighted Matching in General Graphs

  2007cited by this paper
• Phase Transitions in the Coloring of Random Graphs

  2007cited by this paper
• MAP Estimation, Linear Programming and Belief Propagation with Convex Free Energies

  2007cited by this paper
• Clustering by Passing Messages Between Data Points

  2007cited by this paper
• The number of matchings in random graphs

  2006cited by this paper
• Complete Convergence of Message Passing Algorithms for Some Satisfiability Problems

  2006cited by this paper
• On the solution-space geometry of random constraint satisfaction problems

  2006cited by this paper
• A rigorous proof of the cavity method for counting matchings

  2006cited by this paper
• Sudden emergence of q-regular subgraphs in random graphs

  2006cited by this paper
• A Simpler Max-Product Maximum Weight Matching Algorithm and the Auction Algorithm

  2006cited by this paper
• Convergence of the Min-Sum Message Passing Algorithm for Quadratic Optimization

  2006cited by this paper
• The travelling salesman problem in the stochastic mean field model

  2006cited by this paper
• Consensus Propagation

  2005cited by this paper
• Graph-Cover Decoding and Finite-Length Analysis of Message-Passing Iterative Decoding of LDPC Codes

  2005cited by this paper
• Max-Product for Maximum Weight Matching: Convergence, Correctness, and LP Duality

  2005cited by this paper
• Using linear programming to Decode Binary linear codes

  2005cited by this paper
• MAP estimation via agreement on trees: message-passing and linear programming

  2005cited by this paper
• Belief Propagation Based Multi--User Detection

  2005cited by this paper
• Reconstruction on Trees and Spin Glass Transition

  2005cited by this paper
• Low-Density Parity-Check Codes

  2004cited by this paper
• Inferring Cellular Networks Using Probabilistic Graphical Models

  2004cited by this paper
• A new look at survey propagation and its generalizations

  2004cited by this paper
• On the Relationship between Linear Programming Decoding and Min-Sum Algorithm Decoding

  2004cited by this paper
• Maximum Weight Independent Sets and Matchings in Sparse Random Graphs. Exact Results Using the Local Weak Convergence Method

  2004cited by this paper
• Tree consistency and bounds on the performance of the max-product algorithm and its generalizations

  2004cited by this paper
• Maximum weight independent sets and matchings in sparse random graphs. Exact results using the local weak convergence method

  2003cited by this paper
• Polynomial iterative algorithms for coloring and analyzing random graphs.

  2003cited by this paper
• Survey propagation as local equilibrium equations

  2003cited by this paper
• Understanding belief propagation and its generalizations

  2003cited by this paper
• Survey propagation: An algorithm for satisfiability

  2002cited by this paper
• Approximate Inference and Protein-Folding

  2002cited by this paper
• A new class of upper bounds on the log partition function

  2002cited by this paper
• Loopy Belief Propogation and Gibbs Measures

  2002cited by this paper
• On the optimality of solutions of the max-product belief-propagation algorithm in arbitrary graphs

  2001cited by this paper
• Matching: A Well-Solved Class of Integer Linear Programs

  2001cited by this paper
• The capacity of low-density parity-check codes under message-passing decoding

  2001cited by this paper
• An analysis of belief propagation on the turbo decoding graph with Gaussian densities

  2001cited by this paper
• Correctness of Local Probability Propagation in Graphical Models with Loops

  2000cited by this paper
• The zeta(2) limit in the random assignment problem

  2000cited by this paper
• The ζ(2) limit in the random assignment problem

  2000cited by this paper
• Correctness of Belief Propagation in Gaussian Graphical Models of Arbitrary Topology

  1999cited by this paper
• Iterative decoding on graphs with a single cycle

  1998cited by this paper
• Combinatorial optimization

  1997influential reference
• Codes and Decoding on General Graphs

  1996cited by this paper
• Matchings and extensions

  1996cited by this paper
• Combinatorial Optimization

  1992cited by this paper
• Auction algorithms for network flow problems: A tutorial introduction

  1992cited by this paper
• Probabilistic reasoning in intelligent systems: Networks of plausible inference

  1991cited by this paper
• The auction algorithm: A distributed relaxation method for the assignment problem

  1988cited by this paper
• Mean-Field Equations for the Matching and the Travelling Salesman Problems

  1986cited by this paper
• Normal Hypergraphs and the Weak Perfect Graph Conjecture

  1984cited by this paper
• On certain polytopes associated with graphs

  1975cited by this paper
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems

  1972cited by this paper
• Normal hypergraphs and the perfect graph conjecture

  1972influential reference

• Approximate Bipartite b-Matching using Multiplicative Auction

  2024cites this paper
• A distributed message passing algorithm for computing perfect demand matching

  2023cites this paper
• Planted matching problems on random hypergraphs

  2022cites this paper
• Convergence and correctness of belief propagation for weighted min-max flow

  2022cites this paper
• Iterative Message Passing Algorithm for Vertex-Disjoint Shortest Paths

  2022cites this paper
• A distributed message passing algorithm for the capacitated directed Chinese postman problem

  2022cites this paper
• The planted k-factor problem

  2020cites this paper
• Recovery thresholds in the sparse planted matching problem

  2020cites this paper
• Global Alignment of PPI Networks

  2020cites this paper
• Learning to Accelerate Heuristic Searching for Large-Scale Maximum Weighted b-Matching Problems in Online Advertising

  2020cites this paper
• PILS: Exploring high-order neighborhoods by pattern mining and injection

  2019cites this paper
• EUCLIDEAN CORRELATIONS IN COMBINATORIAL OPTIMIZATION PROBLEMS: A STATISTICAL PHYSICS APPROACH

  2019cites this paper
• Optimizing Social Welfare for Network Bargaining Games in the Face of Instability, Greed and Idealism

  2019cites this paper
• Inference-Based Resource Allocation for Multi-Cell Backscatter Sensor Networks

  2019cites this paper
• Convergence and correctness of belief propagation for the Chinese postman problem

  2019influential citation
• Belief propagation for the maximum-weight independent set and minimum spanning tree problems

  2018cites this paper
• Plastic number and possible optimal solutions for an Euclidean 2-matching in one dimension

  2018cites this paper
• Hidden Hamiltonian Cycle Recovery via Linear Programming

  2018influential citation
• RANDOM COMBINATORIAL OPTIMIZATION PROBLEMS: MEAN FIELD AND FINITE-DIMENSIONAL RESULTS

  2018cites this paper
• Maximum Weight Matching Using Odd-Sized Cycles: Max-Product Belief Propagation and Half-Integrality

  2018cites this paper
• Intelligent scatter radio, RF harvesting analysis and resource allocation for ultra-low-power internet-of-things

  2017cites this paper
• Convergence and Correctness of Max-Product Belief Propagation for Linear Programming

  2017influential citation
• Distributed Load Balancing via Message Passing for Heterogeneous Cellular Networks

  2016cites this paper
• Large-Scale Linear Optimization through Machine Learning: From Theory to Practical System Design and Implementation

  2016influential citation
• Bethe Learning of Graphical Models via MAP Decoding

  2016cites this paper
• Smoothed analysis of belief propagation and minimum-cost flow algorithms

  2016influential citation
• Typical performance of approximation algorithms for NP-hard problems

  2016cites this paper
• A hierarchical Bayesian-MAP approach to inverse problems in imaging

  2016cites this paper
• Exactness of Approximate MAP Inference in Continuous MRFs

  2015cites this paper
• Approximate MAP Inference in Continuous MRFs

  2015cites this paper
• Auction/Belief Propagation Algorithms for Constrained Assignment Problem

  2015cites this paper
• Minimum Weight Perfect Matching via Blossom Belief Propagation

  2015cites this paper
• Bethe Learning of Conditional Random Fields via MAP Decoding

  2015cites this paper
• Bottom-Up Approaches to Approximate Inference and Learning in Discrete Graphical Models

  2014cites this paper
• Loopy annealing belief propagation for vertex cover and matching: convergence, LP relaxation, correctness and Bethe approximation

  2014cites this paper
• Making Pairwise Binary Graphical Models Attractive

  2014cites this paper
• Max-Product Belief Propagation for Linear Programming: Convergence and Correctness

  2014cites this paper
• Linear programming techniques for algorithms with applications in economics

  2014cites this paper
• On the Convergence and Optimality of Reweighted Message Passing for Channel Assignment Problems

  2014cites this paper
• A hierarchical Bayesian-map approach to computational imaging

  2014cites this paper
• Max-Product Belief Propagation for Linear Programming: Applications to Combinatorial Optimization

  2014influential citation
• Scalable optimization algorithms for recommender systems

  2014cites this paper
• Weighted matching as a generic pruning technique applied to optimization constraints

  2014cites this paper
• Message Passing Algorithm for the Generalized Assignment Problem

  2014cites this paper
• Belief Propagation and Algorithms for Mean-Field Combinatorial Optimisations

  2014cites this paper
• Modularity Conserved during Evolution: Algorithms and Analysis

  2013cites this paper
• Message-Passing Algorithms for Packing and Covering Linear Programs with Zero-One Matrices

  2013cites this paper
• The Bethe Permanent of a Nonnegative Matrix

  2013cites this paper
• A Graphical Transformation for Belief Propagation: Maximum Weight Matchings and Odd-Sized Cycles

  2013cites this paper
• Fairness in Assignment Markets with Dual Decomposition

  2013cites this paper
• CAMPways: constrained alignment framework for the comparative analysis of a pair of metabolic pathways

  2013cites this paper
• Analysis of the Min-Sum Algorithm for Packing and Covering Problems via Linear Programming

  2013cites this paper
• Convergence of multivariate belief propagation, with applications to cuckoo hashing and load balancing

  2012cites this paper
• Optimizing Social Welfare for Network Bargaining Games in the Face of Unstability, Greed and Spite

  2012cites this paper
• Information Economics in the Age of e-Commerce: Models and Mechanisms for Information-Rich Markets

  2012cites this paper
• Bipartite graph structures for efficient balancing of heterogeneous loads

  2012cites this paper
• Smoothed Analysis of Belief Propagation for Minimum-Cost Flow and Matching

  2012influential citation
• On a class of distributed algorithms over networks and graphs

  2011cites this paper
• Exploiting the structure of distributed constraint optimization problems to assess and bound coordinated actions in multi-agent systems

  2011cites this paper
• Fast b-matching via Sufficient Selection Belief Propagation

  2011cites this paper
• Learning with Degree-Based Subgraph Estimation

  2011cites this paper
• Belief Propagation and LP Relaxation for Weighted Matching in General Graphs

  2011cites this paper
• Local Dynamics in Bargaining Networks via Random-Turn Games

  2010cites this paper
• The Bethe permanent of a non-negative matrix

  2010cites this paper
• Belief propagation for min-cost network flow: convergence & correctness

  2010cites this paper
• Message-passing for Graph-structured Linear Programs: Proximal Methods and Rounding Schemes

  2010cites this paper
• Worst-case bounds on the quality of max-product fixed-points

  2010cites this paper
• Correlation decay and decentralized optimization in graphical models

  2010cites this paper
• On the Performance of Multiuser MIMO Mesh Networks

  2010cites this paper
• Quantifying Statistical Interdependence by Message Passing on Graphs—Part I: One-Dimensional Point Processes

  2009cites this paper
• Distributed Rate Allocation for Network-coded Systems

  2009cites this paper
• Message-Passing Algorithms for Sparse Network Alignment

  2009cites this paper
• A rigorous analysis of the cavity equations for the minimum spanning tree

  2008cites this paper
• Message Passing for Maximum Weight Independent Set

  2008cites this paper
• Journal of Graph Algorithms and Applications Smoothed Analysis of Belief Propagation for Minimum-cost Flow and Matching

  year unknowninfluential citation
• Bipartite graph structures for efficient balancing of heterogeneous loads

  year unknowncites this paper
• 2015 Ieee International Conference on Big Data (big Data) Practical Message-passing Framework for Large-scale Combinatorial Optimization

  year unknowncites this paper