Source-linked AI summary
Conditional independence testing based on a nearest-neighbor estimator of conditional mutual information
Jakob Runge
TL;DR
Conditional independence testing is difficult for continuous data with nonlinear and high-dimensional dependencies, yet it underlies causal discovery. The paper proposes a fully non-parametric conditional mutual information test using nearest-neighbor estimation and local permutations, which reliably simulates the null distribution for small samples and high-dimensional conditioning sets and achieves comparable or higher power than kernel-based alternatives.
Problem
Conditional independence testing for continuous variables must address nonlinear and high-dimensional dependencies without relying on restrictive functional-form assumptions.
Method
The test combines a Kozachenko-Leonenko nearest-neighbor estimator of conditional mutual information with a nearest-neighbor local permutation scheme.
Results
The test reliably simulates the null distribution for small samples and high-dimensional conditioning sets, with better calibration and the same or higher power than compared kernel-based tests.
Takeaways & Limitations
Nearest-neighbor adaptation supports well-calibrated conditional independence tests for highly localized densities and nonlinear dependencies.
Takeaways & Limitations
The estimator's finite-sample variance and convergence rates are unknown, while runtime increases more sharply with sample size and dimensionality than Fourier-feature kernel tests.
Abstract
from arXiv · showhide
Conditional independence testing is a fundamental problem underlying causal discovery and a particularly challenging task in the presence of nonlinear and high-dimensional dependencies. Here a fully non-parametric test for continuous data based on conditional mutual information combined with a local permutation scheme is presented. Through a nearest neighbor approach, the test efficiently adapts also to non-smooth distributions due to strongly nonlinear dependencies. Numerical experiments demonstrate that the test reliably simulates the null distribution even for small sample sizes and with high-dimensional conditioning sets. The test is better calibrated than kernel-based tests utilizing an analytical approximation of the null distribution, especially for non-smooth densities, and reaches the same or higher power levels. Combining the local permutation scheme with the kernel tests leads to better calibration, but suffers in power. For smaller sample sizes and lower dimensions, the test is faster than random fourier feature-based kernel tests if the permutation scheme is (embarrassingly) parallelized, but the runtime increases more sharply with sample size and dimensionality. Thus, more theoretical research to analytically approximate the null distribution and speed up the estimation for larger sample sizes is desirable.
1 Introduction
Conditional independence testing is central to causal discovery but difficult for continuous data with nonlinear, high-dimensional dependencies. The paper develops a non-parametric conditional mutual information test with nearest-neighbor estimation and local permutations.
- Conditional independence testing is central to causal discovery, while conditional dependence supports causal conclusions only under stronger assumptions.
- General conditional-independence testing for continuous variables avoids assuming linearity, additivity, or a functional form for dependencies and distributions.
- Discretizing high-dimensional conditioning sets suffers from the curse of dimensionality, whereas kernel methods handle nonlinear and high-dimensional dependencies but require global bandwidth choices.
- The proposed test directly estimates conditional mutual information with a Kozachenko-Leonenko k-nearest-neighbor estimator and a nearest-neighbor local permutation scheme.Nearest-neighbor statistics adapt locally because neighborhoods become smaller where more samples are available.
- The test reliably simulates the null distribution for small samples and high-dimensional conditioning sets, with better calibration below 1000 samples and the same or higher power than compared approaches.The comparison includes KCIT, RCIT, RCoT, and CDC.
2 Conditional independence test
The test directly estimates conditional mutual information with a nearest-neighbor estimator and generates null surrogates through a local permutation scheme that preserves dependence between X and Z. Both components adapt locally to data density, while the permutation test addresses the unavailable finite-sample distribution of the estimator.
- 2.1 Conditional mutual information: CMI is zero if and only if X ⊥⊥Y |Z, provided the relevant densities exist.
- 2.2 Nearest-neighbor CMI estimator: The CMI estimator generalizes nearest-neighbor entropy estimation by using maximum-norm hypercubes defined from joint-space neighbor distances.Counts in X⊗Z, Y⊗Z, and Z subspaces supply the terms needed for the estimator.
- 2.2 Nearest-neighbor CMI estimator: Nearest-neighbor statistics adapt to local density, reducing neighborhood size where samples are more abundant compared with fixed-bandwidth approaches.Larger k reduces variance but increases bias because larger neighborhoods make constant-density assumptions less plausible.
- 2.2 Nearest-neighbor CMI estimator: Because finite-sample behavior and analytical significance bounds for the CMI estimator are unavailable, the method uses permutation-based null generation.The estimator is asymptotically unbiased and consistent, but finite-size dependence on dimensions, sample length, and k remains unknown.
- 2.3 Nearest-neighbor permutation test: The local permutation maps each X value to a randomized kperm-nearest neighbor in Z while approximately drawing indices without replacement.The procedure searches neighbors in Z, shuffles candidate lists, and tracks used indices; replacement can still occur when without-replacement assignment is impossible.
- 2.3 Nearest-neighbor permutation test: The permutation test repeatedly computes CMI estimates on surrogate data and obtains a p-value by comparing the original estimate with the simulated null estimates.
3 Experiments
Experiments show that CMIknn’s local permutation test is well calibrated across nonlinear, high-dimensional, and small-sample settings, with power generally matching or exceeding kernel alternatives. Its runtime is favorable for modest problems when permutations are parallelized, but grows more sharply with sample size and conditioning-set dimensionality.
- Choosing kCMI and kperm: A full non-local permutation can increase false positives, whereas very small kperm can reduce power; intermediate values can reproduce the true null distribution.The independent-case permuted distribution is negatively biased when kperm is too large, while the dependent-case distribution is positively biased for kperm = 1..3.
- Choosing kCMI and kperm: kperm ≈5..10 yields well-calibrated tests while not affecting power much across a wide range of sample sizes.The n = 1000 experiments used B = 1000 null surrogates, and the pattern also held across a wide range of sample sizes.
- Choosing kCMI and kperm: kCMI ≈0.1..0.2n is suggested as a rule of thumb because power peaks at an intermediate value, while runtime increases linearly with kCMI.Tests remain well calibrated even for kCMI ≈ n/2, but power slowly decreases when kCMI becomes too large.
- Comparison with kernel measures: CMIknn has the lowest KS-values for almost all tested sample sizes and achieves the highest power when kCMI scales with sample size.Kernel tests relying on analytical null approximations are especially poorly calibrated at smaller sample sizes or higher DZ; CMIknn also slightly exceeds RCIT and RCoT for DZ = 8 and n ≥1000.
- Comparison with kernel measures: With parallelized permutations, CMIknn is faster than RCIT or RCoT for not too large sample sizes, but its runtime increases more sharply with sample size and DZ.Efficient KD-tree nearest-neighbor search supports the lower initial runtime, whereas random-Fourier-feature methods have runtime quadratic in the number of features.
- Comparison with kernel measures: Local permutation improves kernel-test calibration, but their power remains mostly lower than CMIknn and their computational advantage is lost.The analytical approximations used by RCIT and RCoT do not work well below n ≈1000.
4 Real data application
CMIknn is applied within a time-series PC causal-discovery analysis of air pollutants and weather variables, using detrended data and lags up to three hours.
- CMIknn is applied in a time-series version of the PC causal-discovery algorithm to study air pollutants and weather variables.
- The analysis uses the first three months of data, yielding an effective sample size of n = 1102 after accounting for missing values.The time series were detrended with a Gaussian kernel smoother using bandwidth σ = 1440 hours.
- The causal-discovery analysis includes time lags from τ = 1 through τmax = 3 hours and reports a graph at a 10% FDR level.
- The CMIknn parameters are kCMI = 200, kperm = 5, and B = 1000 permutation surrogates.
5 Conclusion
The paper concludes that CMIknn provides well-calibrated, fully non-parametric conditional-independence testing across nonlinear and higher-dimensional settings, while computational scaling and analytical null approximations remain open challenges.
- CMIknn adapts to highly localized densities from nonlinear dependencies and maintains reliable false-positive rates across n = 50 to n = 2000 and DZ = 1..10.
- CMIknn has comparable or higher power than KCIT, RCIT, and RCoT, while kernel tests combined with local permutations generally retain lower power.
- CMIknn starts faster for modest sample sizes and dimensions, but its runtime grows more sharply with sample size and conditioning-set dimensionality than Fourier-feature kernel tests.
- The paper identifies approximate null-distribution theory and faster nearest-neighbor computation as priorities for larger-sample applications.
- For strongly oscillatory or localized nonlinear dependencies, analytical RCIT and RCoT can fail calibration, whereas CMIknn remains better calibrated with small kperm.