Intervention Efficient Algorithms for Approximate Learning of Causal Graphs

Understand

We study the problem of learning the causal relationships between a set of observed variables in the presence of latents, while minimizing the cost of interventions on the observed variables.

• We assume access to an undirected graph $G$ on the observed variables whose edges represent either all direct causal relationships or, less restrictively, a superset of causal relationships (identified, e.g., via conditional independence tests or a domain expert).
• Our goal is to recover the directions of all causal or ancestral relations in $G$, via a minimum cost set of interventions.
• It is known that constructing an exact minimum cost intervention set for an arbitrary graph $G$ is NP-hard.