mlsanityData to 7 Oct 2026

Theoretical Guarantees for Causal Discovery on Large Random Graphs

arXiv 2511.02536 ↗First posted 4 Nov 2025cs.LGcited by 0

Not on the map. Why?

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.

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

Builds on

20 of 49 references.

References · 20

  1. 2020Differentiable Causal Discovery from Interventional Datacited by 218
  2. 2019Learning Neural Causal Models from Unknown Interventionscited by 113
  3. 2022Score matching enables causal discovery of nonlinear additive noise modelscited by 108
  4. 2022Amortized Inference for Causal Structure Learningcited by 89
  5. 2017Permutation-based Causal Inference Algorithms with Interventionscited by 78
  6. 2018Characterizing and Learning Equivalence Classes of Causal DAGs under Interventionscited by 76
  7. 2019Permutation-Based Causal Structure Learning with Unknown Intervention Targetscited by 69
  8. 2015Learning Causal Graphs with Small Interventionscited by 63
  9. 2019ABCD-Strategy: Budgeted Experimental Design for Targeted Causal Structure Discoverycited by 52
  10. 2017Cost-Optimal Learning of Causal Graphscited by 44
  11. 2017Budgeted Experiment Design for Causal Structure Learningcited by 38
  12. 2020Active Structure Learning of Causal DAGs via Directed Clique Treecited by 38
8 more
  1. 2023Stable Differentiable Causal Discoverycited by 30
  2. 2020Efficient Intervention Design for Causal Discovery with Latentscited by 22
  3. 2022Differentiable Causal Discovery Under Latent Interventionscited by 21
  4. 2021Near-Optimal Multi-Perturbation Experimental Design for Causal Structure Learningcited by 17
  5. 2019Size of Interventional Markov Equivalence Classes in Random DAG Modelscited by 9
  6. 2023The CausalBench challenge: A machine learning contest for gene network inference from single-cell perturbation datacited by 7
  7. 2024Deriving Causal Order from Single-Variable Interventions: Guarantees & Algorithmcited by 5
  8. 2024Efficient Differentiable Discovery of Causal Ordercited by 2

Built on by

Not cited yet.