# Greedy equivalence search for nonparametric graphical models

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 77 references that are in the map.
- First posted on arXiv 25 Jun 2024.

## Builds on (most cited first, 25 of 25)

- [Causal Discovery with Continuous Additive Noise Models](https://mlsanity.com/paper/1309.6779/) (2013)
- [Learning Bayesian Networks: The Combination of Knowledge and Statistical Data](https://mlsanity.com/paper/1302.6815/) (2013)
- [CAM: Causal additive models, high-dimensional order search and penalized regression](https://mlsanity.com/paper/1310.1533/) (2013)
- [Best Subset Selection via a Modern Optimization Lens](https://mlsanity.com/paper/1507.03133/) (2015)
- [High-dimensional learning of linear causal networks via inverse covariance estimation](https://mlsanity.com/paper/1311.3492/) (2013)
- [Structure Learning in Graphical Modeling](https://mlsanity.com/paper/1606.02359/) (2016)
- [Greedy Relaxations of the Sparsest Permutation Algorithm](https://mlsanity.com/paper/2206.05421/) (2022)
- [A Tutorial on Learning With Bayesian Networks](https://mlsanity.com/paper/2002.00269/) (2020)
- [High-dimensional consistency in score-based and hybrid structure learning](https://mlsanity.com/paper/1507.02608/) (2015)
- [Causal Structure Learning: a Combinatorial Perspective](https://mlsanity.com/paper/2206.01152/) (2022)
- [A simple measure of conditional dependence](https://mlsanity.com/paper/1910.12327/) (2019)
- [Partition MCMC for inference on acyclic digraphs](https://mlsanity.com/paper/1504.05006/) (2015)
- [On Graphical Models via Univariate Exponential Family Distributions](https://mlsanity.com/paper/1301.4183/) (2013)
- [Testing Conditional Independence of Discrete Distributions](https://mlsanity.com/paper/1711.11560/) (2017)
- [The Recovery of Causal Poly-Trees from Statistical Data](https://mlsanity.com/paper/1304.2736/) (2013)
- [Selective Greedy Equivalence Search: Finding Optimal Bayesian Networks Using a Polynomial Number of Score Evaluations](https://mlsanity.com/paper/1506.02113/) (2015)
- [Minimal I-MAP MCMC for Scalable Structure Discovery in Causal DAG Models](https://mlsanity.com/paper/1803.05554/) (2018)
- [Hypothesis Testing for High-Dimensional Multinomials: A Selective Review](https://mlsanity.com/paper/1712.06120/) (2017)
- [Variable Selection with ABC Bayesian Forests](https://mlsanity.com/paper/1806.02304/) (2018)
- [Bayesian model selection consistency and oracle inequality with intractable marginal likelihood](https://mlsanity.com/paper/1701.00311/) (2017)
- [Structure Learning with Adaptive Random Neighborhood Informed MCMC](https://mlsanity.com/paper/2311.00599/) (2023)
- [Kutato: An Entropy-Driven System for Construction of Probabilistic Expert Systems from Databases](https://mlsanity.com/paper/1304.1088/) (2013)
- [Reframed GES with a Neural Conditional Dependence Measure](https://mlsanity.com/paper/2206.08531/) (2022)
- [Causal structure learning with momentum: Sampling distributions over Markov Equivalence Classes of DAGs](https://mlsanity.com/paper/2310.05655/) (2023)
- [On Testing Marginal versus Conditional Independence](https://mlsanity.com/paper/1906.01850/) (2019)

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

- [Causal Explainability of Machine Learning in Heart Failure Prediction from Electronic Health Records](https://mlsanity.com/paper/2506.03068/) (2025)
- [Differentiable Structure Learning and Causal Discovery for General Binary Data](https://mlsanity.com/paper/2509.21658/) (2025)

## Abstract (arXiv)

One of the hallmark achievements of the theory of graphical models and Bayesian model selection is the celebrated greedy equivalence search (GES) algorithm due to Chickering and Meek. GES is known to consistently estimate the structure of directed acyclic graph (DAG) models in various special cases including Gaussian and discrete models, which are in particular curved exponential families. A general theory that covers general nonparametric DAG models, however, is missing. Here, we establish the consistency of greedy equivalence search for general families of DAG models that satisfy smoothness conditions on the Markov factorization, and hence may not be curved exponential families, or even parametric. The proof leverages recent advances in nonparametric Bayes to construct a test for comparing misspecified DAG models that avoids arguments based on the Laplace approximation. Nonetheless, when the Laplace approximation is valid and a consistent scoring function exists, we recover the classical result. As a result, we obtain a general consistency theorem for GES applied to general DAG models.