# Approximate Kernel-based Conditional Independence Tests for Fast Non-Parametric Causal Discovery

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

## Key facts

- Cited by 76 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Feb 2017.

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

- [Deep Stable Learning for Out-Of-Distribution Generalization](https://mlsanity.com/paper/2104.07876/) (2021)
- [OOD-GNN: Out-of-Distribution Generalized Graph Neural Network](https://mlsanity.com/paper/2112.03806/) (2021)
- [Causal Structure Learning: a Combinatorial Perspective](https://mlsanity.com/paper/2206.01152/) (2022)
- [Identifying Patient-Specific Root Causes with the Heteroscedastic Noise Model](https://mlsanity.com/paper/2205.13085/) (2022)
- [A Survey on Causal Discovery Methods for I.I.D. and Time Series Data](https://mlsanity.com/paper/2303.15027/) (2023)
- [WOODS: Benchmarks for Out-of-Distribution Generalization in Time Series](https://mlsanity.com/paper/2203.09978/) (2022)
- [A Theoretical Analysis on Independence-driven Importance Weighting for Covariate-shift Generalization](https://mlsanity.com/paper/2111.02355/) (2021)
- [Signature Kernel Conditional Independence Tests in Causal Discovery for Stochastic Processes](https://mlsanity.com/paper/2402.18477/) (2024)
- [Practical Kernel Tests of Conditional Independence](https://mlsanity.com/paper/2402.13196/) (2024)
- [Federated Causal Discovery from Heterogeneous Data](https://mlsanity.com/paper/2402.13241/) (2024)
- [An Asymptotic Test for Conditional Independence using Analytic Kernel Embeddings](https://mlsanity.com/paper/2110.14868/) (2021)
- [Finding Valid Adjustments under Non-ignorability with Minimal DAG Knowledge](https://mlsanity.com/paper/2106.11560/) (2021)
- [Obtaining Causal Information by Merging Datasets with MAXENT](https://mlsanity.com/paper/2107.07640/) (2021)
- [Conditional Independence Testing via Latent Representation Learning](https://mlsanity.com/paper/2209.01547/) (2022)
- [Leveraging Probabilistic Circuits for Nonparametric Multi-Output Regression](https://mlsanity.com/paper/2106.08687/) (2021)
- [Conditional independence testing under misspecified inductive biases](https://mlsanity.com/paper/2307.02520/) (2023)
- [Semiparametric Bayesian Networks](https://mlsanity.com/paper/2109.03008/) (2021)
- [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)
- [Efficient Ensemble Conditional Independence Test Framework for Causal Discovery](https://mlsanity.com/paper/2509.21021/) (2025)
- [Marginalizable Density Models](https://mlsanity.com/paper/2106.04741/) (2021)
- [Front-door Adjustment Beyond Markov Equivalence with Limited Graph Knowledge](https://mlsanity.com/paper/2306.11008/) (2023)
- [Learning Generalizable Agents via Saliency-Guided Features Decorrelation](https://mlsanity.com/paper/2310.05086/) (2023)
- [General Frameworks for Conditional Two-Sample Testing](https://mlsanity.com/paper/2410.16636/) (2024)
- [The Third Pillar of Causal Analysis? A Measurement Perspective on Causal Representations](https://mlsanity.com/paper/2505.17708/) (2025)
- [Differentiable Constraint-Based Causal Discovery](https://mlsanity.com/paper/2510.22031/) (2025)
- [A Kernel Test for Causal Association via Noise Contrastive Backdoor Adjustment](https://mlsanity.com/paper/2111.13226/) (2021)
- [A survey of some recent developments in measures of association](https://mlsanity.com/paper/2211.04702/) (2022)
- [Causal Discovery via Conditional Independence Testing with Proxy Variables](https://mlsanity.com/paper/2305.05281/) (2023)

## Abstract (arXiv)

Constraint-based causal discovery (CCD) algorithms require fast and accurate conditional independence (CI) testing. The Kernel Conditional Independence Test (KCIT) is currently one of the most popular CI tests in the non-parametric setting, but many investigators cannot use KCIT with large datasets because the test scales cubicly with sample size. We therefore devise two relaxations called the Randomized Conditional Independence Test (RCIT) and the Randomized conditional Correlation Test (RCoT) which both approximate KCIT by utilizing random Fourier features. In practice, both of the proposed tests scale linearly with sample size and return accurate p-values much faster than KCIT in the large sample size context. CCD algorithms run with RCIT or RCoT also return graphs at least as accurate as the same algorithms run with KCIT but with large reductions in run time.