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

  1. Peter Buhlmann
  2. Bernhard Schölkopf
  3. Jan Peters
  4. Marloes H. Maathuis
  5. Nicolai Meinshausen
  6. David Lopez-Paz
  7. Mathias Drton
  8. Yoshua Bengio

In Cognitive Neuroscience

  1. Sacha Epskamp
  2. Denny Borsboom
  3. Lourens J. Waldorp
  4. Marloes H. Maathuis
  5. Alain Hauser
  6. Marco Scutari
  7. Peter Buhlmann
  8. R. Mõttus

In Statistics and Probability

  1. Peter Buhlmann
  2. Jan Peters
  3. Nicolai Meinshausen
  4. Marloes H. Maathuis
  5. Bernhard Schölkopf
  6. Mathias Drton
  7. Sara A. van de Geer
  8. Bin Yu

In Probabilistic & Bayesian Methods

  1. Jan Peters
  2. Peter Buhlmann
  3. Bernhard Schölkopf
  4. Dino Sejdinovic
  5. David Lopez-Paz
  6. Sara A. van de Geer
  7. Bryon Aragam
  8. Jack Kuipers

In Causal Inference & Discovery

  1. Bernhard Schölkopf
  2. Peter Buhlmann
  3. Jan Peters
  4. Nicolai Meinshausen
  5. Xintao Wu
  6. Marloes H. Maathuis
  7. Lu Zhang
  8. Christina Heinze-Deml

Citations in the corpus