- 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
- The paper is well motivated and well organized.
- 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.
- 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.
- The experiments include both synthetic and real-world datasets.
- The authors report error bars for the simulation results and provide running-time comparisons.
Critical weaknesses
- 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.
- 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.
- 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.
- 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
- Could the authors clarify the main novelty of the proposed algorithm compared with existing causal discovery methods that estimate parent sets?
- Could the authors further explain Theorem 2 and clarify how it differs from and contributes beyond Theorem 1 and Proposition 1?
- 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?
- 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
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
| STORM | PC-KCI | CD-NOD | |
|---|---|---|---|
| 300 | 0.468 ± 0.201 | 0.188 ± 0.226 | 0.261 ± 0.230 |
| 600 | 0.629 ± 0.243 | 0.318 ± 0.258 | 0.262 ± 0.150 |
| 900 | 0.680 ± 0.320 | 0.254 ± 0.165 | 0.271 ± 0.114 |
| 1200 | 0.817 ± 0.154 | 0.263 ± 0.158 | 0.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
| STORM | iSCAN | DCI | |
|---|---|---|---|
| 300 | 0.468 ± 0.201 | 0.069 ± 0.095 | 0.542 ± 0.152 |
| 600 | 0.629 ± 0.243 | 0.076 ± 0.102 | 0.561 ± 0.170 |
| 900 | 0.680 ± 0.320 | 0.088 ± 0.105 | 0.529 ± 0.177 |
| 1200 | 0.817 ± 0.154 | 0.086 ± 0.103 | 0.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.
| Condition | Reported shifts (↓) | Runs with no reported shift (↑) |
|---|---|---|
| No change | 0.2 / 45 | 8/10 |
| Only noise change | 0.0 / 45 | 10/10 |
| Only function change | 0.2 / 45 | 8/10 |
| Both | 0.1 / 45 | 9/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 (—).
| Method | Order divergence | F1 score |
|---|---|---|
| STORM | 0.3 ± 0.7 | 0.905 ± 0.100 |
| w/o joint | 0.8 ± 1.2 / 3.2 ± 2.3 | 0.768 ± 0.219 |
| DCI | — | 0.456 ± 0.277 |
| iSCAN | 6.1 ± 2.3 | 0.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 (=1200).
| Environments | STORM | DCI | iSCAN |
|---|---|---|---|
| 2 | 0.817 ± 0.154 | 0.569 ± 0.183 | 0.047 ± 0.102 |
| 3 | 0.833 ± 0.128 | 0.596 ± 0.103 | 0.093 ± 0.095 |
| 4 | 0.894 ± 0.096 | 0.600 ± 0.099 | 0.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.
| STORM | iSCAN | DCI | |
|---|---|---|---|
| 300 | 0.469 ± 0.109 | 0.069 ± 0.095 | 0.542 ± 0.152 |
| 600 | 0.620 ± 0.191 | 0.076 ± 0.102 | 0.561 ± 0.170 |
| 900 | 0.636 ± 0.261 | 0.088 ± 0.105 | 0.529 ± 0.177 |
| 1200 | 0.794 ± 0.172 | 0.086 ± 0.103 | 0.511 ± 0.189 |
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
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.
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
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.
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⋆.
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)
Pr(Sje1,e2=Sje1,e2 for all j, e1<e2)⟶1.