Lune

NeurIPS2025Top-tier venue

Less Greedy Equivalence Search

Adiba Ejaz, Elias Bareinboim

Abstract

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 1010-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.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

Questions to start from

Lune can draw on

the full paper · related work

Get the answer

Free to start. No credit card required.

Lineage

  • Causal discovery from observational and interventional data across multiple environments cites A Calculus for Stochastic Interventions: Causal Effect Identification and Surrogate Experiments
  • Causal discovery from observational and interventional data across multiple environments cites Causal Discovery from Soft Interventions with Unknown Targets: Characterization and Learning
  • Beware of the Simulated DAG! Causal Discovery Benchmarks May Be Easy to Game cites On the Role of Sparsity and DAG Constraints for Learning Linear DAGs
Builds onCited byLeft to right by year; the more cited, the higher.

Builds on8

  1. On the Role of Sparsity and DAG Constraints for Learning Linear DAGsIgnavier Ng, AmirEmad Ghassami, Kun ZhangNeurIPS 2020 · 306 citations
  2. Beware of the Simulated DAG! Causal Discovery Benchmarks May Be Easy to GameAlexander G. Reisach, Christof Seiler, Sebastian WeichwaldNeurIPS 2021 · 213 citations
  3. Causal Discovery from Soft Interventions with Unknown Targets: Characterization and LearningAmin Jaber, Murat Kocaoglu, Karthikeyan Shanmugam, Elias BareinboimNeurIPS 2020 · 136 citations
  4. A Calculus for Stochastic Interventions: Causal Effect Identification and Surrogate ExperimentsJuan D. Correa, Elias BareinboimAAAI 2020 · 90 citations
  5. Causal discovery from observational and interventional data across multiple environmentsAdam Li, Amin Jaber, Elias BareinboimNeurIPS 2023 · 41 citations

Related papers

  1. Score-based Greedy Search for Structure Identification of Partially Observed Causal ModelsXinshuai Dong, Ignavier Ng, Haoyue Dai, Jiaqi Sun et al.ICLR 2026 · 1 citation
  2. Score-Based Causal Discovery of Latent Variable Causal ModelsIgnavier Ng, Xinshuai Dong, Haoyue Dai, Biwei Huang et al.ICML 2024 · 18 citations
  3. On Causal Discovery in the Presence of Deterministic RelationsLoka Li, Haoyue Dai, Hanin Al Ghothani, Biwei Huang et al.NeurIPS 2024 · 10 citations
  4. New metrics and search algorithms for weighted causal DAGsDavin Choo, Kirankumar ShiragurICML 2023 · 1 citation
  5. Efficient Neural Causal Discovery without Acyclicity ConstraintsPhillip Lippe, Taco Cohen, Efstratios GavvesICLR 2022 · 95 citations
Dusk over the sea between two cliffs drawn in fine vertical lines