Design of Experiment for Discovering Directed Mixed Graph
This work addresses the challenge of causal discovery in complex models with cycles and confounding, which is incremental as it builds on existing methods but provides new theoretical bounds and algorithms.
The paper tackles the problem of experimental design for identifying causal graph structures in structural causal models with cycles and latent confounders, establishing lower bounds on interventions and experiments and developing algorithms that recover most edges, showing these algorithms are tight up to logarithmic factors.
We study the problem of experimental design for accurately identifying the causal graph structure of a simple structural causal model (SCM), where the underlying graph may include both cycles and bidirected edges induced by latent confounders. The presence of cycles renders it impossible to recover the graph skeleton using observational data alone, while confounding can further invalidate traditional conditional independence (CI) tests in certain scenarios. To address these challenges, we establish lower bounds on both the maximum number of variables that can be intervened upon in a single experiment and the total number of experiments required to identify all directed edges and non-adjacent bidirected edges. Leveraging both CI tests and do see tests, and accounting for $d$ separation and $σ$ separation, we develop two classes of algorithms, i.e., bounded and unbounded, that can recover all causal edges except for double adjacent bidirected edges. We further show that, up to logarithmic factors, the proposed algorithms are tight with respect to the derived lower bounds.