Complexity of Inference in Graphical Models
This provides a theoretical foundation for understanding computational limits in graphical models, relevant for researchers in machine learning and algorithms, though it is incremental as it builds on prior combinatorial hypotheses.
The paper tackles the problem of whether treewidth is the only structural criterion enabling tractable inference in graphical models, and shows that, subject to a combinatorial hypothesis, low treewidth is indeed the only such restriction, with no polynomial-time algorithm even for optimal graph structures.
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.