A Topological Sorting Criterion for Random Causal Directed Acyclic Graphs

• URL: http://arxiv.org/abs/2605.06288v1
• Date: Thu, 07 May 2026 13:56:40 GMT
• Title: A Topological Sorting Criterion for Random Causal Directed Acyclic Graphs
• Abstract summary: We show that in DAGs, the set of nodes reachable via open paths, termed relatives, increases monotonically along the causal order.<n>We demonstrate that it can be exploited for causal order recovery via sorting by the estimated number of relatives.<n>We propose sampling time-series DAGs as a possible alternative and discuss implications for causal discovery algorithms and their evaluation on synthetic data.
• Score: 44.42106270319047
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Random directed acyclic graphs (DAGs) based on imposing an order on Erdős-Rényi 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.

Related papers

• Stable Causal Discovery via Directed Acyclic Graph Aggregation [7.490209955333202]
  Directed Acyclic Graphs (DAGs) are central to uncovering causal structure in complex systems.<n>We propose DAGgr, a model averaging framework that aggregates multiple candidate DAGs into a single stable representation.<n>We show that DAGgr matches or exceeds the best individual candidate while consistently outperforming bootstrap-aggregation baselines.
  arXiv  Detail & Related papers  (2026-05-18T16:41:31Z)
• Leveraging heterogeneity for identifiability: Bayesian order-based learning of multiple DAGs [0.5801044612920815]
  We propose a joint order-based scoring framework for causal structure learning of directed acyclic graph (DAG) models.<n>Building on this framework, we propose an order-based Bayesian method for Gaussian DAG models.<n>An application to single-nucleus RNA sequencing data from major depressive disorder demonstrates practical utility.
  arXiv  Detail & Related papers  (2026-05-15T05:43:59Z)
• Learning-Order Autoregressive Models with Application to Molecular Graph Generation [52.44913282062524]
  We introduce a variant of ARM that generates high-dimensional data using a probabilistic ordering that is sequentially inferred from data.<n>We demonstrate experimentally that our method can learn meaningful autoregressive orderings in image and graph generation.
  arXiv  Detail & Related papers  (2025-03-07T23:24:24Z)
• Hybrid Top-Down Global Causal Discovery with Local Search for Linear and Nonlinear Additive Noise Models [2.0738462952016232]
  Methods based on functional causal models can identify a unique graph, but suffer from the curse of dimensionality or impose strong parametric assumptions.<n>We propose a novel hybrid approach for global causal discovery in observational data that leverages local causal substructures.<n>We provide theoretical guarantees for correctness and worst-case time complexities, with empirical validation on synthetic data.
  arXiv  Detail & Related papers  (2024-05-23T12:28:16Z)
• Reinforcement Causal Structure Learning on Order Graph [18.344249064559087]
  We propose Reinforcement Causal Structure Learning on Order Graph (RCL-OG) to model different DAG topological orderings. RCL-OG first defines reinforcement learning with a new reward mechanism to approximate the posterior distribution of orderings. It computes the posterior probability of different orderings.
  arXiv  Detail & Related papers  (2022-11-22T10:29:25Z)
• Diffusion Models for Causal Discovery via Topological Ordering [20.875222263955045]
  emphTopological ordering approaches reduce the optimisation space of causal discovery by searching over a permutation rather than graph space. For ANMs, the emphHessian of the data log-likelihood can be used for finding leaf nodes in a causal graph, allowing its topological ordering. We introduce theory for updating the learned Hessian without re-training the neural network, and we show that computing with a subset of samples gives an accurate approximation of the ordering.
  arXiv  Detail & Related papers  (2022-10-12T13:36:29Z)
• Score matching enables causal discovery of nonlinear additive noise models [63.93669924730725]
  We show how to design a new generation of scalable causal discovery methods. We propose a new efficient method for approximating the score's Jacobian, enabling to recover the causal graph.
  arXiv  Detail & Related papers  (2022-03-08T21:34:46Z)
• Sequential Learning of the Topological Ordering for the Linear Non-Gaussian Acyclic Model with Parametric Noise [6.866717993664787]
  We develop a novel sequential approach to estimate the causal ordering of a DAG. We provide extensive numerical evidence to demonstrate that our procedure is scalable to cases with possibly thousands of nodes.
  arXiv  Detail & Related papers  (2022-02-03T18:15:48Z)
• Reinforcement Learning Based Query Vertex Ordering Model for Subgraph Matching [58.39970828272366]
  Subgraph matching algorithms enumerate all is embeddings of a query graph in a data graph G. matching order plays a critical role in time efficiency of these backtracking based subgraph matching algorithms. In this paper, for the first time we apply the Reinforcement Learning (RL) and Graph Neural Networks (GNNs) techniques to generate the high-quality matching order for subgraph matching algorithms.
  arXiv  Detail & Related papers  (2022-01-25T00:10:03Z)
• Adversarial Examples for $k$-Nearest Neighbor Classifiers Based on Higher-Order Voronoi Diagrams [69.4411417775822]
  Adversarial examples are a widely studied phenomenon in machine learning models. We propose an algorithm for evaluating the adversarial robustness of $k$-nearest neighbor classification.
  arXiv  Detail & Related papers  (2020-11-19T08:49:10Z)
• Block-Approximated Exponential Random Graphs [77.4792558024487]
  An important challenge in the field of exponential random graphs (ERGs) is the fitting of non-trivial ERGs on large graphs. We propose an approximative framework to such non-trivial ERGs that result in dyadic independence (i.e., edge independent) distributions. Our methods are scalable to sparse graphs consisting of millions of nodes.
  arXiv  Detail & Related papers  (2020-02-14T11:42:16Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.