Characterization and greedy learning of interventional Markov equivalence classes of directed acyclic graphs

By Alain Hauser, Peter Buhlmann. 2011

518 citations recorded by the source corpus.

The investigation of directed acyclic graphs (DAGs) encoding the same Markov property, that is the same conditional independence relations of multivariate observational distributions, has a long tradition; many algorithms exist for model selection and structure learning in Markov equivalence classes. In this paper, we extend the notion of Markov equivalence of DAGs to the case of interventional distributions arising from multiple intervention experiments. We show that under reasonable assumptions on the intervention experiments, interventionalMarkov equivalence defines a finer partitioning of DAGs than observational Markov equivalence and hence improves the identifiability of causal models. We give a graph theoretic criterion for two DAGs being Markov equivalent under interventions and show that each interventional Markov equivalence class can, analogously to the observational case, be uniquely represented by a chain graph called interventional essential graph (also known as CPDAG in the observational case). These are key insights for deriving a generalization of the Greedy Equivalence Search algorithm aimed at structure learning from interventional data. This new algorithm is evaluated in a simulation study.

Subfields: Artificial Intelligence, 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 Causal Inference & Discovery

Citations in the corpus

Differentiable Causal Discovery from Interventional Data (2020, methodology): “The conditionals of targeted nodes were replaced by the marginal N (2, 1) similarly to [15, 42].”
Learning Neural Causal Models from Unknown Interventions (2019, background): “…of prior work has examined learning causal structure based on observational data (Chickering, 2002; Tsamardinos et al., 2006; Goudet et al., 2017; Hauser & Bühlmann, 2012; Spirtes et al., 2000; Sun et al., 2007; Zhang et al., 2012; Shimizu et al., 2006; Hoyer et al., 2009; Daniusis et al., 2012;…”
Invariant Causal Prediction for Sequential Data (2017, methodology): “Having access to interventional data improves identifiability for inferring causal relations and several methods have been proposed that exploit both observational and interventional data (e.g., Eaton and Murphy 2007; Hauser and Bühlmann 2012; Peters, Bühlmann, andMeinshausen 2016).”
Causal inference by using invariant prediction: identification and confidence intervals (2015, methodology): “Greedy interventional equivalence search (GIES) with known interventions [Hauser and B¨uhlmann, 2012].”
Causal Structure Learning (2017, methodology): “Limiting ourselves to algorithms with an implementation in R (R Core Team, 2017), we obtain the following selection of methods, with assumptions summarized in Table 1: • Constraint-based methods: PC (Spirtes et al., 2000), rankPC (Harris and Drton, 2013), FCI (Spirtes et al., 2000), and rankFCI • Sc”
Towards Scalable Bayesian Learning of Causal DAGs (2020, unknown): “Our implementations build on standard software [33, 13, 12, 1].”
High-dimensional consistency in score-based and hybrid structure learning (2015, methodology): “In fact, we use a slightly modified version of (AR)GES that additionally includes a turning phase [Chickering, 2002a; Hauser and Bühlmann, 2012] and an iteration over all three phases (see Section 6 of the supplementary material for details).”
Differentiable Causal Discovery Under Latent Interventions (2022, methodology): “If there is access to intervention data (in a set of interventions I ), it is possible to shrink the MEC to the so-called I -MEC (Hauser and B¨uhlmann, 2012): the subset of graphs in the MEC that have the same conditional independencies after applying the interventions in I .”
Learning Causal Graphs with Small Interventions (2015, methodology): “Then, we generalize to chordal graph skeletons and provide a novel adaptive algorithm with upper and lower bounds on its performance.”
Characterizing and Learning Equivalence Classes of Causal DAGs under Interventions (2018, methodology): “In particular, we provided a graphical characterization of I -MECs and proved a conjecture of Hauser & B¨uhlmann (2012)”
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).”
Structural Agnostic Modeling: Adversarial Learning of Causal Graphs (2018, methodology): “The following algorithms have been used, with their default parameters: the score-based methods GES (Chickering, 2002) and GIES (Hauser and Bühlmann, 2012) with Gaussian scores; the hybrid method MMHC (Tsamardinos et al., 2006), the L1 penalized method for causal discovery CCDr (Aragam and Zhou,…”
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”
Joint Causal Inference from Multiple Contexts (2016, methodology): “, 2015; Forré and Mooij, 2018), (b) methods that pool all data and construct a single context-independent causal graph directly from the pooled data (Cooper, 1997; Cooper and Yoo, 1999; Tian and Pearl, 2001; Sachs et al., 2005; Eaton and Murphy, 2007; Chen et al., 2007; Hauser and Bühlmann, 2012; Mo”
Permutation-based Causal Inference Algorithms with Interventions (2017, methodology): “Such options have been considered in [8], in which the authors propose GIES, an extension of GES that accounts for interventional data.”