# Less Greedy Equivalence Search

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 66 references that are in the map.
- First posted on arXiv 27 Jun 2025.

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

- [DAGs with NO TEARS: Continuous Optimization for Structure Learning](https://mlsanity.com/paper/1803.01422/) (2018)
- [On the Role of Sparsity and DAG Constraints for Learning Linear DAGs](https://mlsanity.com/paper/2006.10201/) (2020)
- [Causal Inference and Causal Explanation with Background Knowledge](https://mlsanity.com/paper/1302.4972/) (2013)
- [Causal Inference in the Presence of Latent Variables and Selection Bias](https://mlsanity.com/paper/1302.4983/) (2013)
- [Beware of the Simulated DAG! Causal Discovery Benchmarks May Be Easy To Game](https://mlsanity.com/paper/2102.13647/) (2021)
- [Causal-learn: Causal Discovery in Python](https://mlsanity.com/paper/2307.16405/) (2023)
- [Permutation-based Causal Inference Algorithms with Interventions](https://mlsanity.com/paper/1705.10220/) (2017)
- [Causal Discovery with Language Models as Imperfect Experts](https://mlsanity.com/paper/2307.02390/) (2023)
- [A fast PC algorithm for high dimensional causal discovery with multi-core PCs](https://mlsanity.com/paper/1502.02454/) (2015)
- [A Transformational Characterization of Equivalent Bayesian Network Structures](https://mlsanity.com/paper/1302.4938/) (2013)
- [Structure Learning with Continuous Optimization: A Sober Look and Beyond](https://mlsanity.com/paper/2304.02146/) (2023)
- [The impact of prior knowledge on causal structure learning](https://mlsanity.com/paper/2102.00473/) (2021)
- [Learning Bayesian Networks: A Unification for Discrete and Gaussian Domains](https://mlsanity.com/paper/1302.4957/) (2013)
- [Selective Greedy Equivalence Search: Finding Optimal Bayesian Networks Using a Polynomial Number of Score Evaluations](https://mlsanity.com/paper/1506.02113/) (2015)
- [Polynomial-Time Algorithms for Counting and Sampling Markov Equivalent DAGs](https://mlsanity.com/paper/2012.09679/) (2020)
- [Characterization and Greedy Learning of Gaussian Structural Causal Models under Unknown Interventions](https://mlsanity.com/paper/2211.14897/) (2022)
- [Extremely Greedy Equivalence Search](https://mlsanity.com/paper/2502.19551/) (2025)
- [Optimizing Data-driven Causal Discovery Using Knowledge-guided Search](https://mlsanity.com/paper/2304.05493/) (2023)
- [Testing Causal Models with Hidden Variables in Polynomial Delay via Conditional Independencies](https://mlsanity.com/paper/2409.14593/) (2024)

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

- [xWhyL: Causal Interactive Learning](https://mlsanity.com/paper/2609.26037/) (2026)

## Abstract (arXiv)

Greedy Equivalence Search (GES) is a classic score-based algorithm for causal discovery from observational data. In the sample limit, it recovers the Markov equivalence class of graphs that describe the data. Still, it faces two challenges in practice: computational cost and finite-sample accuracy. In this paper, we develop Less Greedy Equivalence Search (LGES), a variant of GES that retains its theoretical guarantees while partially addressing these limitations. LGES modifies the greedy step; rather than always applying the highest-scoring insertion, it avoids edge insertions between variables for which the score implies some conditional independence. This more targeted search yields up to a (10)-fold speed-up and a substantial reduction in structural error relative to GES. Moreover, LGES can guide the search using prior knowledge, and can correct this knowledge when contradicted by data. Finally, LGES can use interventional data to refine the learned observational equivalence class. We prove that LGES recovers the true equivalence class in the sample limit, even with misspecified knowledge. Experiments demonstrate that LGES outperforms GES and other baselines in speed, accuracy, and robustness to misspecified knowledge. Our code is available at https://github.com/CausalAILab/lges.