A million variables and more: the Fast Greedy Equivalence Search algorithm for learning high-dimensional graphical causal models, with an application to functional magnetic resonance images

By J. Ramsey, Madelyn Glymour, Ruben Sanchez-Romero, Clark Glymour. 2016

420 citations recorded by the source corpus.

We describe two modifications that parallelize and reorganize caching in the well-known Greedy Equivalence Search algorithm for discovering directed acyclic graphs on random variables from sample values. We apply one of these modifications, the Fast Greedy Equivalence Search (fGES) assuming faithfulness, to an i.i.d. sample of 1000 units to recover with high precision and good recall an average degree 2 directed acyclic graph with one million Gaussian variables. We describe a modification of the algorithm to rapidly find the Markov Blanket of any variable in a high dimensional system. Using 51,000 voxels that parcellate an entire human cortex, we apply the fGES algorithm to blood oxygenation level-dependent time series obtained from resting state fMRI.

Subfields: Artificial Intelligence, Cognitive Neuroscience, Graph Learning, Causal Inference & Discovery

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Cognitive Neuroscience

In Graph Learning

In Causal Inference & Discovery

Citations in the corpus

Gradient-Based Neural DAG Learning (2019, background): “(2019) provides empirical comparisons to linear approaches, namely NOTEARS and FGS (a faster extension of GES) (Ramsey et al., 2017), comparisons to greedy approaches supporting nonlinear relationships such as CAM and GSF are missing.”
DAGs with NO TEARS: Continuous Optimization for Structure Learning (2018, methodology): “…on approximate algorithms based on order search (Teyssier and Koller, 2005; Schmidt et al., 2007; Scanagatta et al., 2015, 2016), greedy search (Heckerman et al., 1995; Chickering, 2003; Ramsey et al., 2016), and coordinate descent (Fu and Zhou, 2013; Aragam and Zhou, 2015; Gu et al., 2018).”
Causal Discovery with Reinforcement Learning (2019, methodology): “Since the fast greedy search (FGS) implementation3 [19] for GES has been reported to outperform the PC algorithm and other techniques such as hill-climbing and MMHC [11, 34], we will only report the results of FGS, NOTEARS, and ICA-LiNGAM.”
DAG-GNN: DAG Structure Learning with Graph Neural Networks (2019, methodology): “In Table 2, we compare DAG-GNN with DAG-NOTEARS as well as FSG, the fast greedy search method proposed by Ramsey et al. (2017), against the ground truth offered by Sachs et al. (2005).”
A Survey of Learning Causality with Data: Problems and Methods (2018, methodology): “Therefore, heuristics such as Greedy Equivalence Search (GES) [26] and its extension, Fast GES (FGES) [112] are proposed to reach a locally optimal solution.”
A Survey of Learning Causality with Data (2018, methodology): “FGES-MB modifies the first stage of GES by only adding edges found by two-hop markov blanket search on each variable [123].”
Structural Agnostic Modeling: Adversarial Learning of Causal Graphs (2018, background): “…assumption and handle hidden confounders, e.g. by introducing statistical dependencies between the noise variables attached to different variables (Rothenhäusler et al., 2015), or creating shared noise variables (Janzing and Schölkopf, 2018) or proxies of confounders (Wang and Blei, 2021).”
Learning Sparse Nonparametric DAGs (2019, methodology): “To further investigate the efficacy of these additional steps, we applied both preliminary neighborhood selection and edge pruning to NOTEARS-MLP and NOTEARS-Sob on additive GP and GP settings, denoted as NOTEARS-MLP++ and NOTEARS-Sob++. Noticeably, the output from PNS simply translates to a set of ”
Communication-Avoiding Optimization Methods for Distributed Massive-Scale Sparse Inverse Covariance Estimation (2017, background): “Lastly, the works of [41, 42] focus on scalable methods for structure recovery from fMRI data, rather than for the broader problem of sparse inverse covariance estimation.”
Advancing functional connectivity research from association to causation (2019, methodology): “…the following approaches available from the Center for Causal Discovery (http://www.ccd.pitt.edu) for making causal inferences taking into account both confounders and colliders: fGES, IMaGES 2,96 (also available at https://cran.r-proiect.org/web/packages/IMaGES), Two-step 97 , and FASK 97 .”
Learning Directed Acyclic Graphs with Penalized Neighbourhood Regression (2015, methodology): “It follows that for each π ∈ S p , supp( β j ( π )) ⊂ S j ( π ) for each j = 1 , . . . , p . e Recall the objective function deﬁned in (1.3) and the associated estimator (1.5). e The spaces D p [ π ] help give us some intuition into what is going on with the estimator B : Suppose we had oracle knowl”