Using Combinatorial Optimization within Max-Product Belief Propagation

John C. Duchi, Daniel Tarlow, Gal Elidan, Daphne KollerNeurIPS 2006 · OpenReview

Overview

COMPOSE (Combinatorial Optimization for Max-Product on Subnetworks) is a message-passing framework that allows researchers to use efficient combinatorial algorithms—such as min-cut or bipartite matching—as "black-box" subroutines within Max-Product Belief Propagation. By computing exact max-marginals for tractable sub-parts of a complex model, COMPOSE achieves faster convergence and significantly higher-quality Maximum A Posteriori (MAP) assignments than standard loopy Belief Propagation (BP).

The Challenge: Mixing Tractable and Intractable Constraints

Finding the MAP assignment in a Markov Random Field (MRF)—essentially determining the most likely configuration of variables—is generally an NP-hard problem. However, computer science offers certain "islands of tractability":

  1. Matching problems: Constraints like "this point in image A must map to exactly one point in image B" can be solved exactly using bipartite matching.
  2. Regular/Associative networks: Constraints like "neighboring pixels should probably have the same label" can be solved exactly using min-cut/max-flow algorithms.

The core issue is that real-world tasks often mix these constraints. For example, image registration requires both one-to-one matching constraints and geometric smoothness (regularity). When combined, specialized combinatorial algorithms no longer work out of the box. Furthermore, standard BP often fails to converge or gets stuck in poor local optima because its local message-passing nature cannot effectively "see" or enforce these strict global constraints.

The COMPOSE Framework

The authors introduce COMPOSE to bridge the gap between global combinatorial solvers and local message passing.

  1. Subnetwork Partitioning: The MRF is decomposed into an ensemble of overlapping subnetworks. Some are designated as "matching" networks, others as "regular" networks, and the rest as standard pairwise potentials.
  2. Max-Marginal Communication: Instead of passing a single "best" assignment—which starves other parts of the network of alternative options—each subnetwork computes max-marginals. A max-marginal for a variable $X=x$ represents the score of the best possible global assignment for that subnetwork given that $X$ is strictly fixed to $x$.
  3. Efficient "Black Boxes": The paper's primary technical contribution is demonstrating how to compute all max-marginals for these tractable classes efficiently:
  4. For Bipartite Matching: The system uses a max-weight flow algorithm followed by an all-pairs shortest path algorithm (like Floyd-Warshall) on the residual graph. This finds the "best matching given $X_a=b$" for all pairs $(a, b)$ in $O(N^3)$ time.
  5. For Regular Networks: The framework leverages dynamic graph cut algorithms to compute max-marginals rapidly.
  6. Message Passing: These max-marginals are treated as messages in a standard max-product BP framework. This allows the exact, global information derived from the combinatorial solvers to propagate seamlessly through the rest of the network.

Core Insights

  • Global vs. Local: Standard BP is inherently "local," passing messages only between immediate neighbors. Global constraints (like one-to-one matching) create dense loops that confuse local BP. COMPOSE allows a specialized sub-algorithm to handle the global constraint perfectly and then summarize that global knowledge into a local message.
  • The Necessity of Max-Marginals: You cannot simply plug a MAP solver into BP. The network needs the "cost of the second-best" (and third-best) options to negotiate effectively with overlapping subnetworks. Using the residual graph in flow networks to extract these alternative costs is a major algorithmic advantage.
  • Robustness: Even when the global message passing does not strictly converge, the intermediate assignments found by COMPOSE are often significantly better than the final results of standard BP.

Experimental Results

The authors evaluated COMPOSE on synthetic correspondence networks (2D points with Gaussian noise and geometric constraints) and real-world Electron Microscope Tomography (3D reconstruction of cell organelles requiring marker tracking across tilt angles).

  • Convergence: On synthetic networks with 30 variables, COMPOSE converged significantly more often than state-of-the-art methods like Tree-Reweighted Max-Product (TRMP) or Asynchronous Max-Product (AMP).
  • Accuracy and Score: In synthetic tests, COMPOSE achieved the best score in over 90% of cases. In some instances, the log-likelihood of its solution was $2^{40}$ times better than TRMP.
  • Real-World Performance: On the complex electron microscopy data, standard BP variants failed to converge in 11 out of 12 cases and often produced "illegal" assignments (e.g., mapping multiple source points to the same target). COMPOSE failed to converge only twice and strictly maintained all matching constraints.
Performance comparisons showing COMPOSE's superior convergence rates, scaling of Delta Log Score, and overall Log Score over time compared to TRMP and AMP.

Limitations and Future Directions

While powerful, COMPOSE requires that a problem contains a large, tractable sub-structure for which an efficient max-marginal algorithm exists. Additionally, computing all-pairs shortest paths or multiple graph cuts introduces higher computational overhead per iteration than simple BP, though this is generally offset by faster overall convergence. Future work may explore integrating other "islands of tractability," such as specific constraint satisfaction types, into the COMPOSE framework.

Summary updated

Abstract

In general, the problem of computing a maximum a posteriori (MAP) assignment in a Markov random field (MRF) is computationally intractable. However, in certain subclasses of MRF, an optimal or close-to-optimal assignment can be found very efficiently using combinatorial optimization algorithms: certain MRFs with mutual exclusion constraints can be solved using bipartite matching, and MRFs with regular potentials can be solved using minimum cut methods. However, these solutions do not apply to the many MRFs that contain such tractable components as sub-networks, but also other non-complying potentials. In this paper, we present a new method, called C O M P O S E, for exploiting combinatorial optimization for sub-networks within the context of a max-product belief propagation algorithm. C O M P O S E uses combinatorial optimization for computing exact maxmarginals for an entire sub-network; these can then be used for inference in the context of the network as a whole. We describe highly efficient methods for computing max-marginals for subnetworks corresponding both to bipartite matchings and to regular networks. We present results on both synthetic and real networks encoding correspondence problems between images, which involve both matching constraints and pairwise geometric constraints. We compare to a range of current methods, showing that the ability of C O M P O S E to transmit information globally across the network leads to improved convergence, decreased running time, and higher-scoring assignments.
BibTeX
@inproceedings{duchi2006using,
  author = {John C. Duchi and Daniel Tarlow and Gal Elidan and Daphne Koller},
  title = {{Using Combinatorial Optimization within Max-Product Belief Propagation}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2006},
  url = {https://openreview.net/forum?id=S1-ya8WdZH},
}
Figure