A New Family of Tractable Ising Models

Valerii Likhosherstov, Yury Maximov, Michael ChertkovarXiv 2019 · arXiv

Abstract

Calculating the partition function of an Ising model is a fundamental challenge in statistical physics and machine learning, typically known to be NP-hard for general graphs. While exact solutions have long existed for planar graphs and trees, many real-world applications involve more complex, non-planar structures. This paper introduces a new family of tractable Ising models based on a structural framework called $c$-nice decomposition. By "gluing" together planar graphs and small components along shared sets of up to three vertices, the authors extend polynomial-time solvability ($O(N^{3/2})$) to a significantly broader class of graphs, including $K_5$-minor-free graphs. This approach bridges the gap between simple planar models and NP-hard general graphs, offering new tools for both exact inference and high-quality approximations.

Introduction: The Challenge of the Partition Function

The "holy grail" for Ising models is the calculation of the partition function ($Z$), a normalization constant essential for computing probabilities and marginals. Since the 1960s, efficient algorithms like the Fisher-Kasteleyn-Temperley (FKT) method have solved this for planar graphs. However, the gap between planar tractability and general NP-hardness has limited the modeling of complex systems. This research addresses how to expand the library of tractable models without incurring exponential computational costs.

Methods: $c$-nice Decomposition and the "Power of Three"

The core contribution is the $c$-nice decomposition, which breaks a large graph into a tree-like structure of components. Each component is either planar or of a fixed small size $c$.

Overview of the c-nice decomposition framework, showing the tree-like structure of components and prototypical non-planar elements.

Key Algorithmic Steps:

  1. Decomposition: The graph is partitioned into components joined at "attachment sets" (or "navels") containing at most three vertices.
  2. Dynamic Programming: The algorithm processes the component tree from leaves to root, similar to Belief Propagation.
  3. Black-Box Solvers: For planar components, the algorithm uses existing solvers (like FKT); for small components, it employs brute force.
  4. Conditioning: By fixing the states of the 1, 2, or 3 shared vertices, the components become independent. The results are then aggregated using linear equations to maintain zero-field Ising properties.

The insight that conditioning on up to three vertices preserves tractability is pivotal. It allows for much richer connectivity than previous methods restricted to one or two shared vertices.

Results and Theoretical Impact

The paper proves that $K_5$-minor-free graphs—a massive class encompassing all planar graphs and many non-planar ones—can be solved in $O(N^{3/2})$ time. Notably, these graphs can have high genus and high treewidth, metrics traditionally used to bound complexity.

Empirical Performance

Beyond theoretical proofs, the authors tested their method on square-grid Ising models with magnetic fields (an NP-hard problem). Their Decomposition-based Spanning Graphs (DSG) provided:

  • More accurate marginals than standard Planar Spanning Graph (PSG) approaches.
  • Tighter upper bounds on the true partition function.
  • Efficient exact sampling of spin configurations, crucial for Monte Carlo simulations.

Conclusion and Future Directions

This work significantly expands the boundaries of solvable statistical physics. While currently optimized for zero-field models, the framework provides a robust basis for approximating NP-hard cases with external fields. Future research may extend these techniques to "single-crossing" graphs or explore parallelization to further enhance computational speed.

Summary updated

BibTeX
@misc{likhosherstov2019new,
  author = {Valerii Likhosherstov and Yury Maximov and Michael Chertkov},
  title = {{A New Family of Tractable Ising Models}},
  year = {2019},
  eprint = {1906.06431},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1906.06431},
}
Figure