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.

学习因果结构及定向数据是一个根本性问题，具有广泛的应用领域。通过引入 Meek 分隔子，我们介绍了一种寻找具有小规模 Meek 分隔子的高效算法，用于部分搜索和因果匹配问题，从而实现对两个问题的对数逼近，并提供了首个已知的平均情况可证实保证。这为解决其他各种应用中出现的有目标因果结构学习问题的近乎最优方法的设计提供了可能性。