# Fast Causal Discovery by Approximate Kernel-based Generalized Score Functions with Linear Computational Complexity

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 63 references that are in the map.
- First posted on arXiv 23 Dec 2024.

## Builds on (most cited first, 24 of 24)

- [DAGs with NO TEARS: Continuous Optimization for Structure Learning](https://mlsanity.com/paper/1803.01422/) (2018)
- [GPyTorch: Blackbox Matrix-Matrix Gaussian Process Inference with GPU Acceleration](https://mlsanity.com/paper/1809.11165/) (2018)
- [DAG-GNN: DAG Structure Learning with Graph Neural Networks](https://mlsanity.com/paper/1904.10098/) (2019)
- [Gradient-Based Neural DAG Learning](https://mlsanity.com/paper/1906.02226/) (2019)
- [D'ya like DAGs? A Survey on Structure Learning and Causal Discovery](https://mlsanity.com/paper/2103.02582/) (2021)
- [Learning Sparse Nonparametric DAGs](https://mlsanity.com/paper/1909.13189/) (2019)
- [When Gaussian Process Meets Big Data: A Review of Scalable GPs](https://mlsanity.com/paper/1807.01065/) (2018)
- [On the Role of Sparsity and DAG Constraints for Learning Linear DAGs](https://mlsanity.com/paper/2006.10201/) (2020)
- [CAM: Causal additive models, high-dimensional order search and penalized regression](https://mlsanity.com/paper/1310.1533/) (2013)
- [DAGMA: Learning DAGs via M-matrices and a Log-Determinant Acyclicity Characterization](https://mlsanity.com/paper/2209.08037/) (2022)
- [Score matching enables causal discovery of nonlinear additive noise models](https://mlsanity.com/paper/2203.04413/) (2022)
- [Causal-learn: Causal Discovery in Python](https://mlsanity.com/paper/2307.16405/) (2023)
- [Approximate Kernel-based Conditional Independence Tests for Fast Non-Parametric Causal Discovery](https://mlsanity.com/paper/1702.03877/) (2017)
- [Causal Representation Learning from Multiple Distributions: A General Setting](https://mlsanity.com/paper/2402.05052/) (2024)
- [Theoretical Impediments to Machine Learning With Seven Sparks from the Causal Revolution](https://mlsanity.com/paper/1801.04016/) (2018)
- [DAGs with No Fears: A Closer Look at Continuous Optimization for Learning Bayesian Networks](https://mlsanity.com/paper/2010.09133/) (2020)
- [Learning Gaussian Networks](https://mlsanity.com/paper/1302.6808/) (2013)
- [Structure Learning with Continuous Optimization: A Sober Look and Beyond](https://mlsanity.com/paper/2304.02146/) (2023)
- [A Survey on Large-scale Machine Learning](https://mlsanity.com/paper/2008.03911/) (2020)
- [NTS-NOTEARS: Learning Nonparametric DBNs With Prior Knowledge](https://mlsanity.com/paper/2109.04286/) (2021)
- [Large-Scale Kernel Methods for Independence Testing](https://mlsanity.com/paper/1606.07892/) (2016)
- [Theory Refinement on Bayesian Networks](https://mlsanity.com/paper/1303.5709/) (2013)
- [Truncated Matrix Power Iteration for Differentiable DAG Learning](https://mlsanity.com/paper/2208.14571/) (2022)
- [Optimal Kernel Choice for Score Function-based Causal Discovery](https://mlsanity.com/paper/2407.10132/) (2024)

## Built on by (most cited first, 1 of 1)

- [Fast Nonparametric Conditional Independence Testing via Two-Stage Regression](https://mlsanity.com/paper/2606.18011/) (2026)

## Abstract (arXiv)

Score-based causal discovery methods can effectively identify causal relationships by evaluating candidate graphs and selecting the one with the highest score. One popular class of scores is kernel-based generalized score functions, which can adapt to a wide range of scenarios and work well in practice because they circumvent assumptions about causal mechanisms and data distributions. Despite these advantages, kernel-based generalized score functions pose serious computational challenges in time and space, with a time complexity of O(n3) and a memory complexity of O(n2), where n is the sample size. In this paper, we propose an approximate kernel-based generalized score function with O(n) time and space complexities by using low-rank technique and designing a set of rules to handle the complex composite matrix operations required to calculate the score, as well as developing sampling algorithms for different data types to benefit the handling of diverse data types efficiently. Our extensive causal discovery experiments on both synthetic and real-world data demonstrate that compared to the state-of-the-art method, our method can not only significantly reduce computational costs, but also achieve comparable accuracy, especially for large datasets.