# Efficiently learning Ising models on arbitrary graphs

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

## Key facts

- Cited by 50 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Nov 2014.

## Built on by (most cited first, 30 of 50)

- [A survey on the complexity of learning quantum states](https://mlsanity.com/paper/2305.20069/) (2023)
- [A New Approach to Learning Linear Dynamical Systems](https://mlsanity.com/paper/2301.09519/) (2023)
- [Learning quantum Hamiltonians at any temperature in polynomial time](https://mlsanity.com/paper/2310.02243/) (2023)
- [Provable benefits of score matching](https://mlsanity.com/paper/2306.01993/) (2023)
- [Learning non-Gaussian graphical models via Hessian scores and triangular transport](https://mlsanity.com/paper/2101.03093/) (2021)
- [Outlier-Robust Learning of Ising Models Under Dobrushin's Condition](https://mlsanity.com/paper/2102.02171/) (2021)
- [A Unified Approach to Learning Ising Models: Beyond Independence and Bounded Width](https://mlsanity.com/paper/2311.09197/) (2023)
- [Structure learning in polynomial time: Greedy algorithms, Bregman information, and exponential families](https://mlsanity.com/paper/2110.04719/) (2021)
- [Chow-Liu++: Optimal Prediction-Centric Learning of Tree Ising Models](https://mlsanity.com/paper/2106.03969/) (2021)
- [Structure learning of Hamiltonians from real-time evolution](https://mlsanity.com/paper/2405.00082/) (2024)
- [Optimal learning of quantum Hamiltonians from high-temperature Gibbs states](https://mlsanity.com/paper/2108.04842/) (2021)
- [Bypassing the Noisy Parity Barrier: Learning Higher-Order Markov Random Fields from Dynamics](https://mlsanity.com/paper/2409.05284/) (2024)
- [Learning and Testing Latent-Tree Ising Models Efficiently](https://mlsanity.com/paper/2211.13291/) (2022)
- [Learning Hard-Constrained Models with One Sample](https://mlsanity.com/paper/2311.03332/) (2023)
- [Learning to Sample from Censored Markov Random Fields](https://mlsanity.com/paper/2101.06178/) (2021)
- [Exponential Reduction in Sample Complexity with Learning of Ising Model Dynamics](https://mlsanity.com/paper/2104.00995/) (2021)
- [Network reconstruction via the minimum description length principle](https://mlsanity.com/paper/2405.01015/) (2024)
- [Learning the Sherrington-Kirkpatrick Model Even at Low Temperature](https://mlsanity.com/paper/2411.11174/) (2024)
- [Ising Model Selection Using ℓ1-Regularized Linear Regression: A Statistical Mechanics Analysis](https://mlsanity.com/paper/2102.03988/) (2021)
- [Masked prediction tasks: a parameter identifiability view](https://mlsanity.com/paper/2202.09305/) (2022)
- [Provably efficient variational generative modeling of quantum many-body systems via quantum-probabilistic information geometry](https://mlsanity.com/paper/2206.04663/) (2022)
- [Provable learning of quantum states with graphical models](https://mlsanity.com/paper/2309.09235/) (2023)
- [Stein's method for marginals on large graphical models](https://mlsanity.com/paper/2410.11771/) (2024)
- [Learning Juntas under Markov Random Fields](https://mlsanity.com/paper/2506.00764/) (2025)
- [Learning Gaussian DAG Models without Condition Number Bounds](https://mlsanity.com/paper/2511.06164/) (2025)
- [Estimating Ising Models in Total Variation Distance](https://mlsanity.com/paper/2511.21008/) (2025)
- [Scalable network reconstruction in subquadratic time](https://mlsanity.com/paper/2401.01404/) (2024)
- [Discrete distributions are learnable from metastable samples](https://mlsanity.com/paper/2410.13800/) (2024)
- [Efficient Hamiltonian, structure and trace distance learning of Gaussian states](https://mlsanity.com/paper/2411.03163/) (2024)
- [Learning local neighborhoods of non-Gaussian graphical models: A measure transport approach](https://mlsanity.com/paper/2503.13899/) (2025)

## Abstract (arXiv)

We consider the problem of reconstructing the graph underlying an Ising model from i.i.d. samples. Over the last fifteen years this problem has been of significant interest in the statistics, machine learning, and statistical physics communities, and much of the effort has been directed towards finding algorithms with low computational cost for various restricted classes of models. Nevertheless, for learning Ising models on general graphs with p nodes of degree at most d, it is not known whether or not it is possible to improve upon the pd computation needed to exhaustively search over all possible neighborhoods for each node. In this paper we show that a simple greedy procedure allows to learn the structure of an Ising model on an arbitrary bounded-degree graph in time on the order of p2. We make no assumptions on the parameters except what is necessary for identifiability of the model, and in particular the results hold at low-temperatures as well as for highly non-uniform models. The proof rests on a new structural property of Ising models: we show that for any node there exists at least one neighbor with which it has a high mutual information. This structural property may be of independent interest.