# Efficient Learning of Discrete Graphical Models

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

## Key facts

- Cited by 21 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Feb 2019.

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

- [A Unified Approach to Learning Ising Models: Beyond Independence and Bounded Width](https://mlsanity.com/paper/2311.09197/) (2023)
- [A Computationally Efficient Method for Learning Exponential Family Distributions](https://mlsanity.com/paper/2110.15397/) (2021)
- [On counterfactual inference with unobserved confounding](https://mlsanity.com/paper/2211.08209/) (2022)
- [Learning and Testing Latent-Tree Ising Models Efficiently](https://mlsanity.com/paper/2211.13291/) (2022)
- [Learning Continuous Exponential Families Beyond Gaussian](https://mlsanity.com/paper/2102.09198/) (2021)
- [Exponential Reduction in Sample Complexity with Learning of Ising Model Dynamics](https://mlsanity.com/paper/2104.00995/) (2021)
- [Learning the Sherrington-Kirkpatrick Model Even at Low Temperature](https://mlsanity.com/paper/2411.11174/) (2024)
- [Learning Gaussian DAG Models without Condition Number Bounds](https://mlsanity.com/paper/2511.06164/) (2025)
- [Learning Energy-Based Representations of Quantum Many-Body States](https://mlsanity.com/paper/2304.04058/) (2023)
- [On Computationally Efficient Learning of Exponential Family Distributions](https://mlsanity.com/paper/2309.06413/) (2023)
- [A Markov Random Field Multi-Modal Variational AutoEncoder](https://mlsanity.com/paper/2408.09576/) (2024)
- [A Unified View on Learning Unnormalized Distributions via Noise-Contrastive Estimation](https://mlsanity.com/paper/2409.18209/) (2024)
- [Discrete distributions are learnable from metastable samples](https://mlsanity.com/paper/2410.13800/) (2024)
- [Multi-Component VAE with Gaussian Markov Random Field](https://mlsanity.com/paper/2507.12165/) (2025)
- [Fair Inference for Discrete Latent Variable Models](https://mlsanity.com/paper/2209.07044/) (2022)
- [Scientific Data Compression and Super-Resolution Sampling](https://mlsanity.com/paper/2511.13675/) (2025)
- [Symmetric Linear Dynamical Systems are Learnable from Few Observations](https://mlsanity.com/paper/2512.05337/) (2025)
- [Computationally sufficient statistics for Ising models](https://mlsanity.com/paper/2602.12449/) (2026)
- [Selecting Optimal Variable Order in Autoregressive Ising Models](https://mlsanity.com/paper/2602.20394/) (2026)
- [Finite Sample Bounds for Learning with Score Matching](https://mlsanity.com/paper/2605.14168/) (2026)
- [Causal Inference with Unobserved Confounding: A Mixture Learning Perspective](https://mlsanity.com/paper/2609.23219/) (2026)

## Abstract (arXiv)

Graphical models are useful tools for describing structured high-dimensional probability distributions. Development of efficient algorithms for learning graphical models with least amount of data remains an active research topic. Reconstruction of graphical models that describe the statistics of discrete variables is a particularly challenging problem, for which the maximum likelihood approach is intractable. In this work, we provide the first sample-efficient method based on the Interaction Screening framework that allows one to provably learn fully general discrete factor models with node-specific discrete alphabets and multi-body interactions, specified in an arbitrary basis. We identify a single condition related to model parametrization that leads to rigorous guarantees on the recovery of model structure and parameters in any error norm, and is readily verifiable for a large class of models. Importantly, our bounds make explicit distinction between parameters that are proper to the model and priors used as an input to the algorithm. Finally, we show that the Interaction Screening framework includes all models previously considered in the literature as special cases, and for which our analysis shows a systematic improvement in sample complexity.