# A Topological Sorting Criterion for Random Causal Directed Acyclic Graphs

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 37 of its 65 references that are in the map.
- First posted on arXiv 7 May 2026.

## Builds on (most cited first, 30 of 37)

- [DAGs with NO TEARS: Continuous Optimization for Structure Learning](https://mlsanity.com/paper/1803.01422/) (2018)
- [DAG-GNN: DAG Structure Learning with Graph Neural Networks](https://mlsanity.com/paper/1904.10098/) (2019)
- [Causal Discovery with Continuous Additive Noise Models](https://mlsanity.com/paper/1309.6779/) (2013)
- [Gradient-Based Neural DAG Learning](https://mlsanity.com/paper/1906.02226/) (2019)
- [Differentiable Causal Discovery from Interventional Data](https://mlsanity.com/paper/2007.01754/) (2020)
- [D'ya like DAGs? A Survey on Structure Learning and Causal Discovery](https://mlsanity.com/paper/2103.02582/) (2021)
- [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)
- [Causal Inference and Causal Explanation with Background Knowledge](https://mlsanity.com/paper/1302.4972/) (2013)
- [Beware of the Simulated DAG! Causal Discovery Benchmarks May Be Easy To Game](https://mlsanity.com/paper/2102.13647/) (2021)
- [Bayesian Structure Learning with Generative Flow Networks](https://mlsanity.com/paper/2202.13903/) (2022)
- [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)
- [DiBS: Differentiable Bayesian Structure Learning](https://mlsanity.com/paper/2105.11839/) (2021)
- [A survey of Bayesian Network structure learning](https://mlsanity.com/paper/2109.11415/) (2021)
- [Causal Structure Learning](https://mlsanity.com/paper/1706.09141/) (2017)
- [Scalable Causal Discovery with Score Matching](https://mlsanity.com/paper/2304.03382/) (2023)
- [Structure Learning with Continuous Optimization: A Sober Look and Beyond](https://mlsanity.com/paper/2304.02146/) (2023)
- [CausalTime: Realistically Generated Time-series for Benchmarking of Causal Discovery](https://mlsanity.com/paper/2310.01753/) (2023)
- [Towards Scalable Bayesian Learning of Causal DAGs](https://mlsanity.com/paper/2010.00684/) (2020)
- [BayesDAG: Gradient-Based Posterior Inference for Causal Discovery](https://mlsanity.com/paper/2307.13917/) (2023)
- [The Case for Evaluating Causal Models Using Interventional Measures and Empirical Data](https://mlsanity.com/paper/1910.05387/) (2019)
- [A Scale-Invariant Sorting Criterion to Find a Causal Order in Additive Noise Models](https://mlsanity.com/paper/2303.18211/) (2023)
- [Ancestral Causal Inference](https://mlsanity.com/paper/1606.07035/) (2016)
- [A Meta-Learning Approach to Bayesian Causal Discovery](https://mlsanity.com/paper/2412.16577/) (2024)
- [textttcausalAssembly: Generating Realistic Production Data for Benchmarking Causal Discovery](https://mlsanity.com/paper/2306.10816/) (2023)
- [The Landscape of Causal Discovery Data: Grounding Causal Discovery in Real-World Applications](https://mlsanity.com/paper/2412.01953/) (2024)
- [Standardizing Structural Causal Models](https://mlsanity.com/paper/2406.11601/) (2024)
- [Adjustment Identification Distance: A gadjid for Causal Structure Learning](https://mlsanity.com/paper/2402.08616/) (2024)
- [Do we become wiser with time? On causal equivalence with tiered background knowledge](https://mlsanity.com/paper/2306.01638/) (2023)

## Abstract (arXiv)

Random directed acyclic graphs (DAGs) based on imposing an order on ErdHos-R'enyi and scale free random graphs are widely used for evaluating causal discovery algorithms. We show that in such DAGs, the set of nodes reachable via open paths, termed relatives, increases monotonically along the causal order. We assess the prevalence of this pattern numerically, and demonstrate that it can be exploited for causal order recovery via sorting by the estimated number of relatives. We note that many simulations in the literature feature settings where this yields an excellent proxy for the causal order, and show that a strict increase of relatives along the causal order leads to a singular Markov equivalence class. We propose sampling time-series DAGs as a possible alternative and discuss implications for causal discovery algorithms and their evaluation on synthetic data.