# Meek Separators and Their Applications in Targeted Causal Discovery

arXiv: https://arxiv.org/abs/2310.20075 · HTML: https://mlsanity.com/paper/2310.20075/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 36 references that are in the map.
- First posted on arXiv 30 Oct 2023.

## Builds on (most cited first, 14 of 14)

- [Causal Inference and Causal Explanation with Background Knowledge](https://mlsanity.com/paper/1302.4972/) (2013)
- [Invariant Causal Prediction for Nonlinear Models](https://mlsanity.com/paper/1706.08576/) (2017)
- [Characterizing and Learning Equivalence Classes of Causal DAGs under Interventions](https://mlsanity.com/paper/1802.06310/) (2018)
- [Learning Causal Graphs with Small Interventions](https://mlsanity.com/paper/1511.00041/) (2015)
- [ABCD-Strategy: Budgeted Experimental Design for Targeted Causal Structure Discovery](https://mlsanity.com/paper/1902.10347/) (2019)
- [Causal Structure Learning: a Combinatorial Perspective](https://mlsanity.com/paper/2206.01152/) (2022)
- [Cost-Optimal Learning of Causal Graphs](https://mlsanity.com/paper/1703.02645/) (2017)
- [A Transformational Characterization of Equivalent Bayesian Network Structures](https://mlsanity.com/paper/1302.4938/) (2013)
- [Budgeted Experiment Design for Causal Structure Learning](https://mlsanity.com/paper/1709.03625/) (2017)
- [Active Structure Learning of Causal DAGs via Directed Clique Tree](https://mlsanity.com/paper/2011.00641/) (2020)
- [Active Invariant Causal Prediction: Experiment Selection through Stability](https://mlsanity.com/paper/2006.05690/) (2020)
- [Verification and search algorithms for causal DAGs](https://mlsanity.com/paper/2206.15374/) (2022)
- [Matching a Desired Causal State via Shift Interventions](https://mlsanity.com/paper/2107.01850/) (2021)
- [Subset verification and search algorithms for causal DAGs](https://mlsanity.com/paper/2301.03180/) (2023)

## Built on by (most cited first, 3 of 3)

- [Causal Discovery with Fewer Conditional Independence Tests](https://mlsanity.com/paper/2406.01823/) (2024)
- [SNAP: Sequential Non-Ancestor Pruning for Targeted Causal Effect Estimation With an Unknown Graph](https://mlsanity.com/paper/2502.07857/) (2025)
- [Causal Structure and Representation Learning with Biomedical Applications](https://mlsanity.com/paper/2511.04790/) (2025)

## Abstract (arXiv)

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.