Learning Causal Graphs with Small Interventions
  We consider the problem of learning causal networks with interventions, when
each intervention is limited in size under Pearl's Structural Equation Model
with independent errors (SEM-IE). The objective is to minimize the number of
experiments to discover the causal directions of all the edges in a causal
graph. Previous work has focused on the use of separating systems for complete
graphs for this task. We prove that any deterministic adaptive algorithm needs
to be a separating system in order to learn complete graphs in the worst case.
In addition, we present a novel separating system construction, whose size is
close to optimal and is arguably simpler than previous work in combinatorics.
We also develop a novel information theoretic lower bound on the number of
interventions that applies in full generality, including for randomized
adaptive learning algorithms.
  For general chordal graphs, we derive worst case lower bounds on the number
of interventions. Building on observations about induced trees, we give a new
deterministic adaptive algorithm to learn directions on any chordal skeleton
completely. In the worst case, our achievable scheme is an
$\alpha$-approximation algorithm where $\alpha$ is the independence number of
the graph. We also show that there exist graph classes for which the sufficient
number of experiments is close to the lower bound. In the other extreme, there
are graph classes for which the required number of experiments is
multiplicatively $\alpha$ away from our lower bound.
  In simulations, our algorithm almost always performs very close to the lower
bound, while the approach based on separating systems for complete graphs is
significantly worse for random chordal graphs.
