# Local Discovery by Partitioning: Polynomial-Time Causal Discovery Around Exposure-Outcome Pairs

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 89 references that are in the map.
- First posted on arXiv 25 Oct 2023.

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

- [Direct and Indirect Effects](https://mlsanity.com/paper/1301.2300/) (2013)
- [Score matching enables causal discovery of nonlinear additive noise models](https://mlsanity.com/paper/2203.04413/) (2022)
- [Conditional independence testing based on a nearest-neighbor estimator of conditional mutual information](https://mlsanity.com/paper/1709.01447/) (2017)
- [Learning Sparse Causal Models is not NP-hard](https://mlsanity.com/paper/1309.6824/) (2013)
- [A polynomial-time algorithm for learning nonparametric causal graphs](https://mlsanity.com/paper/2006.11970/) (2020)
- [A Unified View of Causal and Non-causal Feature Selection](https://mlsanity.com/paper/1802.05844/) (2018)
- [On the definition of a confounder](https://mlsanity.com/paper/1304.0564/) (2013)
- [Necessary and sufficient graphical conditions for optimal adjustment sets in causal graphical models with hidden variables](https://mlsanity.com/paper/2102.10324/) (2021)
- [Instrumental Variables: An Econometrician's Perspective](https://mlsanity.com/paper/1410.0163/) (2014)
- [On Learning Necessary and Sufficient Causal Graphs](https://mlsanity.com/paper/2301.12389/) (2023)
- [cuPC: CUDA-based Parallel PC Algorithm for Causal Structure Learning on GPU](https://mlsanity.com/paper/1812.08491/) (2018)
- [Causal Feature Selection via Orthogonal Search](https://mlsanity.com/paper/2007.02938/) (2020)
- [Finding Valid Adjustments under Non-ignorability with Minimal DAG Knowledge](https://mlsanity.com/paper/2106.11560/) (2021)
- [Local Causal Discovery for Estimating Causal Effects](https://mlsanity.com/paper/2302.08070/) (2023)
- [Local search for efficient causal effect estimation](https://mlsanity.com/paper/2007.10014/) (2020)
- [Data-Driven Confounder Selection via Markov and Bayesian Networks](https://mlsanity.com/paper/1604.07212/) (2016)
- [Differentiable Causal Backdoor Discovery](https://mlsanity.com/paper/2003.01461/) (2020)
- [MIDAS - An Influence Diagram for Management of Mildew in Winter Wheat](https://mlsanity.com/paper/1302.3587/) (2013)
- [Shortcuts for causal discovery of nonlinear models by score matching](https://mlsanity.com/paper/2310.14246/) (2023)
- [Feature selection in stratification estimators of causal effects: lessons from potential outcomes, causal diagrams, and structural equations](https://mlsanity.com/paper/2209.11400/) (2022)

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

- [Local Causal Discovery for Structural Evidence of Direct Discrimination](https://mlsanity.com/paper/2405.14848/) (2024)
- [Hybrid Top-Down Global Causal Discovery with Local Search for Linear and Nonlinear Additive Noise Models](https://mlsanity.com/paper/2405.14496/) (2024)
- [Local Learning for Covariate Selection in Nonparametric Causal Effect Estimation with Latent Variables](https://mlsanity.com/paper/2411.16315/) (2024)
- [SNAP: Sequential Non-Ancestor Pruning for Targeted Causal Effect Estimation With an Unknown Graph](https://mlsanity.com/paper/2502.07857/) (2025)
- [Local Causal Discovery for Statistically Efficient Causal Inference](https://mlsanity.com/paper/2510.14582/) (2025)
- [LoSAM: Local Search in Additive Noise Models with Mixed Mechanisms and General Noise for Global Causal Discovery](https://mlsanity.com/paper/2410.11759/) (2024)
- [From Local to Cluster: A Unified Framework for Causal Discovery with Latent Variables](https://mlsanity.com/paper/2604.22416/) (2026)
- [Local Covariate Selection for Average Causal Effect Estimation without Pretreatment and Causal Sufficiency Assumptions](https://mlsanity.com/paper/2605.21548/) (2026)
- [Integrating Background Knowledge for Scalable Causal Discovery](https://mlsanity.com/paper/2607.10456/) (2026)

## Abstract (arXiv)

Causal discovery is crucial for causal inference in observational studies, as it can enable the identification of valid adjustment sets (VAS) for unbiased effect estimation. However, global causal discovery is notoriously hard in the nonparametric setting, with exponential time and sample complexity in the worst case. To address this, we propose local discovery by partitioning (LDP): a local causal discovery method that is tailored for downstream inference tasks without requiring parametric and pretreatment assumptions. LDP is a constraint-based procedure that returns a VAS for an exposure-outcome pair under latent confounding, given sufficient conditions. The total number of independence tests performed is worst-case quadratic with respect to the cardinality of the variable set. Asymptotic theoretical guarantees are numerically validated on synthetic graphs. Adjustment sets from LDP yield less biased and more precise average treatment effect estimates than baseline discovery algorithms, with LDP outperforming on confounder recall, runtime, and test count for VAS discovery. Notably, LDP ran at least 1300x faster than baselines on a benchmark.