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

summary

The gist

The standard constraint-based paradigm for causal discovery with incomplete data—impute first, test second—is frequently miscalibrated…

In short

PAIR-CI addresses calibration issues in causal discovery when data is incomplete by integrating multiple imputation directly into conditional independence (CI) testing using a paired permutation design. It ensures that imputation errors cancel out in model comparisons, leading to asymptotically exact inference with correct size and power across various missingness mechanisms, significantly improving graph recovery.

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 used across episodes

This episode discusses

The paper

PAIR-CI: Calibrated Conditional Independence Testing for Causal Discovery with Incomplete Data · Read on arXiv

Thomas S. Robinson, Ranjit Lall

London School of Economics and Political Science · University of Oxford

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.

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 >

More episodes

← Home