Tractable Minor-free Generalization of Planar Zero-field Ising Models
This work addresses the challenge of efficient inference in complex graphical models for researchers in statistical physics and machine learning, though it is incremental as it extends existing planar methods to minor-free generalizations.
The authors tackled the problem of exact inference and sampling in zero-field Ising models by introducing a new family of tractable graphical models based on gluing planar and small components into a tree structure, resulting in polynomial-time algorithms for K3,3-minor-free and K5-minor-free topologies, with empirical improvements in approximation quality for NP-hard inference in non-zero fields.
We present a new family of zero-field Ising models over $N$ binary variables/spins obtained by consecutive "gluing" of planar and $O(1)$-sized components and subsets of at most three vertices into a tree. The polynomial-time algorithm of the dynamic programming type for solving exact inference (computing partition function) and exact sampling (generating i.i.d. samples) consists in a sequential application of an efficient (for planar) or brute-force (for $O(1)$-sized) inference and sampling to the components as a black box. To illustrate the utility of the new family of tractable graphical models, we first build a polynomial algorithm for inference and sampling of zero-field Ising models over $K_{3,3}$-minor-free topologies and over $K_{5}$-minor-free topologies -- both are extensions of the planar zero-field Ising models -- which are neither genus - nor treewidth-bounded. Second, we demonstrate empirically an improvement in the approximation quality of the NP-hard problem of inference over the square-grid Ising model in a node-dependent non-zero "magnetic" field.