A Graphical Transformation for Belief Propagation: Maximum Weight Matchings and Odd-Sized Cycles

Jinwoo Shin, Andrew E. Gelfand, Michael Chertkov

Abstract

This paper introduces a novel graphical transformation that enables Max-Product Belief Propagation (BP) to solve the Maximum Weight Matching (MWM) problem on general graphs. By collapsing odd-sized cycles into auxiliary vertices, the authors ensure BP converges to the correct solution whenever the underlying Linear Programming (LP) relaxation is tight. This approach effectively transforms BP into a distributed LP solver capable of handling complex graph structures that typically cause standard BP to fail.

Introduction

Maximum Weight Matching (MWM) is a fundamental problem in combinatorial optimization, requiring the selection of a set of non-adjacent edges that maximize the total weight. While centralized algorithms like Edmonds' Blossom algorithm solve this efficiently, distributed solutions are highly desirable for large-scale networks. Belief Propagation (BP) is a natural candidate for distributed optimization; however, its performance on MWM is traditionally limited to graphs where the LP relaxation is naturally tight, such as bipartite graphs. On general graphs with odd-sized cycles, standard BP often fails to converge or produces incorrect results.

Methodology: Graphical Transformation and CP-BP

The researchers propose a multi-step methodology to integrate odd-cycle constraints into the BP framework without disrupting its convergence properties.

The Graphical Transformation

The core innovation is the Graphical Transformation ($C-GM'$). Instead of simply adding factor nodes for cycles—which increases graph complexity—the authors "collapse" each odd cycle into a new auxiliary vertex and redefine edge weights accordingly. This transformation maintains a "Degree-Two" condition, where each variable is associated with at most two factor nodes. This structural property is essential for proving BP convergence using computation tree analysis.

Graphical transformation of an odd-sized cycle into a star-like structure with an auxiliary vertex.

Cutting-Plane BP (CP-BP)

To handle general graphs, the authors developed the CP-BP heuristic. This algorithm iteratively runs BP and identifies edges with fractional solutions (typically 0.5). These fractional values signal the presence of an odd cycle. The algorithm then adds the cycle as a constraint, applies the graphical transformation, and restarts BP. This process repeats until an integer solution is found or no more cycles can be identified.

Theoretical Insights and Convergence

A significant contribution of this work is the realization that LP tightness is insufficient for BP convergence on loopy graphs; the factor graph's topology is equally critical. By mathematically restructuring the graph, the authors restore the conditions under which BP is provably well-behaved.

Comparison of computation trees before and after the graphical transformation, illustrating the structural simplification that enables BP convergence.

Theorem 2 in the paper provides a theoretical guarantee: on the transformed graph, BP is guaranteed to converge to the correct MWM assignment in polynomial time, provided the LP relaxation is tight and unique. Furthermore, the cycle-augmented LP always yields "half-integral" solutions, making it straightforward for the BP algorithm to flag cycles for the cutting-plane step.

Experimental Results

The approach was evaluated using Erdős-Rényi (ER) random graphs with varying sizes (10 to 100 nodes) and edge densities. Edge weights were chosen uniformly at random from a wide range ($1$ to $10^6$).

  • Performance Parity: The CP-BP heuristic performed almost identically to traditional centralized cutting-plane methods (CP-LP) using standard solvers.
  • Reliability Gains: The transformed BP significantly outperformed standard BP and basic LP relaxations. For 100-node graphs, the failure rate dropped from approximately 40% to nearly 0% when cycle constraints and transformations were applied.

Conclusion and Future Work

This work demonstrates that graphical transformations can bridge the gap between distributed message-passing and complex combinatorial constraints. While currently limited to edge-disjoint odd cycles, future research aims to extend this theory to intersecting cycles and fully distributed cycle detection. The authors suggest that similar transformation techniques could be applied to other challenging MAP inference problems, such as Independent Set or Network Flow optimization.

Summary updated

BibTeX
@inproceedings{shin2013graphical,
  author = {Jinwoo Shin and Andrew E. Gelfand and Michael Chertkov},
  title = {{A Graphical Transformation for Belief Propagation: Maximum Weight Matchings and Odd-Sized Cycles}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2013},
}
Figure