# Structure Learning for Directed Trees

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 47 references that are in the map.
- First posted on arXiv 19 Aug 2021.

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

- [DAGs with NO TEARS: Continuous Optimization for Structure Learning](https://mlsanity.com/paper/1803.01422/) (2018)
- [Causal Discovery with Continuous Additive Noise Models](https://mlsanity.com/paper/1309.6779/) (2013)
- [Gaussian Processes and Kernel Methods: A Review on Connections and Equivalences](https://mlsanity.com/paper/1807.02582/) (2018)
- [CAM: Causal additive models, high-dimensional order search and penalized regression](https://mlsanity.com/paper/1310.1533/) (2013)
- [High-dimensional consistency in score-based and hybrid structure learning](https://mlsanity.com/paper/1507.02608/) (2015)
- [Efficient multivariate entropy estimation via k-nearest neighbour distances](https://mlsanity.com/paper/1606.00304/) (2016)
- [Nonparametric independence testing via mutual information](https://mlsanity.com/paper/1711.06642/) (2017)
- [The Recovery of Causal Poly-Trees from Statistical Data](https://mlsanity.com/paper/1304.2736/) (2013)
- [Optimal rates of entropy estimation over Lipschitz balls](https://mlsanity.com/paper/1711.02141/) (2017)

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

- [Identifiability of latent-variable and structural-equation models: from linear to nonlinear](https://mlsanity.com/paper/2302.02672/) (2023)
- [Root Cause Analysis of Outliers with Missing Structural Knowledge](https://mlsanity.com/paper/2406.05014/) (2024)
- [Learning Linear Non-Gaussian Polytree Models](https://mlsanity.com/paper/2208.06701/) (2022)
- [A Fast Non-parametric Approach for Local Causal Structure Learning](https://mlsanity.com/paper/2111.14969/) (2021)
- [Optimal estimation of Gaussian (poly)trees](https://mlsanity.com/paper/2402.06380/) (2024)
- [Estimating large causal polytrees from small samples](https://mlsanity.com/paper/2209.07028/) (2022)
- [Learning Linear Gaussian Polytree Models with Interventions](https://mlsanity.com/paper/2311.04636/) (2023)
- [Scalable Structure Learning for Sparse Context-Specific Systems](https://mlsanity.com/paper/2402.07762/) (2024)
- [Optimal structure learning and conditional independence testing](https://mlsanity.com/paper/2507.05689/) (2025)

## Abstract (arXiv)

Knowing the causal structure of a system is of fundamental interest in many areas of science and can aid the design of prediction algorithms that work well under manipulations to the system. The causal structure becomes identifiable from the observational distribution under certain restrictions. To learn the structure from data, score-based methods evaluate different graphs according to the quality of their fits. However, for large, continuous, and nonlinear models, these rely on heuristic optimization approaches with no general guarantees of recovering the true causal structure. In this paper, we consider structure learning of directed trees. We propose a fast and scalable method based on Chu-Liu-Edmonds' algorithm we call causal additive trees (CAT). For the case of Gaussian errors, we prove consistency in an asymptotic regime with a vanishing identifiability gap. We also introduce two methods for testing substructure hypotheses with asymptotic family-wise error rate control that is valid post-selection and in unidentified settings. Furthermore, we study the identifiability gap, which quantifies how much better the true causal model fits the observational distribution, and prove that it is lower bounded by local properties of the causal model. Simulation studies demonstrate the favorable performance of CAT compared to competing structure learning methods.