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 $\epsilon$-interventional faithfulness assumption that accommodates latent confounding. For sparse Erd\H{o}s--R\'enyi directed acyclic graphs, where the edge probability scales as $p_e = \Theta(1/d)$, we show that the FNR concentrates around its mean at rate $O(\frac{\log d}{\sqrt 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 $\gamma > 3$, the deviation width scales as $O(d^{\beta - \frac{1}{2}})$ with $\beta = 1/(\gamma - 1) < \frac{1}{2}$, 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.

翻译：我们研究了在单变量随机干预和允许潜在混杂的$\epsilon$-干预忠实性假设下，因果发现中假阴性率（FNR）——即未被恢复方向的真实因果边所占比例——的理论保证。对于稀疏的Erdős–Rényi有向无环图，其中边概率按$p_e = \Theta(1/d)$缩放，我们证明FNR以$O(\frac{\log d}{\sqrt d})$的速率围绕其均值集中，这意味着随着维数增加，超出期望误差的大偏差以指数级概率变得不可能发生。这种集中性确保了在大规模场景下推导出的上界以高概率成立。将分析扩展至广义Barabási–Albert图揭示了一个更强的现象：当度指数满足$\gamma > 3$时，偏差宽度按$O(d^{\beta - \frac{1}{2}})$缩放，其中$\beta = 1/(\gamma - 1) < \frac{1}{2}$，因此在极限情况下消失。这表明现实的无标度拓扑结构本质上正则化了因果发现，降低了方向误差的变异性。这些有限维结果首次为因果结构恢复提供了维度自适应且忠实性鲁棒的保证，并挑战了高维性和网络异质性必然阻碍准确发现的直觉。我们的仿真结果证实了这些理论预测，显示FNR在实践中确实会集中并随着维数增长而趋于消失。