Almost Optimal Intervention Sets for Causal Discovery

Understand

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.