Almost Optimal Intervention Sets for Causal Discovery

Abstract

We conjecture that the worst case number of experiments necessary and sufficient to discover a causal graph uniquely given its observational Markov equivalence class can be specified as a function of the largest clique in the Markov equivalence class. We provide an algorithm that computes intervention sets that we believe are optimal for the above task. The algorithm builds on insights gained from the worst case analysis in Eberhardt et al. (2005) for sequences of experiments when all possible directed acyclic graphs over N variables are considered. A simulation suggests that our conjecture is correct. We also show that a generalization of our conjecture to other classes of possible graph hypotheses cannot be given easily, and in what sense the algorithm is then no longer optimal.

Appears in Proceedings of the Twenty-Fourth Conference on Uncertainty in Artificial Intelligence (UAI2008)

References in corpus (2)

• Causal Inference and Causal Explanation with Background Knowledge
• Causal Discovery from a Mixture of Experimental and Observational Data

Cited by in corpus (9)

• Characterization and Greedy Learning of Interventional Markov Equivalence Classes of Directed Acyclic Graphs
• Two Optimal Strategies for Active Learning of Causal Models from Interventional Data
• Characterizing and Learning Equivalence Classes of Causal DAGs under Interventions
• Differentiable Causal Discovery from Interventional Data
• Learning Neural Causal Models with Active Interventions
• Active Invariant Causal Prediction: Experiment Selection through Stability
• Optimal experimental design via Bayesian optimization: active causal structure learning for Gaussian process networks
• Efficient Neural Causal Discovery without Acyclicity Constraints
• Causal Structure Learning: a Bayesian approach based on random graphs