A Unified Experiment Design Approach for Cyclic and Acyclic Causal Models
We study experiment design for the unique identification of the causal graph
of a system where the graph may contain cycles. The presence of cycles in the
structure introduces major challenges for experiment design. Unlike the case of
acyclic graphs, learning the skeleton of the causal graph from observational
distribution may not be possible. Furthermore, intervening on a variable does
not necessarily lead to orienting all the edges incident to it. In this paper,
we propose an experiment design approach that can learn both cyclic and acyclic
graphs and hence, unifies the task of experiment design for both types of
graphs. We provide a lower bound on the number of experiments required to
guarantee the unique identification of the causal graph in the worst case,
showing that the proposed approach is order-optimal in terms of the number of
experiments up to an additive logarithmic term. Moreover, we extend our result
to the setting where the size of each experiment is bounded by a constant. For
this case, we show that our approach is optimal in terms of the size of the
largest experiment required for the unique identification of the causal graph
in the worst case.