acceptodds
Under review as a conference paper at ICLR 2027

Causal Structure Shift Detection via Orthogonal Residual Moments

Abstract

Causal relationships may appear or disappear across environments, and capturing them is essential for understanding the structure of the underlying system. Most existing methods can identify which causal mechanisms shift under a common graph, but they cannot attribute a detected shift to a change in the causal structure. In this work, we consider nonlinear additive noise models sharing a causal order and establish conditions under which observed data uniquely identify the causal structure shifts, even when the order is not unique. We also provide conditions that preserve this guarantee under structure shifts consistent with a common order. Building on these identifiability results, we propose STORM, a two-stage algorithm that first estimates a common order by repeatedly removing a node with no children in any environment and then detects shifts by testing whether omitting a candidate parent changes the target node's conditional mean. To reduce the impact of regression estimation errors on both stages, we derive orthogonal scores whose expectations are insensitive to the errors to first order. Experiments on synthetic and real-world datasets showed the effectiveness of STORM in various scenarios.

Primary area:
causal reasoning
Keywords:
Causal mechanism shifts, Multiple environments, Neyman orthogonality

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_1Q6AOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies causal structure shift detection across multiple environments under nonlinear additive noise models. Unlike methods that detect changes in causal mechanisms, the proposed method aims to identify changes in causal parent sets. The method first estimates a common causal order by testing residual independence across environments and then identifies parent sets using conditional mean comparisons. The method uses orthogonal scores to reduce the impact of regression estimation errors. The paper establishes identifiability results under a common causal order and specific assumptions on structural functions and noise distributions. Experiments on synthetic and real-world datasets show that STORM outperforms the chosen baselines.

Critical strengths
  1. The paper is well motivated and well organized.
  2. Theorem 1 establishes the identifiability of a common causal order under conditions that can be satisfied by different environments for different edges. This extends existing identifiability results for additive noise models.
  3. The proposed method uses orthogonal scores and cross-fitting to reduce the impact of regression estimation errors. The ablation experiments also demonstrate the effectiveness of the correction term.
  4. The experiments include both synthetic and real-world datasets.
  5. The authors report error bars for the simulation results and provide running-time comparisons.
Critical weaknesses
  1. The proposed method identifies structure shifts by comparing parent sets estimated separately in each environment, rather than directly testing whether an edge changes across environments. Differences in statistical power may lead to false shift detections. The authors acknowledge this limitation, but no error-control guarantee is established for the reported shifts.
  2. Since environment labels are known, a natural baseline is to perform causal discovery separately in each environment and compare the estimated graphs. An ablation that recovers the order separately in each environment using STORM’s own order-recovery method, followed by the same parent-set estimation, would help isolate the benefit of joint order recovery.
  3. The synthetic experiments only consider edge deletions, so the second graph is always a subgraph of the first. Although the theory allows both additions and deletions, more general shifts are not evaluated. Moreover, structural functions and noise distributions remain unchanged across environments. Since the method aims to distinguish structure shifts from mechanism-only changes, simulations with unchanged graphs but different functions or noise distributions would be useful. Ideally, no structure shifts should be detected in these settings.
  4. The synthetic experiments do not evaluate the complementary-environment setting in Theorem 1. Since the noise distributions are identical across environments, the experiments do not examine scenarios where different environments satisfy the required identifiability conditions for different edges. This leaves a key theoretical contribution empirically untested. Additionally, the experiments consider only two environments, making the evaluation less comprehensive.
Questions for authors
  1. Could the authors clarify the main novelty of the proposed algorithm compared with existing causal discovery methods that estimate parent sets?
  2. Could the authors further explain Theorem 2 and clarify how it differs from and contributes beyond Theorem 1 and Proposition 1?
  3. Since structure shifts are identified by comparing separately estimated parent sets, can the authors provide theoretical guarantees for the accuracy or consistency of shift detection?
  4. Could the baseline comparison be strengthened by including nonlinear constraint-based causal discovery methods, such as PC with a kernel CI test applied separately to each environment or CD-NOD?
4 comments

We thank the reviewer for the careful reading and thoughtful comments. We provide detailed responses below. We have also revised parts of the paper to improve clarity, with the changes highlighted in blue.

Main novelty of the algorithm compared with methods that estimate parent sets

Could the authors clarify the main novelty of the proposed algorithm compared with existing causal discovery methods that estimate parent sets?

a natural baseline is to perform causal discovery separately in each environment and compare the estimated graphs. [...] would help isolate the benefit of joint order recovery.

Main novelty of our algorithm is the two following points:

1. Compared with separate causal discovery, STORM estimates one order jointly and uses the same candidate parents in every environment. Different edges may use different environments containing them to satisfy the noise condition like Figure 1 (Theorem 1). We additionally evaluated a natural baseline that recovers the order separately in each environment, referred to as w/o joint. As shown in the table below, STORM outperforms w/o joint in all settings, isolating the benefit of joint order recovery.

Table R1. F1 score of STORM vs. w/o joint.

nnSTORMw/o joint
3000.468 ± 0.2010.367 ± 0.122
6000.629 ± 0.2430.548 ± 0.179
9000.680 ± 0.3200.546 ± 0.309
12000.817 ± 0.1540.563 ± 0.244

2. Compared with existing estimation procedures, RESIT uses regression followed by residual-independence testing, while iSCAN estimates log-density derivatives. STORM constructs corrected characteristic-function moments from conditional-mean residuals in Stage 1. Stage 2 adapts testing parent membership followed by the projected-covariance principle under the common order. The resulting scores have zero first-order sensitivity to the regression errors (Lemmas 1–2). The correction ablation (w/o correction) isolates the benefit of robustness against first-order errors.

Theorem 2 and its contribution beyond Theorem 1 and Proposition 1

Could the authors further explain Theorem 2 and clarify how it differs from and contributes beyond Theorem 1 and Proposition 1?

Theorem 1 and Proposition 1 already identify the graphs and their structural differences for a given collection of environments. However, this guarantee does not apply under some structure shifts.

  • For example, in Figure 1, delete Z→XZ \to X from environment 1. This shift is compatible with the common order, but Z→XZ \to X now exists only in environment 2, where NZN_Z is logistic, so Assumption 3 fails and Theorem 1 no longer applies. Likewise, adding an edge j→kj \to k violates Assumption 3 if NjN_j lacks the required shape in the environments.

Thus, Assumption 3 depends on which edges are present in which environment, i.e., on the unknown shifts. In other words, with Theorem 1 and Proposition 1 alone, our guarantee for identifying the shifts relies on Assumption 3, which cannot be checked without knowing the shifts themselves. Theorem 2 removes this dependence by imposing the noise-shape condition at every node, so identifiability holds for every order-compatible shift within M⋆\mathcal{M}_\star.

Consistency of shift detection

can the authors provide theoretical guarantees for the accuracy or consistency of shift detection?

We can establish consistency of shift detection for STORM's statistical procedure under standard regularity conditions.

Proof sketch (See revised paper for details)

  1. Common order. Uniform convergence of the characteristic-function moments, together with separation on the chosen frequencies, implies that each greedy removal selects a common sink with probability tending to one (Lemma 1). Repeating the argument yields a valid common order.
  2. Parent sets. Under any valid order, the learned direction satisfies g^→δ\widehat g\to\delta, and Lemma 2 gives ψˉ→pΔ=E[δ2]\bar\psi\xrightarrow{p}\Delta=\mathbb E[\delta^2]. The nuisance-rate and moment conditions imply that absent-edge studentized statistics remain bounded in probability, whereas present-edge statistics grow at rate nse\sqrt{n_s^e} because Δ>0\Delta>0 (Proposition 1). Let the testing level decrease slowly enough that the theoretical Gaussian-multiplier critical value diverges but remains op(nmin⁡)o_p(\sqrt{n_{\min}}), where nmin⁡=min⁡ensen_{\min}=\min_e n_s^e is the smallest support-evaluation sample size. Both false-positive and false-negative probabilities then vanish.
  3. Structure shifts. All parent sets are recovered simultaneously, so their symmetric differences are also correct:

Pr⁡(S^je1,e2=Sje1,e2 for all j, e1<e2)⟶1.\Pr\left(\widehat S_j^{e_1,e_2}=S_j^{e_1,e_2}\text{ for all }j,\ e_1<e_2\right)\longrightarrow1.

Constraint-based baselines

Could the baseline comparison be strengthened by including nonlinear constraint-based causal discovery methods, such as PC with a kernel CI test applied separately to each environment or CD-NOD?

Thank you for the valuable suggestion. We additionally evaluated two constraint-based baselines (PC-KCI and CD-NOD), and STORM outperforms both. See the following table for details.

Table R5. F1 score of STORM and two constraint-based baselines

nnSTORMPC-KCICD-NOD
3000.468 ± 0.2010.188 ± 0.2260.261 ± 0.230
6000.629 ± 0.2430.318 ± 0.2580.262 ± 0.150
9000.680 ± 0.3200.254 ± 0.1650.271 ± 0.114
12000.817 ± 0.1540.263 ± 0.1580.269 ± 0.127

Edge additions and mechanism-only changes

The synthetic experiments only consider edge deletions [...] more general shifts are not evaluated. Moreover, structural functions and noise distributions remain unchanged across environments. [...] simulations with unchanged graphs but different functions or noise distributions would be useful. Ideally, no structure shifts should be detected in these settings.

(a) Edge additions. We first evaluated the case where edges are added in environment 2. STORM outperforms the baselines.

Table R6. F1 score under edge additions in environment 2

nnSTORMiSCANDCI
3000.468 ± 0.2010.069 ± 0.0950.542 ± 0.152
6000.629 ± 0.2430.076 ± 0.1020.561 ± 0.170
9000.680 ± 0.3200.088 ± 0.1050.529 ± 0.177
12000.817 ± 0.1540.086 ± 0.1030.511 ± 0.189

(b) Mechanism-only changes. We also evaluated the case where the graph is unchanged but the structural functions and/or noise distributions differ across environments. In this setting, STORM correctly reports almost no shifts. This confirms that STORM does not falsely detect structure shifts when only mechanism changes occur.

Table R7. Mechanism-only changes with the graph fixed. Reported shifts are the mean count out of 45 candidate edges; every reported shift is false because the graph is unchanged. Structural function changes are implemented by rescaling the functions, and noise changes by replacing Laplace noise with Gumbel noise.

ConditionReported shifts (↓)Runs with no reported shift (↑)
No change0.2 / 458/10
Only noise change0.0 / 4510/10
Only function change0.2 / 458/10
Both0.1 / 459/10

Complementary environments and more than two environments

The synthetic experiments do not evaluate the complementary-environment setting in Theorem 1. [...] Additionally, the experiments consider only two environments [...]

(a) Complementary environments. We consider neither environment alone satisfies the noise condition for all its edges, but the two environments together do, like Figure 1. Specifically, we alternate Laplace and logistic noise across nodes and swap them between environments. Laplace satisfies the noise-shape condition, but logistic does not. This directly tests the setting highlighted in Theorem 1.

Table R8. Complementary environments. DCI does not return a causal order (—).

MethodOrder divergenceF1 score
STORM0.3 ± 0.70.905 ± 0.100
w/o joint0.8 ± 1.2 / 3.2 ± 2.30.768 ± 0.219
DCI—0.456 ± 0.277
iSCAN6.1 ± 2.30.082 ± 0.119

(b) Three and four environments. We evaluated STORM and its baselines across more than two environments.

Table R9. F1 score under two or more environments (nn=1200).

Environments EESTORMDCIiSCAN
20.817 ± 0.1540.569 ± 0.1830.047 ± 0.102
30.833 ± 0.1280.596 ± 0.1030.093 ± 0.095
40.894 ± 0.0960.600 ± 0.0990.101 ± 0.091

Once again, we thank the reviewer for the insightful comments, which helped us strengthen the paper. If any concerns remain, we would be happy to address them during the discussion period.

Thank you for the detailed responses and additional experiments, which address most of my concerns, and I have raised my score. One question remains: the STORM results in Table R6 edge additions are identical to those in the original edge-deletion setting at all sample sizes. Could the authors clarify whether these numbers come from the edge-addition experiment?

We greatly appreciate your thoughtful review and constructive feedback, which has helped us improve our paper. We are delighted to hear that our responses and additional experiments have addressed most of your concerns, and we sincerely thank you for raising your score.

Regarding Table R6, we sincerely apologize for the reporting error. The corrected table is below. This correction does not change our statement that STORM outperforms the baselines.

nnSTORMiSCANDCI
3000.469 ± 0.1090.069 ± 0.0950.542 ± 0.152
6000.620 ± 0.1910.076 ± 0.1020.561 ± 0.170
9000.636 ± 0.2610.088 ± 0.1050.529 ± 0.177
12000.794 ± 0.1720.086 ± 0.1030.511 ± 0.189
Reviewer_A6P4OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies causal structure shifts which happen when parent-child relations over the same variables change across environments. Existing methods detect which mechanisms shift but not whether those shifts imply changes in the causal structure. The authors propose STORM, a 2-stage approach that identifies shift in causal structure across environments; within additive-noise models that share a common causal order but can differ in structural functions, noise distributions, and parent sets---handling non-Gaussian noise and environment shifts that add or delete edges. The proposed method recovers a common causal order by repeatedly identifying a common sink (a variable with no descendants and with conditional-mean residual independent of the remaining variables in every environment). Next, for each variable, STORM identifies the parents in each environment by testing whether removing a candidate predecessor changes that variable's conditional mean. The symmetric difference of the parent sets across environments results in the structure shifts. The authors limit the influence of estimation errors by using Neyman-orthogonal scores giving expectations that are insensitive to 1st-order estimation errors. Experiments on synthetic data show that STORM outperforms baselines; real-world experiments are evaluated qualitatively.

Critical strengths
  • S1. The proposed method permits parent sets, structural functions and noise distributions to change across environments, provided the graphs are still compatible with their shared causal order---compared to existing work which either fixes the underlying causal diagram and allows a subset of mechanisms to change, or detect when mechanisms change but not localize those changes to causal structure shifts. This is a more realistic setup (Figure 1)--when no single environment satisfies the kink-or-tail noise condition for all its edges, the method still works as long as every edge in the union graph is covered by at least an environment that does.

  • S2. Regression errors could compound and lead to incorrect results so the approach of using Neyman-orthogonal scores to reduce the influence of estimation errors makes sense, as shown by the ablation of the 1st stage correction.

Critical weaknesses
  • W1. The pipeline is largely similar to iSCAN; both are 2-stage for nonlinear ANMs that recover a common causal order and then compare parent sets across environments. The difference is that STORM uses regression residuals and characteristic functions instead of log-density derivatives and extends identifiability beyond Gaussian noise--but the overall framework is very closely related. Experiments show that STORM outperforms iSCAN on the synthetic settings, but methodological novelty is incremental.

  • W2. The structural assumptions are strong. STORM requires a shared causal order across environments, an acyclic union graph, and no unobserved/latent confounders. The latent confounder and feedback issues are acknowledged in the limitations, but also the shared-order requirement is restrictive and ignores realistic situations where an intervention reverses the causal direction between two variables.

Reference: Chen, T., Bello, K., Aragam, B., & Ravikumar, P. (2023). iSCAN: Identifying causal mechanism shifts among nonlinear additive noise models. NeurIPs, 36.

Questions for authors
  • How do errors in the estimated shared order propagate into the 2nd stage (identifying the causal structure shift)? It would be useful to know how often a wrong order still ends up giving the correct structure shifts, versus how often an early mistake cascades into the downstream parent tests.

  • How does STORM scale beyond d = 20? The runtime figures grow noticeably with d, so there might be a practical ceiling on the number of variables.

  • What does Stage 1 output when no node is a sink in all environments, and how is a violation of the common-order assumption detected?

  • Beyond edges that appear, what does STORM identify that iSCAN does not? Are there cases where iSCAN's guarantee fails, and STORM's holds?

4 comments

We thank the reviewer for the careful reading and thoughtful comments. We provide detailed responses below. We have also revised parts of the paper to improve clarity, with the changes highlighted in blue.

Propagation of order errors into Stage 2

How do errors in the estimated shared order propagate into the 2nd stage (identifying the causal structure shift)? It would be useful to know how often a wrong order still ends up giving the correct structure shifts, versus how often an early mistake cascades into the downstream parent tests.

While errors in the estimated shared order can reduce Stage 2 accuracy, shift detection errors were concentrated around the missed true parents and the corresponding children. Thus, errors in the estimated shared order appear to propagate locally rather than throughout the graph. In Table R3, 83–93% of errors involved at least one of these parents or children.

  • Specifically, errors in the estimated shared order affect Stage 2 by changing which variables can be tested as parents. Placing a child before its parent excludes the true parent from the candidate set. Conditioning on the child can also introduce spurious parents.

Table R3 groups runs by the total number of true parents missed because of errors in the estimated shared order. Even with one or two true parents missed, STORM remained competitive with DCI (the strongest baseline in Figure 2).

Table R3. F1 score grouped by the total number of true parents missed because of errors in the estimated shared order.

nnSTORM (No missed parents)STORM (1–2 missed parents)STORM (3 or more missed parents)DCIErrors involving a missed parent or its child (%)
3000.650.600.400.5183
6000.850.690.500.5686
9000.920.800.480.5592
12000.950.710.650.5493

Scaling beyond d=20d=20

How does STORM scale beyond d = 20? The runtime figures grow noticeably with d, so there might be a practical ceiling on the number of variables.

At d=50d=50 and n=1200n=1200, STORM took about 8 minutes in a single process.

Both stages require O(d2)O(d^2) regression fits, so runtime grows approximately quadratically with dd at a fixed sample size. The following experimental results are consistent with this scaling.

Table R4. Runtime versus dimension dd.

ddRuntime (s)
1019
2076
30192
40318
50493

Common-order assumption and its violation

the shared-order requirement is restrictive and ignores realistic situations where an intervention reverses the causal direction between two variables.

We agree that situations where an intervention reverses the causal direction between two variables are outside our scope. Our common-order assumption is consistent with standard perfect-intervention models, which many existing work have adopted [1-3] across various domains, including neuroimaging and molecular biology.

References:

[1] Hauser and Bühlmann, "Characterization and Greedy Learning of Interventional Markov Equivalence Classes of Directed Acyclic Graphs," JMLR 2012.

[2] Shimizu, "Joint estimation of linear non-Gaussian acyclic models," Neurocomputing 2012.

[3] Chen et al., "iscan: Identifying causal mechanism shifts among nonlinear additive noise models," NeurIPS 2023.

What does Stage 1 output when no node is a sink in all environments, and how is a violation of the common-order assumption detected?

We agree that the original Stage 1 only returns an order; however, STORM can detect violations of the common-order assumption.

  • Specifically, when no node is a sink in all environments, every candidate's residual depends on the remaining variables in at least one environment. In other words, there exists no node jj such that εR,je⊥XR\{j}e\varepsilon^e_{R,j}\perp X^e_{R\backslash \{j\}}. Therefore, testing residual independence can determine whether a common sink exists.

The following table shows the number of times the diagnostic detects a violation of the common-order assumption due to reversing edges in environment 2. While STORM did not reject cases where the common-order assumption holds, it detected violations of this assumption.

Table R2. Diagnostics results under the common-order assumption violations. Environment 2 has reversed rr edges of environment 1 and changes nothing else. Rejection rate is the rate of runs flagged by the diagnostic.

Reversed edges rrRejection rate
00.00 (0/10)
10.70 (7/10)
20.90 (9/10)

Novelty and advantages over iSCAN

The pipeline is largely similar to iSCAN; both are 2-stage [...] The difference is that STORM uses regression residuals and characteristic functions instead of log-density derivatives and extends identifiability beyond Gaussian noise--but the overall framework is very closely related. [...] methodological novelty is incremental.

We agree that STORM's overall framework is similar to iSCAN's, but this framework is widely used in order-based causal discovery (e.g., RESIT and SCORE), and we do not claim it as a novel contribution. Our main methodological novelty is an estimation procedure that addresses a central challenge when using this framework: the adverse impact of regression errors on the final structure-shift estimates. Specifically, STORM uses conditional means and scores whose first-order sensitivity to regression error is zero in both stages, with cross-fitting (Lemmas 1–2). iSCAN estimates log-density derivatives, which are difficult to estimate accurately, and is adversely affected by first-order estimation errors.

Beyond edges that appear, what does STORM identify that iSCAN does not? Are there cases where iSCAN's guarantee fails, and STORM's holds?

Yes. In addition to this methodological novelty as mentioned above, STORM makes the following theoretical contributions:

  1. STORM can handle non-Gaussian noise, including Laplace and Gumbel (Theorem 1), while iSCAN requires Gaussian noise.
    • For example, Gumbel noise has a log-concave density and a super-exponential left tail, satisfying the noise condition of Theorem 1. In contrast, iSCAN identifies a leaf by Var[∂jj2log⁡p]=0\mathrm{Var}[\partial^2_{jj}\log p]=0. For a leaf with standard Gumbel noise, ∂jj2log⁡p=−e−(xj−fj)\partial^2_{jj}\log p=-e^{-(x_j-f_j)} has positive variance, so iSCAN's criterion fails even when the leaf's mechanism does not change across environments. STORM's guarantee still holds.
  2. STORM requires its noise condition for each edge in only one environment (Theorem 1), while iSCAN requires Gaussian noise at every node in every environment.
  3. STORM identifies the parent sets of all nodes directly (Proposition 1), while iSCAN first screens for mechanism shifts and then estimates parent sets only at those nodes.
  4. STORM preserves identifiability under structure shifts (Theorem 2), while iSCAN does not establish it theoretically.

Once again, we thank the reviewer for the insightful comments, which helped us strengthen the paper. If any concerns remain, we would be happy to address them during the discussion period.

I would like to thank the authors for their responses; I checked them against the updated PDF. I think much of my concern is not addressed yet; so I decided to keep my score; particularly for the following reasons. Regarding novelty against iSCAN and similar pipelines, the Gumbel example is a useful case (iSCAN's guarantee fails and STORM's holds), but it is neither demonstrated empirically nor included in the paper. Points 3 and 4 describe a "procedural" difference (an unproven property of iSCAN not its failure). As the authors acknowledge in their rebuttal, the framework is similar, so the contribution relies on the orthogonal-score estimation. Regarding the shared-order assumption, my point was not that edge reversals are out of scope which is what the authors addressed in the rebuttal; I said the assumption is too restrictive; this should have been addressed as a limitation, with a discussion of how it could be relaxed; the Limitations section currently covers confounders and feedback but not the shared order. Last but not least, the scaling results report runtime only and are not included in the revision.

We thank the reviewer for the follow-up comments. We additionally provide our point-by-point answers for your concerns below.

the Gumbel example is a useful case (iSCAN's guarantee fails and STORM's holds), but it is neither demonstrated empirically nor included in the paper.

Figure 2(d) in our paper compares STORM and iSCAN under Gumbel noise and STORM achieves improvements over iSCAN across all metrics. In addition, Figure 11(d) shows STORM achieves lower order divergence than iSCAN. Therefore, we have already demonstrated the performance empirically and included them in our paper.

Regarding the shared-order assumption, my point was not that edge reversals are out of scope which is what the authors addressed in the rebuttal; I said the assumption is too restrictive

The common-order assumption is consistent with standard perfect-intervention models and can be appropriate in some applications in neuroimaging and molecular biology, as noted in our previous response. We agree that Assumption 1 limits the range of scenarios that STORM can handle, but respectfully disagree that Assumption 1 is too restrictive for the settings considered in this paper. In addition, integer linear programming could relax this assumption by jointly estimating the DAGs with acyclicity constraints for each environment and a penalty for differences in directed edges across environments [4]. We have added this discussion to the paper.

the scaling results report runtime only and are not included in the revision.

Thank you for pointing it out. We have added the result to the paper.


References:

[4] Oates et al., "Exact estimation of multiple directed acyclic graphs," Statistics and Computing 2016.

Reviewer_PhPUOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies causal structure shifts across environments and proposes STORM, a two-stage method that estimates a common causal order and detects structural changes using orthogonal residual moments. The authors provide theoretical guarantees and evaluate the method on synthetic and real-world datasets.

Critical strengths
  • The paper studies an interesting and practically relevant problem.
  • The theoretical analysis is well developed, and the experimental results are promising.
Critical weaknesses
  • First, it is unclear why joint estimation across environments is necessary. Could one instead learn the causal structure separately in each environment and compare the results? It would be helpful to better understand the advantages of the proposed approach over this straightforward alternative.
  • Second, it seems that some closely related works, e.g., iSCAN, have explored similar cross-environment settings. While the proposed approach introduces different techniques, I wonder whether the authors could further clarify its key distinctions and advantages over existing methods.
  • Third, the method assumes a common causal order across environments, which may limit its applicability. It would be interesting to understand how the method performs when this assumption does not hold.
Questions for authors
  • What is the specific benefit of estimating a common causal order over estimating orders separately, with the remaining components unchanged?
  • Beyond the reported comparisons, which differences in assumptions or identifiability guarantees explain STORM’s advantages over iSCAN?
  • If the common-order assumption is violated, can STORM detect the incompatibility, or might it report spurious structure shifts?
4 comments

We thank the reviewer for the careful reading and thoughtful comments. We provide detailed responses below. We have also revised parts of the paper to improve clarity, with the changes highlighted in blue.

Why estimate the order jointly?

[...] it is unclear why joint estimation across environments is necessary. Could one instead learn the causal structure separately in each environment and compare the results? [...]

What is the specific benefit of estimating a common causal order over estimating orders separately, with the remaining components unchanged?

Learning the graphs separately and comparing them is possible. However, joint estimation gives two clear benefits:

  • Environments can supply complementary information. Our order-recovery guarantee requires the noise condition (Assumption 3) for each edge in only one environment (Theorem 1). For the same guarantee to apply to separate order estimation, each environment would need to meet the condition for all of its own edges.
    • For example, in Figure 1, neither environment meets that requirement alone. Together, they satisfy the condition for every edge and identify the common order (Z,X,Y)(Z,X,Y).
  • Both environments use the same candidate parents. In Stage 2, only variables that precede a node in the estimated order are tested as its parents. Therefore, estimated orders in each environment can include a candidate parent in only one environment and exclude it in the other. This mismatch can create an apparent structural difference even when the edge has not changed.

In addition, to isolate the benefit of joint order estimation, we compare STORM with w/o joint, which estimates an order separately in each environment and otherwise uses the same procedure. STORM outperforms w/o joint in all settings, indicating that estimating the order jointly improves shift detection even when Stage 2 is unchanged.

Table R1. F1 score of STORM vs. w/o joint.

nnSTORMw/o joint
3000.468 ± 0.2010.367 ± 0.122
6000.629 ± 0.2430.548 ± 0.179
9000.680 ± 0.3200.546 ± 0.309
12000.817 ± 0.1540.563 ± 0.244

Novelty and advantages over iSCAN

[...] some closely related works, e.g., iSCAN, have explored similar cross-environment settings. [...] I wonder whether the authors could further clarify its key distinctions and advantages over existing methods.

Beyond the reported comparisons, which differences in assumptions or identifiability guarantees explain STORM’s advantages over iSCAN?

Our work makes the following theoretical contributions beyond iSCAN:

  1. STORM can handle non-Gaussian noise, including Laplace and Gumbel (Theorem 1), while iSCAN requires Gaussian noise.
    • For example, Gumbel noise has a log-concave density and a super-exponential left tail, satisfying the noise condition of Theorem 1. In contrast, iSCAN identifies a leaf by Var[∂jj2log⁡p]=0\mathrm{Var}[\partial^2_{jj}\log p]=0. For a leaf with standard Gumbel noise, ∂jj2log⁡p=−e−(xj−fj)\partial^2_{jj}\log p=-e^{-(x_j-f_j)} has positive variance, so iSCAN's criterion fails even when the leaf's mechanism does not change across environments. STORM's guarantee still holds.
  2. STORM requires its noise condition for each edge in only one environment (Theorem 1), while iSCAN requires Gaussian noise at every node in every environment.
  3. STORM identifies the parent sets of all nodes directly (Proposition 1), while iSCAN first screens for mechanism shifts and then estimates parent sets only at those nodes.
  4. STORM preserves identifiability under structure shifts (Theorem 2), while iSCAN does not establish it theoretically.

Common-order assumption and its violation

[...] the method assumes a common causal order across environments, which may limit its applicability. It would be interesting to understand how the method performs when this assumption does not hold.

If the common-order assumption is violated, can STORM detect the incompatibility, or might it report spurious structure shifts?

We agree that the original Stage 1 only returns an order; however, STORM can detect violations of the common-order assumption.

  • Specifically, when no node is a sink in all environments, every candidate's residual depends on the remaining variables in at least one environment. In other words, there exists no node jj such that εR,je⊥XR\{j}e\varepsilon^e_{R,j}\perp X^e_{R\backslash \{j\}}. Therefore, testing residual independence can determine whether a common sink exists.

The following Table R2 shows the number of times the diagnostic detects a violation of the common-order assumption due to reversing edges in environment 2. While STORM did not reject cases where the common-order assumption holds, it detected violations of this assumption. In addition, without the diagnostic, the original procedure reports an average of 3.00 and 5.60 spurious shifts per run for one and two reversed edges, respectively.

Table R2. Diagnostics results under the common-order assumption violations. Environment 2 has reversed rr edges of environment 1 and changes nothing else. Rejection rate is the rate of runs flagged by the diagnostic. Spurious shifts are the number of average spurious shifts per run without the diagnostic.

Reversed edges rrRejection rateSpurious shifts per run
00.00 (0/10)1.20 ± 1.48 / 45
10.70 (7/10)3.00 ± 2.31 / 44
20.90 (9/10)5.60 ± 2.95 / 43

Once again, we thank the reviewer for the insightful comments, which helped us strengthen the paper. If any concerns remain, we would be happy to address them during the discussion period.

Thank you for the response and the revisions. The authors have addressed most of my concerns, so I’ve decided to raise my score. In Table R1, estimating a common order yielded higher mean F1 scores than estimating an order separately in each environment at all four sample sizes tested. The Gumbel example clarifies how STORM’s guarantee differs from iSCAN’s, though I would have liked to see this explanation in the revised paper. The common-order assumption still limits the method’s applicability, but Table R2 shows that the diagnostic can flag violations caused by edge reversals.

We greatly appreciate your thoughtful review and constructive feedback, which has helped us improve our paper. We are delighted to hear that our responses and additional experiments have addressed most of your concerns, and we sincerely thank you for raising your score.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.