A growing body of work has begun to study intervention design for efficient
structure learning of causal directed acyclic graphs (DAGs). A typical setting
is a causally sufficient setting, i.e. a system with no latent confounders,
selection bias, or feedback, when the essential graph of the observational
equivalence class (EC) is given as an input and interventions are assumed to be
noiseless. Most existing works focus on worst-case or average-case lower bounds
for the number of interventions required to orient a DAG. These worst-case
lower bounds only establish that the largest clique in the essential graph
could make it difficult to learn the true DAG. In this work, we develop a
universal lower bound for single-node interventions that establishes that the
largest clique is always a fundamental impediment to structure learning.
Specifically, we present a decomposition of a DAG into independently orientable
components through directed clique trees and use it to prove that the number of
single-node interventions necessary to orient any DAG in an EC is at least the
sum of half the size of the largest cliques in each chain component of the
essential graph. Moreover, we present a two-phase intervention design algorithm
that, under certain conditions on the chordal skeleton, matches the optimal
number of interventions up to a multiplicative logarithmic factor in the number
of maximal cliques. We show via synthetic experiments that our algorithm can
scale to much larger graphs than most of the related work and achieves better
worst-case performance than other scalable approaches. A code base to recreate
these results can be found at this https URL

本研究提出了针对因果有向无环图（DAGs）的干预设计的通用下限，并基于有向团树将 DAG 分解成可独立定向的组件，从而证明在任何 EC 中定向任何 DAG 所需的单节点干预数至少是每个基本图的链组件中最大团大小的一半的总和。另外，我们还提出了一个两阶段干预设计算法，其性能符合以最大团个数的对数乘性为界限的最优干预数，并通过合成实验验证了我们的算法可以比大多数相关工作处理更大的图形并且获得更好的最坏情况性能。