Complexity of Inference in Graphical Models

By Venkat Chandrasekaran, Nati Srebro, P. Harsha. 2008

131 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Computer Networks and Communications

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

In Computer Networks and Communications

Citations in the corpus

A Kernelized Stein Discrepancy for Goodness-of-fit Tests (2016, background): “In fact, it is often a #P-complete problem to calculate or even approximate likelihoods for graphical models (e.g, Chandrasekaran et al., 2008), making likelihood-based approaches fundamentally infeasible.”
Convergent Decomposition Solvers for Tree-reweighted Free Energies (2011, background): “Exact computation of marginal probabilities and the partition function in general graphical models is an NP-hard problem that scales exponentially in the treewidth of the graph (Chandrasekaran et al., 2008).”