# Conditional independence testing based on a nearest-neighbor estimator of conditional mutual information

arXiv: https://arxiv.org/abs/1709.01447 · HTML: https://mlsanity.com/paper/1709.01447/

## Key facts

- Cited by 70 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Sep 2017.

## Built on by (most cited first, 30 of 70)

- [Causal Influence Detection for Improving Efficiency in Reinforcement Learning](https://mlsanity.com/paper/2106.03443/) (2021)
- [Causal Discovery from Temporal Data: An Overview and New Perspectives](https://mlsanity.com/paper/2303.10112/) (2023)
- [Combining Human Predictions with Model Probabilities via Confusion Matrices and Calibration](https://mlsanity.com/paper/2109.14591/) (2021)
- [Discovering Causal Relations and Equations from Data](https://mlsanity.com/paper/2305.13341/) (2023)
- [A Survey on Causal Discovery Methods for I.I.D. and Time Series Data](https://mlsanity.com/paper/2303.15027/) (2023)
- [NTS-NOTEARS: Learning Nonparametric DBNs With Prior Knowledge](https://mlsanity.com/paper/2109.04286/) (2021)
- [CUTS: Neural Causal Discovery from Irregular Time-Series Data](https://mlsanity.com/paper/2302.07458/) (2023)
- [Conditional Mutual Information for Disentangled Representations in Reinforcement Learning](https://mlsanity.com/paper/2305.14133/) (2023)
- [Achieving Long-Term Fairness in Sequential Decision Making](https://mlsanity.com/paper/2204.01819/) (2022)
- [An Asymptotic Test for Conditional Independence using Analytic Kernel Embeddings](https://mlsanity.com/paper/2110.14868/) (2021)
- [Auditing for Human Expertise](https://mlsanity.com/paper/2306.01646/) (2023)
- [Composite Feature Selection using Deep Ensembles](https://mlsanity.com/paper/2211.00631/) (2022)
- [Diffeomorphic Information Neural Estimation](https://mlsanity.com/paper/2211.10856/) (2022)
- [Entropy-based Discovery of Summary Causal Graphs in Time Series](https://mlsanity.com/paper/2105.10381/) (2021)
- [Conditional Independence Testing via Latent Representation Learning](https://mlsanity.com/paper/2209.01547/) (2022)
- [Local Discovery by Partitioning: Polynomial-Time Causal Discovery Around Exposure-Outcome Pairs](https://mlsanity.com/paper/2310.17816/) (2023)
- [Conditional independence testing under misspecified inductive biases](https://mlsanity.com/paper/2307.02520/) (2023)
- [Semiparametric Bayesian Networks](https://mlsanity.com/paper/2109.03008/) (2021)
- [Conditional Independence Testing with Heteroskedastic Data and Applications to Causal Discovery](https://mlsanity.com/paper/2306.11498/) (2023)
- [Towards Causal Representations of Climate Model Data](https://mlsanity.com/paper/2312.02858/) (2023)
- [Local Causal Discovery for Structural Evidence of Direct Discrimination](https://mlsanity.com/paper/2405.14848/) (2024)
- [Scalable and Flexible Causal Discovery with an Efficient Test for Adjacency](https://mlsanity.com/paper/2406.09177/) (2024)
- [Nearest-Neighbor Sampling Based Conditional Independence Testing](https://mlsanity.com/paper/2304.04183/) (2023)
- [Causal Representation Learning in Temporal Data via Single-Parent Decoding](https://mlsanity.com/paper/2410.07013/) (2024)
- [Causal Additive Models with Unobserved Causal Paths and Backdoor Paths](https://mlsanity.com/paper/2502.07646/) (2025)
- [Efficient Ensemble Conditional Independence Test Framework for Causal Discovery](https://mlsanity.com/paper/2509.21021/) (2025)
- [Data AUDIT: Identifying Attribute Utility- and Detectability-Induced Bias in Task Models](https://mlsanity.com/paper/2304.03218/) (2023)
- [Fast Computation of Leave-One-Out Cross-Validation for k-NN Regression](https://mlsanity.com/paper/2405.04919/) (2024)
- [The Third Pillar of Causal Analysis? A Measurement Perspective on Causal Representations](https://mlsanity.com/paper/2505.17708/) (2025)
- [DIET: Conditional independence testing with marginal dependence measures of residual information](https://mlsanity.com/paper/2208.08579/) (2022)

## Abstract (arXiv)

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.