Verification and search algorithms for causal DAGs
We study two problems related to recovering causal graphs from interventional
data: (i) $\textit{verification}$, where the task is to check if a purported
causal graph is correct, and (ii) $\textit{search}$, where the task is to
recover the correct causal graph. For both, we wish to minimize the number of
interventions performed. For the first problem, we give a characterization of a
minimal sized set of atomic interventions that is necessary and sufficient to
check the correctness of a claimed causal graph. Our characterization uses the
notion of $\textit{covered edges}$, which enables us to obtain simple proofs
and also easily reason about earlier results. We also generalize our results to
the settings of bounded size interventions and node-dependent interventional
costs. For all the above settings, we provide the first known provable
algorithms for efficiently computing (near)-optimal verifying sets on general
graphs. For the second problem, we give a simple adaptive algorithm based on
graph separators that produces an atomic intervention set which fully orients
any essential graph while using $\mathcal{O}(\log n)$ times the optimal number
of interventions needed to $\textit{verify}$ (verifying size) the underlying
DAG on $n$ vertices. This approximation is tight as $\textit{any}$ search
algorithm on an essential line graph has worst case approximation ratio of
$\Omega(\log n)$ with respect to the verifying size. With bounded size
interventions, each of size $\leq k$, our algorithm gives an $\mathcal{O}(\log
n \cdot \log \log k)$ factor approximation. Our result is the first known
algorithm that gives a non-trivial approximation guarantee to the verifying
size on general unweighted graphs and with bounded size interventions.