mlsanityData to 14 Oct 2026

Extremely Greedy Equivalence Search

arXiv 2502.19551 ↗First posted 26 Feb 2025cs.LG stat.MLcited by 8

Not on the map. Why?

Abstract (arXiv)

The goal of causal discovery is to learn a directed acyclic graph from data. One of the most well-known methods for this problem is Greedy Equivalence Search (GES). GES searches for the graph by incrementally and greedily adding or removing edges to maximize a model selection criterion. It has strong theoretical guarantees on infinite data but can fail in practice on finite data. In this paper, we first identify some of the causes of GES's failure, finding that it can get blocked in local optima, especially in denser graphs. We then propose eXtremely Greedy Equivalent Search (XGES), which involves a new heuristic to improve the search strategy of GES while retaining its theoretical guarantees. In particular, XGES favors deleting edges early in the search over inserting edges, which reduces the possibility of the search ending in local optima. A further contribution of this work is an efficient algorithmic formulation of XGES (and GES). We benchmark XGES on simulated datasets with known ground truth. We find that XGES consistently outperforms GES in recovering the correct graphs, and it is 10 times faster. XGES implementations in Python and C++ are available at https://github.com/ANazaret/XGES.

Key facts. Cited by 8 papers in the map (data through 14 Oct 2026). Builds on 11 of its 27 references that are in the map. First posted on arXiv 26 Feb 2025.

Builds on

11 of 27 references.

References · 11

  1. 2018DAGs with NO TEARS: Continuous Optimization for Structure Learningcited by 752
  2. 2013Causal Discovery with Continuous Additive Noise Modelscited by 255
  3. 2020Differentiable Causal Discovery from Interventional Datacited by 218
  4. 2013CAM: Causal additive models, high-dimensional order search and penalized regressioncited by 178
  5. 2013Causal Inference and Causal Explanation with Background Knowledgecited by 170
  6. 2013Learning Equivalence Classes of Bayesian Networks Structurescited by 77
  7. 2015High-dimensional consistency in score-based and hybrid structure learningcited by 46
  8. 2023Stable Differentiable Causal Discoverycited by 31
  9. 2020On Low Rank Directed Acyclic Graphs and Causal Structure Learningcited by 23
  10. 2015Selective Greedy Equivalence Search: Finding Optimal Bayesian Networks Using a Polynomial Number of Score Evaluationscited by 14
  11. 2022On the pitfalls of Gaussian likelihood scoring for causal discoverycited by 7

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 4; 2026: 4.

8 papers.

  1. 2025Causal-Copilot: An Autonomous Causal Analysis Agentcited by 15
  2. 2025Embracing Discrete Search: A Reasonable Approach to Causal Structure Learningcited by 4
  3. 2026FoundCause: Causal Discovery with Latent Confounders from Observational Datacited by 3
  4. 2025Less Greedy Equivalence Searchcited by 1
  5. 2025Practical Causal Evaluation Metrics for Biological Networkscited by 0
  6. 2026ORCA: An End-to-End Interactive Copilot for Optimized Root Cause Analysiscited by 0
  7. 2026StableRCA: Robust Graph-Agnostic Mechanism-Level Root Cause Analysiscited by 0
  8. 2026xWhyL: Causal Interactive Learningcited by 0