Tractable minor-free generalization of planar zero-field Ising models

Valerii Likhosherstov, Yury Maximov, Michael Chertkov

Research output: Contribution to journalArticlepeer-review


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 of 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 33-minor-free topologies and over K 5-minor-free topologies - both of which are extensions of the planar zero-field Ising models - which are neither genus- nor treewidth-bounded. Second, we empirically demonstrate an improvement in the approximation quality of the NP-hard problem of inference over the square-grid Ising model in a node-dependent nonzero 'magnetic' field.

Original languageEnglish (US)
Article number124007
JournalJournal of Statistical Mechanics: Theory and Experiment
Issue number12
StatePublished - Dec 21 2020


  • analysis of algorithms
  • inference of graphical models
  • statistical inference

ASJC Scopus subject areas

  • Statistical and Nonlinear Physics
  • Statistics and Probability
  • Statistics, Probability and Uncertainty


Dive into the research topics of 'Tractable minor-free generalization of planar zero-field Ising models'. Together they form a unique fingerprint.

Cite this