# A polynomial-time algorithm for learning nonparametric causal graphs

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

## Key facts

- Cited by 30 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Jun 2020.

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

- [Beware of the Simulated DAG! Causal Discovery Benchmarks May Be Easy To Game](https://mlsanity.com/paper/2102.13647/) (2021)
- [Learning latent causal graphs via mixture oracles](https://mlsanity.com/paper/2106.15563/) (2021)
- [Optimal estimation of Gaussian DAG models](https://mlsanity.com/paper/2201.10548/) (2022)
- [Efficient Bayesian network structure learning via local Markov boundary search](https://mlsanity.com/paper/2110.06082/) (2021)
- [Structure learning in polynomial time: Greedy algorithms, Bregman information, and exponential families](https://mlsanity.com/paper/2110.04719/) (2021)
- [Effective Causal Discovery under Identifiable Heteroscedastic Noise Model](https://mlsanity.com/paper/2312.12844/) (2023)
- [DAG Learning on the Permutahedron](https://mlsanity.com/paper/2301.11898/) (2023)
- [Local Discovery by Partitioning: Polynomial-Time Causal Discovery Around Exposure-Outcome Pairs](https://mlsanity.com/paper/2310.17816/) (2023)
- [Heteroscedastic Causal Structure Learning](https://mlsanity.com/paper/2307.07973/) (2023)
- [Markov Equivalence and Consistency in Differentiable Structure Learning](https://mlsanity.com/paper/2410.06163/) (2024)
- [Learning linear non-Gaussian directed acyclic graph with diverging number of nodes](https://mlsanity.com/paper/2111.00740/) (2021)
- [Scalable and Flexible Causal Discovery with an Efficient Test for Adjacency](https://mlsanity.com/paper/2406.09177/) (2024)
- [A Fast Non-parametric Approach for Local Causal Structure Learning](https://mlsanity.com/paper/2111.14969/) (2021)
- [Order-based Structure Learning with Normalizing Flows](https://mlsanity.com/paper/2308.07480/) (2023)
- [BUILD with Precision: Bottom-Up Inference of Linear DAGs](https://mlsanity.com/paper/2512.16111/) (2025)
- [Sequentially learning the topological ordering of causal directed acyclic graphs with likelihood ratio scores](https://mlsanity.com/paper/2202.01748/) (2022)
- [Differentiable Bayesian Structure Learning with Acyclicity Assurance](https://mlsanity.com/paper/2309.01392/) (2023)
- [Optimal estimation of Gaussian (poly)trees](https://mlsanity.com/paper/2402.06380/) (2024)
- [Learning Gaussian DAG Models without Condition Number Bounds](https://mlsanity.com/paper/2511.06164/) (2025)
- [Learning Sparse Fixed-Structure Gaussian Bayesian Networks](https://mlsanity.com/paper/2107.10450/) (2021)
- [NURD: Negative-Unlabeled Learning for Online Datacenter Straggler Prediction](https://mlsanity.com/paper/2203.08339/) (2022)
- [Probably approximately correct high-dimensional causal effect estimation given a valid adjustment set](https://mlsanity.com/paper/2411.08141/) (2024)
- [Recovering Linear Causal Models with Latent Variables via Cholesky Factorization of Covariance Matrix](https://mlsanity.com/paper/2311.00674/) (2023)
- [Enabling Causal Discovery in Post-Nonlinear Models with Normalizing Flows](https://mlsanity.com/paper/2407.04980/) (2024)
- [Identifiability of AMP chain graph models](https://mlsanity.com/paper/2106.09350/) (2021)
- [Estimating large causal polytrees from small samples](https://mlsanity.com/paper/2209.07028/) (2022)
- [Learning nonparametric DAGs with incremental information via high-order HSIC](https://mlsanity.com/paper/2308.05969/) (2023)
- [Distributionally Robust Skeleton Learning of Discrete Bayesian Networks](https://mlsanity.com/paper/2311.06117/) (2023)
- [Discrete Score Matching Enables Causal Discovery from Count Data](https://mlsanity.com/paper/2609.39326/) (2026)
- [Learning Non-Gaussian SEMs with Conditional Risk, and Why the Direction of Recursion Matters](https://mlsanity.com/paper/2610.14246/) (2026)

## Abstract (arXiv)

We establish finite-sample guarantees for a polynomial-time algorithm for learning a nonlinear, nonparametric directed acyclic graphical (DAG) model from data. The analysis is model-free and does not assume linearity, additivity, independent noise, or faithfulness. Instead, we impose a condition on the residual variances that is closely related to previous work on linear models with equal variances. Compared to an optimal algorithm with oracle knowledge of the variable ordering, the additional cost of the algorithm is linear in the dimension d and the number of samples n. Finally, we compare the proposed algorithm to existing approaches in a simulation study.