Research map / Probabilistic and scientific modeling / Causal discovery
Less Greedy Equivalence Search
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes Less Greedy Equivalence Search (LGES), a GES variant whose insertion step avoids edges implied non-adjacent by a score-decreasing insert, plus a score-based I-Orient procedure for refining observational MECs with interventional data.
Problem
Greedy Equivalence Search for causal discovery is computationally costly and inaccurate in finite samples, with excess adjacencies from greedy insertions; it also lacks principled ways to use prior knowledge and interventional data while staying asymptotically correct.
Approach
Generalize GES to allow applying any score-increasing operator rather than the highest-scoring one, and use score comparisons to skip insertions between variable pairs for which a score-decreasing insert reveals conditional independence (ConservativeInsert and SafeInsert); also orient undirected edges using marginal-independence tests in interventional data via local consistency.
Key results
- LGES (Conservative) is up to 2x more accurate than GES in SHD, e.g. about 30 incorrect edges on average for 150-variable graphs with 300 edges in expectation.
- LGES variants are up to 10x faster than GES on synthetic Erdős–Rényi graphs.
- LGIES (Conservative) is up to 10x faster and up to 1.5x more accurate than GIES in the interventional setting.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| replace highest-scoring greedy insertion with ConservativeInsert | GES · ER graphs, observational data | structural error: up to 2 times more accurate | Helped |
| replace highest-scoring greedy insertion with ConservativeInsert | GES · ER graphs, observational data | runtime: an order of magnitude faster | Helped |
| use ConservativeInsert instead of SafeInsert (ablation) | LGES · ER graphs, observational data | structural error | Helped |
| use ConservativeInsert instead of SafeInsert (ablation) | LGES · ER graphs, observational data | runtime | No clear effect |
| add forced edge deletions and search restarts (ablation) | LGES (Conservative) · ER graphs, observational data | structural error | Helped |
| omit forced edge deletions and search restarts (ablation) | LGES+ (Conservative) · ER graphs, observational data | runtime | Helped |
| add less-greedy insertion (ablation) | GES, XGES-0, and XGES · ER graphs, observational data | structural error | Helped |
| prioritize required-edge insertions instead of initializing from required prior edges (ablation) | LGES · ER2, 50 variables, n=10^3; majority-incorrect prior knowledge | structural error | Helped |
| prioritize insertions using mostly accurate prior knowledge (ablation) | LGES · ER2, 50 variables, n=10^3; prior correctness fc ≥ 0.75 | structural error | Helped |
| initialize from mostly accurate prior knowledge (ablation) | LGES · ER2, 50 variables, n=10^3; prior correctness fc ≥ 0.75 | structural error | Helped |
| provide prior knowledge with fc ≥ 0.5 (ablation) | LGES with priority insertion · ER2, 50 variables, n=10^3 | runtime | Helped |
| use less-greedy insertion in GIES (ablation) | GIES · ER-{2,3} graphs, observational and interventional data | structural error: up to 1.5× more accurate | Helped |
Surprising findings
- Choosing the highest-scoring insertion is not always best: in the example, the highest-scoring DAG was the one closer to the truth only 96% of the time, and the other insertion was highest-scoring 4% of the time, so greedy choice can introduce excess adjacencies.
Limitations
- Only asymptotic correctness is proven for LGES with SafeInsert; ConservativeInsert soundness remains open, though it is empirically more accurate.
- Assumes causal sufficiency (Markovian setting), faithfulness, and decomposable, consistent, score-equivalent scores; linear-Gaussian BIC used with continuous data.
- LGES (Safe) with I-Orient is only slightly less accurate than GIES on ER-2 graphs, and I-Orient uses only observational data for the observational MEC.
Experimental setup
Datasets: synthetic Erdős–Rényi linear-Gaussian graphs (sempler)
Metrics: structural Hamming distance precision recall F1 runtime
Baselines: GES XGES-0 XGES PC NoTears GIES
Builds on: Greedy Equivalence Search GIES XGES FGES PC algorithm
Closest papers by meaning
- Score-based Greedy Search for Structure Identification of Partially Observed Linear Causal Models (ICLR 2026 · similarity 0.92)
- On Causal Discovery in the Presence of Deterministic Relations (NeurIPS 2024 · similarity 0.90)
- Assumption violations in causal discovery and the robustness of score matching (NeurIPS 2023 · similarity 0.89)
- Foundations of Testing for Finite-Sample Causal Discovery (ICML 2024 · similarity 0.87)
- Hybrid Top-Down Global Causal Discovery with Local Search for Linear and Nonlinear Additive Noise Models (NeurIPS 2024 · similarity 0.87)
- CausalTab: Pretraining Across Causal Environments for Tabular Causal Discovery (NeurIPS 2026 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.