TY - JOUR
T1 - Maximum weight matching using odd-sized cycles
T2 - Max-product belief propagation and half-integrality
AU - Ahn, Sungsoo
AU - Chertkov, Michael
AU - Gelfand, Andrew E.
AU - Park, Sejun
AU - Shin, Jinwoo
N1 - Funding Information:
Manuscript received March 9, 2015; revised July 20, 2017; accepted November 30, 2017. Date of publication December 29, 2017; date of current version February 15, 2018. This work was supported by the National Nuclear Security Administration of the U.S. Department of Energy, Los Alamos National Laboratory, under Contract DE-AC52-06NA25396. This paper was presented at the 2013 Neural Information Processing Systems.
Publisher Copyright:
© 1963-2012 IEEE.
PY - 2018/3
Y1 - 2018/3
N2 - 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.
AB - 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.
KW - Maximum weight matching
KW - belief propagation
KW - half-integrality
UR - http://www.scopus.com/inward/record.url?scp=85040047421&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85040047421&partnerID=8YFLogxK
U2 - 10.1109/TIT.2017.2788038
DO - 10.1109/TIT.2017.2788038
M3 - Article
AN - SCOPUS:85040047421
VL - 64
SP - 1471
EP - 1480
JO - IRE Professional Group on Information Theory
JF - IRE Professional Group on Information Theory
SN - 0018-9448
IS - 3
ER -