Belief Propagation and LP Relaxation for Weighted Matching in General Graphs

Loopy belief propagation has been employed in a wide variety of applications with great empirical success, but it comes with few theoretical guarantees. In this paper, we analyze the performance of the max-product form of belief propagation for the weighted matching problem on general graphs. We show that the performance of max-product is exactly characterized by the natural linear programming (LP) relaxation of the problem. In particular, we first show that if the LP relaxation has no fractional optima then max-product always converges to the correct answer. This establishes the extension of the recent result by Bayati, Shah and Sharma, which considered bipartite graphs, to general graphs. Perhaps more interestingly, we also establish a tight converse, namely that the presence of any fractional LP optimum implies that max-product will fail to yield useful estimates on some of the edges. We extend our results to the weighted b-matching and r -edge-cover problems. We also demonstrate how to simplify the max-product message-update equations for weighted matching, making it easily deployable in distributed settings like wireless or sensor networks.

• Publication year

  2011

• Venue

  IEEE Transactions on Information Theory

• Publication date

  2011-04-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1109/TIT.2011.2110170
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Message Passing for Maximum Weight Independent Set

  2008cited by this paper
• Graphical Models, Exponential Families, and Variational Inference

  2008cited by this paper
• Belief Propagation for Weighted b-Matchings on Arbitrary Graphs and its Relation to Linear Programs with Integer Solutions

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

  2007influential reference
• Loopy Belief Propagation for Bipartite Maximum Weight b-Matching

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

  2007cited by this paper
• Walk-Sums and Belief Propagation in Gaussian Graphical Models

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

  2005influential reference
• MAP estimation via agreement on (hyper)trees: Message-passing and linear programming

  2005cited by this paper
• On the Optimality of Tree-reweighted Max-product Message-passing

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

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

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

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

  2002cited by this paper
• Factor graphs and the Sum-Product Algorithm

  2002cited by this paper
• Sparse power efficient topology for wireless networks

  2002cited by this paper
• Factor graphs and the sum-product algorithm

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

  2001cited by this paper
• Combinatorial optimization

  1997cited by this paper
• Combinatorial Optimization

  1992cited by this paper
• Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks

  1990cited by this paper
• Paths, Trees, and Flowers

  1965cited by 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
• Convergence and correctness of belief propagation for weighted min-max flow

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

  2020cites this paper
• Modified Bethe Permanent of a Nonnegative Matrix

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

  2019cites this paper
• Adaptive Anonymization of Data using b-Edge Cover

  2018cites this paper
• Belief propagation for the maximum-weight independent set and minimum spanning tree problems

  2018cites this paper
• Cloud Based Small Cell Networks: System Model, Performance Analysis and Resource Allocation

  2017influential citation
• Sufficient conditions for convergence of the survey propagation algorithm

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

  2017influential citation
• Parallel Optimization Framework for Cloud-Based Small Cell Networks

  2016influential citation
• A New Distributed Approximation Algorithm for the Maximum Weight Independent Set Problem

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

  2016influential citation
• 4-DMWM Approach for Caching Based Optimal D2D Pairing and Channel Allocation: Centralized and Distributed Algorithm Design

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

  2016influential citation
• Approximate MAP Inference in Continuous MRFs

  2015cites this paper
• A distributed cooperative power allocation scheme for small cell networks

  2015influential citation
• Exactness of Approximate MAP Inference in Continuous MRFs

  2015cites this paper
• Bounding the Bethe and the Degree-M Bethe Permanents

  2015cites this paper
• Data fusion and collaborative state estimation in wireless sensor networks

  2015cites this paper
• A belief propagation based hierarchical approach for capacitated network decomposition

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

  2014cites this paper
• Bethe and M-Bethe Permanent Inequalities

  2014cites this paper
• Belief propagation for minimum weight many-to-one matchings in the random complete graph

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

  2014cites this paper
• Automated Stitching of Microtubule Centerlines across Serial Electron Tomograms

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

  2014influential citation
• Distributed transmit power management for small cell networks

  2014influential citation
• Loopy annealing belief propagation for vertex cover and matching: convergence, LP relaxation, correctness and Bethe approximation

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

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

  2013cites this paper
• Optimal wireless scheduling with interference cancellation

  2013cites this paper
• Loop calculus and bootstrap-belief propagation for perfect matchings on arbitrary graphs

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

  2013cites this paper
• Belief Propagation for Linear Programming

  2013influential citation
• Wireless Scheduling with Dominant Interferers and Applications to Femtocellular Interference Cancellation

  2012cites this paper
• Boolean compressed sensing: LP relaxation for group testing

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

  2012cites this paper
• Belief Propagation Methods for Intercell Interference Coordination in Femtocell Networks

  2012cites this paper
• Approximate evaluation of marginal association probabilities with belief propagation

  2012cites this paper
• Message passing algorithms for optimization

  2011influential citation
• Large-deviation analysis and applications Of learning tree-structured graphical models

  2011cites this paper
• Approximating the permanent with fractional belief propagation

  2011cites this paper
• Message-passing in stochastic processing networks

  2011cites this paper
• Pseudocodewords from Bethe permanents

  2011cites this paper
• Belief propagation methods for intercell interference coordination

  2010cites this paper
• Convergence of Min-Sum Message-Passing for Convex Optimization

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

  2010cites this paper
• Belief Propagation for Minimum Convex-Cost Integral Network Flow

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

  2009cites 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
• 2015 Ieee International Conference on Big Data (big Data) Practical Message-passing Framework for Large-scale Combinatorial Optimization

  year unknowncites this paper