A Graphical Transformation for Belief Propagation: Maximum Weight Matchings and Odd-Sized Cycles
Max-product 'belief propagation' (BP) is a popular distributed heuristic for finding the Maximum A Posteriori (MAP) assignment in a joint probability distribution represented by a Graphical Model (GM). It was recently shown that BP converges to the correct MAP assignment for a class of loopy GMs with the following common feature: the Linear Programming (LP) relaxation to the MAP problem is tight (has no integrality gap). Unfortunately, tightness of the LP relaxation does not, in general, guarantee convergence and correctness of the BP algorithm. The failure of BP in such cases motivates reverse engineering a solution -namely, given a tight LP, can we design a 'good' BP algorithm. In this paper, we design a BP algorithm for the Maximum Weight Matching (MWM) problem over general graphs. We prove that the algorithm converges to the correct optimum if the respective LP relaxation, which may include inequalities associated with non-intersecting odd-sized cycles, is tight. The most significant part of our approach is the introduction of a novel graph transformation designed to force convergence of BP. Our theoretical result suggests an efficient BP-based heuristic for the MWM problem, which consists of making sequential, "cutting plane", modifications to the underlying GM. Our experiments show that this heuristic performs as well as traditional cutting-plane algorithms using LP solvers on MWM problems.
The authors extend a known theorem that states that, 
      if the linear relaxation of an MWM problem is tight, then BP will converge 
      correctly on the corresponding graphical model. While this previously was 
      only shown with no "blossom" inequalities -- i.e. inequalities that help 
      to achieve integrality of the LP -- the paper extends this theorem to hold 
      also with such inequalities. That allows more instances of MWM to be 
      solved via BP. This reviewer thinks that the paper adds a tiny 
      puzzle piece to understand loopy BP properties, but is not perfectly clear 
      in the presentation and lacks an (experimental) proof of the usefulness of 
      the results. Clarity of presentation: - The is \Omega a set of 
      node indices or the value range of Z_i? - The GM is introduced in L104 
      without ever referring to a graph. ? - The notation in the 
      introduction is not very clear, which conditions are necessary and which 
      are sufficient (L50: "BP converges ... when LP tight" ==> supposed to 
      mean not sufficient, L68 "BP converges ... if LP is tight" ==> supposed 
      to mean sufficient). - What is an odd-sized cycle? |C| odd or |E(C)| 
      odd? - L139: For general (non-pairwise-potential) GM problems, the 
      messages could have more than one free variable. - L179: What is V(C)? 
      - "it is not hard to check ... updates involving \Phi_C can be done 
      using dynamic programming" I cannot see that. - Figure 1 is not 
      intuitive and is not explained sufficiently. - L293-306 The proof's 
      correctness is obstructed by too complicated notation (e.g. why is 
      y_{e’}{NEW}=1? Is this implied by the odd/even path in your notation?) 
      Usefulness of the results: - Why not simply do LP? The only 
      real advantage to me seems that BP can be implemented in a distributed 
      fashion. But if so, can it also be checked in a distributed fashion, 
      whether the LP is tight (and thus the BP result is trustworthy)? - The 
      experiments should not only use random graphs but real ones. Otherwise the 
      benefit of the blossom inequalities may be overrated. - The 
      experiments should show beneficial timings or some other proof of the 
      advantage of the proposed method. - The potentials \Phi_C potentially 
      contain many variables. Summing over them during the BP update may become 
      exponentially hard. Response to the authors' rebuttal: In their 
      rebuttal, the authors have put their work in the light of "making LP ready 
      for parallel computation". Moreover, they have promised to add more 
      experimental results to support this claim. I think this line of 
      argumentation adds an interesting perspective to the work. It should be 
      elaborated on in the final version of the paper.