Active Structure Learning of Causal DAGs via Directed Clique Tree
  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 https://github.com/csquires/dct-policy
