# Theoretical Guarantees for Causal Discovery on Large Random Graphs

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 20 of its 49 references that are in the map.
- First posted on arXiv 4 Nov 2025.

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

- [Differentiable Causal Discovery from Interventional Data](https://mlsanity.com/paper/2007.01754/) (2020)
- [Learning Neural Causal Models from Unknown Interventions](https://mlsanity.com/paper/1910.01075/) (2019)
- [Score matching enables causal discovery of nonlinear additive noise models](https://mlsanity.com/paper/2203.04413/) (2022)
- [Amortized Inference for Causal Structure Learning](https://mlsanity.com/paper/2205.12934/) (2022)
- [Permutation-based Causal Inference Algorithms with Interventions](https://mlsanity.com/paper/1705.10220/) (2017)
- [Characterizing and Learning Equivalence Classes of Causal DAGs under Interventions](https://mlsanity.com/paper/1802.06310/) (2018)
- [Permutation-Based Causal Structure Learning with Unknown Intervention Targets](https://mlsanity.com/paper/1910.09007/) (2019)
- [Learning Causal Graphs with Small Interventions](https://mlsanity.com/paper/1511.00041/) (2015)
- [ABCD-Strategy: Budgeted Experimental Design for Targeted Causal Structure Discovery](https://mlsanity.com/paper/1902.10347/) (2019)
- [Cost-Optimal Learning of Causal Graphs](https://mlsanity.com/paper/1703.02645/) (2017)
- [Budgeted Experiment Design for Causal Structure Learning](https://mlsanity.com/paper/1709.03625/) (2017)
- [Active Structure Learning of Causal DAGs via Directed Clique Tree](https://mlsanity.com/paper/2011.00641/) (2020)
- [Stable Differentiable Causal Discovery](https://mlsanity.com/paper/2311.10263/) (2023)
- [Efficient Intervention Design for Causal Discovery with Latents](https://mlsanity.com/paper/2005.11736/) (2020)
- [Differentiable Causal Discovery Under Latent Interventions](https://mlsanity.com/paper/2203.02336/) (2022)
- [Near-Optimal Multi-Perturbation Experimental Design for Causal Structure Learning](https://mlsanity.com/paper/2105.14024/) (2021)
- [Size of Interventional Markov Equivalence Classes in Random DAG Models](https://mlsanity.com/paper/1903.02054/) (2019)
- [The CausalBench challenge: A machine learning contest for gene network inference from single-cell perturbation data](https://mlsanity.com/paper/2308.15395/) (2023)
- [Deriving Causal Order from Single-Variable Interventions: Guarantees & Algorithm](https://mlsanity.com/paper/2405.18314/) (2024)
- [Efficient Differentiable Discovery of Causal Order](https://mlsanity.com/paper/2410.08787/) (2024)

## Abstract (arXiv)

We investigate theoretical guarantees for the false-negative rate (FNR) -- the fraction of true causal edges whose orientation is not recovered, under single-variable random interventions and an ε-interventional faithfulness assumption that accommodates latent confounding. For sparse ErdHos--R'enyi directed acyclic graphs, where the edge probability scales as pe = Theta(1/d), we show that the FNR concentrates around its mean at rate O(fraclog d√ d), implying that large deviations above the expected error become exponentially unlikely as dimensionality increases. This concentration ensures that derived upper bounds hold with high probability in large-scale settings. Extending the analysis to generalized Barab'asi--Albert graphs reveals an even stronger phenomenon: when the degree exponent satisfies γ > 3, the deviation width scales as O(d^β - frac12) with β = 1/(γ - 1) < frac12, and hence vanishes in the limit. This demonstrates that realistic scale-free topologies intrinsically regularize causal discovery, reducing variability in orientation error. These finite-dimension results provide the first dimension-adaptive, faithfulness-robust guarantees for causal structure recovery, and challenge the intuition that high dimensionality and network heterogeneity necessarily hinder accurate discovery. Our simulation results corroborate these theoretical predictions, showing that the FNR indeed concentrates and often vanishes in practice as dimensionality grows.