mlsanityData to 13 Oct 2026

Less Greedy Equivalence Search

arXiv 2506.22331 ↗First posted 27 Jun 2025cs.LG cs.AI stat.MEcited by 1

Not on the map. Why?

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.

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

Builds on

19 of 66 references.

References · 19

  1. 2018DAGs with NO TEARS: Continuous Optimization for Structure Learningcited by 748
  2. 2020On the Role of Sparsity and DAG Constraints for Learning Linear DAGscited by 189
  3. 2013Causal Inference and Causal Explanation with Background Knowledgecited by 170
  4. 2013Causal Inference in the Presence of Latent Variables and Selection Biascited by 165
  5. 2021Beware of the Simulated DAG! Causal Discovery Benchmarks May Be Easy To Gamecited by 159
  6. 2023Causal-learn: Causal Discovery in Pythoncited by 108
  7. 2017Permutation-based Causal Inference Algorithms with Interventionscited by 78
  8. 2023Causal Discovery with Language Models as Imperfect Expertscited by 63
  9. 2015A fast PC algorithm for high dimensional causal discovery with multi-core PCscited by 45
  10. 2013A Transformational Characterization of Equivalent Bayesian Network Structurescited by 41
  11. 2021The impact of prior knowledge on causal structure learningcited by 35
  12. 2023Structure Learning with Continuous Optimization: A Sober Look and Beyondcited by 35
7 more
  1. 2013Learning Bayesian Networks: A Unification for Discrete and Gaussian Domainscited by 21
  2. 2015Selective Greedy Equivalence Search: Finding Optimal Bayesian Networks Using a Polynomial Number of Score Evaluationscited by 14
  3. 2020Polynomial-Time Algorithms for Counting and Sampling Markov Equivalent DAGscited by 14
  4. 2022Characterization and Greedy Learning of Gaussian Structural Causal Models under Unknown Interventionscited by 12
  5. 2025Extremely Greedy Equivalence Searchcited by 8
  6. 2023Optimizing Data-driven Causal Discovery Using Knowledge-guided Searchcited by 5
  7. 2024Testing Causal Models with Hidden Variables in Polynomial Delay via Conditional Independenciescited by 1

Built on by

Cited by year (2026 to 13 Oct)

Citing papers per year: 2026: 1.

1 paper.

  1. 2026xWhyL: Causal Interactive Learningcited by 0