Source-linked AI summary
Complexity of Inference in Graphical Models
Venkat Chandrasekaran, Nathan Srebro, Prahladh Harsha
TL;DR
The paper asks whether graph structures beyond bounded treewidth can guarantee tractable inference, even among high-treewidth families. Using graph-minor reductions, it shows that binary-variable inference cannot be polynomial in treewidth under stated assumptions, with a separate planar result requiring a weaker assumption.
Problem
The paper asks whether any structural property beyond bounded treewidth can guarantee tractable inference, including for best-case high-treewidth graph families.
Source: §1 · p. 1Method
The proof reduces planar-graph inference through grids to inference on increasing-treewidth graph families using graph-minor theorems and non-uniformly hardwired minor operations.
Source: §1 · p. 2Results
Under NP̸ ⊆ P/poly and the grid-minor hypothesis, no unbounded-treewidth class of binary-variable models permits inference polynomial in treewidth; for planar graphs, only NP̸ ⊆ P/poly is required.
Source: §1 · p. 2Takeaways & Limitations
A structural property guaranteeing tractable inference without bounding treewidth would imply a counterexample to the grid-minor hypothesis.
Source: §6 · p. 9For general graph classes, the main hardness result depends on the grid-minor hypothesis, which posits a polynomial bound on the relevant treewidth threshold.
Source: §1 · p. 2
Abstract
from arXiv · showhide
It is well-known that inference in graphical models is hard in the worst case, but tractable for models with bounded treewidth. We ask whether treewidth is the only structural criterion of the underlying graph that enables tractable inference. In other words, is there some class of structures with unbounded treewidth in which inference is tractable? Subject to a combinatorial hypothesis due to Robertson et al. (1994), we show that low treewidth is indeed the only structural restriction that can ensure tractability. Thus, even for the "best case" graph structure, there is no inference algorithm with complexity polynomial in the treewidth.
1 INTRODUCTION
The introduction asks whether graph structure other than bounded treewidth can guarantee tractable inference, including for best-case high-treewidth families. It answers no for binary-variable models under stated computational and graph-minor assumptions.
1 INTRODUCTION
- The paper focuses on whether any structural property beyond low treewidth can ensure tractable inference for every choice of potentials.This is framed as best-case hardness: whether inference remains hard even in the easiest high-treewidth graph structures.Source: §1 · pp. 1–2
- The grid-minor hypothesis posits that the treewidth threshold guaranteeing a g×g grid minor is polynomially bounded in g.The paper describes the hypothesis as reflecting the belief that the threshold is closer to the known lower bound than to the upper bound.Source: §1 · p. 2
- Under NP̸ ⊆ P/poly and the grid-minor hypothesis, no class of binary-variable models with unbounded treewidth permits inference polynomial in treewidth.For every sequence of graphs indexed by treewidth, some choice of potentials yields super-polynomial inference runtime.Source: §1 · p. 2
- For planar graphs, the same hardness holds assuming only NP̸ ⊆ P/poly; the paper also gives ETH-based sharper bounds and additive-constant randomized approximation hardness for the partition function.The approximation result concerns estimating the partition function to within an additive constant.Source: §1 · p. 2
- The proof reduces planar-graph inference through grids to inference on any increasing-treewidth graph family using graph-minor theorems.Because known treewidth bounds are too weak, the proof relies on the grid-minor hypothesis or restricts the target family to planar graphs; fixed minor-operation sequences can be hardwired non-uniformly.Source: §1 · pp. 2–3
2 BACKGROUND
Graphical-model inference is framed as computing a partition function, whose complexity depends on graph structure. The section introduces treewidth and graph minors, then shows how inference on a minor can be represented on the original graph.
2.1 GRAPHICAL MODELS AND INFERENCE
- Inference is defined as computing the partition function; computing a marginal is polynomial-time interconvertible with computing that function.The partition function normalizes the distribution, and its sum has exponentially many terms.Source: §2.1 · p. 3
2.2 UNIFORM VS. NON-UNIFORM ALGORITHMS
- Non-uniform algorithms are length-specific families, and the paper uses the assumption NP ⊄ P/poly because its proof reduces best-case inference to a non-uniform algorithm for NP.P/poly is the non-uniform counterpart of P.Source: §2.2 · p. 3
2.3 GRAPH TREEWIDTH
- Treewidth is the minimum treewidth among a graph’s triangulated supergraphs; junction-tree inference scales exponentially with treewidth on general loopy graphs.Figure 1 illustrates a non-triangulated graph and a triangulated supergraph; the example has treewidth 3.Source: §2.3 · pp. 3–4, Figure 1 · p. 4
2.4 GRAPH MINORS
- Graph minors arise through vertex deletion, edge deletion, and edge contraction; the grid-minor theorem links sufficiently high treewidth to grid minors, with a polynomial grid-minor bound assumed for the main result.For planar graphs, the cited theorem gives a grid-minor relation with universal constants and a linear bound on κGM(g).Source: §2.4 · pp. 4–5
2.4.1 Inference and graph minors
- For any potential assignment on a minor H of G, a corresponding assignment on G preserves the partition function, allowing hardness on H to establish hardness on G.The corresponding potentials can be computed in linear time given the minor-operation sequence.Source: §2.4.1 · p. 5
3 PROBLEM STATEMENT
The section asks whether inference can remain tractable on some sequence of graphs whose treewidth grows without bound, even in the easiest graph structures at each treewidth. It formalizes this best-case runtime question and also poses an analogous question for approximate partition-function computation.
3 PROBLEM STATEMENT
- The runtime framework takes a graph and its potentials as input and studies how treewidth affects the time required to compute the partition function.The runtime of algorithm f on input I is denoted T_f(I).Source: §3 · p. 5
- The main question is whether any inference algorithm has best-case runtime β_f(k) polynomial in treewidth k; otherwise, bounded treewidth is the only structural restriction yielding tractability.The paper defines β_f(k) by considering the easiest graph of treewidth k and the worst potential assignment.Source: §3 · pp. 5–6
- The analysis allows a non-uniform sequence of algorithms, each specialized to a graph of its own treewidth, making the question harder than the uniform-algorithm version.For each graph, runtime is taken in the worst case over potential functions.Source: §3 · p. 6
- The paper also asks whether randomized algorithms can approximate the partition function within additive ε with high probability.The approximation is expressed as an estimate bZ between Z(ψ) − ε and Z(ψ) + ε.Source: §3 · p. 6
4 CONSTRAINT SATISFACTION AND INFERENCE
The section connects constraint-satisfaction hardness to graphical-model inference by translating CSP instances into partition-function questions. It first treats arbitrary-cardinality variables, then highlights why separate results are needed for binary variables.
4 CONSTRAINT SATISFACTION AND INFERENCE
- The section distinguishes decision CSPs, which ask whether a satisfying assignment exists, from MAX CSPs, which ask whether at least a specified number of constraints can be satisfied.Planar MAX 2-SAT is NP-complete, despite polynomial-time algorithms for 2-SAT.Source: §4 · p. 6
- A MAX 2-CSP instance can be mapped to an inference decision problem whose partition function crosses a threshold exactly when at least d constraints can be satisfied.The mapping and threshold evaluation are polynomial-time operations.Source: §4 · p. 6
- Setting d = |R| in the reduction converts 2-CSP instances into decision versions of inference, while counting CSP solutions can be encoded in the integer part of the partition function.For #2-CSP, the potentials can be constructed in polynomial time.Source: §4 · p. 7
- Under ETH, arbitrary-cardinality inference cannot have β_f(k,q) ≤ q^r for all instances when r(k) = o(k/log k).The section also derives that an algorithm for arbitrary-cardinality 2-CSP with the stated runtime would imply ETH fails.Source: §4 · p. 7
- This lower bound makes the junction-tree algorithm, which scales as q^k, near-optimal in a stated sense, but it gives no lower bound for any fixed cardinality q.The cited limitation arises because the reductions use large-cardinality variables.Source: §4 · p. 7
5 MAIN RESULTS
The main results establish conditional hardness for exact inference on high-treewidth graph families and extend the argument to approximation. The bounds depend on graph-minor assumptions, with a planar exact-inference result requiring no grid-minor hypothesis.
5.1 EXACT INFERENCE
- Under the grid-minor hypothesis and ETH, exact inference on graph families indexed by treewidth has T(k) = 2^Ω(k^(1/2r)) when κGM(g) = O(g^r); under NP̸ ⊆P/poly and the grid-minor hypothesis, T(k) is super-polynomial.The theorem concerns binary-variable models.Source: §5.1 · p. 7
- For binary-variable models on planar graphs, exact inference has super-polynomial complexity in treewidth without requiring the grid-minor hypothesis; the result also extends to bounded-genus graphs.The proof of the planar result relies on a different graph-minor theorem.Source: §5.1 · p. 8
5.2 APPROXIMATE INFERENCE
- The paper also proves that approximating the partition function within an additive constant is intractable under the grid-minor hypothesis.The argument uses planar #2-SAT and a reduction to inference.Source: §5.2 · p. 8
6 CONCLUSION
The conclusion argues that no alternate graph-structural property is likely to guarantee tractable inference without bounding treewidth: such a property would contradict the grid-minor hypothesis. It identifies removing that hypothesis and restricting potential functions as open directions.
6 CONCLUSION
- A structural property guaranteeing tractable inference without bounded treewidth would provide a counterexample to Robertson and Seymour’s grid-minor hypothesis.The authors present this as evidence that inference remains hard even on the easiest high-treewidth structures.Source: §6 · p. 9
- The authors identify proving the results without the grid-minor hypothesis and establishing hardness for bounded-dynamic-range potentials as open problems.The latter concerns reasonably restricted classes of potential functions.Source: §6 · p. 9