mlsanityData to 7 Oct 2026

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

arXiv 2310.17816 ↗First posted 25 Oct 2023stat.ML cs.LG stat.MEcited by 9

Not on the map. Why?

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.

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

Builds on

20 of 89 references.

References · 20

  1. 2013Direct and Indirect Effectscited by 276
  2. 2022Score matching enables causal discovery of nonlinear additive noise modelscited by 108
  3. 2017Conditional independence testing based on a nearest-neighbor estimator of conditional mutual informationcited by 70
  4. 2013Learning Sparse Causal Models is not NP-hardcited by 48
  5. 2020A polynomial-time algorithm for learning nonparametric causal graphscited by 29
  6. 2018A Unified View of Causal and Non-causal Feature Selectioncited by 23
  7. 2013On the definition of a confoundercited by 19
  8. 2021Necessary and sufficient graphical conditions for optimal adjustment sets in causal graphical models with hidden variablescited by 16
  9. 2014Instrumental Variables: An Econometrician's Perspectivecited by 15
  10. 2023On Learning Necessary and Sufficient Causal Graphscited by 14
  11. 2018cuPC: CUDA-based Parallel PC Algorithm for Causal Structure Learning on GPUcited by 12
  12. 2020Causal Feature Selection via Orthogonal Searchcited by 11
8 more
  1. 2021Finding Valid Adjustments under Non-ignorability with Minimal DAG Knowledgecited by 10
  2. 2023Local Causal Discovery for Estimating Causal Effectscited by 10
  3. 2020Local search for efficient causal effect estimationcited by 9
  4. 2016Data-Driven Confounder Selection via Markov and Bayesian Networkscited by 5
  5. 2020Differentiable Causal Backdoor Discoverycited by 5
  6. 2013MIDAS - An Influence Diagram for Management of Mildew in Winter Wheatcited by 4
  7. 2023Shortcuts for causal discovery of nonlinear models by score matchingcited by 4
  8. 2022Feature selection in stratification estimators of causal effects: lessons from potential outcomes, causal diagrams, and structural equationscited by 2

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 4; 2025: 2; 2026: 3.

9 papers.

  1. 2024Local Causal Discovery for Structural Evidence of Direct Discriminationcited by 6
  2. 2024Hybrid Top-Down Global Causal Discovery with Local Search for Linear and Nonlinear Additive Noise Modelscited by 5
  3. 2024Local Learning for Covariate Selection in Nonparametric Causal Effect Estimation with Latent Variablescited by 3
  4. 2025SNAP: Sequential Non-Ancestor Pruning for Targeted Causal Effect Estimation With an Unknown Graphcited by 3
  5. 2025Local Causal Discovery for Statistically Efficient Causal Inferencecited by 2
  6. 2024LoSAM: Local Search in Additive Noise Models with Mixed Mechanisms and General Noise for Global Causal Discoverycited by 1
  7. 2026From Local to Cluster: A Unified Framework for Causal Discovery with Latent Variablescited by 0
  8. 2026Local Covariate Selection for Average Causal Effect Estimation without Pretreatment and Causal Sufficiency Assumptionscited by 0
  9. 2026Integrating Background Knowledge for Scalable Causal Discoverycited by 0