📊 statistics

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

This paper introduces PAIR-CI, a nonparametric conditional independence test that integrates multiple imputation directly into the inferential procedure via a paired permutation design to eliminate spurious dependencies caused by imputation error, thereby restoring statistical calibration and significantly improving causal discovery accuracy in datasets with missing values, particularly under nonlinear and missing-not-at-random conditions.

Original authors: Thomas S. Robinson, Ranjit Lall

Published 2026-05-07

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Thomas S. Robinson, Ranjit Lall

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Problem: The "Broken Puzzle"

Imagine you are trying to figure out how a complex machine works (like a car engine) by looking at its parts. You want to know: Does the spark plug cause the engine to turn over, or is it just the battery?

In data science, this is called Causal Discovery. To solve this, researchers use a method that checks if two parts are independent of each other once you account for a third part. This is called a Conditional Independence (CI) test.

The Catch: Real-world data is messy. Often, parts of the puzzle are missing (like a missing gear in your diagram).

The Old Way: The standard approach is to "guess" (impute) what the missing parts look like first, and then run the test.
The Flaw: The paper argues that this "guess-then-test" method is like trying to solve a puzzle while wearing foggy glasses. If your guess about the missing piece is slightly wrong, it creates a fake connection between parts that aren't actually connected. This leads researchers to draw lines on their map where no lines should exist, creating a false map of how the machine works.

The Solution: PAIR-CI (The "Paired" Approach)

The authors, Thomas Robinson and Ranjit Lall, introduce a new method called PAIR-CI. Instead of guessing the missing pieces and then testing, they change the game entirely.

Think of it like a taste test in a cooking competition:

The Setup: You have a soup (your data) with some missing ingredients. You create several versions of the soup where the missing ingredients are filled in with guesses (this is called "Multiple Imputation").
The Pairing: For every single version of the soup, you run two taste tests side-by-side:
- Test A: A chef tastes the soup with the candidate ingredient (e.g., "Does adding salt change the flavor?").
- Test B: A chef tastes the soup without the candidate ingredient (e.g., "Does the soup taste the same if we pretend salt wasn't there?").
The Magic Trick: Crucially, both chefs are tasting the exact same version of the soup with the exact same guessed ingredients.
- If the "guess" for the missing ingredient was bad (foggy glasses), it affects both chefs equally.
- When you compare the two results, the "bad guess" cancels out. It's like if both chefs are wearing the same foggy glasses; they will both think the soup tastes weird, but when they compare notes, they realize, "Hey, the weirdness is the same for both of us, so it must be the glasses, not the soup."

By comparing the two models directly, PAIR-CI removes the error caused by the missing data guesses, leaving only the true signal.

Why This Matters: The "False Alarm" Problem

The paper ran thousands of simulations to see how well this works.

The Old Way: When data was missing in tricky ways (not just random, but systematic), the old methods sounded the "false alarm" (thinking there was a connection when there wasn't) 28% to 45% of the time. That's like a smoke detector going off every time you toast bread.
PAIR-CI: This new method kept the false alarm rate down to less than 5%, which is the standard goal for scientific tests. It stayed calm and accurate even when the data was messy.

The "Engine" Behind the Scenes

To make this work, the authors had to solve a math problem that no one else had solved before.

The Challenge: Their method involves two types of "noise": the noise from guessing the missing data, and the noise from splitting the data into chunks to test it (cross-validation).
The Fix: They built a new mathematical "ruler" (a variance estimator) that measures both types of noise at the same time. It's like having a single scale that can weigh both the fruit and the basket it's sitting in, giving you the true weight of just the fruit.

Real-World Results

The authors tested this on maps of different sizes:

Small Maps (10 variables): It worked well, slightly better than the old methods.
Medium Maps (30 variables): The advantage grew. The old methods started making many mistakes, while PAIR-CI stayed accurate.
Large Maps (56 variables - The "HAILFINDER" weather network): This is where the new method shined. The old methods were so confused by the missing data that their maps were almost useless. PAIR-CI reduced the errors by 44%.

The Bottom Line

PAIR-CI is a new tool for scientists trying to figure out cause-and-effect relationships when their data has holes in it.

Old Tool: Guess the holes, then test. (Prone to seeing ghosts/connections that aren't there).
New Tool (PAIR-CI): Test two scenarios side-by-side using the same guesses. The errors cancel out, revealing the true truth.

The paper claims this method is more reliable, especially when the data is missing in complex, non-random ways, and it works best when the relationships between variables are complex (non-linear) rather than simple straight lines. It doesn't claim to fix all missing data problems, but it fixes the specific problem of "fake connections" caused by bad guesses in causal discovery.

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

1. Problem Statement

Causal discovery via constraint-based methods (e.g., the PC algorithm) relies fundamentally on a sequence of conditional independence (CI) tests to determine the skeleton and orientation of a causal graph. A critical bottleneck arises when data are incomplete. Standard approaches typically follow an "impute first, test second" paradigm: missing values are imputed, and standard CI tests are applied to the completed data.

The authors identify a fundamental flaw in this paradigm: miscalibration. When imputation models are misspecified (e.g., under Missing Not At Random (MNAR) conditions or when functional forms are incorrect), imputation error induces spurious conditional dependence between test variables. Proposition 1 formalizes that under these conditions, any consistent CI test will asymptotically reject the true null hypothesis with probability approaching 1. This leads to causal graphs populated with spurious edges, which propagate errors through edge orientation rules (Meek's rules), compromising downstream inference. Existing remedies, such as test-wise deletion (sacrificing data and inducing selection bias) or standard multiple imputation combined with Rubin's rules (which fails to correct for bias entering through the conditioning set), do not resolve this structural issue.

2. Methodology: PAIR-CI

The paper introduces PAIR-CI, a nonparametric CI test designed to restore calibration by integrating multiple imputation directly into the inferential procedure via a paired permutation design.

Core Mechanism

The test compares two cross-validated models predicting a target variable $Z$ given a conditioning set $X$ :

Full Model: Predicts $Z$ using $(X, Y)$ .
Partial Model: Predicts $Z$ using $(\hat{X}, U)$ , where $\hat{X}$ is the imputed conditioning set and $U$ is a "placebo" variable.

Key Design Features:

Paired Imputation: Both models receive the exact same imputed conditioning set $\hat{X}$ derived from the same multiple imputation (MICE) process. This ensures that any bias or distortion introduced by the imputation error affects both models identically.
Conditional Permutation: The placebo $U$ is constructed by conditionally permuting $Y$ among its $k$ -nearest neighbors in the $\hat{X}$ -space. This breaks the link between $Y$ and $Z$ given $X$ while preserving the marginal dependence of $Y$ on $X$ .
Loss Difference: The test statistic is the difference in out-of-sample loss (e.g., binary cross-entropy or MSE) between the full and partial models. Because both models share the same imputed $\hat{X}$ , the imputation-induced bias cancels out in the loss difference, preventing it from contaminating the test statistic.
Unified Variance Estimation: The test statistic aggregates loss differences across $K$ cross-validation folds and $M$ imputed datasets. The authors propose a novel variance estimator that nests the provably consistent within-imputation cross-validation variance estimator (Bayle et al., 2020) inside Rubin's rules for between-imputation variation. This accounts for dependence arising from both fold overlap and imputation variation simultaneously.

Theoretical Guarantees

Calibration: Under four mild regularity assumptions (imputation consistency, bounded loss, proper imputation, and learner stability), PAIR-CI achieves exact asymptotic size for the internal null ( $Z \perp\!\!\perp Y \mid \hat{X}$ ).
Robustness to MNAR: The paired design extends calibration to the scientific null ( $Z \perp\!\!\perp Y \mid X$ ) even under MNAR, provided the imputation error varies randomly across observations rather than being systematic.
Consistency: The test is consistent under the alternative hypothesis ( $H_1$ ), with power converging to 1 as sample size increases.
PC Consistency: When used as an oracle within the PC algorithm, PAIR-CI guarantees the recovery of the true Completed Partially Directed Acyclic Graph (CPDAG) under standard faithfulness assumptions.

3. Key Contributions

The paper outlines three principal contributions:

A Calibrated Nonparametric CI Test: PAIR-CI is the first method to integrate multiple imputation, cross-validation, and conditional permutation into a single framework that maintains calibration under misspecification. It achieves an average false positive rate $\le 4\%$ across diverse data-generating processes (DGPs) and missingness mechanisms, whereas existing methods exhibit rates of 28–45% under MNAR.
Unified Variance Estimation: The authors provide the first formal unification of cross-validation and multiple imputation variance estimation. By embedding the Bayle et al. (2020) estimator within Rubin's rules, they derive an asymptotically exact estimator that improves statistical power by 9–10 percentage points at intermediate effect sizes and allows for $K=10$ folds without sacrificing calibration.
Robust Causal Discovery: Empirical results demonstrate that PAIR-CI significantly outperforms baselines in graph recovery, particularly in nonlinear settings and as graph size increases.

4. Experimental Results

The authors validate PAIR-CI through three stages of experimentation:

A. Standalone Performance

In simulations across linear Gaussian, post-nonlinear, and latent confounder DGPs with sample sizes $n \in \{500, 5000\}$ :

False Positive Rates: PAIR-CI maintains an average FPR $\le 4\%$ across all missingness conditions (Complete, MAR, MNAR). In contrast, baselines like FZ-Rubin, GCM, and KCI exhibit FPRs of 28–45% under MNAR.
Power: PAIR-CI achieves $>80\%$ power at signal strengths $\ge 0.6$ and $n \ge 2000$ . While it is less powerful than parametric tests (e.g., Fisher's Z) when assumptions are perfectly met, it avoids the uninformative rejections of miscalibrated tests.

B. Synthetic Graph Recovery

Using the PC algorithm on Erdős–Rényi DAGs ( $p=10, 20, 30$ ):

Nonlinear Edges: PAIR-CI reduces the Structural Hamming Distance (SHD) significantly compared to baselines. The SHD gap widens with graph size: 8% reduction at $p=10$ , 15% at $p=30$ , and up to 44% on the 56-variable HAILFINDER network.
Linear Edges: PAIR-CI matches or exceeds baselines as conditioning sets grow, where partial correlations become less reliable.
Precision-Recall: PAIR-CI exhibits high precision (often 1.0) at the cost of slightly lower recall, avoiding the propagation of spurious edges that plagues other methods.

C. Real-World Benchmarks

ALARM Network ( $p=37$ ): PAIR-CI achieves SHD 22.5–24 (linear) and 31–33.5 (nonlinear), outperforming all constraint-based baselines (SHD 30–62).
HAILFINDER Network ( $p=56$ ): PAIR-CI achieves SHD 62.5–65.5, compared to 103.5–128 for baselines. Notably, complete-case analysis achieves a similar SHD (66) but with an F1 score of 0.0 (empty skeleton), illustrating the "winning by giving up" artifact of aggressive data deletion.

5. Significance and Claims

The paper claims that PAIR-CI addresses a critical gap in automated scientific inference by providing a calibrated approach to causal discovery with incomplete data.

Motivation: The authors argue that the "impute then test" paradigm is structurally flawed under common real-world conditions (MNAR, functional misspecification), leading to unreliable causal graphs.
Scope: The method assumes causal sufficiency (no unobserved confounders) but is agnostic to the specific discovery algorithm, serving as a drop-in oracle for PC or FCI.
Limitations: The authors acknowledge that PAIR-CI trades some power for calibration, particularly in small samples with weak signals or when relationships are strictly linear and missingness is MCAR/MAR (where parametric tests excel). They also note that the method relies on the assumption that imputation error varies randomly; systematic errors (e.g., from mean imputation) can still cause miscalibration.
Conclusion: PAIR-CI offers a principled, nonparametric solution that restores reliability to constraint-based causal discovery in the presence of missing data, with performance gains that scale with graph complexity and nonlinearity.