Theoretical Guarantees for Causal Discovery on Large Random Graphs
Authors: Mathieu Chevalley
Arash Mehrjou
Patrick Schwab
Venue: ICLR 2026 Poster (2026)
Keywords: causality
causal discovery
theoretical guarantees
single-variable interventions
large-scale causal discovery
Primary area: causal reasoning

Abstract: We investigate theoretical guarantees for the \emph{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ős--Rényi 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\bigl(\tfrac{\log d}{\sqrt d}\bigr)$, 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ási--Albert graphs reveals an even stronger phenomenon: when the degree exponent satisfies $\gamma > 3$, the deviation width scales as $O\bigl(d^{\beta - \frac{1}{2}}\bigr)$ with $\beta = 1/(\gamma - 1) < \frac{1}{2}$, and hence vanishes in the limit. This demonstrates that heterogeneous, heavy-tailed degree structures commonly observed in empirical networks can intrinsically regularize causal discovery by 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.

Published as a conference paper at ICLR 2026
THEORETICAL GUARANTEES FOR CAUSAL DISCOVERY ON LARGE RANDOM GRAPHS
Mathieu Chevalley!
Arash Mehrjou Patrick Schwab
GSK.ai "ETH Zürich
3 MPI for Intelligent Systems
ABSTRACT
We investigate theoretical guarantees for the false-negative rate (hh frac- tion of true causal edges whose orientation is not recovered, under single-variable random interventions and an e-interventional faithfulness assumption that accom- modates latent confounding. For sparse where the edge probability scales as Pe ( (d), we show that the FNR con- log ) implying that large deviations above centrates around its mean at rate O va
Rényi directed acyclic graphs,
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 generalized Barabási-Albert graphs reveals an even stronger phenomenon: when the degree exponent satis- fies > 3, the deviation width scales as O (dd-1/²) with 8 = 1/(7 - 1) < 1/2, and hence vanishes in the limit. This demonstrates that heterogeneous, heavy- tailed degree structures commonly observed in empirical networks can intrinsically regularize causal discovery by 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 di- mensionality 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 dimensionality grows.
INTRODUCTION
Causal discovery aims to recover directed acyclic graph (DAG) structures that encode cause-effect relationships among variables. In systems biology, for instance, reconstructing gene regulatory networks from interventional single-cell data provides insight into the mechanisms driving cellular processes (Dixit et al.) 2016; Meinshausen al. 2016 Chevalley al. 2025a b). Similarly, in
neuroscience, mapping the causal structure of brain activity supports the understanding of functional connectivity and its alterations in disease (Smith et al., 2011: Park & Friston, 2013). A hallmark
of such applications is their high dimensionality: typical datasets involve hundreds to thousands of variables. This setting motivates need for theoretical guarantees that reflect practical constraints and typical graph structures encountered in real-world systems.
substantial body of work has developed worst-case bounds for causal discovery under interventions, often focusing on the number of experiments required to recover the full DAG (Eberhardt et al. 2005 SShanuugam et al. 2013) Kocaoglu al, 2017a). However, such analyses assume idcalized conditions e.g., full faithfulness, causal sufficiecy.. or adversarial intervention designs that limit their applicability in large-scale settings. Moreover, they do not capture the variability of discovery accuracy across random instances, nor do they account for structural features like degree heterogeneity or sparsity commonly observed in empirical networks (Barabási & Albert 1999).
In this work, we analyze the performance of interventional causal discovery under more realistic assumptions and with a focus on the false-negative rate (FNR), defined as the proportion true edges whose orientation is not recovered. We adopt e-interventional faithfulness assumption (Chevalley ct al. 2025c) that allows for latent confounding and does not require the full faithfulness property to hold. Interventions assumed be selected random, mimicking experimental designs where
Corrrespondence to m. cheval 1 com

---

Published as a conference paper at ICLR 2026
only limited control over perturbations is feasible. Our focus is on deriving tiite-dimension deviation bounds that quantify how tightly the FNR concentrates around its expectation in large graphs.
A wide range of real-world networks exhibit structural features that are well captured. at least approximately, by classical random- granphgrphhhhhh ensembles such as Eédōs-Rééní (Erdós et al. 1960) and Barabási-Albert (Barabási & Albert 1999) models. Gene regulatory, protein-interaction, and metabolic networks typically display strong sparsity, heterogeneous node degnees, and hub-dominated organization, with numerous studies reporting approximately heavy-tailed truncated power-law degree distributions (Albert 2005). Similar patterns arise in neural and brain connectivity networks, where structural and functional connectomes consistently show hub regions and fat-tailed degree behavior (Achard et al. [0066] Eguiluz et al. (2005). Although real networks are not generated by these models exactly, ER and BA distributions capture the dominant combinatorial regularities, such as sparsity levels, neighborhood sizes, and degree heterogeneity. They therefore provide an analytically tractable proxy for understanding how these properties influence the stability of causal discovery at scale.
Our analysis yields several key insights. First, we show that in dense Erdōs-Rényi where the edge probability Pe is constant-the FNR vanishes in expectation at rate (1/d)) and concentrates with typical width 1/2). Thus, in dense random graphs the orientation error not only goes to on average, but also becomes sharply localized, providing strong guarantees for reliable causal discovery at large scale. Second, in sparse Erdōs Rényi DAGs- where the number of edges scales linearly with the number of nodes- the FNR remains bounded (1(1) in expectation for non- vacuuuu constant, ( This implies that even under relaxed assumptions and partial interventions, the orientation error becomes increasingly stable in high dimensions. Third, we extend the results to generalized Barabási- -Abeer models, which generate scale-free free DAGs reflecting the degree distributions of empirical networks. In this case, when the degree exponent satisfies 7 3, we prove that the deviation from the expected FNR vanishes asymptotically, confirming that scale-free topologies regularize causal inference by suppressing error variability. These findings surprising: contrary to common beliefs that high dimensionality and structural heterogeneity hinder reliable discovery, we show that they can in fact improve its statistical robustness.
and concentrates at rate O va
Beyond their theoretical interest, these results are useful to both methodologists and practitioners. For methodologists, the deviation bounds provide a principled baseline for understanding which structural regimes make causal orientation intrinsically easier or harder. This baseline is valuable in two complementary ways. First, it sets an upper bound on the stability guarantees one should expect under more optimistic assumptions, richer intervention designs, or additional structural priors: any method leveraging such information should exhibit deviation behavior that at least as good as, and typically better than, the guarantees we derive under minimal conditions. Second, it provides sound reference point for empirical evaluation: synthetic benchmarks routinely use ER, BA, or related random-graph families, and our deviation bounds clarify what variability in FNR one should expect in these settings, as well as how such variability should scale with dimension. For practitioners, the results offer guidance randomized intervention designs: when performance variability can be assessed on moderate-sized systems, our bounds imply that (in terms of FNR) the variability will typically remain comparable or improve larger scale due to stronger concentration. This provides reassurance about the behavior of the Intersort score under random interventions and offers a principled way to reason about how many such interventions are required to achieve a desired reliability level.
While prior work has focused on identifiability or asymptotic consistency, ours is the first to establish finiee-dmmension deviation guarantees showing that causal orientation errors are not only small in expectation but also sharply concentrated in large-scale, structured settings. To our knowledge, these are the first deviation inequalities for topological errors in interventional causal discovery that (i) hold under minimal e-interventional faithfulness, (ii) capture the distributional properties of widely used random graph ensembles reflecting common structural regimes, (iii) yield dimension-adaptiee sariance-sensitive guarantees for false-negative error. By linking graph structure and intervention probability to maite-sample reliability, results provide both new theoretical insight and practical guidelines for designing interventional studies, and are further corroborated by extensive simulations.
2

---

Published as a conference paper at ICLR 2026
Table 1: Summary of theoretical results Asymptotic orders for the expected topological error and the concentration rate (typical deviation scale around the mean) in the three madomm-grahh regimes considered. For the generalized Barabási-Albert (BA) model, 3 7-1 with y = 2 + k/m, k > measures the number of misorentations in the predicted causal order, whereas g is normalized by the number of true edges (false-ngaative rate (FNR)). The probability for variable to be intervened on is denoted Pint-
Model
E[
Elg]
Dev. f
Dev. O
ER dense (p: = (1))
0
(1 Lippat d Pint
2(1- 2(1-pina) Pined
(
ER sparse (pe c/d)
0
(1 [1prust Pint
201 2(1-piss)
O(Vd logd) 1(
Old-1/2 log d) 0128-112)
opint Pint) )
BA (3 E (0.1))
(1 Pint) 2md
RELATED WORK
Classical results in interventional causal discovery analyze the worst-case number of interventions needed for full graph recovery. For multi-variable interventions, Ollo d) sets suffice (Eberhardt
ct al. 2005). while for atomic interventions d 1 suffice (Eberhardt et al. 2006). Subsequent refinements related this complexity to graph structure, c.g. (O(log((G)) in terms of clique size
(Hauser & Bühlmann 2014). These analyses adopt adversarial view: the intervention strategy must succeed against any possible graph. (See Appendix A for more detailed survey of refinements based on randomization (Eberhardi 2010 Hu et al. 2014) and minimax lower bounds (Shanmugam
ct al. 2015
Kocaoglu et al. 2017a Squires et al. 2020a Porwal et al. 2022).)
A parallel line of work studies intervention design under constraints, e.g. budgeted adaptive designs, where the goal is to maximize utility given limited number of experiments (He & Geng 2008 Hytti
nen et al. 2013 Ghassami al., 2018 Hauser & Bühlmann 2014; (Sussex et al. [021] Agrawal et al.
2019). Here the focus is typically on approximate greedy algorithms rather than fundamental limits.
Beyond worst-case identifiabilityy another thread studies interventional Markov equivalence classes (I-MECs): the partially identified structures remaining after a given set of interventions. Seminal work by Hauser & Bühlmann (2012) introduced I T-MECs and greedy algorithms for learning with interventional data. Subsequent work extended these ideas to more general settings (Yang et al., 2018: Daber et al.] 2020 Kocaoglu et al. 2019 Squires al. 2020b) and proposed efficient learning
methods (Brouillard et al. 22000] Ke et al. 2019 2023 Mooij et al. 2020 Nazaret al.) 2023 Wang
ct al. 2017 Faria et al., 2022 Lorch et al. 2022). (See Appendix for a fuller survey.)
However, existing work leaves open key question: what is the expected size of an interventional Markov equivalence class (I-MEC)? This expectation depends not only on the intervention policy but also on the underlying graph distribution. Most prior results emphasize worst-case scenarios e.g.. bounded-degree wriphs-which yield robust guarantees but can be overly conservative. By contrast, an average-case analysis under parameterized graph models can provide more realistic insight. For example, many empirical networks in systems biology exhibit heterogeneous, hub-dominated degree patterns, which tend to shrink I-MECs far more than worst-case analyses suggest. Incorporating such stylized but analytically tractable graph ensembles into the theory therefore refines our understanding of intervention utility and provides more practically relevant guidance for experimental design.
Two works that have aimed at analyzing the expected size of I-MECs are Katz et al. (019) and Chevalley et al.] (002cc). both considering single-variable variable interventions. Under an Erdös Erdös-Rényi graph distribution (Erdōs et al.) 1960), Katz et al. (2019) derive upper bounds for various metrics such as the number of unoriented edges and the logarithm of the I-MEC size-under the assumptions of causal sufficiency and faithfulness, and assuming optimal intervention selection policy (i.e., selecting interventions that minimize the number of unoriented edges). They show that, as the number of variables d tends to infinity, these metrics converge well-defined limits, and they provide finite-d upper-boume bounds that can be estimated using Monte Carlo simulations.
In contrast, Chevalley al. (2025c) also analyze assumptions by replacing causal sufficiency and strict faithfulness with an e-interventional faithfulness assumption under task agnostic selection policy, where interventions are selected
graphs but relax some of these
3

---

Published as a conference paper at ICLR 2026
at random. They define score causal orders that leverages the statistical distances from the interventional data. The causal orders that maximize this score form an equivalence class for which they derive closed-form upper bounds the expected number of misoriented edges (i.e., true edges that do not follow the causal order).
In this work, extend these theoretical results by analyzing another metric: the false negative rate (FNR), defined as the number of misoriented edges divided by the total number of edges. More importantly, we derive deviation bounds from the mean of those metries, offering a more detailed perspective on the performance variability of individual instances compared to the expected performance. We also extend all those results to a generalized Barabási-Albert graph distribution (Barabási & Albert [199). whose scale-free behavior more closely mimics real-world networks. To the best of our knowledge, our work provides the first deviation bounds for causal discovery errors, as opposed to worst-case or asymptotic consistency results. These bounds hold under c-interventional faithfulness and scale favorably with graph size and topological heterogeneity.
DEFINITIONS AND NOTATIONS
In this section, we introduce the main notions and assumptions that underlie our analysis, following the formulation in (Chevalley et al. (025c).. In our setting, the causal graph is represented as a directed acyclic graph (DAG) g (V, over set of d random variables X = (X1,.. .a)) with V {1. ....., d}. The matrix A denotes the corresponding adjacency matrix, with A, = 1 if (i,J) E E and otherwise. For any node j, the parent set is defined as Pa(j) = {i V (f, F.). and the sets of ancestors and descendants of node are denoted by Aneg (i) and Descg (i) respectively.
In the context of structural causal models (SCMs) C (S, PN), each variable X, is generated by structural equation S₁ E S : X, fy (Pact): NY), where N, is exogenous noise variable. We consider interventions that replace the original structural equation of a variable X by X₂ = Ng.. Given a set of intervention targets I C V. let I = (J,...., .....,a Ia) E {0, be the corresponding intervention indicator vector, such that 1j- if and only j E I. We denote by
Px (C.(0) the observational distribution and by Pint do do , I} the set of interventional distributions.
A causal order is any permutation π V V such that for every edge (i,j) E we have (i) < xj). To measure the divergence of an ordering π from the true causal ordering of G, we use the top order divergence (Rolland et al.) 2022)) defined by
D Dwp (0p(9, x)
Σ
AG iy
<(}>>((
This score measure the number of misoriented edges given permutation. Given the observational and interventional distributions, Chevalley et al. (2025c) propose a score function to evaluate the quality of a candidate causal order. For a statistical distance D: P(M) x P(M) + [0, 00) and parameters e >> 0 and e, the score function is defined as
D,I, (0) Pints c) =
Σ (cdd
iEIJEV (())((()
where D;j = D(pE .P (o)))((.:=N))) This score quantifies how well the ordering π aligns with interventional effects, and it is used to define the optimal causal order Topt as the maximizer of the score. The main practical limitations of derived theoretical results lie in the need to find optimal solution to the score. However, a recently proposed (Chevalley et al. 2024) algorithm show that the objective can be solved at large scale.
Assumption 1 (c-Interventional Faithfulness (Chevalley al. 2025c)). Let C be a structural causal model with associated DAG G and Ñ' denote exogenous noise variables under interventions. We say that [N, C) is e-interventionally faithful if, for every pair i + with i I and V.
D
c.((0) Px2 Pxx,
(x) >e
there exists a directed path i ~ j in G.
4

---

Published as a conference paper at ICLR 2026
Unlike classical faithfulness, which requires every d-separation in G to manifest as conditional independence in the joint distribution, e-interventional faithfulness imposes only a marginal shift requirement: whenever there is directed path from an intervened node i to j. the distribution of X; changes by at least under intervention on i. This weaker assumption does not rely on conditional independence structure and is preserved under marginalizzaion, making it compatible with latent confounding. In particular, as long as interventions on observed variables induce distributional shifts that detectable above threshold e, the assumption continues to hold even when hidden confounders influence both i and j.
Chevalley et al. (2025c) show that for an intervention policy in which each intervention indicator is chosen independently as I3 ~ (errooull(Puaa) k E V. one can derive upper bounds on the expected number of misorientations Pipp(9 Topt (T) Here I (J1...., Ta) is the random intervention vector, and Topt (T) denotes the optimal causal order under that intervention design, i.e., the permutation that maximizes the score function given the specific realization of I. Writing Topt (T) emphasizes that the optimal order is itself random variable induced by the random choice of interventions, and thus Dup inherits its stochasticity through I. this paper, we extended those bounds for the FNR, derive deviation bounds for both metrics, and derive all those properties for Barabási-Albert graph distribution. A complete list of all notation provided in Appendix
Although our analysis is phrased in terms of the score-optimae order Topt associated with the InterSort objective, the guarantees themselves are far more general. The quantity is simply a convenient formalization of a possible orientation performance achievable under the given intervention design and data assumptions. Any causal-discovery method that relies on single-node interventions and exploits the same e-interventional faithfulness property must obey the same upper bounds and deviation behavior, since these depend only on the structure of G, the intervention probability Pine. and the induced reachability relations not on the specifics of the InterSort score. Conversely, an algorithm attains strictly higher error, our results quantify the remaining performance gap attributable to suboptimal use of the interventional information. Thus, while the InterSort score provides a clean mathematical vehicle for theoretical analysis, the deviation guarantees we derive characterize the intrinsic statistical difficulty of orientation under randomized interventions for any method operating under these assumptions.
THEORETICAL RESULTS
In what follows we assume access to both the observational distribution CC,(0) and the single-variable interventional distributions p do.do(X===N)) for all I, under the condition that (Ñ,C) is (restricted) e-interventionallyy faithful (ef. Chevalley et al. (2025c)). In the restricted setting, interventions reveal only direct parent-child relations.
Assumption 2 (Unique optimizer). Let
Topt arg max; STT. Pin..c..
where arg max* denotes a deterministic bie-breaking rule (e.g.. lexicographic ordering). Thus Topt is unique for every E), and all definitions below are taken with respect this unique optimizer.
Flipping the intervention status of a node le can only affect edges that "use l as evidence." " An edge (i,j) is already secured if is directly intervened, or if some intervened ancestor of j is not ancestor of i. Thus the only vulnerable edges lie in k's ancestral and descendant cones, Counting these provides structural bound on how much the error can change when /3 toggled.
Lemma (Lipschitz bound for intervention variables). Define
f(I) Drop (G, Topt (I)),
g(I)
f(I)
For each lo E V, let
|(T) s(K))
max Ck I. WEEk
Then
Ck |Ano(k)] [Desc(k)]
== TET
Lemma 4 (Restricted case). Under restricted e-interventional faithfulnees, flipiig It only affects edges incident to k, hence
Ck degin (k) + degout (k).
5

---

Published as a conference paper at ICLR 2026
Lemma 5 (Edge variables). Let
S(I := Deop (G( Topt (I, E)).
only a single edge indicator Eej flipped, the set of affected edges is
Ass- :- [(k; E i:ig (kg(
and the Lipschitz constant satisfies
Cij = |Ang dogin (i)-
Remark 6. Without Assumption ties between distinct maximizers could cause Topt to jump discontinuously, leading to Cą or Czj large as [E] and voiding any
concentration.
The Lipschitz constants derived above translate the structural sensitivity of the error functional into a uniform control on how much any single random input (intervention or edge) can affect it. This functional property is precisely what allows a function of independent random variables changes only slightly when one coordinate is altered, then the function is concentrated around its mean. Thus, the Lipschitz analysis provides the bridge from graph-theoretic theoretic properties of G to probabilistic concentration results for the error metrics, which form the core theoretical guarantees of this paper. In the next section, we leverage this connection to derive deviation bounds for different random graph models. Complementary results that establish upper bounds on the mean error are provided Appendix
invoke deviation inequalities such McDiarmid's
4.1 SETTING I: FIXED GRAPH, RANDOM INTERVENTIONS
In this first setting, we consider the graph to be fixed, and the randomness comes only from the random choice of intervention targets.
Once we know how much a single intervention flip can change the top-order error-captured by the Lipschitz constants from the previous lemmas, McDiarmid's inequality immediately yields concentration. Normalizing by [B] simply scales all constants down, so the normalized error concentrates even more tightly.
Theorem 7 (Deviation bounds for topological errors). Let c == ma Cj. By McDiarmid's inequality and Lemma 3 for any t >> O, we have the following deviation bounds:
Unnormalized error:
2t Ek=1
2t
(I -()() 2) 2exp
S
(V
c
Normalized error:
21 F1
2/17/42
((g((I) [[g([]] 2 < exxp
S 2 exp
Σ1
|V|22
4.2 SETTING II: ERDŌS- RÉNYI GRAPHS
In addition to the previous assumptions, ically, we generate an Erdós Rényi random DAG on nodes by first sampling a uniform random topo- logical ordering
take the underlying graph itself to be random. Specif-
Sa, and then including each forward edge (o()))(()) with independent proba- bility p. whenever < This construction ensures acyclicity by orienting edges consistently with a.
Formally, let E = { Fi. EG = 1, with i.i.d distribution Bernoull(pp)). denotes that the directed edge (i.j) is present. The total number of edges is [E] Ensiessa Eij: [E[ Pe did-1)
< < j d} be the of independent edge indicators, where
We adopt the parents-only local influence rule, i.e. flipping an intervention Ig orientations of edges directly incident to k (as assumed Section 7 of Chevalley et al. (2025c)) )
only affect
Since both the intervention vector I and the edge set E are random, the optimal ordering itself becomes random: Kope (I, Thiss notation emphasizes that the optimizer determined jointly by the realized interventions and by the sampled random graph, and hence the topological error

---

Published as a conference paper at ICLR 2026
(I, = Dip((((E), Topt (I, EJ) and its normalized form g(I.E) E) variables depending on both sources of randomness.
are random
We now state theorem that characterizes the deviation from the mean for the misorientation count and the false-negative rate g = f/ The first part uses the classical couded-ddifereenc inequality, while the second part invokes variance bound via Bhatia-Dart together with Chebyshev's 's inequality, using an upper-bound on the mean derived in Lemma 20 Appendix
Theorem 8 (Deviation bounds for and g in ER graphs). Fix d 2 2 and let the deterministic tie-break described in Assumption 2 select a deterministic Topt (I, E) in the equivalence class.
1. Unnormalised error. There exists C₁ > 0 such that for every t
21a
(( - T [[(LE) 21) - 2exp
C1 da
Hence f is concentrated around its mean on the O(d²) scale.
2. Normalised error. For any I. >> 0 and any choice of da E (0,
1 2(1 Pint) )
P (g) gL E) t) < 12
exp
Pi 8.2
[((1 (1- (1--8a 5a) Pe Pint
where pdd E [ Hence gI, E) is concentrated rate Of
Va around its mean.
The theorem shows that both the raw error f and the normalized error g are tightly concentrated in Prdōs--Rényl graphs. For f, deviations around the mean are exponentially unlikely once they exceed the natural (dd) scale the number of edges. After normalization, 9 has mean ((1/d) and variance of the same order, so its fluctuations occur on the typical width d-1/2, other words, as the graph grows, the expectation and fluctuation of the FNR both vanishes, providing strong guarantee of reliability for large-scale causal discovery.
In addition the previous Erdōs Rényi setting, now consider the sparse regime, where the edge probability scales inversely with the number of nodes, Pe := á. c > 0. In this regime, the expected number of edges is E [|] ((d), each node has constant expected degree. Thus the graph remains sparse even as grows, in contrast to the dense case above. This leads to an upper- bound for the mean that is constant in (Lemma 22). As result, variance-based arguments such as Chebyshev are not sufficient, and establishing deviation bounds requires stronger concentration tools.
We next state theorem that characterizes the deviation of the misorientation count and the normalized error S/|E| from their expectations in this sparse regime. The proof relies on the typical bounded differences theorem for functions of 0-1 variables (Warnke) (016) (see Theorem [3 in Appendix (). which sharpens concentration once atypical high-degree configurations are excluded. Specifically, standard results show that the maximum degree of Erdös-Rényi DAG in this regime is Ollog d) with high probability, which provides the required Lipschitz control for our analysis.
Theorem (Deviation bounds in the sparse regime Pe = e/ d). Fix and let K 0. For all d 2 2 the following hold:
1. Unnormalised topological error. For every > O,
t² 2e1 d d + Eol l log
P(]
J
+2exp
bounding Bedges and deggmare
with universal constants C1, 02 O logd) around its mean.
>
Consequently [(I E) is concentrated at rate
2. Normalised topological error. For every >
dt²
P()g(L,E)-B((L..
t)
J-
+2exp(
C3 log + Eest
bounding Bedges deg
with universal constants Ca2 > 0. Hence 9I1, E) is concentrated at rate O logd Jd
around
its mean.
7

---

Published as a conference paper at ICLR 2026
Compared to the dense Erdós Erdös-Rényi Rényi case (where Pe (1) and g concentrates with typical width 1/21 around vanishing mean @(1/d)), the sparse regime Pe c/d behaves differently: the mean of 9 does not vanish (Lemma 22 yet still concentrates with typical width Of log d This weaker than the dense case by only logarithmic factor. The log d penalty arises from controlling the maximum degree (degmax = (log d) w.h.p.); once such rare high-degres events are excluded, Warnke's ' typical bounded- For the unnormalized error f. fluctuations are O(v log d) around an (dd) mean, again reflecting the log d overhead due maximum degree control in the sparse regime.
va
inequality yields the stated sub-Gaussian tail.
4.3 SETTING III: GENERALIZED BARABÁSI-ALBERT GRAPHS
Many real-world networks from biological systems to social interactions-exhinee heterogeneous connectivity patterns, often characterized by a small number of highly connected hubs and many nodes with few connections. To capture such structures, we extend our analysis to generalized version of the Barabási-Albert (BA) (Barabási & Albert 1999) model that incorporates an initial attractiveness parameter 0 (Dorogovtsev et al. 2000).
In this generalized model, one begins with a small seed network of my nodes. New nodes are introduced sequentially, and each new node attaches to existing nodes. The probability that new node connects to an existing node is given by
1; +
P(1) = Eg +k)
(kg
where k; is the current degree of node This leads power-law degree distribution (Bollobás) et al. 2001 Dorogovtsev et al. 2000 Buckley & Osthus 2004) of the form
P(k) ~ k-,
with an exponent y that depends on both the number of links m per new node and the attractiveness parameter K. By tuning K, the model can generate networks with range of exponents, thereby accommodating different levels of heterogeneity observed in empirical data.
Since our analysis concerns causal discovery in directed acyclic graphs (DAGs), we must ensure that the network generated by this model is both directed and acyclic. To achieve this, we impose a natural time-ordering on the nodes based on their arrival sequence. Specifically, we direct all edges from older nodes (those that appeared earlier in the growth process) younger nodes (those added later). This rule guarantees that no cycles can form, as it impossible to have a directed edge pointing from newer node back to older one. With this construction, the generalized BA model produces a directed acyclic graph (DAG) that retains the desired scale-free properties.
Crucially, the emergence of hub nodes can have pronounced effect the concentration of topological errors causal discovery. In the sections that follow, we derive deviation bounds for these errors in the context of generalized BA graphs and discuss how varying y impacts the robustness of causal inference methods.
If start our generating process from empty graph, after d steps, we will obtain DAG of d nodes and E = d m edges.
Lemma 10
Bound on Node Degrees). Let G be a generalized Barabási-Alba DAG with nodes constructed described above. Then there exist constant C > O such that, with high probability, every node i E V satisfies
in-deg(i) + out-deg(i) S Cdd.
where 8 = - and
We denote this event ΣB with support EBA
Lemma 10 is a direct corollary of several well-known results on initial-attractiveness preferential- attachment processes. Van Der Hofstad (2024) Theorem 8. 1.) prove that for any fixed (m, k) the rescaled maximum degree d "A converges almost surely to a non degenerree random limit; almost- sure convergence immediately implies the stated prohh-hiigh-rrobbbliit bound. See also seminal results such as (Móri 2005; Buckley & Osthus 2004; Dorogovtsev et al. 2000) Bollobás & Riordan
2003 Bollobás et al. 2001
8

---

Published as a conference paper at ICLR 2026
Preferential erefeeentallattachmeett graphs have heavy-tailed degrees with well-understood maximum degree. Under the parents-only assumption, flipping one intervention can only affect edges incident to that node, the per-coordinate sensitivity is at most + C Cd Applying McDiarmid to the intervention vector then gives the deviations.
Theorem 11 (Deviation Bounds in Generalized BA Graphs), Let 9 generalized Barubási-Alber DAG on d nodes, with parameters >> O, K > 0, and y = 2 &. Under the natural time-ordering of edges and with [E] m d (starting from an empty seed), there exist a constants > 0 such that, with high probability, flipping one node's intervention indicator changes (II by at most Cd,,
Consequently, with high probability, by McDiarmid's 's inequality:
Unnormalized error. For any t O, EE EBA.
21
P( P( - 2 2 S exp(-
d (m + dd
In other words, f(I) concentrates around its conditional mean up to deviations on the scale d 2 for any fixed graph in the high probability event.
Normalized error. For gTT) [(T)/ (m d), fliping intervention of any single node changes gII) by most (m + C d d). Hence, letting >> 0, VE
EBA.
(11(1)- - [[]
2 2((E) S expl
2
11 d
Since Dd
m+ d ) (d the exponent scales like mn
21 Consequently. g(I) concen-
428-1
trates around [[g([)]E) at the d d scale 2B > 1, or even faster when 7 3 (i.e. B < for any fixed graph in the high probability event ΣB
5 EMPIRICAL ILLUSTRATION OF DEVIATION CONCENTRATION
Our theoretical results establish non-asymptotic deviation bounds for the normalized topological error g(, E) = Doo (E), Topt (I, E)) These guarantees concern the optimal solution to the Intersort score, for which no polynomial-time algorithm is known. As such, any practical simulation must rely on approximation algorithm, which may introduce bias. We therefore emphasize that the following experiments are provided only as an illustration of deviation concentration trends, and DIFFINTERSORT (Chevalley et al. 2024), which approximates the maximizer of the score using Sinkhorn- based optimization. While Difflntersort is not guaranteed to recover the true optimum, prior work shows that it achieves close approximations in practice and is scalable up to 2000 variables, making it suitable for empirical illustration of the scaling behavior. We generated synthetic random DAGS from three graph families: (i) Erdós Erdös-Rényt Rényi (ER) with edge probability Pa E {0.2, 0.4, 0.6]. (ii) scale-free DAGs preferential attachment with hub parameter i. E 3.0, 9.0} and m = edges per variable, and (iii) scale-free ER graphs with average degree per node [2, Gr.hr sizes ranged from d = 30 up vectors with probability Pint f0.25, 0.5, 0.75). For each configuration report the mean and deviation width of (I. E). To match the theoretical focus on concentration, report the typical deviation width of the empirical mean of the normalized topological, measured by the interquartile range (IQR). Standard deviations are reported in the appendix (Figure 2
direct of our finite-sample bounds. We employ the differentiable relaxation
2000. For each graph, we sampled single-variable intervention
repeated 10 runs and
Results. Figure reports the empirical deviation width of gI, E) as a function of for represen- tative parameter settings. Across all graph families, variability decreases with dimension, in line with our concentration theorems. For ER and sparse ER graphs, the simulations clearly confirm the theory, showing vanishing deviation as d grows. For scale-free BA graphs, the theoretical predictions are more nuanced: when x 9.0, the deviation should vanish; for 3.0, should remain constant; and for 1.0, it should grow at rate (dd/44). Empirically, the deviation shrinks for = 3.0 and 9.0, while for x = 1.0 remains less stable and fluctuates more strongly, consistent with the weaker theo- retical control in this regime. Overall, the simulations provide strong support for the theoretical results.

---

Published as a conference paper at ICLR 2026
Erdos Ranyl grap"s
graphs
Scale grachs
3.1
Orann per Verable
3.15
30
28
1/m
0:22
0,31
8.5
3.20
6.00
0:35
6:10
23
562
150 1005 1252 1963
1790 2000
200
26
1200 -C0 2000 1100 2002
589
730
1883 1230 19:0 1750 2000
(a) ER
(b) Scale-free ER
(c) Scale-free BA
Figure/ 1: Interquartile range (IQR) of the FNR as function of graph size d. For each graph family, results are shown across three density parameters and three values intervention coverage Pint- The IQR decreases with d, demonstrating vanishing variability predicted by our theoretical results, except for scale-free BA graphs with к = 1, which correspond to the heavy-tailed regime with exponent Y 1 3.
LIMITATIONS
Our analysis relies several simplifying assumptions. e-interventional faithfulness still requires that interventions induce measurable shifts in downstream distributions, which may fail in high-noise systems or with very weak effects. The random graph models we study are stylized abstractions and do not capture domain-specific structure such as modularity or hierarchy. Nonetheless, Erdös-Rényi Rényi and generalized Barabási-Albert distributions reflect several key structural features found in real-world networks, such as sparsity, variation in local neighborhood sizes, and heavy-tailed degree patterns, even though no single model captures all biological or neural properties simultancously. Likewise, our assumption of random single-node interventions represents conservative, worst-case setting: more targeted or optimized intervention designs can only improve the guarantees. Our assumption of access to sufficiently large number of interventions is not always realistic, but is increasingly common experimental settings such as high-throughpe perturbation screens (Replogle al. 2012 Yang et al. [021 Momi et al. 2025). We note that our deviation bounds do not depend on the intervention probability Pint. a limitation inherent McDiarmid-stee
al. 2022) or large-scale neurostimulation studies
inequalities; exploring proof techniques that yield deviation- level dependence on Pint is an interesting direction for future work. We also assume that causal systems are acyclic, excluding feedback loops that arise in many dynamical settings. Finally, our empirical evaluation uses DiffIntersort as proxy search algorithm. Our theoretical results concern the optimum of the score and not the performance of any specific approximation algorithm; improving practical algorithms for large-scale settings is complementary future work.
7 CONCLUSION
We presented finite-dimension deviation bounds on the false-negative rate of causal discovery under single-variable random interventions and an e-interventional faithfulness assumption that accommo- dates latent confounding. Our results demonstrate that graphs exhibiting structural regimes commonly observed in empirical systems have desirable statistical regularity: the false- delgaieee rate not only remains bounded but concentrates tightly, and in many regimes, vanishes asymptotically. These find- ings challenge worst-case intuitions and suggest that high-dimensional structure learning can, under plausible conditions, be more stable than previously expected. Our results offer principled way to reason about the trade-off between intervention budget and error, providing guidance for designing large-scale interventional studies with controlled orientation error rates. Future work may extend these guarantees to adaptive intervention policies, alternative error metrics, and more general graph distributions, paving the way for robust and efficient causal inference in large scale complex systems.
10

---

Published as a conference paper at ICLR 2026
8 REPRODUCIBILITY STATEMENT
Complete proofs for all the theoretical results are provided in Appendix with corresponding notations in Appendix B For the simulations, the parameters used are described in Section | and corresponding code is provided as supplementary material.
REFERENCES
Sophie Achard, Raymond Salvador, Brandon Whitcher, John Suckling, and ED Bullmore. A resilient, low-frequency, small-world human brain functional network with highly connected association cortical hubs. Journal of Neuroscience, 26(1):63-72, 2006.
Raghavendra Addanki, Shiva Kasiviswanathan, Andrew McGregor, and Cameron Musco. Efficient intervention design for causal discovery with latents. In International Conference Machine Learning, pp. 63-73. PMLR, 2020.
Raj Agrawal, Chandler Squires, Karren Yang, Karthikeyan Shanmugam, and Caroline Uhler. Abed- strategy: Budgeted experimental design for targeted causal structure discovery. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 3400-3409, PMLR, 2019.
Reka Albert. Scale-free networks in cell biology. Journal of cell science, 1 (1(21))4947-49577 2005.
Albert-László Barabási and Réka Albert. Emergence of scaling in random networks. science, 286 (5439):509-512, 1999.
B' ela Bollobás, Oliver Riordan, Joel Spencer, and Gábor Tusnády. The degree sequence of scale-free random graph process. Random Structures & Algorithms, 18(3):279-290, 2001.
Béla Bollobás and Oliver M Riordan. Mathematical results on scale-free random graphs. Handlbook of graphs and networks: from the genome the internef, pp. 1-34, 2003.
Philippe Brouillard, Sébastien Lachapelle, Alexandre Lacoste, Simon Lacoste-Julien, and Alexandre Drouin. Differentiable causal discovery from interventional data. Advances in Neural Information Processing Systems, 33:21865-21877, 2020.
Pierce G Buckley and Deryk Osthus. Popularity based random graph models leading scale-free degree sequence. Discrete Mathematics, 282(1-3):33-68, 2004.
Mathieu Chevalley, Arash Mehrjou, and Patrick Schwab. Efficient differentiable discovery of causal order. arXiv preprint arxiv:2410.08777, 2024.
Mathieu Chevalley, Yusuf H. Roohani, Arash Mehrjou, Jure Leskovec, and Patrick Schwab. A large-scale benchmark for network inference from single-cell perturbation data. Communications Biology, 8(1):412, 2025a. ISSN 2399- 3642.
doi: 10. 10.10388/420030055-07770
URL https
Mathieu Chevalley, Jacob Sackett-Sanders, Yusuf H Roohani, Pascal Notin, Artemy Bakulin, Dariusz Brzezinski, Kaiwen Deng. Yuanfang Guan, Justin Hong. Michael Ibrahim, Wojciech Kotlowski, Marcin Kowiel, Panagiotis Misiakos, Achille Nazaret, Markus Püschel, Chris Wendler, Arash Mehrjou, and Patrick Schwab. The causalbench challenge: machine learning contest for gene network inference from single-cell perturbation data. In Biwei Huang and Mathias Drton (eds.), Proceedings of the Fourth Conference on Causal Learning and Reasoning, volume 275 of Proceedings of Machine Learning Research, pp. 533-551. PMLR, 07-09 May 2025b. URL https::/pproceediggs mlr
www.:smmmr..p.e......mm press http://///ccaceeeeeee2 html
Mathieu Chevalley, Patrick Schwab, and Arash Mehrjou. Deriving Causal Order from Single-Variable Variable Interventions: Guarantees & Algorithm. In The Thirteenth International Conference Learning Representations, 2025c. URL
Atray Dixit, Oren Parnas, Biyu Li, Jenny Chen, Charles P Fulco, Livnat Jerby-Amon, Nemanja D Marjanovic, Danielle Dionne, Tyler Burks, Raktima Raychowdhury, et al. Perturb-seq: dissecting molecular circuits with scalable single-cell ma profiling of pooled genetic screens. cell, 167(7): 1853-1866, 2016.
11

---

Published as a conference paper at ICLR 2026
Sergey N Dorogovtsev, José Fernando F Mendes, and Alexander N Samukhin. Structure of growing networks with preferential linking. Physical review letters, 85(21):4633, 2000.
Frederick Eberhardt. Almost optimal intervention sets for causal discovery. In Proceedings of the Cnenty-Fourrhe Conference on Uncertainty in Artificial Intelligence, UAI'08, pp. 161-168, Arlington, Virginia, USA, 2008. AUAI Press. ISBN 0974903949.
Frederick Eberhardt. Causal discovery as a game. In Isabelle Guyon, Dominik Janzing, and Bernhard Schölkopf (eds.), Proceedings of Workshop on Causality: Objectives and Assessment NIPS 2008, volume 6 of Proceedings of Machine Learning Research, pp. 87-96, Whistler, Canada, 12 Dec 2010. PMLR.
ml press v6 wwweberaaaaeeeeeeeeeeeeeeeeeaaaa rdt. 0a html
Frederick Eberhardt, Clark Glymour, and Richard Scheines. On the number of experiments sufficient and in the worst case necessary to identify all causal relations among n variables. In Proceedings of the Twenty-First Conference on Uncertainty in Artificial Intellignnee UAI005, pp. 178-184, Arlington, Virginia, USA, 2005, AUAI Press. ISBN 0974903914.
Frederick Eberhardt, Clark Glymour, and Richard Scheines. N-1 experiments suffice to determine the causal relations among n variables. Innovations in machine learning: theory and applications, pp. 17-199921221 2006.
Victor M Eguiluz, Dante R Chialvo, Guillermo Cecchi, Marwan Baliki, and Vania Apkarian. Scale-free brain functional networks. Physical review letters, 94(1):018100 2005.
Paul Erdös, Alfréd Rényi, et al. On the evolution of random graphs. Publ. Math. Inst. Hung, Acad. Sci, 5(1):17-60, 1960.
Gonçalo Rui Alves Faria, Andre Martins, and Mário AT Figueiredo. Differentiable causal discovery under latent interventions. In Conference on Causal Learning and Reasoning, pp. 253-274 PMLR, 2022.
AmirEmad Ghassami, Saber Salehkaleybar, Negar Kiyavash, and Elias Bareinboim. Budgeted experiment design for causal structure learning. In International Conference on Machine Learning. pp. 1724-1733. PMLR, 2018.
Alain Hauser and Peter Bühlmann. Characterization and greedy learning of interventional markov equivalence classes of directed acyclic graphs. The Journal of Machine Learning Research, 13(1); 2409-2464, 2012.
Alain Hauser and Peter Bühlmann. Two optimal strategies for active learning of causal models from interventional data. International Journal of Approximate Reasoning. 55(4):926-939, 2014.
Yang-Bo Bo He and Zhi Geng. Active learning of causal networks with intervention experiments and optimal designs. Journal of Machine Learning Research, 9(11), 2008
Huining Hu, Zhentao Li, and Adrian R Vetta. Randomized experimental design for causal graph discovery. Advances in neural information processing systems, 27, 2014.
Antti Hyttinen, Frederick Eberhardt, and Patrik O Hoyer. Experiment selection for causal discovery. The Journal of Machine Learning Research, 14(1):3041-3711, 2013.
Amin Jaber, Murat Kocaoglu, Karthikeyan Shanmugam, and Elias Bareinboim. Causal discovery from soft interventions with unknown targets: Characterization and learning. Advances in neural information processing systems, 33:9551-9555 2020.
Dmitriy Katz, Karthikeyan Shanmugam, Chandler Squires, and Caroline Uhler. Size of interventional markov equivalence classes in random dag models. In The 22nd International Conference Artificial Intelligence and Staristics. pp. 3234-3243. PMLR, 2019.
Nan Rosemary Ke, Olexa Bilaniuk, Anirudh Goyal, Stefan Bauer, Hugo Larochelle, Bernhard Schölkopf. Michael C Mozer, Chris Pal, and Yoshua Bengio. Learning neural causal models from unknown interventions. arXiv preprint arXiv: 191.00009 2019.
12

---

Published as a conference paper at ICLR 2026
Nan Rosemary Ke, Olexa Bilaniuk, Anirudh Goyal, Stefan Bauer, Hugo Larochelle, Bernhard Schölkopf, Michael Curtis Mozer, Christopher Pal, and Yoshua Bengio. Neural causal structure discovery from interventions. Transactions Machine Learning Research, 2023.
Murat Kocaoglu, Alex Dimakis, and Sriram Vishwanath. Cost-optimal learning of causal graphs. In International Conference on Machine Learning, pp. 1875-1884, PMLR, 2017a.
Murat Kocaoglu, Karthikeyan Shanmugam, and Elias Bareinboim. Experimental design for learning causal graphs with latent variables. Advances in Neural Information Processing Systems, 30, 2017b.
Murat Kocaoglu, Amin Jaber, Karthikeyan Shanmugam, and Elias Bareinboim. Characterization and learning of causal graphs with latent variables from soft interventions. Advances in Neural Information Processing Systems, 32, 2019.
Lars Lorch, Scott Sussex, Jonas Rothfuss, Andreas Krause, and Bernhard Schölkopf. Amortized inference for causal structure learning. arXiv preprint urXiv:2205.12991 2022.
Colin McDiarmid et al. On the method of bounded differences. Surveys in combinatorics, 141(1): 148-188, 1989.
Nicolai Meinshausen, Alain Hauser, Joris M Mooij, Jonas Peters, Philip Versteeg, and Peter Bühlmann. Methods for causal inference from gene perturbation experiments and validation. Proceedings of the National Academy of Sciences, 113/27):7361-7368 2016.
Davide Momi, Zheng Wang, Sara Parmigiani, Ezequiel Mikulan, Sorenza P Bastiaens, Mohammad Oveisi, Kevin Kadak, Gianluca Gaglioti, Allison C Waters, Sean Hill, et al. Stimulation mapping and whole-brain modeling reveal gradients of excitability and recurrence in cortical networks. Nature Communications, 16(1):3222, 2025.
Joris M Mooij, Sara Magliacane, and Tom Claassen, Joint causal inference from multiple contexts. Journal of machine learning research, 21(99)11-108, 2020.
Tamás F Móri. The maximum degree of the barabási-albert random tree. Combinatorics, Probability and Computing, 14(3):339-348, 2005.
Achille Nazaret, Justin Hong, Elham Azizi, and David Blei. Stable differentiable causal discovery. arXiv preprint 2rXiv:2311..0222 2023.
Hae-Jeong Park and Karl Friston. Structural and functional brain networks: from connections to cognition. Science, 342(6155): 2013.
Cleofé Peña-Gómmz, Roser Sala-Lonch, Carme Junqué, Immaculada C Clemente, Dídac Vidal, Núria Bargalló, Carles Falcón, Josep Valls-Solé, Álvaro Pascual- Leone, and David Bartrés-Faz. Modulation of large-scale brain networks by transcranial direct current stimulation evidenced by resting-state functional mri. Brain stimulation, ((3):252-263, 2012.
Vibhor Porwal, Piyush Srivastava, and Gaurav Sinha. Almost optimal universal lower bound for learning causal dags with atomic interventions. In International Conference on Artificial Intelligence and Statisties, pp. 5583-5603. PMIR, 2022.
Joseph M Replogle, Reuben A Saunders, Angela N Pogson, Jeffrey A Hussmann, Alexander Lenail, Alina Guna, Lauren Mascibroda, Eric J Wagner, Karen Adelman, Gila Lithwick- Yanai, al. Mapping information-rich genotype-phenotyye landscapes with genome-scale perturb-seq. Cell, 2022.
Paul Rolland, Volkan Cevher, Matthäus Kleindessner, Chris Russell, Dominik Janzing, Bernhard Schölkopf, and Francesco Locatello. Score matching enables causal discovery of nonlinear additive noise models. In International Conference on Machine Learning, pp. 18741-18753. PMLR, 2022.
Karthikeyan Shanmugam, Murat Kocaoglu, Alexandros G Dimakis, and Sriram Vishwanath. Learning causal graphs with small interventions. Advances in Neural Information Processing Systems, 28, 2015.
13

---

Published as a conference paper at ICLR 2026
Stephen M Smith, Karla L Miller, Gholamreza Khorsiii, Matthew Webster, Christian F Beckmann, Thomas E Nichols, Joseph D Ramsey, and Mark W Woolrich. Network modelling methods for finri. Neuroinage, 54(2)8875-911, 2011.
2011.
Chandler Squires, Sara Magliacane, Kristjan Greenewald, Dmitriy Katz, Murat Kocaoglu, and Karthikeyan Shanmugam. Active structure learning of causal dags via directed clique trees. Advances in Neural Information Processing Systems, 33:21500-21511, 2020a.
Chandler Squires, Yuhao Wang, and Caroline Uhler. Permutation-based causal structure learning with unknown intervention targets. In Conference on Uncertainty in Artificial Intelligence, pp. 1039-1048, PMLR, 2020b.
Scott Sussex, Caroline Uhler, and Andreas Krause. Near-optimal multi-pertuurbar experimental design for causal structure learning. Advances in Neural Information Processing Systems, 34: 777-788, 2021.
Tim Van den Bulcke, Koenraad Van Leemput, Bart Naudts, Piet van Remortel, Hongwu Ma, Alain Verschoren, Bart De Moor, and Kathleen Marchal. SynTReN: a generator of synthetic gene expression data design and analysis of structure learning algorithms. BMC Bioinformatics, (1):43, January 2006. ISSN 1471-2105, doi: 10.1186/1471-2215---42 URL https://doi
org 1tc//00.116/144712211 2115--
Remco Van Der Hofstad. Random graphs and complex networks, volume 2. Cambridge university press, 2024.
Yuhao Wang, Liam Solus, Karren Yang, and Caroline Uhler. Permutation- based causal inference algorithms with interventions. Advances in Neural Information Processing Systems, 30, 2017.
Lutz Warnke, On the method typical bounded differences. Combinatorics,, Probability and Computing, 25(2):269-299, 2016.
Karren Yang, Abigail Katcoff, and Caroline Uhler. Characterizing and learning equivalence classes of causal dags under interventions. In International Conference on Machine Learning, pp. 5541-5550.
PMLR, 2018
Yuxiao Yang, Shaoyu Qiao, Omid G. Sani, J. Isaac Sedillo, Breonna Ferrentino, Bijan Pesaran, and Maryam M. Shanechi. Modelling and prediction of the dynamic responses of large-scale brain networks during direct electrical stimulation. Nature Biomedical Engineering, 5(4):324-345, 2021.
doi: 10.
A EXTENDED RELATED WORK
Theoretical guarantees in interventional causal discovery often focus on deriving upper and lower bounds on the number of interventions required to fully recover a causal DAG. Given the the observational MEC, the goal is to use targeted interventions to oriented the unoriented edges in the MEC. Intervention sets can be atomic, where only one variable can be intervened on per experiments, multiple, where the set of intervened variables multiple intervention sets, Ollog d) intervention sets are sufficient, and in the worst-case necessary to identify the true graph (Eberhardt al., 2005), and that for atomic sets, d - experiments sufficient (Eberhardt et al. 2006). Those result were later refined to show that ((logw()) (Hauser Bühlmann, 22044), where w()) is the maximum clique size of the graph, are actually sufficient for multiple interventions, as was conjecture by Eberbard (2088) These worst-case analyses take an adversarial view of the problem, where the goal is then to find an experiment selection that is robust to any adversary. [Eberhardi] (2010) expands on this game-theoretic view and proposes to use randomization to improve the expected worst case, showing that for atomic intervention (dd experiments are sufficient. Hu al. (2014) used this idea show that for multiple interventions, a randomized algorithm needs Olog log d) experiment mini-max bounds were derived under various settings (Shanmugam al. 2015 Kocaoglu al.) 2017a). Lower bounds on the minimum number of needed experiments to orient any DAG in a MEC has also been analyzed (Squires et al. 2020a Porwal et al. 2022). Relaxing the causal sufficiency
be up to d. Early work showed that for
the worse case in expectation. Similar
14

---

Published as a conference paper at ICLR 2026
assumption, Addanki Addanki et al. 2020);; Kocaoglu et al. (2017b) derive sufficient set of interventions to recover the graph, as well has its latent variables. Regarding "average case" scenarios, for example by considering parameterized graph distribution, the literature is more limited. For example, (Hu et al. (2014); Katz et al. 2019) show that for an Erdös-Rényí graph distribution, the sufficient numher of interventions to recover the graph is constant in expectation. Average case analysis may provide more practical insights for real-world causal discovery compared to worse-case analysis. Existing literature also limited in the sense that faithfulness or knowledge of the observational MEC, as well as causal sufficiency, are often assumed.
adjacent line of research considers the problem of intervention design under budget constraints (e.g. limited number of interventions), or adaptive sequential selection of interventions (He & Geng 2008 |yyttinn et al. 2013; Ghassami et al. 2018 Hauser & Bühlmann 2014] Sussex al. 2021 Agrawal et al., 2019). Here, the goal is to maximize the utility of the limited set of performed interventions. Given that finding the optimal set general not tractable, the focus is around finding provably approximate (greedy) algorithms.
The characterization of necessary intervention sets to fully identify causal graphs also does not answer the question of partial identification under limited number of interventions. In seminal work, Hauser Bühlmann (2012) characterize an interventional Markov equivalence class (I-MEC) given multiple interventions and propose greedy algorithm for structure learning with interventional data. I-MECs can only be smaller than the corresponding observational MFC, and thus interventions improve identifiability. Many work followed and refined on this idea, both around characterizing equivalences classes under various assumptions (Yang et al., 2018 Jaber et al. [2020] Kocaoglu et al.) al.] [2019] Sqqiies
al. 2020b) as well proposing more efficient learning algorithms (Brouillard al. [020 Ke
et al.
2019
Mooij et al. 2020 Nazaret et al. 2023 Wang et al. 2017 Paria et al. 2022 Lorch
al.
2022
B
LIST OF NOTATIONS
V. The set of nodes (or random variables), with V (1,2.....d)
d The number of nodes (or dimensionality) in the causal graph.
g = (V, E) A directed acyclic graph (DAG) representing the causal structure, where E CVVVV the set of directed edges.
A The adjacency matrix of G, where
1, if (1,)) A
0, otherwise.
Pa(j) The set of parents of node j. i.e., Pa(j) (i e (1.))
Ajg(j) The set of ancestors of node j (all nodes with directed paths leading to j).
Deg (j) The set of descendants of node j (all nodes reachable by directed paths from j)-
C C= (S, PN) A structural causal model (SCM), where S is the set of structural equations and Px is the joint distribution over the exogenous noise variables N = (Ni...., Na).
X, The j-th random variable in the SCM, with structural equation
X, = fx (X Pa())) N2)-
N, The exogenous noise variable associated with Xy.
Nu The new exogenous noise variable used in an intervention on Xx.
I The set of intervention targets, where I C V.
I = (I,....,Ta Ta) The intervention indicator vector, where
1, E
T 0. otherwise.
P The observational distribution of X corresponding the SCM C (i.e., with interventions).
15

---

Published as a conference paper at ICLR 2026
pe N No) The interventional distribution of X when the structural equation for Xg is replaced
by Xx Na.
A permutation of V representing candidate causal order.
II" The set of all causal orders (permutations) consistent with G.
Drop (G, T) The topological error of ordering with respect to G, defined as
Diop (9, Tt)
Σ
A
((1)>=())
Drop (G, Topt (I)) The topological error of the optimal order under fixed graph G when the interven- tion vector is random. Here Topt (I) denotes the score-maximizing permutation given the specific realization of I. Thus Dtup (G, Topt (I)) is random variable through its dependence on I, while the graph G is treated as fixed.
Drop (9, Topt (I)) The topological error of the optimal causal order when the underlying graph G is fixed and only the intervention vector I random. Here Tope (I) denotes the order that maximizes the score function given the specific realization of Thus, Drop is random variable induced solely by the randomness in the intervention design.
D A statistical distance (or divergence) function
D: P(M) P(M) + [0. oo),
which measures the discrepancy between two probability distributions.
c significance threshold used in the definition of c-interventional faithfulness and in the score function.
A constant with c used in scaling terms of the score function.
S(T, D,I, ,C Pint, <) The score function defined in equation that evaluates how well candidate ordering ı aligns with the interventional data.
f(I) The unnormalized topological error in the fixed-grane graph setting, defined as
f(I) := Drop (G, Topt (T)).
This quantity is random only through the intervention vector I.
g(I The normalized topological error (false negative rate, FNR) in the fixed-grape setting, defindd
as
9 T = f(I)
E
where E is the total number of edges in the fixed graph G.
f(I, E) The unnormalized topological error, defined
(I, E) := Drop (G(E), Topo Topc E)).
Here the dependence on (I, E) is made explicit, since both the optimal order and hence the error are random variables determined by the intervention vector and the random graph.
g(, E) The normalized topological error (false negative rate, FNR), defined as
[1 E) = f(I, E)
E
where E is the total number of edges in ((E).
The Lipschitz constant measuring the maximum change in f(I, E) upon flipping the k-th inter- vention indicator, i.e.,
Ck
max
S(I E) - f(I,
1= Egkk
16

---

Published as a conference paper at ICLR 2026
C BOUNDED DIFFERENCES THEOREMS
Theorem 12 (Bounded differences inequality, McDiarmid et (1989)) ) Let X (X1,..., XN) be
independent random variables with X₃ taking values in Ag- Suppose f I Ax + R satisfies
[f(z) - f(=')) - ck whenever x, x' differ only the kth coordinate.
(3)
Let μ [X)] Then for all z 0,
2t
P(J(X) 2+1 exp
N
=k=1 C
An analogous bound holds for the lower tail P(f(X) S 14-11 t).
Theorem 13 (Typical bounded differences inequality, Warnke (2016). Let X (XI,... XN) be independent with X E Ag, and let C II A be an event. Suppose
II As + I satisfies
Ck: TET,
If(z) f(x') 5
du. x I,
whenever x, x' differ only in coordinate For any 7 (0, 11, ler ex = nx(dk cx). Then there is
"bad" event B with
P(-1")
P(B) S
7h
k=1
for all 2 0, on B one has
12 {xp(=2 2 (cr + e
P(f(X) 2 Ef(X) + and -B) & exp(
2
Theorem 14 (Typical bounded differences for 0-1 variables, Warnke 2016)). Let (Xi..... XN) be independent with X₁ E {0, 1} and ps (Xx, =). Let [ 10.1 and suppose f {0. 1) satisfies the same one-sidee Lipschitz condition above with coefficients ck. dg and compensation e* (dl - -ck). Define C = max; (Ck + ex) and V = = Pk)Pk(Ck + ex)? Then there is "bad" event B with the same bound as above, and for all 2 0.
t²
F(f(X) 2 Ef(X) + and -B) S eexp
2V + 2Ct/3
D THEOREMS FROM CHEVALLEY ET AI.. 2025c
Lemma 15 (Sufficient condition for orienting an edge Chevalley et (2025c)) ). Assume that
given pC,(0) and PCC.. do,do(X, Ny) Vk I, such that (Ñ,C) W) is e-interventionally faithful for some e O, and let opp aargmax, S(T). Let (i,5) E, then if I or for some k AN9 (AN k I. then Topt (i) < Topt (j).
Lemma 16 (Sufficient condition for orienting an edge under restricted interventional faithfulness Chevalley et al. 2025c)). Let (i,j) E E, then if I or for some k E Pay Pa k I, then Tope (1) < Topt (3)-
E ADDITIONAL THEORETICAL RESULTS
We here derive set of theoretical results that upper-bound the expected FNR for all the graph types considered in this paper. Corresponding simulations to verify the theory can be found in Appendix G.2
17

---

Published as a conference paper at ICLR 2026
E. BOUNDS ON THE MEAN FOR FIXED GRAPH, RANDOM INTERVENTIONS
An edge (i.j) fails to orient correctly only if neither nor any of the "useful" ancestors of (those not shared with are intervened. Under independent random interventions, this failure probability is a simple power of (1 - -Pss),, and summing over edges gives the expected FNR. A direct Markov inequality then converts this expectation into tail bound.
Lemma 17 (Probability bound on the fraction of topological errors). Let Ca R, 0 < <1. and the graph is non-empty, i.e. |g] = [E| > Then we have Vcc
( 2 ce) S
Σ
(1 Pine) ANJUUMANN?
Co |
(b.))gg
The probability is also strictly bounded by 1.
Corollary 18 (Expected FNR). Under the same assumptions, we have
E [
S
1
Σ (1
Pint)) ((--Pmt))AAg)) JANJUURAN)
E
(1J)
E.2 BOUNDS ON THE MEAN FOR ER GRAPHS
In an Rénds DAG, the expected number of misorientations grows only linearly with d, whereas the number of edges is quadratic. We therefore expect the normalized error to be small with high probability. Formally, we pair a Markov bound on the numerator with a Chernoff lower tail on the random denominator [E), obtained by conditioning the event that |E| is close to its mean.
Lemma 19 (Probability bound for FNR). For any O < Ce < and 0 < < <81 1
(1 E) 2 co) S Ce (d + exp (- ["ppd(dd11
2(1 Pint) )2
The proof splits "good" event where |E] is not too small. On that event, the ratio is small; off it, the event's probability is exponentially tiny. This yields an explicit finite-d tail bound for the FNR in ER graphs.
Because E[Drop] = (d) while E| = O(d²) in ER graphs, the expected FNR should decay to The only technicality is that F is random; again good-event/bad-event split resolves this.
Lemma 20 (Fraction of Misoriented Edges Vanishes in Expectation). Let G be an Tadōs-Rényl DAG on [d] with edge inclusion probability Pe (0, 1], and let Pine (0, 1]. For any sequence 8 E (0, 1), define the event
Aba = F. 2 (1 (1) ma].
Pe d(d 1).
Ad =
Then
Drop (G, Topt)
2(1 Pint)
1
Hld 53
E
exp
E
(1 54) Pe Pint
d
In particular, choosing any da + (e.g. 5, = 1/2 yields
D Drop G Topt)
2(1 + o(1)) Pint)
1 exp(- ((-((()))
E
d +
Pe Pint
and hence limd+ E EiDrop (9, Topt |/| 0.
On the good event EE| ~ d,, the ratio is O (1)); the bad event the ratio is at most but the event is exponentially rare. Taking expectations yields the vanishing limit.
E.3 BOUND ON THE MEAN FOR SCALE-FREE ER GRAPHS
When the graph is sparse with Pe -. the number of edges is only Odd), normalization is weaker and concentration should less sharp. Nevertheless, the same Markov+Chermoff recipe delivers explicit non-asymptotic FNR bounds, and one read the precise dependence on and Pint-
18

---

Published as a conference paper at ICLR 2026
Lemma 21 (Probability Bounds for FNR in Scale-Free Setting), For any <c < 1,0 <d<,
Ce. E
2(1 Pine)?
+ exp ( 8cd
(-44)
(g ce) I
(1 -)c c Pine
4
We have at infinity:
2(1 pint)
lim d-000
(I. E) 2 Cc)
1
Pint (1 Pintic)
Pint
The proof mirrors the ER case after substituting El E (d). For the asymptotic expression,
use the known limit for E E/Dtopl/d (Chevalley et al. 2025c).
Lemma 22 (Expectation Bound for FNR in Scale-Free Setting). For any sequence dα E (0, 1), we have
Deop (9, Topt.
2(1 Pint)
d
Hd 53
E (()
d- +
exp
E
(1 8d) c Pint
2
In particular, taking any da + O with Pddd
+ 00 (e.g. 5d d 1/2 yields
- Pine)?
+ exp(-
cpint
Corollary 23 (Asymptotic expectation bound). Under the same assumptions, we have
Drop(( (9, Topt.
2(1 Pine))
(1- -ineer
limsup E d-+00
Cint
Pint
E.4 BOUNDS ON THE MEAN FOR SCALE-FREE BA GRAPHS
Theorem 24. Let be chosen uniformly at random, G a random generalized Barabási-Albert model directed acyclic graph with my = 0 and m >> 0, where Pint := P(i E TYVi E V,0 Pint 1, then Lop (9, Topt)] I (1 Ppnn)² m
This bound can seem quite loose. However from Theorem 3 of Chevalley et al. (2025c), the general bound for graph is Lo] Topt]] S EL Pint) Pa
Furthermore, for each
edge in BA graph, we have PPay U [ Pa < + m, which is close to 2 for sparse graph. Moreover, for the edge case where λ = O, and thus there is single a single node that the parent of all the other nodes, the bound is exact. In any case, the bound O(d).
Corollary 25. The expected FNR is E
Drop Fope)
< (1 pint)a and the probability bound on
[
the fraction of topological errors is P
Drop [7]
2 Ce
(1-
F PROOFS
Proof of Lemma Under the stated assumptions and by the result of Lemma 4 in (Chevalley et al. 2025ch, for any edge (i.j) the optimal permutation Topt satisfies
Topt (i) < (o)
if either E I there exists some & E AN \ ANŞ such that & E I. Hence, when flipping the intervention indicator at node k, the only edges whose correct orientation might be affected are those for which the intervention status of ls is crucial, and misorientation of an edge affects Dcop by 1; define
A = (1.)) E: (k (k= j=jon or & E AND AN?)
By the definition of the Lipschitz constant, we have
C₁ |A
We now partition A into two disjoint subsets:
1 = ((i.)) E E: k) and
(2)
((1,)) F: F: AND ANŞ).
19

---

Published as a conference paper at ICLR 2026
1. For any edge (i:5) E A have j k. Since must be an ancestor of k. the number of edges in A is at most the number of ancestors of k, so
144 (1) - |Anc(k)]
2. For any edge (i,j) E A the condition E ANY implies that j is descendant of k.
In the worst-case, each descendant of contributes at most one edge in (22) (this is conservative bound given that multiple edges may share the same descendant but assume a one-to-one correspondence in the worst-case scenario). Thus,
A S [Desc(A)].
Combining these two bounds, we get
Ck |A&l 14 (1)
|A
(2)
S Annc()]] + [Desc(k)]-
This concludes the proof.
Proof of Lemma 4 Under the relaxed c-interventional faithfulness assumption, by Lemma of (Chevalley et al. 2025c), for any edge (i,j) E E the condition
JEI or 3E Pay. Pa with ls E I
holds, then Topt (i) < (j). Hence, when flipping the intervention indicator of node k, the only edges that might be affected are those whose correct orientation is determined by a direct parental relationship involving k. Define
By = (i.)) k E Paf Pa!)
Then the Lipschitz constant is given by
Ck Bx
We now consider the two components of By:
1. For edges (i,j) with j = k: here, must be direct parent of k. Hence,
(((i,)) B& : = k} s in-dog(k).
2. For edges (i.j) with Paf Paf: this case, l: is direct parent of j. Consequently, each such edge corresponds to a unique edge emerging from node (i.e., an edge for which i parent). Therefore,
((i,)) E By k Paf Pa & out-deg(k).
Combining these, we conclude that
Ck = |Bal S in-deg(k)) + out-deg(k)..
This completes the proof.
Proof of Lemma Let (V, F.) and G' (V,,A(()))))) differ only the indicator of the edge (i.j), and let
π = Tppt (I, E),
n' Topt
denote the uniquely broken maximisers (Assumption 2}. We distinguish three cases according to the intervention pattern for the endpoints.
Case 1:4 &
20

---

Published as a conference paper at ICLR 2026
Lemma 16 can only use intervened parents to force orientation. Since i is not intervened, adding deleting the edge (1,j) never adds a new "witness" parent to any edge (k, Hence every orientation rule is unchanged and fI, E) f(I,E')
Case 2: E I and E I
Because the child vertex j itself is intervened. (k, is already forced to point ++ ý in n; the extra parent i does not alter that decision. Again fII, E) = f')
Case 3 (worst-case): I, j j I
Now sufficient condition Lemma 16 can change. For an edge (k, E define
5kg if
Pa
If 5 the set Paj Pag is the same in G and g', so (k, keeps its orientation. If ōkj the new parent i is added to that set, so (k, may flip direction; this contributes at most 1 to E) f(I, E.
The total number of such edges is
Agg
Σ
ōkj S
Pa
degm (f),
l:: (KJ)EE
hence [(I, E) E') & degin (i).
Combining the three cases, the coordinate Lipschitz constant is
Ci max /(I f(I, E') S degin flip B.,
and the bound is attained only in the worst-case pattern i I, J J
Proof of Lemma 17 The proof follows directly from the results in (Chevalley et al. 2025c). Under c-
interventional faithfulness and the uniform random choice of I, each edge misorientation probability can be bounded by term involving (1 - -Pint) - (ANYUU)) AN??, We then apply the Markov inequality to obtain the upper bound.
Proof of Corollary 18
The result is a direct corollary of Theorem 2 of Chevalle et al. (202cc).
Proof of Theorem 7 From Lemma 3 the orientation of each edge (i,j) can be guaranteed to be correct if either is intervened upon, or if there is at least one ancestor of (not an ancestor of i) that intervened upon. Thus, the intervention status of single node can influence only those edges that rely on & to establish correctness.
By definition of Ck, these are exactly the edges (i,j) for which k = or h: E EAN! \ the maximum over all & gives max; Ck. Hence, flipping Iş can change f(I) by at most eæ S and g(I) = /[T)/| by most c=/|E| e/
ANN Taking
Since I consists of independent Bernoulli variables and (resp. g) satisfies a bounded--differences condition with constants (cx) (resp. (Fl)) we can apply McDiarmid's inequality. For f [I), we get:
212
[_222
212
P(J(() - E[f(D) 2 S 2exp
S 2exp
(-1v|e²
IV]
2
For g(T) [(T applying McDiarmid's with differences bounded by Ck E/, we have:
2ta
22 Σ km
2/2)222
P())())-Ei(() 2 t) < exx
= 2exp
< 2 exp
>
(c)/1
2
[V|02
21

---

Published as a conference paper at ICLR 2026
This completes the proof.
Proof of Lemma 19
Part (Normalized by I=(
By Markov's inequality, for nonnegative random variable X and > have:
[
P(X 2 a
Apply this with X Drop and a = E
Dtop 2 Ce = P(Drop 2 ce B(
E8 D top
E( E])
E
From Theorem of Chevaleey al. (2025c), we know:
Pint) )2
E Deoppl -
d.
Pint
Also,
d(d 1)
E[ Pe
Substitute these into the ratio:
Pini) d Pint
E Dropl
E'
d(d-1) Cp Pe 2
Simplify the fraction:
(1 pint)2
CoPoele (dd 1) d.
Pint
Hence:
Drop E((E))
2(1 - Pine))
P
Ce
CopintPe (d
Part 2 (Normalized by |E);
Normalizing by the random variable |E] is more challenging since |E] is not constant. Consider any
0 < 8 < and split the event:
Dtop
2 =
P(Drop 2 Eel S P(Drop 2 ce(1 cc(1-o)E((E))) + E < (1 6) El).
For the first term, apply Markov's inequality again:
P(Drop 2 ca(1 - 5)B( < E[Drop]
Ce E
Using the same bounds as before:
Pine) d.
E[[E|] = Pe d(d 1)
E toopl
Pine
2
Substitute:
(1-pine)² d
E[D (1 - 81
2(1 Pine)
Pint
co
8)p d(d-1)
ce - dippna (d 1)
2
For the second term, |b| is a Binomial random variable with parameters d(d-1) and Pe Chernoff bound gives:
(- 8
8 ppp -
P([E) < (1 ())( & exp
-exp
2
4
22

---

Published as a conference paper at ICLR 2026
Combining both results:
Drop 2 cc)
2(1 - -Pint)
-pp.ddd11)
P
S co(1 O)pintPe (d-1) + exp
E
4
This completes the proof.
Proof of Lemma 20
Step 1. Concentration for [B] Let pa
Eljll|
2d(d 1). By the
multiplicative Chernoff bound, for any óg E (0, 1).
Md 62
P(E < (1 - -da)pa) S exp
2
Set As, { 2 (1 5a)pa} } so that P(A S exp
Mdt o2
Step 2. Bounding the ratio on As, and on A We use the deterministic upper bound Dtop S
pine)
d. Thus, on Aöa-
Pont
(1-pint) d
Diop [
(1 - pine)?
d
2(1 - Pint))
Pont 8a)
(1- da) Bg d(d -
(1 (1-60, 5a) Pe Pint 1
Pint
On A we trivially have
Drop
< 1.
TEl
Step 3. Taking expectations. Decomposing over Ab,, and Agg-
Drop
2(1 pint))
E
P(Ass) + 1 P((S))-
E
(1 8d) Pe Pint
Since P(As.) $ 1 and P(AA.)
I <expl n4. 83
we obtain
Diop E
2(1 - -Pins)
1
+ exp (app-11u Md 82
(1 5a) Pe Pint
d 1
2
which is the claimed bound.
Choice of dd. Taking any da I. improves the leading constant toward 2(1 pimi)? while the tail P.Pine
remains exponentially small provided naod - co. For example, da = d-1/2 gives p0 = ((d) and thus an exp(-s?(d) tail, yielding
Drop
2(1 o(1))( Pint)
d + exp( -dd))
E
Pe Pint
Proof of Theorem nanommamdd error Flipping any single coordinate affects most all edges incident on vertex, |Afl < d. With N - (2) + d = ((d)) coordinates, Ee og Cid for a universal constant C1. McDiarmid's inequality yields the stated tail.
(b) Normalised error.
Since 0 S g S 1, Shatia-Davis with (m, M) (0, 1) gives
Var(g) < (M - Eg) (Eg - m) = (1- Eg) Eg S Eg.
Chebyshev's inequality then implies
Var(g)
Eg
P(gg Egl 2 t) <
<
12
12
Finally, insert the expectation bound (Lemma 20
2(1 Pint) )
My 63
Eg < (1 64) Pint d -
+
exp
2
Choosing 5, 1/1 makes the exponential term 1/d, as stated.
and the leading term decays like
23

---

Published as a conference paper at ICLR 2026
Proof of Lemma 21 The proof of both bounds follows from Lemma 19 19 by replacing Pe by For the limits at infinity, we use Lemma of Chevalley et al. (2025c), which states that:
lim d0000
IE Ei(Dopp (9, Tapt]]
Pint
(1 E Pinerc)
d
Pint
Pint
The bound infinity for the first part, i.e. normalized by the expected number of edges, follows directly by applying markov and using Lemma 6. For the second bound, where we normalized by the actual number edges, we do the same, with the extra step of taking ((d) d", where - < a Then taking the Taylor expansion of I-a(aj around 0, only the first term, which is the same as the first part, does not vanish to O.
Proof of Lemma 22 Step 1. Lower-tail concentration for E]. By multiplicative Chernoff, for any da 10,
P( < 6a)ra) I exp
Md 0
c (d-11) 1).
Nd
2
Let As2- = (1E) 2 (1 - 6a)pa), so P( S 1
Step 2. Bounding the ratio on As, and - We use the deterministic bound Deop S [1-Pine) d. Pini
On Asg-
(1 (1-pint)² d
Doop E
(1 Pint )
d
2(1 - Pinn) d
<
Pirt
Pint
(1 - 52) (d (1 52) Cint d - 1
On Ag. trivially
Dtop |
< 1.
Step 3. Taking expectations. Decomposing over As, and Ag, gives
Doop F
< - Pime)?
E
58) cPint d P((Aa) + PP(A)));
and the claim follows since P(As,) 1 1 and P(AA,) S exp(- (xp((~163//2)
Proof of Corollary 23
Pick any da J 0 with f + xo (e.g. 8s d d/2)), By Lemma 22
2(1 pint) 2 d
g(I EI)
<
+ exp(-H203/1
(1 - 6 d-1
d Letting d - oo sends the exponential term to 0, d-1 1, and 1 scale-free limit for the por-node misorientations (Lemma 6 of Chevalley et al. (2025c)), namely
1-8, - 1. Finally, plug in the
lim E[D (G, ma
(1 - Pint))
1
<
(1- --Piee)))
Pince)
Pint
PintC
and combine with E E pd bound.
5 1) in the proof of Lemma
22 to obtain the stated
Proof of Theorem the families (Eighej and (1 j
We apply Warnke's 0-1 typical bounded differences inequality (Theorem 13) to jointly.
1. Hiob-brobability event r. Define
F== deg S Ko logg |Ba < 2ed
where Ko > O is chosen so that P(-T)= < d (K+4), (K44),K > The two parts of follow from Chermoff bounds and union bound over vertices.
24

---

Published as a conference paper at ICLR 2026
2. Typical and worst-case Lipschitz constants.
edge (i,j): Cij Ko log d 1r,
dig d; du = d.
intervention 4 Cj Ko log lr,
Indeed, on flipping any coordinate changes f by at most degmax S Ko log d, whereas the worst case it may change many edges.
3. Parameters 7k, compensations ck. and yk- Choose the uniform parameter
d Ko log d 1r
Th = d (vk),
Ck : (a (k))
da
4. Bad event B. Warnke's bound gives
S P(-T) & (0(d)) dl (k++4) S d K
N
P(B)
5. Constants C' and V for the two functionals.
(i) Unnormalised error f-
max (c+ ex) S Ko log + (d d)/ogd)/d S 02 log d for some 02 >
Edge variables: Pe = c/d, one-bit bit variance (1 - Pc)Pe(Cc + ex)² (gog d))). With
( edges this sums (dd d).
Intervention variables: Pint constant, d terms of order (log d) yielding the same order. Hence V Ogg d).
Warnke's inequality gives the tail in part (a).
(ii) Normalised error g = f/
On I. EE| S 2cd, dividing the and dz 1. C and every summand of V by |E|-2 2 = O)d
C O logd d
log
times (2), i.c. O los Edge contribution to V: 0 lox"
de Intervention contribution: d terms, each O log d). same order.
Thus V O log 2d and Warnke's 0-1 inequality yields the bound in part (b).
Proof of Theorem 77 Step 1:
High-Probability Degree Bound. By construction in the generalized Barabási-Alle model, every node (beyond the initial seed) has in in-degree exactly m. Existing results show that with high probability the out-degree of every node is at most C d where
1
8
and
7 = 2 +
That is, with high probability, the entire graph satisfies
in-deg(i) out-dog(i) I Cd
VieV.
We denote this event by EBA and its support by FEA
25

---

Published as a conference paper at ICLR 2026
Step 2: Bounded Differences (Conditional on E EBA). Fix any graph E EBΛ. Then the graph is deterministic, and only the intervention vector = (II...., Ia) is random, with each I; being an independent Bernoulli (pie)) variable. Define
f(I) Drop (9, Tope (I)),
where G is the DAG determined by E. For each node let
[(X) f(())
Cj
max 11
1 for jzf
Under the "parents-only local influence" assumption is, flipping I; can only affect the orienta- tions of edges incident on node i-we have for any fixed EBA
C S in-deg(i) + out-deg(i) - m + Cd
Thus, for all we may take
c S m Cdd.
Consequently, the sum of squares is bounded by
c s d (m +
Step 3: Application of McDiarmid's Inequality (Unnormalized Error). Conditional the fixed graph E E EBA, the intervention vector I consists of independent random variables. Hence, by McDiarmid's inequality,
21 Σ
2t
P(I5()- - E[
E
E
S
exp
S 2 exp
d d(m + C d
Thus, for every fixed graph E E EBA. ((T) concentrates around its conditional mean [[[(T) with deviation scale ())
E
Step 4: Application for the Normalized Error. Define the normalized topological error by
f(I)
f() md
gII
F
since by construction, [E|
m d (when starting from empty seed). For any fixed E E EBA- flipping the intervention I, changes f[I) by at most m + C d hence the corresponding change in g(I) is at most
+ Cd
m
Since this bound holds for each i, the sum of squares of these differences is
Σ
m + C
(
m C d 2
= -
=d
m.d
md
==1
Thus, applying McDiarmid's inequality conditionally on E yields, for any t t> 0.
2ta
p( [((I) EIg(I)
E
E
< 2 exp( Od22-11)
That is, gI) concentrates around its conditional mean [I at the scale 0 Notably, = (so that 3 = 1)) the concentration at an O()) level; if y > 3 (so that 3 < 1), the normalized error becomes tighter.
Conclusion.
The proof shows that for any fixed graph E EBA (i.e., in the high- probaabbbbbty event ΣBA),, the deviation of the topological error f[I (and hence (I)) from its conditional mean is bounded by the stated exponential terms. The overall statement then holds with high probability for almost every graph (over the random graph generation) for every such fixed graph.
This completes the proof.
26

---

3 edges per node and consider Published as a conference paper at ICLR 2026
G ADDITIONAL EMPIRICAL RESULTS
We provide supplementary plots corresponding to the parameter sweep described in Section
G.1 DEVIATION PLOTS USING THE STANDARD DEVIATION OF FNR
Figure replicates the analysis of Figure T but reports the standard deviation instead of the interquar- tile range (IQR). The qualitative behavior is the same: variability decreases with d for all graph families, consistent with our theoretical predictions.
G.2 EMPIRICAL EVALUATION OF THE SCALING OF THE MEAN ERROR OF FNR
Using the same parameter sweep as in Section Figure plots the mean false negative rate (FNR) as a function of graph size d, alongside the theoretical upper bounds derived in Appendix E Across all graph families and parameter settings, the empirical means remain below the theoretical bounds, confirming their validity. The only visible exception occurs at high intervention coverage (Pine 0.75), where the empirical error occasionally exceeds the bound. One possible explanation is that in this regime the distance matrix becomes denser, which increases the difficulty of the optimization and may cause DiffIntersort to return orderings farther from the true optimum. This highlights that results analyze theoretical properties of the score function, while the empirical performance also depends on the optimization dynamics of the chosen algorithm.
G.3 ADDITIONAL RESULTS FOR THE UNNORMALIZED ERROR DrOP
For completeness, we report the same set of empirical results in Section but using the unnormal- ized topological error (9 Topt) instead of the normalized false negative rate (FNR). Figures o show the mean values and deviation widths of Dop across the three graph families (ER, scale-free ER, BA) under the same parameter sweep.
G.4 SCALING OF MAXIMUM DEGREE IN BA GRAPHS
Figure (aaureeee how the empirical scaling of the maximum degree in Barabási-Albert (BA) graphs approaches the theoretical prediction. We generate graphs with
7 3, 5, while the empirical fits yield (1.0, 3 3.0, 9.0). Theory predicts degree exponents 7 = 3: 2.37, 2.93, 4.11, respectively. The estimates align closely with the theoretical values, with only a mild underestimation for x 9.0, suggesting slower convergence in this regime. Overall, these results validate that our generated BA graphs faithfully reproduce the expected heavy-tailed behavior.
H ANALYSIS ON SYNTREN-STYLE NETWORKS
To complement our analysis parametric random- -rapp ensembles, perform additional study on biologically inspired synthetic networks generated using the SynTReeN model (Van den Bulcke al. 2006). These networks do not follow closed-form generative model (e.g. ER generalized BA), and therefore our parametric deviation theorems cannot be applied to them. However, the general fixed-graph deviation inequality (Theorem 7 together with the expectation upper bound of Corollary 18 hold for any fixed DAG. We also apply the parent-only local influence assumption. This makes it possible assess whether the camension-adaptivy behavior observed on ER/BA persists on more realistic network topologies.
Datasets. We extract gene-regulatory networks of sizes d = 300 and d 1000 from the grndata Bioconductor package, which provides SynlReN-style topologies We construct the corresponding DAGs, removing edges when necessary to avoid cycles. The resulting graphs, which we refer as SYNTREN300 and SYNTREN 1000, contain realistic regulatory motifs but do not arise from a known parametric distribution.
27

---

Published as a conference paper at ICLR 2026
Across all metrics expectation bounds, deviation bounds, and large-error probability bounds- SYNTREN 1000 exhibits consistently smaller orientation error than SYNTREN300 for all values of Pint (Figure 8) Specifically:
Results.
the upper bound on [T)( is uniformly lower in the d = 1000 network;
the deviation width shrinks as the network dimension increases;
consequently, the bound on (Ig 2 0.4) is much smaller for SYNTREN100F across all examined Pint-
These findings align with the cnneasion-adaapive behavior predicted by our parametric results: larger networks exhibit both lower or equal expected orientation error and tighter concentration, even when the graph does not follow a simple random-grap distribution. This provides empirical support that the stabilizing effect of dimension, established analytically for ER and BA distributions, also appears in realistic biological network topologies under randomized interventions.
I LLM USAGE DECLARATION
We declare that LLM systems were used perform part of this work, such polishing the text and presentation, writing (plotting) scripts, and exploring potential proof techniques.
28

---

Published as a conference paper at ICLR 2026
Std FNR vs. d Erdos-Renyi graphs
0.06
p.e
0.05
0.4
0.25
Std of FNR
0.75
0.00
250
500
750
1000
1250
1500
1750 2000
Dimension (d)
(a) ER
Std of FNR vs. d for Scale-Free ER graphs
0.12
Edges per Variable (c)
0.10
3.0
5.0
R_int
0.25
Std of FNR
0.5
0.00
1250 Dimension (d)
1750 2000
(b) Scale-free ER
Std of FNR vs. for Scale-Free BA graphs
0.200
Kappa
1.0
0.175
9,0
0.150
p_int
of FNR
0.125
0.5
... 0.75
0.050
0.025
0.000
500
750
1000
1250
1500
1750 2000
Dimension
(c) Scale-free BA
Figure Standard deviation of the FNR as function of graph size d. For each graph family, results are shown across three density parameters and three values of intervention coverage Pint- The deviation vanishes with growing in line with theory, except for scale-free BA graphs with x corresponding to heavy-tailed regime with exponent 3 < 3.
29

---

Published as a conference paper at ICLR 2026
Mean FNR Frdos-Renyi graphs
p.e
1.4
0.4
1.2
1.0
0.25
Mean FNR
0.6
0.4
0.2
0.0
250
500
750
1000
1250
1500
1750 2000
Dimension (d)
(a) ER
Mean FNR vs. d for Scale- Free ER graphs
0.5
Edges per Variable (c)
3.0
5.0
R_int
0.25
0.5
Mean
0.2
0.1
0.0
1500 Dimension (d)
1750
(b) Scale-frce ER
Mean FNR vs. d for Scale-Free BA graphs
Kappa
1.0
0.5
9.0
p_int
Mean FNR
0.5
0.75
0.3
0.2
500
750
1250
1500
1750
2000
Dimension
(c) Scale-free BA
Figure Mean false negative rate (FNR) versus graph size d across Erdös Rényi (ER), scale-free ER. and Barebá (BA) graphs. The solid lines with points denote empirical averages; lines without points show theoretical upper bounds from Appendix E The bounds hold across all settings, with slight mismatch at high intervention coverage (Pint 0.75), likely due to optimization difficulties in DiffIntersort.
30

---

Published as a conference paper at ICLR 2026
Mean D top vs. d for Erdos Erdos-Renyi graphs
4000
3500
3000
0.6
p.int
Mean t.top
2500
0.25
0.5
0.75
1500
1000
500
250
1250
Dimension (d)
(a)
Mean D p_top vs. d for Scale-Free ER graphs
1400
Edges per Variable (c)
2.0
1200
5.0
1000
R_int
Mean D top
800
0.5
11 0.75
600
400
200
0-
250
750
1000
1250 1500
1750 2000
Dimension
(b) Scale-free ER
Mean D top d for Scale-Fres Freee BA graphs
2000
Kappa
1750
1.0
1500
P_int
Mean D_ __top
1250
0.25
1000
0.75
750
250
0
250
500
750
1000
1250 1500
1750
2000
Dimension (d)
(c) Scale-free BA
Figure 4: Mean unnormalized error Drop versus graph size across Erdós Erdös-Rényi (ER), scale-free ER, and Barabási-Albert (BA) graphs.
31

---

Published as a conference paper at ICLR 2026
IQR of D top vs. d for Erdos-Ress Renos- graphs
250
0.2
0.6
p
IOR of D top
0.25
0.5
1150
0.75
100
50
250
1750
Dimension (d)
(a)
IQR of D top vs. d for Srele-Free ER graphs
Edges per Variable (c)
2,0
5.0
R_int
D_top
p_top
0.5
0.75
IOR
20
250
500
750
1000
1250
1500
1750 2000
Dimension (d)
(b) Scale-free free ER
IQR of D top vs. d for Scale-Frea BA graphs
700
Kappa
1.0
3.0
500
P_int
of top
0.25
400
0.75
300
250
500
750
1000
1250
1500
1750
2000
Dimension (d)
(c) Scale-free BA
Figure 5: IQR of unnormalized error Drop versus graph size across Erdós Erdös-Rényi (ER), scale-free ER, and Barabási-Allas (BA) graphs.
32

---

Published as a conference paper at ICLR 2026
Std of D top vs. d for Ronyi graphs
200
0.6
p.
Std of D topp
0.25
150
0.5
0.75
250
1500
1750
Dimension (d)
(a)
Std of D D_top vs. d for Scale-Free ER graphs
Edges per Variable (c)
50
2.0
5.0
i_
Std of topp
0.5
330
0.75
20
10
250
500
750
1000
1250
1500
1750 2000
Dimension (d)
(b) Scale-fres free ER
Std of D top vs. for Scale- Free BA graphs
500
Kappa
1.0
3.0
400
P_int
Std of top
0.25
300
0.75
100
250
500
750
1000
1250
1500
1750
2000
Dimension (d)
(c) Scale-free BA
Figure 6: Standard deviation of unnormalized enror Drop versus graph size across Erdös Rényii (ER), scale-free ER, and Barabási-Albert (BA) graphs.
33

---

Published as a conference paper at ICLR 2026
Scalling of Max Out-Degree vs Graph Size for different Kappas
Empirical
Kappa=1.0 8-0.73.912
K.ppa-3.0
Kappa=100 8e0.32, 4-2.93
Kappa- Emptrical
6.0
Kappama.0. Hit 5m0.32 fm4.1
5.5
loa/Max OUt degres)
4.0
3.5
logiNumber of modes))
Figure 7: Empirical scaling of the maximum degree BA graphs with m edges per node for different values of k. Fitted lines correspond to estimated exponents 5, compared against theoretical predictions. Graph sizes range from d = 30 to d = 4000. The close match confirms that the generated graphs reproduce the expected heavy-tailed scaling.
Concentratin
Threshoi
Eypeciat Upper Bound intevvatioon Frebab to 1300
Probabiitt Probbiity
20
Untevationn tnsacot)
Movelse
(a) Deviation
(b) Expectation upper-bound
(c) Upper-bound on probability of large error
Figure 8: Comparison of the upper-bounds on the deviation, expectation and probability of large errors between SYNTREN300 and SYNTREN networks (Van den Bulcke et al.) 2006). For the deviation plot (a), we have i E [0.1, 1.0] for 20 values on a logarithmic scale. For (b) and (c), we have Pint 00.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.9.
34


Reviews:
[{"review_id": "VlLM8xME1u", "reviewer": "Reviewer_esW9", "summary": "This paper considers the problem of  causal discovery under random interventions on large random graphs. The authors study how accurately causal directions can be identified when single-variable interventions are applied to networks drawn from Erd\\H{o}s--R\\'{e}nyi (ER) and Barab\\'{a}si--Albert (BA) models. A key contribution is the  derivation of the deviation bounds for the false-negative rate (FNR)---the fraction of causal edges whose orientation is not correctly recovered. The paper shows that, under an $\\varepsilon$-interventional faithfulness assumption (milder than $d$-separation based faithfulness), the FNR not only remains small in expectation but also concentrates sharply around its mean as the number of nodes grows. For dense ER graphs, the expected FNR decays as $\\Theta(1/d)$ with concentration rate $O(d^{-1/2})$; for sparse ER graphs, it stabilizes at $O(1)$ with $O((\\log d)/\\sqrt{d})$ deviations. The paper also give bound for and BA (scale-free) graphs, though they are bit more technical to write. The paper also empirical illustrates the predicted concentration trends.", "questions": "My main question is related to the weakness I mentioned. Can the authors provide motivating examples where causal-discovery performance on random-graph models offers insights applicable to real-world causal networks? Are there particular domains where random interventions approximate realistic experimental designs?", "limitations": "", "rating": 4, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "Causal structure discovery is a fundamental and challenging problem in machine learning and scientific inference. Any progress in understanding its limits and guarantees is valuable. Thus the broad topic of the  paper is well motivated. The paper is primarily theoretical, providing detailed proofs in the appendix and clearly stated assumptions. They also give a very good description of related work. While the main results are theoretical, the authors also include empirical experiments illustrating the concentration of the FNR on both ER and BA graphs. These simulations, though modest, help validate the theoretical findings.", "weaknesses": "The main weakness I find is that it is not clear whether causal discovery on random graphs corresponds to realistic application domains. Most real-world causal systems are I presume are more structured rather than randomly generated. Without concrete scenarios where random-graph analysis informs practice, the practical utility of these results remains uncertain. Thus the paper would be strengthened by examples of settings where such asymptotic guarantees could guide real causal-discovery in practice. While the paper appears technically sound, I am not able to enthusiastically recommend acceptance without a clearer bridge to practical utility of the modeling. That said, I am open to other expert reviewers’ perspectives, especially those with stronger background in causal-discovery theory that the paper is addressing.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "dMa2YpTIvN", "reviewer": "Reviewer_Do7d", "summary": "This paper studies identifiability properties of causal graphs under single-node interventions from a probabilistic perspective. In particular, the authors study the number of misoriented edges (or, normalizing, the false negative rate), when the topological ordering of the graph is estimated via the InterSort algorithm. \n\nThe authors study three random graph models: dense Erdos-Renyi (ER) models, sparse ER models, and a generalized Barabasi-Albert (BA) model, and a single intervention model where each single-node intervention is present with probability $p_{\\text{int}}$. For graphs on $d$ nodes, they show that the expected false negative rate (FNR) under the dense ER is $O(d^{-1})$, and for the latter two models, they show that the expected FNR is $O(1)$. Further, they provide deviation bounds on the FNR: in the dense ER model, they show that the FNR has deviations of order $O(d^{-1/2})$, in the sparse ER model, deviations are of order $O(\\log(d) \\cdot d^{-1/2})$, and under the BA model, the deviations are of the order $O(d^{\\beta - 1/2})$, where $\\beta = (1 + \\kappa/m)^{-1} \\in (0, 1)$ for an attractiveness parameter $\\kappa > 0$ and a link-count parameter $m > 0$. These theoretical findings are corroborated by experiments on synthetic data using the DiffInterSort extension of the InterSort algorithm.", "questions": "**Intervention probability:** It was somewhat hard to track how the probability of having data from any particular single-node intervention plays a role in the bounds, e.g., this probability does not appear in Table 1. I see this dependence in other places (e.g. Theorem 8), but it would be nice to make this dependence more explicit and transparent throughout, as I would consider it one of the key quantities.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "**Originality and significance:** To the best of my knowledge, this paper is the first to study deviation bounds for identifiability metrics in random causal graph models. Compared to just expectation results, these results are more informative and provide stronger guidance for downstream applications (e.g., the development of causal discovery algorithms which are targeted towards more easily identifiable cases).\n\n**Quality and clarity:** The theoretical results are strong under the relatively weak assumptions (random intervention targets and single-node interventions only identify neighbors). The presentation is well-structured, with the results presented in a very logical order, the writing is clear, with related work being particularly well-described.", "weaknesses": "In my opinion, the main weakness of the paper (shared by similar papers in the area, and even related areas like average-case complexity theory) is a somewhat shaky relation between theory and practice. In the \"Limitations\" section, the authors acknowledge that the random graph models are somewhat realistic, and I would also prefer the paper to emphasize that the \"random intervention\" model may be overly pessimistic. \n\nHowever, for the sake of argument, assume that both the random graph and intervention models were realistic. In practice, causal discovery is not often applied to a large number of different high-dimensional datasets with interventions, both due to a lack of interventional data and a lack of enough samples per intervention for reliability in high-dimensional settings. Hence, it is somewhat difficult to translate these forms of theoretical results into practical relevance. While the authors make a good effort to connect their theory with potential practical implications in their \"Conclusion\" section, I still feel that this flavor of work verges towards \"theory for its own sake\".", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ZRa3upXw8E", "reviewer": "Reviewer_A2f8", "summary": "This paper proposes a new framework for causal structure discovery based on a finite-dimensional permutation representation of DAGs. The authors develop a differentiable objective function in which acyclicity is enforced implicitly through the permutation parameterization rather than via explicit matrix constraints as in NOTEARS. They derive theoretical results showing that this formulation admits dimension-adaptive and faithfulness-robust guarantees for causal structure recovery under ideal conditions. The work thus contributes a mathematically elegant alternative to existing continuous-optimization approaches, linking causal identifiability to permutation-based relaxations. Although the focus is primarily theoretical, the paper positions the framework as a potential foundation for scalable causal discovery in high-dimensional or heterogeneous systems.", "questions": "1.\tClarifying the algorithmic contribution.\nIt is not clear from the abstract or introduction that the paper proposes a new algorithm rather than purely a theoretical framework. Could the authors explicitly describe the practical procedure—what is optimized, how the permutation variable is represented or relaxed, and how the optimization proceeds? A concise summary of the algorithmic steps would greatly aid comprehension.\n2.\tConnection between theory and practical search.\nThe theoretical guarantees are stated in terms of identifiability and dimension adaptivity, but it remains unclear how these relate to the performance of the implemented optimization. Are the guarantees properties of the objective itself (assuming global optimization), or do they also hold for the proposed search procedure in finite-sample, non-ideal conditions?\n3.\tRelation to prior permutation-based work.\nPrior studies such as Lam, Andrews & Ramsey (2022) identified both strengths and limitations of permutation-based DAG formulations. How does the present approach overcome those issues—particularly the tendency toward local minima and sensitivity to score design? Clarifying this connection would help establish novelty.\n4.\tComparison to continuous acyclicity formulations.\nThe paper briefly mentions NOTEARS and related work, but the empirical and theoretical distinctions between matrix-based and permutation-based relaxations are not fully developed. Could the authors elaborate on what advantages their finite-dimensional permutation formulation provides relative to these existing continuous-optimization methods?\n5.\tOn claims of scalability.\nThe paper describes the method as “large-scale” and “dimension-adaptive,” but the experiments are limited to moderate-size graphs. Could the authors clarify whether “large-scale” refers only to asymptotic complexity, or whether they expect tangible computational benefits in practice? If the latter, are there empirical results or runtime analyses supporting this claim?\n6.\tFaithfulness-robust guarantees.\nThe abstract mentions “faithfulness-robust guarantees for causal structure recovery.” Could the authors specify what kind of robustness is meant—e.g., tolerance to near-unfaithful parameterizations, violations of Markov equivalence, or resilience of recovery under approximate conditional independencies?\n7.\tTerminology and framing.\nThe terms “dimension-adaptive,” “finite-dimensional,” and “summary formulation” are used prominently but somewhat interchangeably. Could the authors provide a more precise definition of each and clarify how they differ conceptually?", "limitations": "", "rating": 2, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "1.\tAmbitious theoretical framing.\nThe paper tackles a central challenge in causal structure discovery—learning DAGs in high-dimensional or heterogeneous settings—by proposing a finite-dimensional permutation formulation that encodes acyclicity by construction. The theoretical framing is ambitious and conceptually interesting, even if the practical payoff is not yet demonstrated.\n2.\tSound mathematical development.\nThe formal derivations appear internally consistent, and the proofs provide a logically coherent set of identifiability and faithfulness-robustness results for the proposed objective. The mathematics is solidly presented, though its empirical implications remain uncertain.\n3.\tConceptual link between identifiability and optimization.\nBy connecting permutation-based relaxations with identifiable scoring properties, the paper makes a reasonable attempt to bridge causal identifiability theory and differentiable optimization, offering a potentially useful theoretical synthesis.\n4.\tAlternative view of acyclicity enforcement.\nThe permutation-based representation provides an alternative to matrix-based continuous optimization methods like NOTEARS, handling acyclicity implicitly rather than through explicit constraints. This framing offers a different theoretical perspective, though the comparative advantages are not empirically explored.\n5.\tFoundation for future empirical work.\nThe finite-dimensional formulation could, in principle, enable more scalable algorithms once effective optimization strategies are developed. As it stands, the framework provides a theoretical starting point for such future work.\n6.\tClear high-level motivation.\nThe goal of achieving dimension-adaptive, faithfulness-robust causal discovery in complex systems is well articulated, and the paper situates itself within a coherent line of theoretical progress, even if the empirical validation is lacking.", "weaknesses": "1. Connection between theory and search.\nThe paper presents strong theoretical results on identifiability and robustness for a permutation-based DAG formulation, but it remains unclear how these guarantees translate to the actual optimization procedure. The analysis establishes properties of the objective function and representation rather than of the search itself. Clarifying whether the theoretical results apply to the implemented algorithm—or only to its ideal global optimum—would strengthen the paper.\n2. Relation to existing permutation-based approaches.\nThe method builds on a permutation representation of DAGs, similar in spirit to prior work such as Lam, Andrews & Ramsey (2022). That literature already discusses both the strengths and limitations of permutation-based formulations, including the sensitivity of search to scoring design and high-dimensional heterogeneity. The authors should clarify what aspects of their framework overcome these earlier difficulties and in what precise sense their theoretical guarantees are novel.\n3.\tComparison with continuous acyclicity formulations.\nThe paper positions its method as distinct from continuous-optimization approaches such as NOTEARS, DAG-GNN, and GOLEM, but the practical differences are not clearly explained. Since those methods also encode acyclicity differentiably, a clearer contrast—both conceptually and empirically—would help establish the contribution.\n4.\tClaims of scalability.\nThe paper repeatedly describes its framework as “large-scale” and “dimension-adaptive,” yet these appear to refer to theoretical rather than empirical scalability. The experiments do not extend beyond a few hundred variables, whereas recent permutation-based methods such as BOSS (Andrews et al., 2023) have been validated at scales of up to 1000 nodes. It would strengthen the work if the authors clarified whether “large-scale” refers only to asymptotic complexity or whether they expect genuine computational advantages in practice. If the latter, additional empirical evidence or runtime analysis would be needed to substantiate the claim.\n5.\tScope of empirical evaluation.\nThe empirical results are limited to moderate-size graphs and do not provide comparisons to recent permutation-based or continuous-relaxation algorithms. Demonstrating competitive recovery or runtime behavior would help connect the theoretical framework to its practical utility.\n6. Presentation and framing.\nThe exposition is difficult to follow, and the central algorithmic contribution is not clearly stated in the abstract or introduction. Key distinctions—particularly between the theoretical guarantees and the practical optimization behavior—are left implicit. Several claims, especially those concerning robustness, scalability, and novelty, would benefit from clearer qualification and direct comparison to prior work.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "oM2eDTdxeO", "reviewer": "Reviewer_ifw6", "summary": "The authors derive high-probability deviation bounds for the (normalized) number of true edges missed due to incorrect causal ordering — that is, for the false negative rate — in the context of causal discovery with interventional data on random graphs. Their theory applies to the score-optimal causal order (as defined by the score function introduced in Chevalley et al., 2025c) and covers both Erdős–Rényi and Barabási–Albert graph models.", "questions": "- **Experiments.** I’d like to see the plots of figure 1  also for $D_{top}$, to visualize whether there is any additional information we can gain from knowing concentration results on FNR on top of what we already know for $D_{top}$\n- **Assumption 2.** Is there any dependency of the results on the tie breaking rule chosen?\n- **L427-428**: authors write that “prior work shows” that DiffiIntersort “achieves close approximations [..] and is scalable”. What prior work?", "limitations": "", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The presentation of the technical contributions of the paper is clear. The technical contribution themselves seem solid (although I haven’t checked the proofs myself). The empirical evidence of figure 1 convingly support the theory.", "weaknesses": "- **Presentation.**\n    - In the abstract and introduction, it is not clear that the FNR concentration refers to the causal order that optimizes the specific score in Eq. (2) (this only becomes precise later via the notation and Assumption 2). This oversells the scope: the bounds apply to the score-optimal order for Eq. (2).\n    - The goal is scattered: L48–49 suggests a broad “analysis of interventional CD,” whereas L52–53 focuses on finite-sample deviation bounds for FNR. Please state *up front* (abstract + intro) that the paper derives deviation bounds for $D_{\\text{top}}$ and its normalization (FNR) **for the Eq. (2) optimizer**, on ER and BA random graphs. The problem definition currently appears only in Related Work (L135–143); it belongs in the introduction.\n- **Motivation**. I’d appreciate a clearer case for the value and motivation of this work.\n    - Why does the authors believe that it is valuable to prove this results for optimizers of the score of eq. (2)? Should we expect similar behaviour for the causal order found by other interventional causal discovery methods? Can we show that empirically?\n    - Why do the authors believe that it is interesting to study concentration bounds for synthetically generated graphs? Would the theoretical results on ER/BA be relevant for real world causal discovery? Can we have an empirical analysis on real world / semi synthetic data (e.g. syntren) supporting the claim that these results would be useful for real world problems?\n    \n    The technical contributions are sound. I don’t see why they are valuable for the causal discovery community, due to their narrow scope (they refer specifically to optimizers o the score of eq.(2)) and empirical evidence limited to artificial settings.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)