Characterization and Greedy Learning of Interventional Markov Equivalence Classes of Directed Acyclic Graphs
arXiv:1104.2808
Abstract
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, interventional Markov 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.
References in corpus (7)
- Estimating high-dimensional directed acyclic graphs with the PC-algorithm
- A simple approach for finding the globally optimal Bayesian network structure
- Causal Discovery from a Mixture of Experimental and Observational Data
- Causal Discovery from Changes
- Jointly interventional and observational data: estimation of interventional Markov equivalence classes of directed acyclic graphs
- Almost Optimal Intervention Sets for Causal Discovery
- On the Number of Experiments Sufficient and in the Worst Case Necessary to Identify All Causal Relations Among N Variables
Cited by in corpus (67)
- -penalized maximum likelihood for sparse directed acyclic graphs
- A Survey on Causal Discovery: Theory and Practice
- Constraint-based Causal Discovery from Multiple Interventions over Overlapping Variable Sets
- Two Optimal Strategies for Active Learning of Causal Models from Interventional Data
- Jointly interventional and observational data: estimation of interventional Markov equivalence classes of directed acyclic graphs
- Graphical Criteria for Efficient Total Effect Estimation via Adjustment in Causal Linear Models
- Learning Neural Causal Models from Unknown Interventions
- Inferring large graphs using l1-penalized likelihood
- Optimizing regularized Cholesky score for order-based learning of Bayesian networks
- backShift: Learning causal cyclic graphs from unknown shift interventions
- Characterizing and Learning Equivalence Classes of Causal DAGs under Interventions
- Deriving a Usage-Independent Software Quality Metric
- Interpreting and using CPDAGs with background knowledge
- Learning and Testing Causal Models with Interventions
- Learning Causal Graphs with Small Interventions
- Differentiable Causal Discovery from Interventional Data
- Learning Neural Causal Models with Active Interventions
- Statistical Perspective on Functional and Causal Neural Connectomics: A Comparative Study
- Discovering Nonlinear Relations with Minimum Predictive Information Regularization
- A Local Method for Identifying Causal Relations under Markov Equivalence
- Efficient adjustment sets for population average treatment effect estimation in non-parametric causal graphical models
- Comparative Benchmarking of Causal Discovery Techniques
- ABCD-Strategy: Budgeted Experimental Design for Targeted Causal Structure Discovery
- Variational Causal Networks: Approximate Bayesian Inference over Causal Structures
- Causal Network Learning from Multiple Interventions of Unknown Manipulated Targets
- Investigating the effect of binning on causal discovery
- High-Dimensional Joint Estimation of Multiple Directed Gaussian Graphical Models
- Discovering Markov Blanket from Multiple interventional Datasets
- Active Invariant Causal Prediction: Experiment Selection through Stability
- Ranking academic institutions on potential paper acceptance in upcoming conferences
- Switching Regression Models and Causal Inference in the Presence of Discrete Latent Variables
- Experimental Design for Cost-Aware Learning of Causal Graphs
- Efficient least squares for estimating total effects under linearity and causal sufficiency
- Permutation-Based Causal Structure Learning with Unknown Intervention Targets
- A review of some recent advances in causal inference
- Interventional Experiment Design for Causal Structure Learning
- Amortized learning of neural causal representations
- Efficient Intervention Design for Causal Discovery with Latents
- Towards Scalable Bayesian Learning of Causal DAGs
- Marginal integration for nonparametric causal inference
- Near-Optimal Multi-Perturbation Experimental Design for Causal Structure Learning
- Identifying causal effects in maximally oriented partially directed acyclic graphs
- Identifying Invariant Factors Across Multiple Environments with KL Regression
- Intelligence, physics and information -- the tradeoff between accuracy and simplicity in machine learning
- Causal aggregation: estimation and inference of causal effects by constraint-based data fusion
- Causal learning with sufficient statistics: an information bottleneck approach
- Efficient Neural Causal Discovery without Acyclicity Constraints
- A practical guide to causal discovery with cohort data
- Variance Minimization in the Wasserstein Space for Invariant Causal Prediction
- Learning Linear Gaussian Polytree Models with Interventions
- Intervention Efficient Algorithms for Approximate Learning of Causal Graphs
- Disentangling Observed Causal Effects from Latent Confounders using Method of Moments
- Typing assumptions improve identification in causal discovery
- Distributional Invariances and Interventional Markov Equivalence for Mixed Graph Models
- Obtaining Causal Information by Merging Datasets with MAXENT
- Efficient Permutation Discovery in Causal DAGs
- Matching a Desired Causal State via Shift Interventions
- Size of Interventional Markov Equivalence Classes in Random DAG Models
- Dis-entangling Mixture of Interventions on a Causal Bayesian Network Using Aggregate Observations
- Corrected score methods for estimating Bayesian networks with error-prone nodes
- Estimation Rates for Sparse Linear Cyclic Causal Models
- A New Statistical Framework for Genetic Pleiotropic Analysis of High Dimensional Phenotype Data
- Identifying Causal Influences on Publication Trends and Behavior: A Case Study of the Computational Linguistics Community
- Ancestral causal learning in high dimensions with a human genome-wide application
- Minimal enumeration of all possible total effects in a Markov equivalence class
- Evaluation of Causal Structure Learning Algorithms via Risk Estimation
- Collaborative Causal Discovery with Atomic Interventions