Complexity of Inference in Graphical Models

Abstract

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.

Appears in Proceedings of the Twenty-Fourth Conference on Uncertainty in Artificial Intelligence (UAI2008)

References in corpus (2)

• Loop series for discrete statistical models on graphs
• MAP Estimation, Message Passing, and Perfect Graphs

Cited by in corpus (23)

• Perturbation Biology: inferring signaling networks in cellular systems
• SPPL: Probabilistic Programming with Fast Exact Symbolic Inference
• Advances in Learning Bayesian Networks of Bounded Treewidth
• Fast and Three-rious: Speeding Up Weak Supervision with Triplet Methods
• Rapidly Mixing Gibbs Sampling for a Class of Factor Graphs Using Hierarchy Width
• A Kernelized Stein Discrepancy for Goodness-of-fit Tests and Model Evaluation
• Graphical modeling of stochastic processes driven by correlated errors
• Tractable Lineages on Treelike Instances: Limits and Extensions
• Towards common-sense reasoning via conditional simulation: legacies of Turing in Artificial Intelligence
• The Sum-Product Theorem: A Foundation for Learning Tractable Models
• Learning Clique Forests
• Chordal Decomposition in Rank Minimized Semidefinite Programs with Applications to Subspace Clustering
• Convergence Rates of Biased Stochastic Optimization for Learning Sparse Ising Models
• Graph Neural Networks Including Sparse Interpretability
• Learning Maximum-A-Posteriori Perturbation Models for Structured Prediction in Polynomial Time
• Limitations of Autoregressive Models and Their Alternatives
• Multi-Context Models for Reasoning under Partial Knowledge: Generative Process and Inference Grammar
• Neural Trees for Learning on Graphs
• Max-Product Belief Propagation for Linear Programming: Applications to Combinatorial Optimization
• Polynomial-Time Exact MAP Inference on Discrete Models with Global Dependencies
• CSMA using the Bethe Approximation: Scheduling and Utility Maximization
• Fairness constraints can help exact inference in structured prediction
• A Thorough View of Exact Inference in Graphs from the Degree-4 Sum-of-Squares Hierarchy