Extremely Greedy Equivalence Search
Authors:
Preprint
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.Keywords
All Related Versions
This publication has 11 references indexed in Scilit:
- Improving greedy local search methods by switching the search spaceApplied Intelligence, 2023
- On Low-Rank Directed Acyclic Graphs and Causal Structure LearningIEEE Transactions on Neural Networks and Learning Systems, 2023
- On the pitfalls of Gaussian likelihood scoring for causal discoveryJournal of Causal Inference, 2023
- Equivalence and Synthesis of Causal Models2022
- seaborn: statistical data visualizationJournal of Open Source Software, 2021
- High-dimensional consistency in score-based and hybrid structure learningThe Annals of Statistics, 2018
- On the use of local search heuristics to improve GES-based Bayesian network learningApplied Soft Computing, 2018
- CAM: Causal additive models, high-dimensional order search and penalized regressionThe Annals of Statistics, 2014
- Identifiability of Gaussian structural equation models with equal error variancesBiometrika, 2013
- On the Choice of a Model to Fit Data from an Exponential FamilyThe Annals of Statistics, 1988