Constraint-based causal discovery from multiple interventions over overlapping variable sets

By Sofia Triantafillou, Ioannis Tsamardinos. 2014

166 citations recorded by the source corpus.

Scientific practice typically involves repeatedly studying a system, each time trying to unravel a different perspective. In each study, the scientist may take measurements under different experimental conditions (interventions, manipulations, perturbations) and measure different sets of quantities (variables). The result is a collection of heterogeneous data sets coming from different data distributions. In this work, we present algorithm COmbINE, which accepts a collection of data sets over overlapping variable sets under different experimental conditions; COmbINE then outputs a summary of all causal models indicating the invariant and variant structural characteristics of all models that simultaneously fit all of the input data sets. COmbINE converts estimated dependencies and independencies in the data into path constraints on the data-generating causal model and encodes them as a SAT instance. The algorithm is sound and complete in the sample limit. To account for conflicting constraints arising from statistical errors, we introduce a general method for sorting constraints in order of confidence, computed as a function of their corresponding p-values. In our empirical evaluation, COmbINE outperforms in terms of efficiency the only pre-existing similar algorithm; the latter additionally admits feedback cycles, but does not admit conflicting constraints which hinders the applicability on real data. As a proof-of-concept, COmbINE is employed to co-analyze 4 real, mass-cytometry data sets measuring phosphorylated protein concentrations of overlapping protein sets under 3 different interventions.

Subfields: Artificial Intelligence, Representation & Self-Supervised Learning, 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

In Representation & Self-Supervised Learning

In Causal Inference & Discovery

Citations in the corpus

Differentiable Causal Discovery from Interventional Data (2020, methodology): “Methods that support interventional data include COmbINE [37] and HEJ [16], which rely on Boolean satisﬁability solvers to ﬁnd a graph that satisﬁes all constraints.”
Domain Adaptation by Using Causal Inference to Predict Invariant Conditional Distributions (2017, methodology): “;j2I: I i $I j 2G); no system variable is confounded with an intervention variable with respect to V (8j2O;8i2I: X j $I i 2G= ). Logic-based causal discovery methods, such as [Hyttinen et al., 2014, Triantaﬁllou and Tsamardinos, 2015, Magliacane et al., 2016], are ideally suited to exploit the backg”
Permutation-Based Causal Structure Learning with Unknown Intervention Targets (2019, background): “…B¨uhlmann, 2012) and IGSP (Wang et al., 2017; Yang et al., 2018) under the assumption of causal suﬃ-ciency, i.e., when there are no latent confounders, and ACI (Magliacane et al., 2016), HEJ (Hyttinen et al., 2014) and COmbINE (Triantaﬁllou and Tsamardinos, 2015) that allow for latent confounders.”
Permutation-based Causal Inference Algorithms with Interventions (2017, methodology): “The Supplementary Material contains a comparison of the results obtained by IGSP on this dataset to other recent methods that allow also for latent confounders, such as ACI, COmbINE and ICP.”
D’ya Like DAGs? A Survey on Structure Learning and Causal Discovery (2021, unknown): “PC [223] 1993 constraint yes yes yes no CPDAG CCD [196] 1996 constraint yes yes both no PAG FCI [223] 2000 constraint no yes yes no PAG TPDA [31] 2002 constraint yes yes yes no CPDAG CPC [190] 2006 constraint yes relaxed yes no CPDAG KCL [227] 2007 constraint yes yes yes no CPDAG ION [234] 2008 cons”
Causal Network Learning from Multiple Interventions of Unknown Manipulated Targets (2016, background): “Triantafillou and Tsamardinos (2014) propose an approach in which a function of their corresponding p-values is used to sort the constrains in order of confidence.”
Characterization and Learning of Causal Graphs with Latent Variables from Soft Interventions (2019, methodology): “For causally insufficient systems, [22] uses SAT solvers to learn a summary graph over the observed variables given data from different experimental conditions.”
Structure Learning in Graphical Modeling (2016, background): “Finally, we note that heterogeneity from diﬀerent experimental conditions can also be exploited in structure learning for directed graphical models (Danks et al., 2009; Hauser & B¨uhlmann, 2012; Hyttinen et al., 2012; Triantaﬁllou & Tsamardinos, 2015).”
Joint Causal Inference from Multiple Contexts (2016, methodology): “The latter approach is commonly used by constraint-based methods for causal discovery from multiple data sets (e.g., Tillman, 2009; Claassen and Heskes, 2010; Tillman and Spirtes, 2011; Hyttinen et al., 2014; Triantafillou and Tsamardinos, 2015; Rothenhäusler et al., 2015; Forré and Mooij, 2018).”
Do-calculus when the True Graph Is Unknown (2015, background): “If the causal constraints are to be obtained from heterogeneous data sets, possibly including experimental data or background knowledge, then a search algorithm such as GIES, IOD or a SAT-based procedure may be better (Hauser and Bühlmann, 2012; Tillman and Spirtes, 2011; Triantafillou and Tsamardin”
Characterizing and Learning Equivalence Classes of Causal DAGs under Interventions (2018, background): “Methods that allow for latent confounders and unknown intervention targets include Eaton & Murphy (2007), JCI (Magliacane et al., 2016), HEJ (Hyttinen et al., 2014), CombINE (Triantaﬁllou & Tsamardinos, 2015), and ICP (Peters et al., 2016), but they do not have consistency guarantees for returning a”
Causal Transfer Learning (2017, methodology): “;j2I: I i $I j 2G); no system variable is confounded with an intervention variable with respect to V (8j2O;8i2I: X j $I i 2G= ). Logic-based causal discovery methods, such as [Hyttinen et al., 2014, Triantaﬁllou and Tsamardinos, 2015, Magliacane et al., 2016], are ideally suited to exploit the backg”
Learning Optimal Causal Graphs with Exact Search (2018, methodology): “Weights for the (in)dependence constraints can be obtained by Bayesian model selection (Margaritis and Bromberg, 2009; Claassen and Heskes, 2012) or statistical hypothesis testing (Triantafillou and Tsamardinos, 2015; Magliacane et al., 2016).”
Ancestral Causal Inference (2016, unknown): “COmbINE (Causal discovery from Overlapping INtErventions) [25] is an algorithm that combines the output of FCI on several overlapping observational and experimental datasets into a single causal model by first pooling and recalibrating the independence test p-values, and then adding each constraint ”