Estimating High-Dimensional Directed Acyclic Graphs with the PC-Algorithm
By Markus Kalisch, Peter Buhlmann. 2005
1,070 citations recorded by the source corpus.
We consider the PC-algorithm (Spirtes et al., 2000) for estimating the skeleton and equivalence class of a very high-dimensional directed acyclic graph (DAG) with corresponding Gaussian distribution. The PC-algorithm is computationally feasible and often very fast for sparse problems with many nodes (variables), and it has the attractive property to automatically achieve high computational efficiency as a function of sparseness of the true underlying DAG. We prove uniform consistency of the algorithm for very high-dimensional, sparse DAGs where the number of nodes is allowed to quickly grow with sample size n, as fast as O(na) for any 0 < a < ∞. The sparseness assumption is rather minimal requiring only that the neighborhoods in the DAG are of lower order than sample size n. We also demonstrate the PC-algorithm for simulated data.
Subfields: Artificial Intelligence, Cognitive Neuroscience, Statistics and Probability, Probabilistic & Bayesian Methods, 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
- Peter Buhlmann
- Bernhard Schölkopf
- Jan Peters
- Marloes H. Maathuis
- Nicolai Meinshausen
- David Lopez-Paz
- Mathias Drton
- Yoshua Bengio
In Cognitive Neuroscience
- Sacha Epskamp
- Denny Borsboom
- Lourens J. Waldorp
- Marloes H. Maathuis
- Alain Hauser
- Marco Scutari
- Peter Buhlmann
- R. Mõttus
In Statistics and Probability
- Peter Buhlmann
- Jan Peters
- Nicolai Meinshausen
- Marloes H. Maathuis
- Bernhard Schölkopf
- Mathias Drton
- Sara A. van de Geer
- Bin Yu
In Probabilistic & Bayesian Methods
- Jan Peters
- Peter Buhlmann
- Bernhard Schölkopf
- Dino Sejdinovic
- David Lopez-Paz
- Sara A. van de Geer
- Bryon Aragam
- Jack Kuipers
In Causal Inference & Discovery
- Bernhard Schölkopf
- Peter Buhlmann
- Jan Peters
- Nicolai Meinshausen
- Xintao Wu
- Marloes H. Maathuis
- Lu Zhang
- Christina Heinze-Deml
Citations in the corpus
- Causal Modeling-Based Discrimination Discovery and Removal: Criteria, Bounds, and Algorithms (2019, background): “Many algorithms have been proposed to learn the causal graph from data [27], [28], [29], [30].”
- A Causal Framework for Discovering and Removing Direct and Indirect Discrimination (2016, background): “In the past decades, many algorithms have been proposed to learn the causal network from data and they are proved to be quite successful (Spirtes, Glymour, and Scheines 2000; Neapolitan and others 2004; Colombo and Maathuis 2014; Kalisch and Bühlmann 2007).”
- Achieving Non-Discrimination in Data Release (2016, background): “In the past decades, many algorithms have been proposed to learn causal DAGs, and they are proved to be quite successful [26, 21, 5, 12].”
- Causal inference by using invariant prediction: identification and confidence intervals (2015, background): “…2012], estimate such a class based on observational or interventional data [Spirtes et al., 2000, Chickering, 2002, Castelo and Kocka, 2003, Kalisch and B¨uhlmann, 2007, He and Geng., 2008, Hauser and B¨uhlmann, 2015, cf.], and finally infer the iden-tifiable causal effects or provide some…”
- A Kernel Test for Three-Variable Interactions (2013, methodology): “In the PC algorithm [13, 14, 15], a V-structure (a directed graphical model with two independent parents pointing to a single child) is detected when an independence test between the parent variables accepts the null hypothesis, while a test of dependence of the parents conditioned on the child reje”
- Characterization and greedy learning of interventional Markov equivalence classes of directed acyclic graphs (2011, methodology): “For some number p of vertices, we randomly generated Gaussian causal models parameterized by a structure D , a weight matrix B ∈ B ( D ) and a vector of error covariances σ 2 ∈ R p> 0 by a procedure slightly adapted from Kalisch and B¨uhlmann (2007): 1.”
- Causal Structure Learning (2017, methodology): “The PC algorithm was shown to be consistent in certain sparse high-dimensional settings (Kalisch and Bühlmann, 2007).”
- Estimating the effect of joint interventions from observational data in sparse high-dimensional settings (2014, background): “Moreover, assume that Algorithm 4 Joint-IDA estimator Input: n i.i.d. observations of X (data), intervention nodes (1, . . . , k), OPIN method Output: Estimate of (1,...,k)p [see (11)] 1: obtain an estimate of the underlying CPDAG Ĉ from observational data (e.g., using the PC-algorithm); 2: P̂As ← ”
- High-dimensional consistency in score-based and hybrid structure learning (2015, background): “Such an assumption is not required for high-dimensional consistency of the PC algorithm [Kalisch and Bühlmann, 2007].”
- Partition MCMC for Inference on Acyclic Digraphs (2015, methodology): “The edges of a Bayesian network encode conditional independence relationships, which constitute the main ingredient of constraint based learning methods, such as the widely used PC algorithm (Spirtes et al., 2000; Kalisch and Bühlmann, 2007) which was also recently implemented in the pcalg R package”
- A Survey of Learning Causality with Data: Problems and Methods (2018, methodology): “Other constraint-based algorithms include the IC algorithm [104] and their variants [75, 82].”
- Learning Bayesian networks: approaches and issues (2011, methodology): “A modification of the PC algorithm that decreases the amount of Causal Inference (CI) tests needed is called PC* (Spirtes et al., 2000), and recently, applicability of PC to high-dimensional data is shown by Kalisch and Bühlmann (2007).”
- $\ell_0$-penalized maximum likelihood for sparse directed acyclic graphs (2012, methodology): “Kalisch and B¨uhlmann (2007) provide consistency results of the PC-algorithm [Spirtes, Glymour and Scheines (2000)] for estimating the Markov equivalence class of DAGs based on Gaussian observational data, in the PENALIZED MAXIMUM LIKELIHOOD FOR DAG 3 high-dimensional, sparse setting.”
- Causal Inference Using Graphical Models with the R Package pcalg (2012, methodology): “See Kalisch and B¨uhlmann (2007) for full details.”
- Masked Gradient-Based Causal Structure Learning (2019, methodology): “, faithfulness, are usually stronger than score-based methods (Spirtes, 2010; Kalisch and Bühlmann, 2007).”
- Inferring gene regulatory networks from gene expression data by path consistency algorithm based on conditional mutual information (2012, methodology): “For the PC-algorithms, PCA-CMI does better than PCA-PCC.”