# PAIR-CI: Calibrated Conditional Independence Testing for Causal Discovery with Incomplete Data

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 28 references that are in the map.
- First posted on arXiv 6 May 2026.

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

- [Causal Inference and Causal Explanation with Background Knowledge](https://mlsanity.com/paper/1302.4972/) (2013)
- [Consistency of random forests](https://mlsanity.com/paper/1405.2881/) (2014)
- [Approximate Kernel-based Conditional Independence Tests for Fast Non-Parametric Causal Discovery](https://mlsanity.com/paper/1702.03877/) (2017)
- [Graphical Models for Processing Missing Data](https://mlsanity.com/paper/1801.03583/) (2018)
- [Causal Discovery in the Presence of Missing Data](https://mlsanity.com/paper/1807.04010/) (2018)
- [Model-Powered Conditional Independence Test](https://mlsanity.com/paper/1709.06138/) (2017)
- [Conditional Independence Testing using Generative Adversarial Networks](https://mlsanity.com/paper/1907.04068/) (2019)
- [Cross-validation Confidence Intervals for Test Error](https://mlsanity.com/paper/2007.12671/) (2020)
- [Testing Conditional Independence in Supervised Learning Algorithms](https://mlsanity.com/paper/1901.09917/) (2019)
- [MissDAG: Causal Discovery in the Presence of Missing Data with Continuous Additive Noise Models](https://mlsanity.com/paper/2205.13869/) (2022)
- [Multiple imputation and test-wise deletion for causal discovery with incomplete cohort data](https://mlsanity.com/paper/2108.13331/) (2021)

## Abstract (arXiv)

The standard constraint-based paradigm for causal discovery with incomplete data -- impute first, test second -- is frequently miscalibrated: any consistent conditional independence (CI) test rejects a true null with probability approaching 1 when imputation error induces spurious conditional dependence. We introduce PAIR-CI, a nonparametric CI test that restores calibration by integrating multiple imputation directly into the inferential procedure via a paired permutation design. PAIR-CI compares cross-validated models that include and exclude the candidate variable while receiving the same imputed conditioning set, forcing imputation error to cancel in their loss difference rather than contaminate the test statistic. A provably consistent variance estimator jointly accounts for uncertainty arising from cross-validation and multiple imputation -- to our knowledge, the first formal unification of these two inferential frameworks. In simulations, existing imputation-based CI tests exhibit false positive rates of 28--45% when data are missing not at random (MNAR), whereas PAIR-CI averages below the nominal 5% level across data-generating processes and missingness mechanisms. These gains are largest in nonlinear settings and grow with causal graph size: when integrated into the PC algorithm, PAIR-CI reduces structural Hamming distance by 8% on 10-variable nonlinear graphs, 15% on 30-variable equivalents, and up to 44% on the 56-variable HAILFINDER network, with stable performance in all settings.