Extremely Greedy Equivalence Search
Achille Nazaret, David Blei · 2025
Read Extremely Greedy Equivalence Search by Achille Nazaret, David Blei (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-19551.txt.
Introduction
Achille Nazaret and David Blei present, in a 2025 paper, a faster and more reliable way to learn causal graphs from data. The task is to recover a directed network of causes from observations. A classic greedy method builds the graph edge by edge, but on real, limited data it can get stuck in a good-enough graph that is wrong.
Their variant favors removing edges early rather than adding them, which keeps the search from settling too soon. The theory behind the older method still holds. On simulated data with known answers, the new search recovered the right graphs more often and ran about ten times faster.
Catalog record
| CREATOR | Achille Nazaret, David Blei |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 105 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2502-19551
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Extremely Greedy Equivalence Search Achille Nazaret, David Blei Abstract 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 . 1 Introduction In the problem of causal discovery, we observe a multivariate data set x^{1:n} , where each x^{i}=(x^{i}_{1},...,x^{i}_{d}) . Our goal is to learn a d -node directed graphical model for p(x^{i}_{1},\ldots,x^{i}_{d}) , i.e., a factorization of the joint distribution. In practice, causal discovery learns an equivalence class of graphs, called a Markov equivalence class , where each graph in the class implies the same set of conditional independence statements. The goal is to find the class whose set of independence statements exactly holds in the data. The challenge to causal discovery is that the space of graphs on d nodes is prohibitively large. To this end, researchers have explored a number of ideas, including developing efficient tests for conditional independence ( Spirtes et al.,, 2000 ; Zhang et al.,, 2011 ) , restricting the space of graphs to a smaller class ( Bühlmann et al.,, 2014 ; Fang et al.,, 2023 ) , or searching efficiently the space of graphs. One of the most theoretically sound methods is greedy equivalence search (GES) ( Chickering,, 2002b ) . GES posits a proper scoring function for the graph (relative to the data) and then greedily optimizes it by inserting and deleting edges. In the limit of large data, GES enjoys theoretical guarantees of reaching the true graph. However, with finite data, GES can fail to find the solution. In particular, its performance decreases for graphs with non-trivial number of edges, e.g. more than two parents per node. And so we cannot apply GES to the kinds of large-scale problems that we regularly encounter in machine learning. To this end, researchers have proposed computationally efficient approximations ( Ramsey et al.,, 2017 ) and continuous relaxations with gradient-based optimization ( Zheng et al.,, 2018 ; Brouillard et al.,, 2020 ) . These methods can handle more variables and denser graphs, but they do not enjoy the same guarantees. In this paper, we improve on GES in two ways. First, we empirically examine the failure modes of GES and then use this analysis to propose better heuristics to explore the space of DAGs. Second, we develop superefficient algorithms for implementing the low-level graph operations that GES requires. Put together, these innovations describe extreme GES (XGES), a new algorithm for causal discovery. XGES is more reliable and scalable than GES, and without sacrificing its important theoretical guarantees. While GES’s performance degrades as the density of edges increases, XGES’s performance remains stable. We study XGES on a battery of simulations. We find that XGES outperforms GES and its variants in all scenarios, achieving significantly better accuracy and faster runtimes. Related Work. Causal discovery encompasses a wide range of methods ( Glymour et al.,, 2019 ) . Here, we focus on score-based methods, which posit a proper scoring rule, and proceed to find the sets of graphs that maximize it. The Greedy Equivalence Search (GES) algorithm maximizes it using a greedy search strategy ( Chickering,, 2002b ) . Extensions and variants of GES include OPS ( Chickering,, 2002b ) , GIES ( Hauser & Bühlmann,, 2012 ) , GDS-EEV ( Peters & Bühlmann,, 2014 ) , and ARGES ( Nandy et al.,, 2018 ) . Fast-GES (fGES) is a more efficient implementation of GES ( Ramsey et al.,, 2017 ) . But we find that it does not reproduce exactly GES’s search strategy and hurts performance (see Section 5 ). Selective GES (SGES) guarantees a polynomial worst-case complexity but has limited speed improvement in practice ( Chickering & Meek,, 2015 ) . Other works improve GES by randomly perturbing the search ( Alonso et al.,, 2018 ; Liu et al.,, 2023 ) . However, they are computationally expensive. More recently, differentiable causal discovery methods have been proposed to maximize the score using gradient-based methods ( Zheng et al.,, 2018 ; Brouillard et al.,, 2020 ; Nazaret et al.,, 2024 ) . These methods can model causal relations using neural networks, but unlike GES and XGES (proposed here), their optimization procedures have no theoretical guarantees of converging to the true graph. 2 Causal Discovery and GES We first review the causal discovery problem and the necessary details of the greedy equivalence search (GES) method. 2.1 Causal Graphical Models Causal discovery aims to identify cause-and-effect relationships between random variables \{X_{1},...,X_{d}\} . We reason about causal relationships using causal graphical models (CGM). A CGM has two components: 1. a directed acyclic graph (DAG), G^{*}=(V,E) , where a node j\in V represents variable X_{j} and an edge (j,k)\in E denotes a direct causal link from X_{j} to X_{k} , 2. conditional distributions p(X_{j}\mid X_{\operatorname{Pa}_{j}^{G^{*}}}) , defining the distribution of X_{j} given its causal parents X_{\operatorname{Pa}^{G^{*}}_{j}} . The joint distribution of the variables X_{1},...,X_{d} writes: p^{*}(X)=\prod\limits_{j\in V}p^{*}(X_{j}\mid X_{\operatorname{Pa}^{G^{*}}_{j}}). (1) The goal of causal discovery is to recover the graph G^{*} from the joint distribution p^{*} or from samples drawn from p^{*} . However, multiple CGMs with different graphs can generate the same p^{*}\!. Two important concepts address this difficulty: faithfulness and Markov equivalence ( Spirtes et al.,, 2000 ) . Faithfulness. In Equation 1 , G^{*} induces a factorization of p^{*} , which, in turn, induces independencies between variables: each X_{j} is independent of its non-descendants given its parents X_{\operatorname{Pa}^{G^{*}}_{j}} ( Pearl,, 1988 ) . Reciprocally, we say that a distribution p^{*} and a graph G^{*} are faithful if all the independencies in p^{*} are exactly those implied by G^{*} and no more. For example, H=(\{1,2\},\{1\rightarrow 2\}) and q=q(X_{1})q(X_{2}) form a valid CGM. But the independence X_{1}\perp\!\!\!\perp X_{2} present in q is not suggested by H . Rather, q is faithful to H^{\prime}=(\{1,2\},\varnothing) , which has no superfluous edges like 1\rightarrow 2 . Limiting the search to faithful graphs reduces the possible CGMs that could have generated p^{*} . But this is not enough. Markov Equivalence. Two distinct graphs can both be faithful to p^{*} if they induce the same set of independencies on p^{*} . For example, A\rightarrow B\rightarrow C and A\leftarrow B\leftarrow C impose the same set of