Order-independent constraint-based causal structure learning

By Diego Colombo, Marloes H. Maathuis. 2012

735 citations recorded by the source corpus.

We consider constraint-based methods for causal structure learning, such as the PC-, FCI-, RFCI- and CCD- algorithms (Spirtes et al., 1993, 2000; Richardson, 1996; Colombo et al., 2012; Claassen et al., 2013). The first step of all these algorithms consists of the adjacency search of the PC-algorithm. The PC-algorithm is known to be order-dependent, in the sense that the output can depend on the order in which the variables are given. This order-dependence is a minor issue in low-dimensional settings. We show, however, that it can be very pronounced in high-dimensional settings, where it can lead to highly variable results. We propose several modifications of the PC-algorithm (and hence also of the other algorithms) that remove part or all of this order-dependence. All proposed modifications are consistent in high-dimensional settings under the same conditions as their original counterparts. We compare the PC-, FCI-, and RFCI-algorithms and their modifications in simulation studies and on a yeast gene expression data set. We show that our modifications yield similar performance in low-dimensional settings and improved performance in high-dimensional settings. All software is implemented in the R-package pcalg.

Subfields: Artificial Intelligence, Molecular Biology, 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. Marloes H. Maathuis
  2. Bernhard Schölkopf
  3. Peter Buhlmann
  4. Jan Peters
  5. Mathias Drton
  6. Nicolai Meinshausen
  7. Christina Heinze-Deml
  8. David Lopez-Paz

In Molecular Biology

  1. Marloes H. Maathuis
  2. Christina Heinze-Deml
  3. Mathias Drton
  4. Sara Magliacane
  5. Tom Claassen
  6. David Lopez-Paz
  7. Emilija Perkovi'c
  8. Preetam Nandy

In Causal Inference & Discovery

  1. Xintao Wu
  2. Lu Zhang
  3. Bernhard Schölkopf
  4. Peter Buhlmann
  5. Nicolai Meinshausen
  6. Yongkai Wu
  7. Christina Heinze-Deml
  8. Joris M. Mooij

Citations in the corpus