Polynomial-Time Exact Inference in NP-Hard Binary MRFs via Reweighted Perfect Matching

Nic SchraudolphAISTATS 2010

Abstract: Exact inference in non-planar binary Markov Random Fields (MRFs) is a fundamental NP-hard problem in computer vision and machine learning. This paper introduces Reweighted Perfect Matching (RPM), a technique that bridges the gap between tractable planar Ising models and complex non-planar topologies. By mapping the problem to a dual decomposition of planar subgraphs and integrating reweighting directly into the Blossom algorithm via "slack sharing," RPM achieves exact MAP inference with empirical polynomial-time complexity. On large toroidal lattices, RPM demonstrates $O(n^3)$ scaling, outperforming existing exact solvers by orders of magnitude and consistently finding global optima where heuristic message-passing fails.

Introduction

Finding the ground state—the configuration with the lowest energy or Maximum A Posteriori (MAP) state—of a Markov Random Field (MRF) is a cornerstone of probabilistic graphical models. While efficient algorithms exist for trees (Belief Propagation) and submodular graphs (Graph Cuts), the problem becomes NP-hard when the graph is non-planar and contains "frustrated" cycles. Traditional approaches often resort to heuristics like Loopy BP, which may not converge, or exponential-time exact solvers that are impractical for large-scale grids.

The Challenge of Non-Planar MRFs

The complexity of MAP inference is deeply tied to the topology of the underlying graph. A classic result in statistical physics allows the ground state of a planar Ising model to be found in polynomial time by mapping it to a minimum-weight perfect matching problem. However, real-world problems often involve non-planar graphs—those with crossing edges or those defined on complex surfaces like a torus.

Figure 4: A toroidal lattice, representing a genus-1 surface where standard planar inference techniques fail due to non-trivial cycles.

In these non-planar cases, the presence of cycles that cannot be enclosed within a single planar face introduces topological constraints that break standard matching-based solvers. The author shifts the focus of "hardness" from the number of nodes to the genus (number of holes/crossings) of the graph.

Reweighted Perfect Matching (RPM)

The proposed Reweighted Perfect Matching (RPM) algorithm overcomes these constraints by leveraging a collection of planar embeddings. The core methodology involves:

  1. Extended Ground States: For non-planar graphs, a single matching approach only yields a lower bound on the energy, termed an extended ground state.
  2. Consistent Collections: The graph is decomposed into a set of planar subgraphs. These are chosen such that their faces collectively cover every possible cycle in the original graph, forming a "consistent collection."
  3. Dual Decomposition and Slack Sharing: Using a reweighting framework, the algorithm iteratively adjusts edge weights across these subgraphs until they reach consensus on the state of every edge. To optimize this, "slack sharing" integrates the reweighting directly into the linear programming steps of the Blossom algorithm.
Figure 6: Decomposition of a non-planar grid into a consistent collection of planar subgraphs to facilitate exact inference.

Experimental Evaluation and Results

The algorithm was evaluated on synthetic benchmarks designed to challenge state-of-the-art solvers, including $n \times n$ Ising lattices and toroidal lattices with periodic boundary conditions. RPM was compared against BiqMac (semidefinite programming), MPLP (Message Passing Linear Programming), and the specialized Spin Glass Server (SGS).

RPM demonstrated remarkable performance across all benchmarks:

  • Scalability: The algorithm successfully solved $256 \times 256$ grids (over 65,000 nodes) in approximately 45 minutes. In contrast, BiqMac failed to process grids larger than $20 \times 20$ within a three-hour window.
  • Exactness: Unlike MPLP, which often failed to converge on toroidal grids, RPM consistently identified the exact global optimum.
  • Empirical Complexity: Across the range of tested grid sizes, the CPU time followed a clear $O(n^3)$ power law, suggesting that while the problem is NP-hard in the worst case, it is practically solvable for these structures.

Discussion and Limitations

While RPM offers a powerful tool for exact inference, it has certain limitations. The number of iterations required for convergence could theoretically be exponential, though this was not observed in practice for the tested lattices. Additionally, the current implementation relies on hand-crafted subgraph collections for specific topologies; automating this discovery for arbitrary graphs remains an open research question. Finally, numerical precision issues can arise in extremely large grids ($n > 200$), requiring careful handling of degenerate edge weights.

Conclusion

Reweighted Perfect Matching represents a significant step forward in exact inference for NP-hard MRFs. By shifting the focus to graph topology and employing a sophisticated reweighting scheme, it provides a polynomial-time path to global optima in complex, non-planar models.

Summary updated

BibTeX
@article{schraudolph2010polynomial,
  author = {Nic Schraudolph},
  title = {{Polynomial-Time Exact Inference in NP-Hard Binary MRFs via Reweighted Perfect Matching}},
  journal = {AISTATS},
  year = {2010},
}
Figure