Maximum weight matching using odd-sized cycles: Max-product belief propagation and half-integrality

Sungsoo Ahn, Michael Chertkov, Andrew E. Gelfand, Sejun Park, Jinwoo Shin

Research output: Contribution to journalArticlepeer-review

2 Scopus citations


We study the maximum weight matching (MWM) problem for general graphs through the max-product belief propagation (BP) and related Linear Programming (LP). The BP approach provides distributed heuristics for finding the maximum a posteriori (MAP) assignment in a joint probability distribution represented by a graphical model (GM), and respective LPs can be considered as continuous relaxations of the discrete MAP problem. It was recently shown that a BP algorithm converges to the correct MAP/MWM assignment under a simple GM formulation of MWM, as long as the corresponding LP relaxation is tight. First, under the motivation for forcing the tightness condition, we consider a new GM formulation of MWM, say C-GM, using non-intersecting odd-sized cycles in the graph; the new corresponding LP relaxation, say C-LP, becomes tight for more MWM instances. However, the tightness of C-LP now does not guarantee such convergence and correctness of the new BP on C-GM. To address the issue, we introduce a novel graph transformation applied to C-GM, which results in another GM formulation of MWM, and prove that the respective BP on it converges to the correct MAP/MWM assignment, as long as C-LP is tight. Finally, we also show that C-LP always has half-integral solutions, which leads to an efficient BP-based MWM heuristic consisting of making sequential, 'cutting plane', modifications to the underlying GM. Our experiments show that this BP-based cutting plane heuristic performs, as well as that based on traditional LP solvers.

Original languageEnglish (US)
Pages (from-to)1471-1480
Number of pages10
JournalIEEE Transactions on Information Theory
Issue number3
StatePublished - Mar 2018
Externally publishedYes


  • Maximum weight matching
  • belief propagation
  • half-integrality

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences


Dive into the research topics of 'Maximum weight matching using odd-sized cycles: Max-product belief propagation and half-integrality'. Together they form a unique fingerprint.

Cite this