  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.
