PAIR-CI: Calibrated Conditional Independence Testing for Causal Discovery with Incomplete Data
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Statistics. The day in statistics: methods, theory and the inference under them.
Tom: I'm Tom.
Jane: And I'm Jane, here with Lu, Meng and our in-house large language model, Lalam.
Tom: We're looking at the paper: "PAIR-CI: Calibrated Conditional Independence Testing for Causal Discovery with Incomplete Data".
Jane: Here's the gist of the paper. 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 PAIR-CI, a nonparametric CI test that restores calibration by integrating multiple imputation directly into the inferential procedure via a paired permutation design Core Problem and Proposed Solution Conditional independence (CI) testing is the inferential engine of constraint-based methods for causal discovery across the sciences This creates a fundamental problem when data are incomplete: missing values in the conditioning set X prevent direct evaluation of relationships between test variables Imputing missing values before testing is valid under Preprint However, imputing can lead to miscalibration under MNAR and other forms of misspecified imputation, where residual bias in the completed data may introduce spurious associations between test variables that are mistaken for genuine conditional dependence To avoid this miscalibration, PAIR-CI proposes a nonparametric CI test that integrates multiple imputation directly into the inferential procedure via a paired permutation design PAIR-CI compares cross-validated models of Z that differ in access to the candidate variable but receive the same imputed conditioning set, ensuring that any distortion introduced by imputation affects both models identically and thus cancels in their loss difference rather than entering the test statistic Theoretical Guarantees and Calibration PAIR-CI achieves exact asymptotic size for the internal null Z ⊥⊥ Y Xˆ under four relatively undemanding assumptions (Proposition 2) The paired design cancels imputation bias by feeding both models the same imputed conditioning set, while caching further reduces residual bias κ by absorbing the test variables’ correlation with Xmiss into Xˆ Under Assumptions (A1)–(A4), and applying Theorem 4 to the combined variance estimator, PAIR-CI has exact asymptotic size: P(tCI > tα,ν) → α The unified inference under cross-validation and multiple imputation is achieved by nesting the provably consistent within-imputation estimator developed by Bayle et al.
2020: inside Rubin’s rules This combined estimator delivers asymptotically valid inference with correct size and power—to our knowledge, the first formal result connecting cross-validation and multiple imputation Empirical Performance Across Mechanisms In simulations spanning multiple data-generating processes (DGPs), sample sizes, and missingness mechanisms, existing imputation-based CI tests exhibit false positive rates of 28–45% under MNAR whereas PAIR-CI averages below the nominal level The resulting gains in graph recovery grow with scale, rising from an 8% reduction in structural Hamming distance (SHD) on 10-variable graphs to 15% on 30-variable equivalents and up to 44% on the 56-variable HAILFINDER network Standalone performance shows that PAIR-CI maintains an average false positive rate ≤ 4% across all missingness conditions Only one DGP × mechanism cell slightly exceeds the nominal level at 7%—still an order of magnitude below the 41–59% inflation observed for FZ-single, FZ-Rubin, GCM, and KCI Graph Recovery and Robustness In synthetic graph recovery experiments, PAIR-CI yields SHD 11 with nonlinear edges under all mechanisms At p = 56 in the HAILFINDER weather forecasting network, PAIR-CI delivers SHD 62.5–65.5 across all three missingness mechanisms The performance of PAIR-CI is stable across MAR, MNAR, and mixed mechanisms for all graph sizes The distinctive feature of PAIR-CI at this scale is perfect precision: conservatism manifests as missing edges rather than spurious ones PAIR-CI addresses a key gap in constraint-based causal discovery, achieving false positive rates near nominal levels across missingness mechanisms, edge types, and graph sizes The primary cost is reduced power relative to well-specified parametric tests when their assumptions hold—that is, when relationships are approximately linear and missingness is either MCAR or MAR Where parametric assumptions are violated or the missingness mechanism is unverifiable, PAIR-CI’s calibration advantage outweighs its loss in power, opening a performance gap that widens with scale The paper concludes that PAIR-CI requires—among other, less demanding conditions—that the imputation model converge to the true conditional distribution of missing values The paired design’s κ-cancellation is robust in these settings because cached imputation includes Y and Z in the imputer, allowing the linear MICE model to absorb information about Xmiss into Xˆ Practitioners working with strongly nonlinear DGPs and adversarial missingness should verify calibration empirically prior to deployment References Bruce Abramson, John Brown, Ward Edwards, Allan Murphy, and Robert L Winkler.
Jane: HAILFINDER: A Bayesian System for Forecasting Severe Weather.
Tom: International Journal of Forecasting, 12(1):57–71, 1996 John Barnard and Donald B Rubin.
Title and authors: Tom: Moving on to the authors and title, we have Thomas S. Robinson from London School of Economics and Political Science and Ranjit Lall from Oxford University. Their work, "PAIR-CI: Calibrated Conditional Independence Testing for Causal Discovery with Incomplete Data," is a big name in this area >
Jane: It sounds very technical, but the main idea is that they are building a nonparametric test for conditional independence that handles missing data without getting biased by it >
Lu: The paper focuses on how to make these tests robust when we can't just assume simple missingness like MCAR or MAR, because those assumptions often lead to miscalibration in standard methods >
Meng: So they are trying to build a tool that works even when the missing data mechanism is more complex, like MNAR, where the data is not just randomly missing >
Tom: That’s right. They want to avoid those spurious edges in your causal graph that come from imputation error propagating through the structure >
Jane: It suggests a new way of looking at conditional independence testing where the multiple imputation isn't just a preprocessing step, but part of the inferential procedure itself >
Lu: It’s about comparing models under different access to variables while keeping the imputed set consistent, which is a clever way to control for that bias >
Tom: So, instead of just fixing the data first and hoping it works, they are building a test that's inherently designed to be stable against imputation errors >
Jane: It’s about making sure the test statistic doesn't get skewed by the missing values we had to guess >
The paper's summary: Jane: Now let’s look at what the paper actually summarizes. They are proposing PAIR-CI, which is this nonparametric conditional independence test that uses a paired permutation design to integrate multiple imputation directly into the testing >
Tom: Basically, they compare cross-validated models of Z that differ only by whether they can see the candidate variable but both receive the same imputed conditioning set >
Lu: They evaluate the difference in out-of-sample loss between these two models, and then average that across different folds and imputations using Rubin’s rules to get a combined test statistic >
Meng: That sounds like a lot of computation. What's the practical cost of running this whole procedure compared to just running a standard PC algorithm on complete data?
Tom: The paper claims they achieve exact asymptotic size for the internal null, which means if your hypothesis is true, the test has that exact probability of rejecting it as you increase your sample size >
Jane: And they claim this unified inference—combining cross-validation and multiple imputation—delivers asymptotically valid inference with correct size and power, which is a first for connecting those two things formally >
Lu: It’s about showing that you can get asymptotically exact results even when dealing with the uncertainty from both the imputation process and the cross-validation error simultaneously >
Meng: So, if this works as claimed, does it mean we can deploy this on massive datasets where running standard CI tests is too slow?
Tom: The paper suggests it’s particularly useful because when missingness is not well-specified, like MNAR, existing imputation-based tests have been showing false positive rates up to forty-five percent > <ref:2605.04838#pg3>
The paper's improvements: Jane: The authors highlight several key improvements. First, they show that their method achieves a false positive rate near nominal levels across all missingness mechanisms and edge types, which is a huge win for reliability >
Lu: They see gains in graph recovery that grow with scale; it starts at an eight percent reduction in structural Hamming distance on ten-variable graphs and goes up to forty-four percent on the HAILFINDER weather network with fifty-six variables >
Meng: Forty-four percent? That’s significant. But what about when the imputation quality is poor, like if we use mean or marginal imputation instead of a full MICE process?
Tom: When imputation quality degrades, they report that the false positive rate inflates substantially, reaching twenty-nine point zero percent under MAR and forty-three point three percent under MNAR >
Jane: That part is important. The authors are clear that when you use simpler imputation methods, the false positive rate shoots up because those methods don't cancel out the imputation bias properly >
Lu: So, in a practical sense, it means you have to be careful about which imputation method you choose; it’s load-bearing for calibration >
Meng: So the paper isn't just proposing a black box solution; it’s telling us we need to verify the quality of our imputation models before we trust the final result >
Tom: Right. They are saying that if your imputation model converges to the true distribution of missing values, then this paired design’s bias cancellation is robust >
Conclusion: Jane: So, to wrap up, PAIR-CI addresses the fundamental problem of miscalibration in constraint-based causal discovery by integrating multiple imputation directly into the test via a paired permutation design >
Lu: It gives us a unified framework where we can get asymptotically exact inference with correct size and power when combining cross-validation and multiple imputation >
Tom: The big implication here is that for researchers dealing with strongly nonlinear data or adversarial missingness, PAIR-CI’s calibration advantage outweighs any loss in power compared to simpler parametric tests if those assumptions are violated >
Meng: If you're running something at scale, the gain in structural Hamming distance reduction can be up to forty-four percent on networks like HAILFINDER, which suggests this could be a useful tool for large-scale graph recovery >
Lalam: I’m confident that the paper confirms what we see in simulations—that standalone performance stays below four percent false positive rate across all missingness conditions >
Tom: So, in short, PAIR-CI is a nonparametric CI test that achieves near nominal false positive rates even when imputation error introduces spurious conditional dependence >
Jane: It requires the authors to verify that their imputation model converges to the true conditional distribution of missing values for their strongest claims to hold >
Thomas S. Robinson, Ranjit Lall
London School of Economics and Political Science · University of Oxford
stat.ME, cs.LG, stat.ML
Submitted: 2026-05-06
Updated: 2026-11-16
Comments: Camera-ready version, accepted at NeurIPS 2026. 64 pages. Code and replication materials: https://github.com/tsrobinson/pair-ci (doi:10.5281/zenodo.23976940)
License: http://creativecommons.org/licenses/by/4.0/
Importance score: 95/100
The gist: The standard constraint-based paradigm for causal discovery with incomplete data—impute first, test second—is frequently miscalibrated…
Key concepts
- Conditional Independence (CI) Testing
- This is the statistical engine used in constraint-based causal discovery methods to determine if two variables are related given a set of conditioning variables. When data is incomplete, standard CI tests become unreliable because missing values prevent direct evaluation of these relationships.
- Multiple Imputation
- This technique involves creating several complete datasets by filling in missing values based on statistical models. The challenge is that imputing first and then testing can introduce errors that falsely suggest a relationship between variables, miscalibrating the test results.
- Paired Permutation Design
- PAIR-CI uses this design to fix the calibration problem. It compares two models of the missing variable Z under cross-validation, ensuring both models receive the exact same imputed conditioning set. This forces imputation bias to cancel out in their loss difference, leading to a more accurate test statistic.
Terminology
Summary
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
PAIR-CI, a nonparametric CI test that restores calibration by integrating multiple imputation directly into the inferential procedure via a paired permutation design
Core Problem and Proposed Solution
Conditional independence (CI) testing is the inferential engine of constraint-based methods for causal discovery across the sciences This creates a fundamental problem when data are incomplete: missing values in the conditioning set X prevent direct evaluation of relationships between test variables Imputing missing values before testing is valid under Preprint However, imputing can lead to miscalibration under MNAR and other forms of misspecified imputation, where residual bias in the completed data may introduce spurious associations between test variables that are mistaken for genuine conditional dependence
To avoid this miscalibration, PAIR-CI proposes a nonparametric CI test that integrates multiple imputation directly into the inferential procedure via a paired permutation design PAIR-CI compares cross-validated models of Z that differ in access to the candidate variable but receive the same imputed conditioning set, ensuring that any distortion introduced by imputation affects both models identically and thus cancels in their loss difference rather than entering the test statistic
Theoretical Guarantees and Calibration
PAIR-CI achieves exact asymptotic size for the internal null Z ⊥⊥ Y Xˆ under four relatively undemanding assumptions (Proposition 2) The paired design cancels imputation bias by feeding both models the same imputed conditioning set, while caching further reduces residual bias κ by absorbing the test variables’ correlation with Xmiss into Xˆ Under Assumptions (A1)–(A4), and applying Theorem 4 to the combined variance estimator, PAIR-CI has exact asymptotic size: P(tCI > tα,ν) → α
The unified inference under cross-validation and multiple imputation is achieved by nesting the provably consistent within-imputation estimator developed by Bayle et al. [2020] inside Rubin’s rules This combined estimator delivers asymptotically valid inference with correct size and power—to our knowledge, the first formal result connecting cross-validation and multiple imputation
Empirical Performance Across Mechanisms
In simulations spanning multiple data-generating processes (DGPs), sample sizes, and missingness mechanisms, existing imputation-based CI tests exhibit false positive rates of 28–45% under MNAR whereas PAIR-CI averages below the nominal level The resulting gains in graph recovery grow with scale, rising from an 8% reduction in structural Hamming distance (SHD) on 10-variable graphs to 15% on 30-variable equivalents and up to 44% on the 56-variable HAILFINDER network
Standalone performance shows that PAIR-CI maintains an average false positive rate ≤ 4% across all missingness conditions Only one DGP × mechanism cell slightly exceeds the nominal level at 7%—still an order of magnitude below the 41–59% inflation observed for FZ-single, FZ-Rubin, GCM, and KCI
Graph Recovery and Robustness
In synthetic graph recovery experiments, PAIR-CI yields SHD 11 with nonlinear edges under all mechanisms At p = 56 in the HAILFINDER weather forecasting network, PAIR-CI delivers SHD 62.5–65.5 across all three missingness mechanisms
The performance of PAIR-CI is stable across MAR, MNAR, and mixed mechanisms for all graph sizes The distinctive feature of PAIR-CI at this scale is perfect precision: conservatism manifests as missing edges rather than spurious ones
Conclusion
PAIR-CI addresses a key gap in constraint-based causal discovery, achieving false positive rates near nominal levels across missingness mechanisms, edge types, and graph sizes The primary cost is reduced power relative to well-specified parametric tests when their assumptions hold—that is, when relationships are approximately linear and missingness is either MCAR or MAR Where parametric assumptions are violated or the missingness mechanism is unverifiable, PAIR-CI’s calibration advantage outweighs its loss in power, opening a performance gap that widens with scale
The paper concludes that PAIR-CI requires—among other, less demanding conditions—that the imputation model converge to the true conditional distribution of missing values The paired design’s κ-cancellation is robust in these settings because cached imputation includes Y and Z in the imputer, allowing the linear MICE model to absorb information about Xmiss into Xˆ Practitioners working with strongly nonlinear DGPs and adversarial missingness should verify calibration empirically prior to deployment
References
Bruce Abramson, John Brown, Ward Edwards, Allan Murphy, and Robert L Winkler. HAILFINDER: A Bayesian System for Forecasting Severe Weather. p. 9 References
Bruce Abramson, John Brown, Ward Edwards, Allan Murphy, and Robert L Winkler. HAILFINDER:
A Bayesian System for Forecasting Severe Weather.Where the paper says it
John Barnard and Donald B Rubin. Small-sample degrees of freedom with multiple imputation. p. 9 John Barnard and Donald B Rubin. Small-sample degrees of freedom with multiple imputation.Where the paper says it
Pierre Bayle, Alexandre Bayle, Lucas Janson, and Lester Mackey. Cross-validation confidence intervals for test error. p. 9 Pierre Bayle, Alexandre Bayle, Lucas Janson, and Lester Mackey. Cross-validation confidence
intervals for test error.Where the paper says it
Ingo A Beinlich, Henri Jacques Suermondt, R Martin Chavez, and Gregory F Cooper. The ALARM Monitoring System: A Case Study with Two Probabilistic Inference Techniques for Belief Networks. p. 9 Ingo A Beinlich, Henri Jacques Suermondt, R Martin Chavez, and Gregory F Cooper. The ALARM
Monitoring System: A Case Study with Two Probabilistic Inference Techniques for Belief Networks. The ALARM
Monitoring System: A Case Study with Two Probabilistic Inference Techniques for Belief Networks. In Proceedings of the Second European Conference on Artificial Intelligence in Medicine
(AIME), pages 247–256.Where the paper says it
Where the paper says it
Alexis Bellot and Mihaela van der Schaar. Conditional independence testing using generative adversarial networks. p. 9 Alexis Bellot and Mihaela van der Schaar. Conditional independence testing using generative
adversarial networks.Where the paper says it
Thomas B Berrett, Yi Wang, Rina Foygel Barber, and Richard J Samworth. The conditional permutation test for independence while controlling for confounders. p. 9 Thomas B Berrett, Yi Wang, Rina Foygel Barber, and Richard J Samworth. The conditional
permutation test for independence while controlling for confounders.Where the paper says it
Alexander Gain and Ilya Shpitser. Structure learning under missing data. p. 0 Widely used algorithms
such as PC (Peter–Clark), FCI (Fast Causal Inference), and their variants reduce the problem of
learning causal structure to a sequence of CI tests over variable pairs with progressively expanding
conditioning sets [Spirtes et al. This creates a fundamental problem when data are incomplete:
missing values in the conditioning set X prevent direct evaluation of relationships between test
variables.Where the paper says it
Erdun Gao, Ignavier Ng, Mingming Gong, Li Shen, Wei Huang, Tongliang Liu, Kun Zhang, and Howard Bondell. MissDAG: Causal discovery in the presence of missing data with continuous additive noise models. p. 9 Erdun Gao, Ignavier Ng, Mingming Gong, Li Shen, Wei Huang, Tongliang Liu, Kun Zhang, and
Howard Bondell. MissDAG: Causal discovery in the presence of missing data with continuous
additive noise models.Where the paper says it
Pierre Geurts, Damien Ernst, and Louis Wehenkel. Extremely randomized trees. p. 9 Pierre Geurts, Damien Ernst, and Louis Wehenkel. Extremely randomized trees.Where the paper says it
John W Graham. Missing data analysis: Making it work in the real world. p. 9 John W Graham. Missing data analysis: Making it work in the real world.Where the paper says it
Markus Kalisch and Peter Bühlmann. Estimating high-dimensional directed acyclic graphs with the PC-algorithm. p. 9 Markus Kalisch and Peter Bühlmann. Estimating high-dimensional directed acyclic graphs with the
PC-algorithm.Where the paper says it
Christopher Meek. Causal inference and causal explanation with background knowledge. p. 9 Christopher Meek. Causal inference and causal explanation with background knowledge.Where the paper says it
Karthika Mohan and Judea Pearl. Graphical models for processing missing data. p. 9 Karthika Mohan and Judea Pearl. Graphical models for processing missing data.Where the paper says it
Kun Zhang, Jonas Peters, Dominik Janzing, and Bernhard Schölkopf. Kernel-based conditional independence test and application in causal discovery. p. 0 lall@politics. uk
Abstract
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. lall@politics. uk
Abstract
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.Where the paper says it
Where the paper says it
Alexandre B Tsybakov. Introduction to Nonparametric Estimation. p. 3 2The neighborhood size is knn = max(2, ⌊n
2/(d+2)⌋), where d = |X|. This is the minimax-optimal bandwidth for
nonparametric density estimation in dimension d [Tsybakov, 2009], ensuring that U | Xˆ converges to Y | Xˆ at the rate
required by the exchangeability argument in Proposition 2. 2The neighborhood size is knn = max(2, ⌊n
2/(d+2)⌋), where d = |X|. This is the minimax-optimal bandwidth for
nonparametric density estimation in dimension d [Tsybakov, 2009], ensuring that U | Xˆ converges to Y | Xˆ at the rate
required by the exchangeability argument in Proposition 2. In Proceedings of the Second European Conference on Artificial Intelligence in Medicine
(AIME), pages 247–256. Springer, 1989. In Proceedings of the Second European Conference on Artificial Intelligence in Medicine
(AIME), pages 247–256. Springer, 1989.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Ruibo Tu, Cheng Zhang, Paul Ackermann, Karthika Mohan, Hedvig Kjellström, and Kun Zhang. Causal discovery in the presence of missing data. p. 9 Erdun Gao, Ignavier Ng, Mingming Gong, Li Shen, Wei Huang, Tongliang Liu, Kun Zhang, and
Howard Bondell. MissDAG: Causal discovery in the presence of missing data with continuous
additive noise models. The ALARM
Monitoring System: A Case Study with Two Probabilistic Inference Techniques for Belief Networks. In Proceedings of the Second European Conference on Artificial Intelligence in Medicine
(AIME), pages 247–256.Where the paper says it
Where the paper says it
Stef Van Buuren and Karin Groothuis-Oudshoorn. mice: Multivariate imputation by chained equations in R. p. 2 2 relaxes
this restriction for computational tractability, with the added benefit of improved calibration. Our
default imputation method is MICE (Multiple Imputation by Chained Equations) with Bayesian ridge
regression [Van Buuren and Groothuis-Oudshoorn, 2011].Where the paper says it
David S Watson and Marvin N Wright. Testing conditional independence in supervised learning algorithms. p. 0 1 Introduction
Conditional independence (CI) testing—determining whether Z ⊥⊥ Y | X—is the inferential engine
of constraint-based methods for causal discovery across the sciences. Widely used algorithms
such as PC (Peter–Clark), FCI (Fast Causal Inference), and their variants reduce the problem of
learning causal structure to a sequence of CI tests over variable pairs with progressively expanding
conditioning sets [Spirtes et al.Where the paper says it
Janine Witte, Ronja Foraita, and Vanessa Didelez. Multiple imputation and test-wise deletion for causal discovery with incomplete cohort data. p. 2 Incomplete data in causal discovery. Test-wise deletion [Tu et al.Where the paper says it
Kun Zhang, Jonas Peters, Dominik Janzing, and Bernhard Schölkopf. Kernel-based conditional independence test and application in causal discovery. In Proceedings of the Twenty-Seventh Conference on Uncertainty in Artificial Intelligence, UAI’11, page 804–813, Arlington, Virginia, USA, 2011
Donald B Rubin. Multiple Imputation for Nonresponse in Surveys. p. 0 uk
Abstract
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.Where the paper says it
Erwan Scornet, Gérard Biau, and Jean-Philippe Vert. Consistency of random forests. p. 3 In Step 2, any supervised learner satisfying modest stability conditions (Theorem 4) can be used to train the full and partial models. In subsequent validation experiments,
we implement two variants of PAIR-CI: a general variant based on random forests, which meet
these conditions and exhibit universal consistency [Scornet et al. In subsequent validation experiments,
we implement two variants of PAIR-CI: a general variant based on random forests, which meet
these conditions and exhibit universal consistency [Scornet et al. , 2015]; and a fast variant based on
ExtraTrees [Geurts et al.Where the paper says it
Where the paper says it
Rajat Sen, Ananda Theertha Suresh, Karthikeyan Shanmugam, Alexandros G Dimakis, and Sanjay Shakkottai. Model-powered conditional independence test. p. 0 lall@politics. uk
Abstract
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.Where the paper says it
Rajen D Shah and Jonas Peters. The hardness of conditional independence testing and the generalised covariance measure. p. 2 ,
2011] and the Randomized Conditional Independence Test [RCIT; Strobl et al. , 2019] assess CI by
embedding variables into high-dimensional feature spaces, while the Generalized Covariance Measure
[GCM; Shah and Peters, 2020] measures dependence between regression errors. 447
post-nonlinear (13. 7%) DGPs, where a Bayesian ridge imputer is misspecified, FZ-Rubin’s MAR
false positive rate increases monotonically with n, confirming that pooling test statistics does not
restore calibration when bias enters through the imputed conditioning set (Proposition 1).Where the paper says it
Where the paper says it
Peter Spirtes, Clark Glymour, and Richard Scheines. Causation, Prediction, and Search. p. 4 [2020, Theorem 3], which
holds for random forests with bounded loss [Scornet et al. , 2015]; (A5) universal consistency: the
learner converges to the Bayes-optimal prediction function for any distribution as n → ∞; and
(A6) faithfulness: every CI relation in the observed distribution corresponds to a d-separation in the
true DAG.Where the paper says it
Eric V Strobl, Kun Zhang, and Shyam Visweswaran. Approximate kernel-based conditional independence tests for fast non-parametric causal discovery. p. 0 1 Introduction
Conditional independence (CI) testing—determining whether Z ⊥⊥ Y | X—is the inferential engine
of constraint-based methods for causal discovery across the sciences. Widely used algorithms
such as PC (Peter–Clark), FCI (Fast Causal Inference), and their variants reduce the problem of
learning causal structure to a sequence of CI tests over variable pairs with progressively expanding
conditioning sets [Spirtes et al.Where the paper says it
Alexandre B Tsybakov. Introduction to Nonparametric Estimation. Springer Series in Statistics. Springer, New York, NY, 2009 doi: 10. p. 9 In Proceedings of the Second European Conference on Artificial Intelligence in Medicine
(AIME), pages 247–256. Springer, 1989.Where the paper says it
Pruning redundant reasoning tokens
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
PAIR-CI restores calibration by integrating multiple imputation directly into the inferential procedure via a paired permutation design
How the training signal is built
The PAIR-CI testing procedure involves four steps: 1) Multiple imputation, 2) Cross-validated model comparison, 3) Loss comparison, and 4) Combined test statistic Step 2 involves comparing two models of Z on the remaining K − 1 folds: a full model gˆZYkm and a partial model gˆZUkm Step 3 evaluates the difference in out-of-sample loss: µˆkm = lgˆZUkm - lgˆZYkm (1)
The combined test statistic T is estimated by averaging across folds and imputations, combining within-imputation cross-validation variance W¯ with between-imputation variation B using Rubin’s rules The resulting combined estimator delivers asymptotically exact inference with correct size and power—to our knowledge, the first formal result connecting cross-validation and multiple imputation
Where the gains come from
The gains in graph recovery grow with scale, rising from an 8% reduction in structural Hamming distance (SHD) on 10-variable graphs to 15% on 30-variable equivalents and up to 44% on the 56-variable HAILFINDER network PAIR-CI overtakes test-wise deletion by p = 30 (SHD 53 vs. 58) as conditioning sets grow larger and partial correlations degrade in higher dimensions
The paired comparison cancels imputation bias by feeding both models the same Xˆ, causing imputation-induced bias to enter both losses identically and cancel in the difference This cancellation occurs when error varies randomly across observations—as with MICE under MNAR—but fails when it is systematic, as with mean or marginal imputation The residual κ is thus controlled by the differential dependence of Y and Z on δ
Imputation Degradation
When imputation quality is degraded—such as using mean or marginal imputation—the false positive rate inflates substantially, reaching 29.0% under MAR and 43. p. 1 MCAR or missing at random (MAR) but can lead to miscalibration under MNAR and other forms of
misspecified imputation: residual bias in the completed data may introduce spurious associations
between test variables that are mistaken for genuine conditional dependence. 1 We formalize this
bias in Proposition 1: miscalibration is not a small-sample artifact but an asymptotic inevitability
whenever imputation error induces residual conditional dependence between test variables.Where the paper says it
PAIR-CI reliably detects moderate-to-strong conditional dependencies (signal ≥ 0.
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Integrated Causal Discovery Oracle for Constraint-Based Methods The improved system can serve as a drop-in oracle for algorithms like FCI by incorporating PAIR-CI to recover true Directed Acyclic Graphs (DAGs) under incomplete conditioning sets with calibration guarantees.
-
Unified Variance Estimation Framework The system can provide a provably consistent variance estimator that jointly accounts for uncertainty arising from crossvalidation and multiple imputation, yielding asymptotically valid inference even when combining these two inferential frameworks.
-
Robust Causal Discovery Across Missingness Mechanisms The system can achieve false positive rates near nominal levels across all missingness mechanisms (MAR, MNAR, mixed) and edge types (linear/nonlinear), significantly outperforming existing imputation-based CI tests which exhibit false positive rates of 28–45% under MNAR.
-
Enhanced Structural Hamming Distance Reduction The system can reduce structural Hamming distance by up to 44% on complex networks like the 56-variable HAILFINDER network when integrated into the PC algorithm, with gains growing with causal graph size and nonlinearity.
-
Improved Inference Under Misspecification The system restores calibration by ensuring that
any consistent conditional independence (CI) test rejects a true null with probability approaching 1 when imputation error induces spurious conditional dependence
is avoided by forcing imputation error tocancel in their loss difference rather than contaminate the test statistic.
-
Principled Inference with Correct Size and Power Estimation The system enables principled inference by combining cross-validation and multiple imputation via a variance estimator that delivers
asymptotically exact inference with correct size and power,
improving power by 9–10 percentage points at intermediate effect sizes.
Abstract
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, so that imputation error cancels in their loss difference rather than contaminating the test statistic. A variance estimator that nests a provably consistent cross-validation estimator inside Rubin's rules yields inference that is asymptotically valid in the many-imputation limit and conservative by a derived, sign-definite mechanism -- to our knowledge, the first formal result combining 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's pooled rate is at most 3.6%, exceeding the nominal 5% only in some cells with five or more conditioning variables. Integrated into the PC algorithm, PAIR-CI is stable across functional forms and missingness mechanisms, whereas every parametric pipeline we consider, including missing-value PC, has a regime in which it fails badly. On nonlinear network benchmarks it reduces structural Hamming distance by 18% (ALARM) and 11% (HAILFINDER) relative to missing-value PC and by 31-48% relative to test-wise deletion and imputation-based Fisher- Z pipelines, while attaining the highest skeleton F1; when relationships are linear, a well-specified parametric pipeline remains preferable.
Related papers
- Learning Robust Treatment Rules for Censored Data
- Neural Estimation of Summary Statistics for Simulation-Based Inference with Non-Asymptotic Guarantees
- Spectral divide-and-conquer MCMC for long stationary time series
- Improving the Efficiency of Subgroup Analysis in Randomized Controlled Trials with TMLE
- Personalized Federated Vector Autoregression with Personalization Diversity
- Doubly Robust and Efficient Calibration of Prediction Sets for Right-Censored Time-to-Event Outcomes