  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 MWM assignment under a simple GM formulation
of MAP/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.
