Meek Separators and Their Applications in Targeted Causal Discovery
Kirankumar Shiragur Jiaqi Zhang Caroline Uhler
Learning causal structures from interventional data is a fundamental problem
with broad applications across various fields. While many previous works have
focused on recovering the entire causal graph, in practice, there are scenarios
where learning only part of the causal graph suffices. This is called
$targeted$ causal discovery. In our work, we focus on two such well-motivated
problems: subset search and causal matching. We aim to minimize the number of
interventions in both cases.
  Towards this, we introduce the $Meek~separator$, which is a subset of
vertices that, when intervened, decomposes the remaining unoriented edges into
smaller connected components. We then present an efficient algorithm to find
Meek separators that are of small sizes. Such a procedure is helpful in
designing various divide-and-conquer-based approaches. In particular, we
propose two randomized algorithms that achieve logarithmic approximation for
subset search and causal matching, respectively. Our results provide the first
known average-case provable guarantees for both problems. We believe that this
opens up possibilities to design near-optimal methods for many other targeted
causal structure learning problems arising from various applications.