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
- Marloes H. Maathuis
- Bernhard Schölkopf
- Peter Buhlmann
- Jan Peters
- Mathias Drton
- Nicolai Meinshausen
- Christina Heinze-Deml
- David Lopez-Paz
In Molecular Biology
- Marloes H. Maathuis
- Christina Heinze-Deml
- Mathias Drton
- Sara Magliacane
- Tom Claassen
- David Lopez-Paz
- Emilija Perkovi'c
- Preetam Nandy
In Causal Inference & Discovery
- Xintao Wu
- Lu Zhang
- Bernhard Schölkopf
- Peter Buhlmann
- Nicolai Meinshausen
- Yongkai Wu
- Christina Heinze-Deml
- Joris M. Mooij
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 Generative Neural Networks (2017, methodology): “For PC, we employ the better-performing, order-independent version of the PC algorithm proposed by [Colombo and Maathuis, 2014].”
- Causal Structure Learning (2017, methodology): “We use the order-independent version of Colombo and Maathuis (2014).”
- A Complete Generalized Adjustment Criterion (2015, background): “…criterion for DAGs, MAGs, CPDAGs and PAGs, where CPDAGs andPAGs represent Markov equivalence classes of DAGs or MAGs, respectively, and can be inferred directly from data (see, e.g., Spirtes et al., 2000; Chickering, 2003; Colombo et al., 2012; Claassen et al., 2013; Colombo and Maathuis, 2014).”
- Situation Testing-Based Discrimination Discovery: A Causal Inference Approach (2016, background): “In the past decades, many algorithms have been proposed to learn CBNs, and they are proved to be quite successful [Spirtes et al., 2000; Neapolitan and others, 2004; Colombo and Maathuis, 2014].”
- Explainable and Interpretable Models in Computer Vision and Machine Learning (2017, positive): “For PC, we employ the better-performing, order-independent version of the PC algorithm proposed by Colombo and Maathuis (2014).”
- Structure Learning in Graphical Modeling (2016, background): “Colombo & Maathuis (2014) observe that the output of the PC algorithm can depend strongly on the variable ordering.”
- Partition MCMC for Inference on Acyclic Digraphs (2015, methodology): “By their very nature, methods building on this strategy are sensitive to local errors of the tests and to the order in which they are run (Colombo and Maathuis 2014), but they tend to scale relatively well with the dimension.”
- High-dimensional consistency in score-based and hybrid structure learning (2015, methodology): “…were shown to be consistent in sparse high-dimensional settings where the number of variables is allowed to grow with the sample size [Kalisch and Bühlmann (2007), Harris and Drton (2013), Colombo and Maathuis (2014)], and partly because they scale well to sparse graphs with thousands of variables.”
- Efficient Sampling and Structure Learning of Bayesian Networks (2018, methodology): “Interesting directions may also come from the ILP method of Cussens (2011) and Cussens et al. (2017), if the solver manages to complete and the number of parents in the maximally scoring DAG is less than the low limit needed for their input score tables.”
- Anti-discrimination learning: a causal modeling-based framework (2017, methodology): “In practical, the causal graph can be learned from the data using the structure learning algorithms [8,16,23,33].”
- Joint Causal Inference from Multiple Contexts (2016, methodology): “mentation in the R package pcalg (Kalisch et al., 2012). We used the default conguration, i.e., an orderindependent (\stable") skeleton phase, and no conservative or majority rule modications (Colombo and Maathuis, 2014). For simplicity, we assumed that no selection bias is present, which means”
- Estimating the effect of joint interventions from observational data in sparse high-dimensional settings (2014, methodology): “1, and (ii) the CPDAG is estimated from the data, using the order independent version of the PC-algorithm [8] with tuning parameter α = 0.”