Meek Separators and Their Applications in Targeted Causal Discovery
This work addresses the problem of learning partial causal graphs with fewer interventions for researchers and practitioners in fields like medicine or economics, offering incremental improvements through novel algorithmic approaches.
The paper tackles targeted causal discovery by minimizing interventions for subset search and causal matching problems, introducing Meek separators and efficient algorithms that achieve logarithmic approximation with the first known average-case provable guarantees.
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.