Learning high-dimensional directed acyclic graphs with latent and selection variables

By Diego Colombo, Marloes H. Maathuis, Markus Kalisch, Thomas S. Richardson. 2011

534 citations recorded by the source corpus.

We consider the problem of learning causal information between random variables in directed acyclic graphs (DAGs) when allowing arbitrarily many latent and selection variables. The FCI (Fast Causal Inference) algorithm has been explicitly designed to infer conditional independence and causal information in such settings. However, FCI is computationally infeasible for large graphs. We therefore propose the new RFCI algorithm, which is much faster than FCI. In some situations the output of RFCI is slightly less informative, in particular with respect to conditional independence information. However, we prove that any causal information in the output of RFCI is correct in the asymptotic limit. We also define a class of graphs on which the outputs of FCI and RFCI are identical. We prove consistency of FCI and RFCI in sparse high-dimensional settings, and demonstrate in simulations that the estimation performances of the algorithms are very similar. All software is implemented in the R-package pcalg.

Subfields: Artificial Intelligence, Statistics and Probability

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 Statistics and Probability

Citations in the corpus

Causal Generative Neural Networks (2017, methodology): “We compare CGNN to the RFCI algorithm (Gaussian or HSIC conditional independence tests) [Colombo et al. , 2012], which is a modiﬁcation of the PC algorithm that accounts for hidden variables.”
Invariant Causal Prediction for Nonlinear Models (2017, methodology): “ The output of FCI is a partial ancestral graph (PAG), i.e. it estimates the Markov equivalence class of the underlying maximal ancestral graph (MAG). Faster versions, RFCI and FCI+, were proposed by Colombo et al. (2012) and Claassen et al. (2013), respectively. The PC, FCI, RFCI and FCI+ algorithm”
CAM: Causal Additive Models, high-dimensional order search and penalized regression (2013, background): “Finally, it would be very interesting to extend (sparse) permutation search to (possibly nonidentifiable) models with hidden variables [7, 11, 23, 34] or with graph structures allowing for cycles [19, 20, 30, 33].”
Order-independent constraint-based causal structure learning (2012, methodology): “The grey line labelled as RG represents the random guessing. stable plus stability selection (with or without permuted variable orderings) produces the best ﬁt over all results. and RFCI-algorithms remain valid for their modiﬁcations under the same conditions.”
Structural Intervention Distance (SID) for Evaluating Causal Graphs (2013, background): “, 2000) and its successors (Colombo et al., 2012; Claassen et al., 2013) output an equivalence class of MAGs that are called partial ancestral graphs (PAGs) (Richardson and Spirtes, 2002).”
Causal Structure Learning (2017, methodology): “Colombo et al. (2012) proved high-dimensional consistency of FCI and RFCI.”
Comparison of Strategies for Scalable Causal Discovery of Latent Variable Models from Mixed Data (2018, methodology): “Really Fast Causal Inference (RFCI) is a modification of FCI that uses fewer independence tests than FCI to achieve a significant speedup at the cost of reduced information in the final output graph [5].”
Review of Causal Discovery Methods Based on Graphical Models (2019, methodology): “As with PC there are variants of FCI, mostly designed to speed up the algorithm at the cost of reduced information (e.g., see the RFCI algorithm Colombo et al., 2012).”
Differentiable Causal Discovery Under Latent Interventions (2022, background): “There are many works that do causal discovery with latent confounders (Spirtes et al., 1993; Colombo et al., 2012; Claassen et al., 2013; Ogarrio et al., 2016).”
Causal Learning for Partially Observed Stochastic Dynamical Systems (2018, background): “candidate separator sets may be chosen in more-or-less efficient ways, but we will not discuss this aspect of the algorithm (Colombo et al., 2012; Claassen et al., 2013).”
A Survey of Learning Causality with Data (2018, methodology): “e tests are proposed to cover other families of distributions [45, 124, 136, 164]. To take unobserved confounders into consideration, algorithms such as FCI (fast causal inference) and its extensions [31, 145] are proposed to search through an extended space of causal graphs. Moreover, to go beyond ”
Discovery of Causal Models that Contain Latent Variables through Bayesian Scoring of Independence Constraints (2017, methodology): “Fast Causal Inference (FCI) [33] is a constraint-based causal discovery algorithm, which we discuss in more detail here because it serves as a good example of a constraint-based algorithm, and we use an adapted version of it, called Really Fast Causal Inference (RFCI) [10], in the research reported ”
Causal Regularization (2017, background): “Methods for discovering causal relationships among multiple variables from observational data (Chickering, 2002; Kalisch and Bühlmann, 2007; Colombo et al., 2012) are largely based on the principle that any given set of causal relationships among multiple variables leaves well-deﬁned marks in the…”
Approximate Kernel-Based Conditional Independence Tests for Fast Non-Parametric Causal Discovery (2017, methodology): “We next examine the accuracy of graphical structures as recovered by PC (Spirtes et al., 2000), FCI (Zhang, 2008) and RFCI (Colombo et al., 2012) when run using RCIT, RCoT or KCIT.”
PC algorithm for nonparanormal graphical models (2013, background): “One example is the FCI algorithm that infers a more complex graphical object to deal with situations in which some relevant variables remain unobserved (Spirtes et al., 2000; Colombo et al., 2012).”
High-Dimensional Statistics with a View Toward Applications in Biology (2014, background): “Some relaxations of these conditions have been worked out: the FCI algorithm allows for hidden variables (Spirtes et al., 2000; Colombo et al., 2012) while graphs with directed cycles are considered in Spirtes (1995), Richardson (1996) and Mooij et al. (2011).”
Estimating the effect of joint interventions from observational data in sparse high-dimensional settings (2014, background): “, [4, 7, 33]) and the adjustment criteria developed in [18, 26, 37].”