# Structure learning of antiferromagnetic Ising models

arXiv: https://arxiv.org/abs/1412.1443 · HTML: https://mlsanity.com/paper/1412.1443/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Dec 2014.

## Built on by (most cited first, 8 of 8)

- [Provable benefits of score matching](https://mlsanity.com/paper/2306.01993/) (2023)
- [Outlier-Robust Learning of Ising Models Under Dobrushin's Condition](https://mlsanity.com/paper/2102.02171/) (2021)
- [Bypassing the Noisy Parity Barrier: Learning Higher-Order Markov Random Fields from Dynamics](https://mlsanity.com/paper/2409.05284/) (2024)
- [Learning CNF formulas from uniform random solutions in the local lemma regime](https://mlsanity.com/paper/2511.02487/) (2025)
- [Robust Learning of Fixed-Structure Bayesian Networks in Nearly-Linear Time](https://mlsanity.com/paper/2105.05555/) (2021)
- [Recoverability Landscape of Tree Structured Markov Random Fields under Symmetric Noise](https://mlsanity.com/paper/2102.08554/) (2021)
- [Interaction Screening and Pseudolikelihood Approaches for Tensor Learning in Ising Models](https://mlsanity.com/paper/2310.13232/) (2023)
- [One-Shot Learning for k-SAT](https://mlsanity.com/paper/2502.07135/) (2025)

## Abstract (arXiv)

In this paper we investigate the computational complexity of learning the graph structure underlying a discrete undirected graphical model from i.i.d. samples. We first observe that the notoriously difficult problem of learning parities with noise can be captured as a special case of learning graphical models. This leads to an unconditional computational lower bound of Omega (pd/2) for learning general graphical models on p nodes of maximum degree d, for the class of so-called statistical algorithms recently introduced by Feldman et al (2013). The lower bound suggests that the O(pd) runtime required to exhaustively search over neighborhoods cannot be significantly improved without restricting the class of models. Aside from structural assumptions on the graph such as it being a tree, hypertree, tree-like, etc., many recent papers on structure learning assume that the model has the correlation decay property. Indeed, focusing on ferromagnetic Ising models, Bento and Montanari (2009) showed that all known low-complexity algorithms fail to learn simple graphs when the interaction strength exceeds a number related to the correlation decay threshold. Our second set of results gives a class of repelling (antiferromagnetic) models that have the opposite behavior: very strong interaction allows efficient learning in time O(p2). We provide an algorithm whose performance interpolates between O(p2) and O(pd+2) depending on the strength of the repulsion.