mlsanityData to 14 Oct 2026

Efficiently learning Ising models on arbitrary graphs

arXiv 1411.6156 ↗First posted 22 Nov 2014cs.LG cs.IT math.ITcited by 50

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 12; 2022: 3; 2023: 9; 2024: 11; 2025: 12; 2026: 3.

50 papers.

Sort:

  1. 2023A survey on the complexity of learning quantum statescited by 32
  2. 2023A New Approach to Learning Linear Dynamical Systemscited by 23
  3. 2023Learning quantum Hamiltonians at any temperature in polynomial timecited by 23
  4. 2023Provable benefits of score matchingcited by 18
  5. 2021Learning non-Gaussian graphical models via Hessian scores and triangular transportcited by 16
  6. 2021Outlier-Robust Learning of Ising Models Under Dobrushin's Conditioncited by 14
  7. 2023A Unified Approach to Learning Ising Models: Beyond Independence and Bounded Widthcited by 14
  8. 2021Structure learning in polynomial time: Greedy algorithms, Bregman information, and exponential familiescited by 11
  9. 2021Chow-Liu++: Optimal Prediction-Centric Learning of Tree Ising Modelscited by 9
  10. 2024Structure learning of Hamiltonians from real-time evolutioncited by 9
  11. 2021Optimal learning of quantum Hamiltonians from high-temperature Gibbs statescited by 8
  12. 2024Bypassing the Noisy Parity Barrier: Learning Higher-Order Markov Random Fields from Dynamicscited by 8
38 more
  1. 2022Learning and Testing Latent-Tree Ising Models Efficientlycited by 7
  2. 2023Learning Hard-Constrained Models with One Samplecited by 7
  3. 2021Learning to Sample from Censored Markov Random Fieldscited by 6
  4. 2021Exponential Reduction in Sample Complexity with Learning of Ising Model Dynamicscited by 6
  5. 2024Network reconstruction via the minimum description length principlecited by 5
  6. 2024Learning the Sherrington-Kirkpatrick Model Even at Low Temperaturecited by 5
  7. 2021Ising Model Selection Using ℓ1-Regularized Linear Regression: A Statistical Mechanics Analysiscited by 4
  8. 2022Masked prediction tasks: a parameter identifiability viewcited by 4
  9. 2022Provably efficient variational generative modeling of quantum many-body systems via quantum-probabilistic information geometrycited by 3
  10. 2023Provable learning of quantum states with graphical modelscited by 3
  11. 2024Stein's method for marginals on large graphical modelscited by 3
  12. 2025Learning Juntas under Markov Random Fieldscited by 3
  13. 2025Learning Gaussian DAG Models without Condition Number Boundscited by 3
  14. 2025Estimating Ising Models in Total Variation Distancecited by 3
  15. 2024Scalable network reconstruction in subquadratic timecited by 2
  16. 2024Discrete distributions are learnable from metastable samplescited by 2
  17. 2024Efficient Hamiltonian, structure and trace distance learning of Gaussian statescited by 2
  18. 2025Learning local neighborhoods of non-Gaussian graphical models: A measure transport approachcited by 2
  19. 2025Learning CNF formulas from uniform random solutions in the local lemma regimecited by 2
  20. 2026A Blueprint for Equilibrium-Based Differentiable Continuous-Variable Thermodynamic Computingcited by 2
  21. 2021Robust Learning of Fixed-Structure Bayesian Networks in Nearly-Linear Timecited by 1
  22. 2021On Model Selection Consistency of Lasso for High-Dimensional Ising Modelscited by 1
  23. 2025Learning the Inverse Temperature of Ising Models under Hard Constraints using One Samplecited by 1
  24. 2026Learning mathsfAC0 under Locally Sampleable Graphical Modelscited by 1
  25. 2021Recoverability Landscape of Tree Structured Markov Random Fields under Symmetric Noisecited by 0
  26. 2021Learned Optimizers for Analytic Continuationcited by 0
  27. 2023Learning Networks from Gaussian Graphical Models and Gaussian Free Fieldscited by 0
  28. 2023Interaction Screening and Pseudolikelihood Approaches for Tensor Learning in Ising Modelscited by 0
  29. 2024Polynomial-time derivation of optimal k-tree topology from Markov networkscited by 0
  30. 2024Quantum Maximum Entropy Inference and Hamiltonian Learningcited by 0
  31. 2024Efficient Sample-optimal Learning of Gaussian Tree Models via Sample-optimal Testing of Gaussian Mutual Informationcited by 0
  32. 2025One-Shot Learning for k-SATcited by 0
  33. 2025Robust Learnability of Sample-Compressible Distributions under Noisy or Adversarial Perturbationscited by 0
  34. 2025Learn to Vaccinate: Combining Structure Learning and Effective Vaccination for Epidemic and Outbreak Controlcited by 0
  35. 2025Optimal structure learning and conditional independence testingcited by 0
  36. 2025On approximating the f-divergence between two Ising modelscited by 0
  37. 2025Scientific Data Compression and Super-Resolution Samplingcited by 0
  38. 2026Computationally sufficient statistics for Ising modelscited by 0