A Topological Sorting Criterion for Random Causal Directed Acyclic Graphs

arXiv:2605.06288 · stat.ME, cs.AI · Submitted 2026-05-07 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Statistics. The day in statistics: methods, theory and the inference under them.

Tom: I'm Tom.

Jane: And I'm Jane, here with Lu, Meng and our in-house large language model, Lalam.

Tom: We're looking at the paper: "A Topological Sorting Criterion for Random Causal Directed Acyclic Graphs".

Paper summary: Tom: So this paper, "A Topological Sorting Criterion for Random Causal Directed Acyclic Graphs," it looks at how we can actually order these random graphs—the kind used to test causal discovery algorithms. The main idea is that the set of nodes reachable from a starting point, which they call relatives, has a special property in these random directed acyclic graphs.

Jane: Relatives, right? So if you're driving and you see this concept, what's the naive question people would ask about it? Like, how does counting these relatives help us figure out the true causal order of events in a system we're modeling?

Lu: Basically, they show that as you follow the causal order of the graph, say from cause to effect, this number of relatives goes up in a predictable way. This is what they call monotonicity along the causal order >

Meng: Okay, so it's not just that it goes up; there's a numerical test for this pattern. They assess how often this pattern shows up across different kinds of random graphs, like Erdos-Renyi and scale-free ones >

Lalam: And they found that you can actually use this prevalence to recover the causal order by sorting the nodes based on their estimated number of relatives in increasing order >

Tom: That sounds really practical for building a tool. So, if I'm looking at a bunch of these graphs, I can sort them by these relative counts and see if that ordering actually works as a good approximation for the causal structure >

Jane: Right. But what does this mean for someone just trying to build an AI model? If you have a massive graph from some real-world data, does sorting by relatives give you a reliable starting point, or is it just a heuristic >

Meng: It's not guaranteed perfect, but the analysis suggests it can be quite effective. They found that this method seems pretty robust and doesn't really depend on the specific simulation schemes used to create those graphs that try to remove other sortabilities >

Lu: And they even suggest that high rel-sortability might explain why some algorithms, like FLOP, perform well even when the graphs are sparser than usual >

Tom: So it sounds like this isn't just a theoretical thing. It has some real implications for how we evaluate these discovery algorithms in practice. But what about the underlying models they are using? Are we only talking about Erdos-Renyi and scale-free graphs, or does this apply more broadly >

Jane: They extend the scrutiny to synthetic data generation based on DAG models for time series. They even propose a condition to control how much rel-sortability is present in the resulting graphs >

Meng: That's interesting because existing evaluation methods often use synthetic data that might not fully capture the real world, so this work might show that those evaluations systematically underestimate how good these causal discovery algorithms really are on real data >

Lu: They also connect this to other research on how different preferential attachment rules in scale-free graphs affect constraint-based discovery, which is relevant for understanding the underlying topology >

Tom: So it's about using topological properties—like these relatives—as a new way to guide how we test and evaluate the causal structures we discover >

Jane: And ultimately, they show that a strict increase in the number of relatives along the causal order leads to a singular Markov equivalence class, which is another nice topological property >

Meng: That singular equivalence class part is cool because it gives us a very clear boundary condition for what we expect when we sort by this measure >

Lu: It gives us a concrete result about the topology of these random DAGs and points toward guiding the development of better data generation regimes to test our algorithms against >

Tom: So, to wrap up this paper, "A Topological Sorting Criterion for Random Causal Directed Acyclic Graphs," it suggests that we can use the concept of relatives to sort these graphs by their estimated number in increasing order >

Jane: And this sorting method is suggested as a way to recover the causal order because the number of relatives increases monotonically along that true causal path >

Meng: The main implication for deployment is that if you can estimate these relative counts reliably, you have a new, computationally tractable way to impose an order on complex graphs >

Lu: It really adds a new tool for evaluating the topological properties of random DAGs and helps us figure out which graph sampling schemes are actually realistic to use when testing causal discovery algorithms >

Conclusion: Tom: So we're wrapping up this paper about "A Topological Sorting Criterion for Random Causal Directed Acyclic Graphs." Basically, they’ve found a way to order these complex random graphs using a new measure called relatives.

Jane: Relatives, right? So what does this actually mean for the world? Like, if someone is trying to figure out cause and effect in a massive system we're building with AI models, how does this sorting help them?

Lu: The core finding is that the number of nodes reachable through open paths—these relatives—tends to grow as you move along the true causal order. They show this pattern holds for many different random graph setups.

Meng: But it’s not just that they go up; they test it numerically across Erdos-Renyi and scale-free graphs, and they found a way to actually use those counts to recover the true causal order by sorting the nodes by their estimated relative number.

Lalam: I've looked at the literature on this, Tom, and I'm pretty sure what they found is solid. It suggests that this method can give us a good approximation of the causal structure we are looking for in these systems.

Tom: So it’s a new way to impose an order on these graphs without having to run every single causal discovery algorithm from scratch every time, right?

Jane: Exactly. And they pointed out that if you sort by this number—the estimated relatives—it leads to a single Markov equivalence class, which is another topological property of the graph structure.

Lu: That singular class thing is important because it sets a very clear boundary for what we expect when we use this sorting method. It gives us some structural certainty about these random DAGs.

Meng: From my side, it means if you can reliably estimate these relative counts, you have a more efficient way to impose an order on these massive graphs before you run resource-heavy discovery algorithms. That could save serious compute time at scale.

Lalam: It really helps guide the development of better data generation regimes because we now have a topological criterion we can use to check if the synthetic data we create is realistic enough for testing our AI models.

Tom: So it’s about using these topological properties, like relatives, as a new tool to evaluate how good certain graph sampling schemes are when testing causal discovery algorithms.

Jane: Right. And that leads us nicely into the next thing—we need to talk about those alternative ways we can sample data for our AI models.

Alexander G. Reisach, Antoine Chambaz, Gilles Blanchard, Sebastian Weichwald

Laboratoire de Mathematiques d’Orsay, University Paris-Saclay, CNRS, MAP5, Department of Mathematical Sciences and Pioneer Centre for Artificial Intelligence, University of Copenhagen

stat.ME, cs.AI

Submitted: 2026-05-07

Updated: 2026-11-15

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 83/100

The gist: Random directed acyclic graphs (DAGs) based on imposing an order on Erdos-Rényi and scale-free graphs are widely used for evaluating causal discovery algorithms We show that in such DAGs…

Key concepts

Relatives
Relatives of a node are all other nodes reachable from it through paths in the graph. The key finding is that as you move along the true causal order of the DAG, this number consistently increases. This provides a measurable topological property that can be used to infer the correct causal sequence.
Causal Order Recovery
This refers to using a specific ordering derived from graph properties to reconstruct the underlying causal structure of a DAG. The authors demonstrate that sorting nodes based on their estimated number of relatives in increasing order can effectively approximate the true causal order, which is crucial for algorithms that rely on this ordering.
Singular Markov Equivalence Class (MEC)
A Markov Equivalence Class groups together different DAGs that are indistinguishable by certain statistical tests. The paper proves that a strict increase in the number of relatives along the causal order leads to only one such class, meaning this property is a strong indicator of a unique underlying causal structure.

Terminology

Summary

Random directed acyclic graphs (DAGs) based on imposing an order on Erdos-Rényi and scale-free 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. p. 0

Pruning redundant reasoning tokens

The paper introduces the notion of relatives and provides theoretical results indicating its importance for causal discovery The relatives of a node are interesting for the purpose of causal discovery primarily due to the monotonicity property in Theorem 1, which suggests that an ordering based on the estimated number of relatives in increasing fashion may result in a good approximation of a causal ordering.

How the training signal is built

The authors propose an algorithm called rel-SortnRegress that combines Algorithm 1 and Algorithm 2 to sort by the estimated number of relatives and regresses in the resulting order. This process involves estimating the number of relatives empirically using a threshold based on correlation matrix entries and then using sparse regression to estimate the DAG given an order. p. 4

Where the gains come from

The analysis of rel-sortability shows that it is largely unaffected by simulation schemes aimed at removing other sortabilities and that sorting by relatives can be highly effective for causal discovery. Furthermore, the work suggests that high rel-sortability may explain why certain algorithms like FLOP perform well even in sparser settings. p. 6

Exploring alternative sampling schemes

The paper proposes turning to graph sampling schemes based on DAG models for time series as a possible alternative to existing graph sampling schemes. Specifically, it constructs time-unrolled DAGs and states a condition to control rel-sortability in the resulting DAG. p. 7 This approach suggests that existing evaluation methods on synthetic data may systematically misestimate the promise of causal discovery algorithms on real-world data. p. 7

Conclusion

The contribution provides new insight into the topological properties of common random DAG models in causal discovery. The authors show that the number of relatives tends to increase along the causal order and that a strict increase in the number of relatives leads to a singular MEC. p. 9 The work suggests that the concept of relatives provides a new tool for evaluating the topological properties of random DAGs that can help guide the development of alternative data generation regimes. p. 9 The findings call for a systematic evaluation of which graph sampling scheme may be considered realistic. p. 8

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Implement a causal order recovery algorithm using sorting by relatives to exploit the set of nodes reachable via open paths, termed relatives as a proxy for causal ordering in random directed acyclic graphs.

  2. Develop an empirical estimation procedure for the number of relatives from data, such as Algorithm 1: Estimating an ordering by the number of relatives, to obtain a causal order from observations without relying on strict parametric assumptions.

  3. Create a DAG discovery algorithm called rel-SortnRegress that combines Algorithm 1 and Algorithm 2 to sort by the estimated number of relatives and then regresses in the resulting order, which can be used as a baseline for assessing causal discovery simplicity.

  4. Enhance evaluation methods by using rel-sortability to probe the connection between high rel-sortability and MEC size, potentially identifying why certain data generation schemes are problematic for causal discovery algorithms.

  5. Propose time-unrolled DAGs as a potential alternative to existing graph sampling schemes, suggesting that unrolling them in time may be a natural alternative to deleting edges and controlling their rel-sortability using conditions derived from Theorem 4.

Related papers