Conditional independence testing based on a nearest-neighbor estimator of conditional mutual information
A non-parametric conditional independence test based on nearest-neighbor conditional mutual information estimation, offering superior calibration and efficiency in high-dimensional, nonlinear settings.
Key Findings
Methodology
This paper introduces a fully non-parametric conditional independence test leveraging a nearest-neighbor estimator of conditional mutual information (CMI). The core component is the Kozachenko-Leonenko k-nearest neighbor (k-NN) entropy estimator, which directly estimates the mutual information between variables by adaptively capturing local density variations. The approach combines this estimator with a local permutation scheme that preserves the dependency structure of the conditioning variables, enabling accurate null distribution simulation without distributional assumptions. The permutation is performed within local neighborhoods determined by kperm, ensuring the dependence structure between X and Z remains intact while testing the independence of X and Y conditioned on Z. The method is computationally efficient, scalable with data size and dimension, and particularly effective for non-smooth, nonlinear dependencies, outperforming kernel-based methods in small-sample and high-dimensional regimes.
Key Results
- Simulation studies demonstrate that the proposed nearest-neighbor CMI test reliably approximates the null distribution even with small sample sizes (e.g., n=50), maintaining false positive rates below 5%. It outperforms kernel-based tests such as KCIT, RCIT, and RCoT in calibration, especially in high-dimensional or non-smooth density scenarios. The test achieves comparable or higher power, with improvements of 10-15% in detecting nonlinear dependencies under various models, including post-nonlinear and oscillatory functions.
- Computational experiments show that, with parallelization, the nearest-neighbor approach significantly reduces runtime compared to kernel methods, especially for small to moderate sample sizes (up to n=2000). The method maintains robustness across different conditioning set sizes (D_z=1 to 10) and dependency complexities, demonstrating adaptability in real-world scenarios like air quality data analysis.
- Application to real air quality time series data successfully identified causal relationships among pollutants and meteorological variables, aligning with domain knowledge and validating the method's practical utility. The approach effectively handles missing data, temporal dependencies, and nonlinear interactions, providing a valuable tool for causal inference in environmental sciences.
Significance
This research advances the state-of-the-art in non-parametric conditional independence testing, addressing critical limitations of existing kernel-based methods, such as poor calibration in small samples and high computational costs. By integrating local density estimation with a data-adaptive permutation scheme, it offers a robust, scalable, and theoretically grounded tool for causal discovery, especially suited for complex, high-dimensional datasets common in modern scientific and industrial applications. Its ability to reliably control false positives while maintaining high detection power makes it a promising foundation for automated causal inference pipelines and large-scale data analysis.
Technical Contribution
The primary technical innovation lies in combining the Kozachenko-Leonenko k-NN entropy estimator with a novel local permutation scheme that preserves the dependency structure of the conditioning variables. This approach circumvents the need for kernel bandwidth tuning and global density assumptions, providing a fully data-adaptive, non-parametric estimator of CMI. The local permutation method ensures the null distribution is accurately approximated even in small samples and high dimensions, significantly improving calibration over asymptotic or global permutation methods. Additionally, the implementation leverages efficient KD-tree neighbor searches, enabling scalable computation. Theoretically, the method offers a new paradigm for non-parametric dependence testing rooted in local density estimation and data-driven permutation strategies.
Novelty
Unlike existing kernel-based tests that rely on fixed bandwidths and global density assumptions, this work introduces a local density-adaptive estimator of conditional mutual information combined with a neighborhood-based permutation scheme. This hybrid approach effectively captures complex, non-smooth dependencies and maintains calibration in small samples and high-dimensional spaces. It is, to our knowledge, the first to integrate nearest-neighbor density estimation with local permutation testing for conditional independence, providing a flexible, robust, and scalable alternative to traditional kernel methods.
Limitations
- The theoretical distribution of the estimator under the null hypothesis remains analytically intractable, relying on extensive simulations for calibration. Precise finite-sample bounds and asymptotic distributions are yet to be derived.
- Parameter selection for k (nearest neighbors) and kperm (permutation neighborhood size) currently depends on empirical tuning, which may affect robustness across different datasets and dependency structures.
- While scalable for moderate dimensions, the computational cost increases with the dimension of the conditioning set, potentially limiting applicability in extremely high-dimensional settings (D_z>20).
- The method assumes continuous variables with well-defined densities; performance on discrete or mixed data types requires further investigation.
Future Work
Future research should focus on deriving theoretical guarantees for the estimator’s distribution under the null, enabling more rigorous significance testing. Developing adaptive parameter tuning strategies, possibly via cross-validation or Bayesian optimization, could enhance robustness. Extending the approach to handle discrete and mixed data types, as well as integrating it into causal discovery algorithms for large-scale systems, are promising directions. Additionally, exploring approximate nearest-neighbor algorithms and GPU acceleration could further improve computational efficiency for big data applications.
AI Executive Summary
In the realm of causal discovery and high-dimensional statistical analysis, the challenge of reliably testing for conditional independence remains a fundamental obstacle. Traditional methods, such as linear regression-based tests, are limited to linear or monotonic relationships, while kernel-based approaches like KCIT, RCIT, and RCoT, though more flexible, often suffer from calibration issues in small samples and high dimensions, alongside significant computational burdens.
This paper introduces a novel non-parametric conditional independence test rooted in a nearest-neighbor estimation of conditional mutual information (CMI). The core idea is to leverage the Kozachenko-Leonenko k-nearest neighbor estimator, which adaptively captures local density variations without requiring explicit distributional assumptions. By integrating a local permutation scheme that preserves the dependency structure of the conditioning variables, the method accurately simulates the null distribution, enabling precise p-value computation.
The significance of this approach lies in its ability to handle complex, nonlinear, and non-smooth dependencies, which are common in real-world data such as environmental measurements, biological systems, and social networks. Unlike kernel methods that rely on global bandwidth parameters, this nearest-neighbor-based estimator adapts to local data density, providing superior calibration, especially in small-sample scenarios. Empirical results from extensive simulations demonstrate that the proposed method maintains false positive rates below 5%, while achieving higher detection power compared to existing techniques.
Furthermore, the method scales efficiently with data size, especially when parallelized, making it suitable for large-scale applications. Its application to air quality time series data successfully uncovered meaningful causal relationships, validating its practical utility. While current limitations include the lack of a formal theoretical distribution under the null and the need for empirical parameter tuning, future work aims to address these issues through theoretical analysis and algorithmic optimization.
Overall, this work offers a significant step forward in non-parametric conditional independence testing, providing a robust, adaptable, and scalable tool that can facilitate more accurate causal inference across diverse scientific domains.
Deep Dive
Abstract
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.
References (20)
Approximate Kernel-Based Conditional Independence Tests for Fast Non-Parametric Causal Discovery
Eric V. Strobl, Kun Zhang, S. Visweswaran
CONDITIONAL DISTANCE CORRELATION
Xueqin Wang, Wenliang Pan, Wenhao Hu et al.
Causation, prediction, and search
P. Spirtes, C. Glymour, R. Scheines
Kernel-based Conditional Independence Test and Application in Causal Discovery
Kun Zhang, J. Peters, D. Janzing et al.
Partial mutual information for coupling analysis of multivariate time series.
S. Frenzel, B. Pompe
A Simplified Method of Experimentally Evaluating the Entropy of a Stationary Sequence
R. Dobrushin
Model-Powered Conditional Independence Test
Rajat Sen, A. Suresh, Karthikeyan Shanmugam et al.
It's okay to be skinny, if your friends are fat
S. Maneewongvatana, D. Mount
Testing conditional independence for continuous random variables
Wicher P. Bergsma
Feature-to-Feature Regression for a Two-Step Conditional Independence Test
Qinyi Zhang, S. Filippi, S. Flaxman et al.
The Local Bootstrap for Kernel Estimators under General Dependence Conditions
E. Paparoditis, D. Politis
Estimating mutual information.
A. Kraskov, Harald Stögbauer, P. Grassberger
Causation, Prediction, and Search
T. Burr
A new class of random vector entropy estimators and its applications in testing statistical hypotheses
M. N. Goria, N. N. Leonenko, V. Mergel et al.
Distribution-Free Learning of Bayesian Network Structure in Continuous Domains
D. Margaritis
Kernel Measures of Conditional Dependence
K. Fukumizu, A. Gretton, Xiaohai Sun et al.
Inferring the directionality of coupling with conditional mutual information.
M. Vejmelka, M. Paluš
On field calibration of an electronic nose for benzene estimation in an urban pollution monitoring scenario
S. D. Vito, Ettore Massera, M. Piga et al.
A class of Rényi information estimators for multidimensional densities
N. Leonenko, L. Pronzato, V. Savani
Divergence Estimation for Multidimensional Densities Via $k$-Nearest-Neighbor Distances
Qing Wang, S. Kulkarni, S. Verdú
Cited By (20)
Deep Nonparametric Conditional Independence Tests for Images
Complex dynamics in psychological data: Mapping individual symptom trajectories to group-level patterns
Efficient Ensemble Conditional Independence Test Framework for Causal Discovery
Multiscale Cochran-Mantel-Haenszel Scanning for Conditional Dependency
Single-nucleoid imaging in whole cells defines the dynamics of the mtDNA life cycle
Conditional Independence Tests for Constraint-Based Causal Discovery: A Survey
AutoCause: A Python framework that automates expert decisions in environmental time-series causal discovery
Facing Asymmetry - Uncovering the Causal Link between Facial Symmetry and Expression Classifiers using Synthetic Interventions
Interventional Causal Structure Discovery Over Graphical Models With Convergence and Optimality Guarantees
Linear Scaling Causal Discovery from High-Dimensional Time Series by Dynamical Community Detection.
Understanding bus network delay propagation: Integration of causal inference and complex network theory
Causal Additive Models with Unobserved Causal Paths and Backdoor Paths
Amortized Conditional Independence Testing
Learning Causal Response Representations through Direct Effect Analysis
Locally Explaining Prediction Behavior via Gradual Interventions and Measuring Property Gradients
Addressing Information Asymmetry: Deep Temporal Causality Discovery for Mixed Time Series
Kernel Copula Density Estimation of Hellinger Correlation
Learning double balancing representation for heterogeneous dose-response curve estimation
The Third Pillar of Causal Analysis? A Measurement Perspective on Causal Representations
Causal discovery from nonstationary time series