# On the Unlikelihood of D-Separation

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 31 references that are in the map.
- First posted on arXiv 10 Mar 2023.

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

- [D'ya like DAGs? A Survey on Structure Learning and Causal Discovery](https://mlsanity.com/paper/2103.02582/) (2021)
- [Causal Inference in the Presence of Latent Variables and Selection Bias](https://mlsanity.com/paper/1302.4983/) (2013)
- [Causal Discovery from Heterogeneous/Nonstationary Data with Independent Changes](https://mlsanity.com/paper/1903.01672/) (2019)
- [Causal Structure Learning](https://mlsanity.com/paper/1706.09141/) (2017)
- [Temporally Disentangled Representation Learning](https://mlsanity.com/paper/2210.13647/) (2022)
- [Latent Hierarchical Causal Structure Discovery with Rank Constraints](https://mlsanity.com/paper/2210.01798/) (2022)
- [Causal discovery for observational sciences using supervised machine learning](https://mlsanity.com/paper/2202.12813/) (2022)

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

- [CausalMan: A physics-based simulator for large-scale causality](https://mlsanity.com/paper/2502.12707/) (2025)
- [CausalSteward: An Agentic Divide-Conquer-Combine Copilot for Causal Discovery](https://mlsanity.com/paper/2607.01936/) (2026)

## Abstract (arXiv)

Causal discovery aims to recover a causal graph from data generated by it; constraint based methods do so by searching for a d-separating conditioning set of nodes in the graph via an oracle. In this paper, we provide analytic evidence that on large graphs, d-separation is a rare phenomenon, even when guaranteed to exist, unless the graph is extremely sparse. We then provide an analytic average case analysis of the PC Algorithm for causal discovery, as well as a variant of the SGS Algorithm we call UniformSGS. We consider a set V=v1,ldots,vn of nodes, and generate a random DAG G=(V,E) where (va, vb) ∈ E with i.i.d. probability p1 if a<b and 0 if a > b. We provide upper bounds on the probability that a subset of V-x,y d-separates x and y, conditional on x and y being d-separable; our upper bounds decay exponentially fast to 0 as |V| rightarrow ∞. For the PC Algorithm, while it is known that its worst-case guarantees fail on non-sparse graphs, we show that the same is true for the average case, and that the sparsity requirement is quite demanding: for good performance, the density must go to 0 as |V| rightarrow ∞ even in the average case. For UniformSGS, while it is known that the running time is exponential for existing edges, we show that in the average case, that is the expected running time for most non-existing edges as well.