# Sequentially learning the topological ordering of causal directed acyclic graphs with likelihood ratio scores

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 51 references that are in the map.
- First posted on arXiv 3 Feb 2022.

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

- [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)
- [Learning Sparse Nonparametric DAGs](https://mlsanity.com/paper/1909.13189/) (2019)
- [CAM: Causal additive models, high-dimensional order search and penalized regression](https://mlsanity.com/paper/1310.1533/) (2013)
- [Permutation-based Causal Inference Algorithms with Interventions](https://mlsanity.com/paper/1705.10220/) (2017)
- [On Causal Discovery with Equal Variance Assumption](https://mlsanity.com/paper/1807.03419/) (2018)
- [A polynomial-time algorithm for learning nonparametric causal graphs](https://mlsanity.com/paper/2006.11970/) (2020)
- [Concave Penalized Estimation of Sparse Gaussian Bayesian Networks](https://mlsanity.com/paper/1401.0852/) (2014)
- [Learning Identifiable Gaussian Bayesian Networks in Polynomial Time and Sample Complexity](https://mlsanity.com/paper/1703.01196/) (2017)
- [High-Dimensional Causal Discovery Under non-Gaussianity](https://mlsanity.com/paper/1803.11273/) (2018)
- [Estimating the effect of joint interventions from observational data in sparse high-dimensional settings](https://mlsanity.com/paper/1407.2451/) (2014)
- [A Potential Outcomes Calculus for Identifying Conditional Path-Specific Effects](https://mlsanity.com/paper/1903.03662/) (2019)
- [Learning Large-Scale Bayesian Networks with the sparsebn Package](https://mlsanity.com/paper/1703.04025/) (2017)
- [Optimizing regularized Cholesky score for order-based learning of Bayesian networks](https://mlsanity.com/paper/1904.12360/) (2019)
- [Directed Graphical Models and Causal Discovery for Zero-Inflated Data](https://mlsanity.com/paper/2004.04150/) (2020)
- [Graphical Models for Zero-Inflated Single Cell Gene Expression](https://mlsanity.com/paper/1610.05857/) (2016)

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

- [Order-based Structure Learning with Normalizing Flows](https://mlsanity.com/paper/2308.07480/) (2023)
- [Causal Layering via Conditional Entropy](https://mlsanity.com/paper/2401.10495/) (2024)
- [Retrieving Classes of Causal Orders with Inconsistent Knowledge Bases](https://mlsanity.com/paper/2412.14019/) (2024)

## Abstract (arXiv)

Causal discovery, the learning of causality in a data mining scenario, has been of strong scientific and theoretical interest as a starting point to identify "what causes what?" Contingent on assumptions and a proper learning algorithm, it is sometimes possible to identify and accurately estimate a causal directed acyclic graph (DAG), as opposed to a Markov equivalence class of graphs that gives ambiguity of causal directions. The focus of this paper is in highlighting the identifiability and estimation of DAGs with general error distributions through a general sequential sorting procedure that orders variables one at a time, starting at root nodes, followed by children of the root nodes, and so on until completion. We demonstrate a novel application of this general approach to estimate the topological ordering of a DAG. At each step of the procedure, only simple likelihood ratio scores are calculated on regression residuals to decide the next node to append to the current partial ordering. The computational complexity of our algorithm on a p-node problem is O(pd), where d is the maximum neighborhood size. Under mild assumptions, the population version of our procedure provably identifies a true ordering of the underlying DAG. We provide extensive numerical evidence to demonstrate that this sequential procedure scales to possibly thousands of nodes and works well for high-dimensional data. We accompany these numerical experiments with an application to a single-cell gene expression dataset.