Complexity of Inference in Graphical Models

Venkat Chandrasekaran, Nathan Srebro, Prahladh HarshaUAI 2008

Abstract

This paper investigates the fundamental structural properties that govern the tractability of inference in probabilistic graphical models (PGMs). By synthesizing graph minor theory with computational complexity, the authors demonstrate that treewidth is likely the unique structural parameter that guarantees polynomial-time inference. The study proves that for any class of graphs with unbounded treewidth, both exact and approximate inference remain super-polynomially hard, even for the simplest case of binary variables.

Introduction: Is Treewidth the Only Way to Win?

In the field of PGMs, inference tasks—such as computing marginal distributions or the partition function $Z$—are essential but generally NP-hard. It is well-established that these tasks become tractable when the underlying graph has low treewidth, typically via the junction tree algorithm. This research asks a critical converse question: Does there exist any other structural property besides low treewidth that enables efficient inference? By focusing on "best-case" hardness, the authors aim to show that bounding treewidth is a necessary condition for tractability across any general class of graphs.

Methods and Theoretical Framework

The authors approach this problem using sophisticated tools from graph theory and complexity science. A central pillar of their proof is the Robertson-Seymour theorem, which states that any graph with sufficiently large treewidth contains a large grid as a "minor." A minor is a graph derived through a sequence of vertex deletions, edge deletions, and edge contractions.

Figure 2: Illustration of graph minor operations, showing the sequential transformation from a grid $G$ to various minors $H_1, H_2, H_3$ through edge deletions and contractions.

The proof involves reducing Constraint Satisfaction Problems (specifically MAX 2-SAT) to inference problems on these grid-like structures. The results are predicated on several key complexity-theoretic assumptions:

  • NP $\not\subseteq$ P/poly: A non-uniform version of the P $\neq$ NP hypothesis.
  • Grid-Minor Hypothesis: The belief that the size of an embedded grid minor grows polynomially with the graph's treewidth.
  • Exponential Time Hypothesis (ETH): A stronger version of P $\neq$ NP used to derive tighter lower bounds.

Key Insights: Grids as Universal Hard Structures

A major contribution of this work is proving hardness for binary variables. Previous research required the number of states per variable to scale with graph size; this paper shows that even the simplest variables cannot overcome the complexity of high-treewidth structures.

Figure 1: A grid graph $G$ and a modified structure $H$, illustrating how grid-based gadgets can be used to encode hard combinatorial problems.

Because large grids are inherent in all high-treewidth graphs and are sufficiently expressive to encode hard problems like MAX 2-SAT, the grid serves as a "universal" bridge for proving hardness. For planar graphs, the authors provide even stronger results that do not rely on the Grid-Minor Hypothesis.

Key Results

The paper establishes rigorous computational lower bounds for inference:

  • Exact Inference: Assuming the grid-minor hypothesis and NP $\not\subseteq$ P/poly, the time required for inference is super-polynomial in the treewidth $k$.
  • Quantitative Bounds: Under ETH, the authors show that for any sequence of graphs with treewidth $k$, inference takes at least $2^{\Omega(k^{1/2r})}$ time.
  • Approximate Inference: The paper extends these findings to show that approximating the partition function to within an additive constant is NP-hard, as it would enable solving #P-complete counting problems.

Discussion and Future Work

The primary limitation of the general result is its dependence on the grid-minor hypothesis. While widely accepted by graph theorists, current proven bounds for grid-minor sizes are super-exponential, which is too weak for some of the paper's tighter complexity claims.

Additionally, the paper assumes that potential functions can be chosen "adversarially." Future work could investigate if restricting the dynamic range or the specific nature of potential functions (e.g., ferromagnetic Ising models) might allow for tractability even in high-treewidth graphs. The use of non-uniform complexity classes (P/poly) also highlights the theoretical depth required to address these fundamental limits.

Summary updated

BibTeX
@inproceedings{chandrasekaran2008complexity,
  author = {Venkat Chandrasekaran and Nathan Srebro and Prahladh Harsha},
  title = {{Complexity of Inference in Graphical Models}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2008},
}
Figure