Maximum Weight Matching via Max-Product Belief Propagation

Abstract

Max-product "belief propagation" is an iterative, local, message-passing algorithm for finding the maximum a posteriori (MAP) assignment of a discrete probability distribution specified by a graphical model. Despite the spectacular success of the algorithm in many application areas such as iterative decoding, computer vision and combinatorial optimization which involve graphs with many cycles, theoretical results about both correctness and convergence of the algorithm are known in few cases (Weiss-Freeman Wainwright, Yeddidia-Weiss-Freeman, Richardson-Urbanke}. In this paper we consider the problem of finding the Maximum Weight Matching (MWM) in a weighted complete bipartite graph. We define a probability distribution on the bipartite graph whose MAP assignment corresponds to the MWM. We use the max-product algorithm for finding the MAP of this distribution or equivalently, the MWM on the bipartite graph. Even though the underlying bipartite graph has many short cycles, we find that surprisingly, the max-product algorithm always converges to the correct MAP assignment as long as the MAP assignment is unique. We provide a bound on the number of iterations required by the algorithm and evaluate the computational cost of the algorithm. We find that for a graph of size $n$, the computational cost of the algorithm scales as $O(n^3)$, which is the same as the computational cost of the best known algorithm. Finally, we establish the precise relation between the max-product algorithm and the celebrated {\em auction} algorithm proposed by Bertsekas. This suggests possible connections between dual algorithm and max-product algorithm for discrete optimization problems.

In the proceedings of the 2005 IEEE International Symposium on Information Theory

Cited by in corpus (54)

• Message Passing Algorithms for Compressed Sensing
• Approximate evaluation of marginal association probabilities with belief propagation
• Message-passing for Maximum Weight Independent Set
• Scaling hypothesis for the Euclidean bipartite matching problem
• Belief-Propagation for Weighted b-Matchings on Arbitrary Graphs and its Relation to Linear Programs with Integer Solutions
• High-Dimensional Gaussian Graphical Model Selection: Walk Summability and Local Separation Criterion
• The Bethe Permanent of a Non-Negative Matrix
• Inference in particle tracking experiments by passing messages between images
• On the exactness of the cavity method for Weighted b-Matchings on Arbitrary Graphs and its Relation to Linear Programs
• Fully distributed optimal channel assignment for open spectrum access
• Distributed Learning for Channel Allocation Over a Shared Spectrum
• The zero-patient problem with noisy observations
• Mathematical Programming Decoding of Binary Linear Codes: Theory and Algorithms
• Conditional Set Generation with Transformers
• Belief Propagation and Loop Calculus for the Permanent of a Non-Negative Matrix
• Approximating the Permanent with Fractional Belief Propagation
• Exactness of Belief Propagation for Some Graphical Models with Loops
• Belief Propagation and Beyond for Particle Tracking
• Classification-Aided Multitarget Tracking Using the Sum-Product Algorithm
• A Natural Dynamics for Bargaining on Exchange Networks
• The edge-disjoint path problem on random graphs by message-passing
• Dandelion: Redesigning the Bitcoin Network for Anonymity
• On belief propagation guided decimation for random k-SAT
• One-loop diagrams in the Random Euclidean Matching Problem
• Recovery thresholds in the sparse planted matching problem
• Inference-Based Distributed Channel Allocation in Wireless Sensor Networks
• Belief propagation for optimal edge cover in the random complete graph
• Graphical model approximations of random finite set filters
• Random-link matching problems on random regular graphs
• A Graphical Transformation for Belief Propagation: Maximum Weight Matchings and Odd-Sized Cycles
• Boolean Matrix Factorization and Noisy Completion via Message Passing
• SERENADE: A Parallel Randomized Algorithm Suite for Crossbar Scheduling in Input-Queued Switches
• Loopy annealing belief propagation for vertex cover and matching: convergence, LP relaxation, correctness and Bethe approximation
• My Fair Bandit: Distributed Learning of Max-Min Fairness with Multi-player Bandits
• The Random Fractional Matching Problem
• Minimum Weight Perfect Matching via Blossom Belief Propagation
• Loop Calculus and Bootstrap-Belief Propagation for Perfect Matchings on Arbitrary Graphs
• Belief Propagation for Min-cost Network Flow: Convergence and Correctness
• Bargaining dynamics in exchange networks
• Bounding the Bethe and the Degree-$M$ Bethe Permanents
• Some observations on the ambivalent role of symmetries in Bayesian inference problems
• Wireless Scheduling with Dominant Interferers and Applications to Femtocellular Interference Cancellation
• Bargaining Dynamics in Exchange Networks
• Belief Propagation for Linear Programming
• Belief Propagation Methods for Intercell Interference Coordination
• Belief propagation : an asymptotically optimal algorithm for the random assignment problem
• R(QPS-Serena) and R(QPS-Serenade): Two Novel Augmenting-Path Based Algorithms for Computing Approximate Maximum Weight Matching
• Message-Passing Algorithms for Optimal Utilization of Cognitive Radio Networks
• Belief Propagation Min-Sum Algorithm for Generalized Min-Cost Network Flow
• Planted matching problems on random hypergraphs
• The closest vector problem and the zero-temperature p-spin landscape for lossy compression
• Smoothed Analysis of Belief Propagation for Minimum-Cost Flow and Matching
• Correct Convergence of Min-Sum Loopy Belief Propagation in a Block Interpolation Problem
• Belief propagation for minimum weight many-to-one matchings in the random complete graph