We study experiment design for 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 as, unlike acyclic graphs, learning the skeleton of causal graphs with cycles may not be possible from merely the observational distribution. Furthermore, intervening on a variable in such graphs 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 uniquely identifying the causal graph in the worst case.

翻译：我们研究一个系统的独特因果图的实验设计,这个系统中的因果图可能包含周期。在结构中存在周期给实验设计带来重大挑战,因为与非循环图不同,仅仅从观测分布中不可能了解循环因果图的骨架。此外,在这种图表中的一个变量上进行干预并不一定导致将所有边缘事件都指向它。在本文中,我们建议一种实验设计方法,既可以学习周期图,也可以学习周期图,从而统一两种类型的图表的实验设计任务。我们对最坏情况下确保独特识别因果图所需的实验数量提供了较低的限制,表明就实验数量而言,拟议的方法是符合逻辑的。此外,我们把结果扩大到每个实验的大小都与一个常数捆绑在一起的设置。对于这种情况,我们表明我们的方法在最坏的案例中,最理想的实验规模是确定因果图所需的最大试验。