Revisiting the Limits of MAP Inference by MWSS on Perfect Graphs.

Adrian WellerAISTATS 2015 · OpenReview

Abstract

A recent, promising approach to identifying a configuration of a discrete graphical model with highest probability (termed MAP inference) is to reduce the problem to finding a maximum weight stable set (MWSS) in a derived graph. This paper significantly expands the known "tractable" frontier for MAP inference in binary pairwise graphical models. By relaxing previous restrictive assumptions, the author proves that any model where each 2-connected component is "almost balanced" (can be made frustration-free by removing a single vertex) can be solved exactly in polynomial time using graph-theoretic reductions.

Introduction: The Challenge of MAP Inference

In machine learning, Maximum A Posteriori (MAP) inference involves finding the most likely configuration of variables in a graphical model, such as a Markov Random Field (MRF). While general MAP inference is NP-hard, researchers seek "tractable subclasses"—specific model structures where exact answers can be found efficiently.

A promising technique involves reducing the MAP problem to finding the Maximum Weight Stable Set (MWSS) in a derived graph called a nand Markov random field (NMRF). If this derived graph is "perfect," the problem becomes solvable in polynomial time. Previous characterizations of this approach were limited by restrictive assumptions; this work addresses those gaps by considering the full range of possible reparameterizations.

Methodology: From MRF to Perfect NMRF

The core of the approach lies in mapping the MRF to a weighted graph where nodes represent variable assignments and edges represent inconsistencies.

The reduction of an input Markov Random Field (a) to its corresponding Derived nand Markov Random Field (b).

Reparameterization and the "Break" Technique

The author utilizes "singleton transformations" to shift energy between nodes and edges without altering the global optimum. A key innovation is the "break" technique at a vertex. By strategically absorbing singleton potentials into edge potentials and adding "phantom edges" (zero-weight structural edges), one can prevent the formation of "odd holes" (cycles of odd length $\geq 5$). According to the Strong Perfect Graph Theorem, a graph is perfect if and only if it contains no odd holes or their complements, ensuring the derived NMRF remains tractable.

Characterizing Tractable Subclasses

The paper identifies "almost balanced" graphs as the fundamental structural requirement for tractability. A signed graph is balanced if it contains no frustrated cycles (cycles with an odd number of repulsive edges). An almost balanced graph is one where the removal of a single, carefully chosen vertex leaves the remaining subgraph balanced.

Examples of tractable graph structures: (i) balanced $B_R$, (ii) $T_{m,n}$, and (iii) $U_n$, which are unified under the new "almost balanced" framework.

This unified framework handles models containing many such blocks automatically, subsuming several narrow classes of models identified in earlier research.

Key Results and Complexity

  • Theorem 8 (The Main Result): A binary pairwise MRF is tractable via a perfect NMRF if and only if each of its blocks (maximal 2-connected subgraphs) is almost balanced.
  • Efficiency: The paper provides an $O(|E||V|)$ algorithm to detect if a model meets these criteria. This involves identifying the block structure and testing if deleting any one vertex in a block results in a balanced subgraph.
  • Theoretical Expansion: This result proves that the MWSS-on-perfect-graphs approach is far more powerful than previously theorized, providing a single polynomial-time algorithm for a broad class of models.

Limitations and Future Work

While this work expands the theoretical frontier, it is currently limited to binary pairwise models. Extending these results to multi-state variables or higher-order potentials remains a significant challenge. Additionally, while the algorithms are polynomial-time, general MWSS solvers for perfect graphs can be slow in practice; future research may focus on specialized combinatorial algorithms for the specific perfect graphs generated by almost-balanced MRFs.

Summary updated

Abstract

A recent, promising approach to identifying a configuration of a discrete graphical model with highest probability (termed MAP inference) is to reduce the problem to finding a maximum weight stable...
BibTeX
@inproceedings{weller2015revisiting,
  author = {Adrian Weller},
  title = {{Revisiting the Limits of MAP Inference by MWSS on Perfect Graphs.}},
  booktitle = {AISTATS},
  year = {2015},
  url = {https://openreview.net/forum?id=WIVo76MfCOY},
}
Figure