0

A Topological Sorting Criterion for Random Causal Directed Acyclic Graphs

Random directed acyclic graphs (DAGs) based on imposing an order on Erdős-Rényi or scale-free graphs are widely used to generate synthetic data from causal models, in particular for evaluating causal discovery algorithms.

Preview
Year
2026
Hosting
Abstract onlyARXIV-DEFAULT

Cite

Notes

Only stored in your browser.

Attribution

Abstract & full text
arxiv.org/abs/2605.06288ARXIV-DEFAULT
TL;DR
Semantic Scholar
Attribution policy →

Abstract

Random directed acyclic graphs (DAGs) based on imposing an order on Erdős-Rényi or scale-free graphs are widely used to generate synthetic data from causal models, in particular for evaluating causal discovery algorithms. We show that the set of nodes reachable via open paths, termed relatives, never decreases along the causal order in all DAGs. We find that it tends to increase strictly for DAGs with certain density parameters, and demonstrate that this pattern can be exploited for causal discovery via sorting by the estimated number of relatives. We note that many simulations in the literature are focused on a narrow range of parameter settings where sorting by relatives yields an excellent proxy for the causal order, and show that a strict increase of relatives leads to a singleton Markov equivalence class. We propose sampling time-series DAGs as a possible alternative and discuss implications for causal discovery and synthetic data generation. Implementations of our algorithms can be found at https://causaldisco.github.io/CausalDisco/.