iSCAN: Identifying Causal Mechanism Shifts among Nonlinear Additive Noise Models

Summary

This paper focuses on identifying mechanism shifts in related structural causal models without learning the structures of the individual SCMs. It builds on the recent advances in score-matching based causal discovery and consider nonlinear additive noise models, unlike the prior work that assumed linear Gaussian models. The proposed algorithm first identifies the shifted variables and then estimates the structural changes associated with each shifted variable.

Strengths

- I find the main problem — identifying the changes without learning the graphs in their entirety — important. - Score-based (gradient of log likelihood) are gaining momentum in causal inference and this can be a timely paper to expand the existing recent work. Also, I think soft interventions are also relatively understudied but are important for modeling different environments with sparse changes. - Paper is written clearly, the flow is natural and easy to follow.

Weaknesses

- *Invariant noise assumption (Assumption B) and shifted node definition*: I see that invariant noise assumption is crucial for your results, especially it is used in Lemma 2 (and subsequently for the proof of Theorem 1). However, I find this a somewhat unrealistic assumption. For instance, your current definition of shifted nodes excludes root nodes — they can be intervened only upon a change in the noise distribution. I believe Assumption B needs a convincing discussion. I add more comments on questions below. - The main contribution (Theorem 1) is rather a straightforward extension of the existing result (Proposition 1). Sure, there may be technical challenges, but I don’t see a fundamental difficulty. If I am missing anything, please let me know. - Although the paper provides extensive experiments in numerous settings, it misses comparisons with some important related work. ========= AFTER AUTHORS' REBUTTAL ========== A major concern, the invariant noise assumption, is addressed by the reviewers in their rebuttal. Hence, I updated my score accordingly.

Questions

- After finding the shifted nodes, finding the parents should not be a big deal besides the computational burden. One angle can be your efficiency of Algorithm 2. Can you elaborate on its efficiency and which parts are your contribution? - Invariant noise (Assumption B): How do you deal with the root nodes? Do you simply assume that root nodes are never intervened? I see that this is how simulations are conducted. It should be clearly stated in the paper as well, as part of the assumptions perhaps. - If I recall correctly, DCI algorithm of Wang et al. [77] does not require invariant noise assumption. In contrast, the algorithm of Ghoshal et al. (2019) [23] relies on invariant noise and offers some advantages over DCI. I believe the algorithm of Ghoshal et al. can be an important comparison too. - Speaking of related work and comparisons, I believe the present work misses an important reference, “Scalable intervention target estimation in linear models” Varici el al. (2021). Although it’s focused on just identifying the intervened (shifted) nodes, their algorithm also finds some edges. For the comparison of Algorithm 1, along with Ghoshal et al. (2019), Varici et al. (2021) should also be a valid comparison in addition to the already used DCI. The formulation in Varici et al. (2021) differs by assuming that the noise variables necessarily change, but I believe a change in the linear weights is enough to relax the “varying noise” assumption. (you can check their follow-up Varici et al. (2022) in which they discuss the same problem for causally insufficient models with multiple environments) - Finally, all these three papers (Wang et al., Ghoshal et al., Varici et al.) are based on linear models whereas the present paper requires non-linear models. More complex algorithms that can work with non-parametric causal models can be used. For instance, UT-IGSP algorithm of Squires et al. (2020), JCI algorithm of Mooij et al. (2020), and $\psi$-FCI algorithm of Jaber et al. (2020) all can return intervention targets along with the causal graph. The latter two can be computationally prohibitive, but I think UT-IGSP can work on fairly large graphs as well for a fair comparison of identifying shifted nodes. - Including code in supplementary could have been helpful. Varici, B., Shanmugam, K., Sattigeri, P., & Tajer, A. (2021). Scalable intervention target estimation in linear models. Advances in Neural Information Processing Systems, 34, 1494-1505. Varici, B., Shanmugam, K., Sattigeri, P., & Tajer, A. (2022, August). Intervention target estimation in the presence of latent variables. In Uncertainty in Artificial Intelligence (pp. 2013-2023). PMLR. Squires, C., Wang, Y., & Uhler, C. (2020, August). Permutation-based causal structure learning with unknown intervention targets. In Conference on Uncertainty in Artificial Intelligence (pp. 1039-1048). PMLR. Mooij, J. M., Magliacane, S., & Claassen, T. (2020). Joint causal inference from multiple contexts. The Journal of Machine Learning Research, 21(1), 3919-4026. Jaber, A., Kocaoglu, M., Shanmugam, K., & Bareinboim, E. (2020). Causal discovery from soft interventions with unknown targets: Characterization and learning. Advances in neural information processing systems, 33, 9551-9561. **Minor notes**: - Montagna et al. “Scalable Causal Discovery with Score Matching”: This is cited in the appendix. I believe it deserves more discussion in the main paper as it has some improvements over Rolland et al. (2020) especially for parent selection and efficiency of their algorithm. I see that the recent version became public at arXiv just shortly before the submission of the present paper, though an earlier version was available (NeurIPS 2022 Workshop on Score-Based Methods). - *ICM assumption*: Do you really need ICM assumption? It seems to me that you only need modularity principle of Pearl, that is each causal mechanism (conditional prob. dist.) is independent of the others. I see that you use it to say that “there are only a few shifted nodes” but if I am not mistaken, your analysis does not depend on such sparsity assumption. - [62] (Saeed et al. 2020): To my knowledge, their result for identifying shifted variables comes under poset compatibility assumption that can be quite restrictive for the structural changes.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

2 fair

Contribution

3 good

Limitations

The main limitations of the present work would be their assumptions. They are not discussed in a separate paragraph or pointed out somewhere in the paper (if I am not missing). But they are clearly written and can be understood at where they appear in the main text.

Summary

The authors propose a two-step algorithm for identifying causal mechanism shifts. The algorithm is motivated by a characterization of the nodes with mechanism shifts and the procedure is based on several existing tools. The proposed algorithm outperforms the baseline.

Strengths

1. Theorem 1 provides a new perspective for the characterization of nodes with shifted mechanisms. 2. The combination of existing tools in Algorithm 2 is interesting. 3. The computation complexity of the algorithm is reported.

Weaknesses

1. Assumption B (invariant noise distribution) makes the setting quite restrictive. There is no discussion or experiments about how sensitive the proposed method is w.r.t. shifted noise distributions, or whether the proposed idea can be generalized to handle shifted noise distributions. 2. I suspect that the statistic is not well-defined in some cases (see Questions below). 3. The threshold $t$ is a key hyper-parameter for the method, but the suggested elbow strategy is not a principled approach.

Questions

Regarding the statistics defined in (6) from Appendix, if the leaf node L is not shifted, the statistics may not be small since both the numerator and denominator are approximately zeros. Did I miss something here?

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

2 fair

Presentation

2 fair

Contribution

2 fair

Limitations

No potential negative societal impact.

Summary

This work addresses the problem of estimating differences in the causal models in two (or more) environments, over a single set of variables with the same causal ordering. The authors are interested in discovering those variables that undergo a functional or structural mechanism shift. As their main insight, they show that under additive noise models, the Jacobian of the score function of the data distribution provides information about such shifts. With this, they follow up on a line of research that uses this Jacobian to identify leaf nodes in a causal DAG (Rolland et al. 22, Montagna et al. 23). The authors propose the MSG algorithm, which given data from two environments, first discovers nodes which undergo a mechanism shifts, and in a second stage discovers the causal parents of shifted nodes as well as the edge differences between the causal DAGs in each environment. Empirically, they evaluate MSG on discovering nodes with mechanism shifts, and show that MSG outperforms the DCI approach (Wang et al. 18) while scaling linearly in the number of variables.

Strengths

- *Presentation*: The authors motivate the problem well and place the approach appropriately into the context of existing work. The paper has a clear structure and is easy to follow. - *Soundness*: The authors state the theoretical results clearly and provide detailed proofs for each claim. - *Scalability*: As the authors point out, their approach can identify mechanism shifts while avoiding a computationally costly estimation of the complete causal DAG. In addition, the proposed algorithm scales linearly in the number of DAG nodes, contrary to most existing work. Lastly, they propose to estimate the score function using the mixture distribution over multiple environments, suggesting an improved sample efficiency compared to approaches that use per-environment distributions. - *Assumptions*: MSG does not make any structural assumptions on the DAGs, nor restrictive functional modelling assumptions. - *Contribution*: Existing work on discovering difference DAGs assumes linear functional models (Wang et al. 18, Ghoshal et al. 21). Meanwhile, nonlinear approaches that can indirectly solve this problem by discovering a causal DAG over multiple contexts and identifying mechanism changes for each node (e.g. Mooij et al. 16, Huang et al. 19) do not scale well in practice. Hence, this work is a valuable addition to the literature.

Weaknesses

- *Novelty*: This work follows a recent line of research which also uses the Jacobian of the score of the data distribution to identify leaves in a causal DAG (SCORE, Rolland et al. 22, Montagna et al. 23). The proposed approach applies similar techniques and algorithms, making the approach incremental in nature. - *Comparison to SCORE*: To demonstrate the practical relevance of their insights and the novelty compared to the SCORE framework, it would be helpful to see a comparison to SCORE in the experiments. For example, is there a noticeable benefit of MSD compared to applying SCORE to each environment and comparing the resulting DAGs for structural differences? - *Comparison to DCI*: Given that DCI makes a linearity assumption, the superior performance of MSD in the experiments might only be due to DCI's model misspecification in the nonlinear setting. It might be interesting to include the linear case, where MSD's functional model is misspecified, or to consider additional competitors. - *Competitors:* There are many approaches that solve this problem indirectly, by (a) discovering a joint DAG over multiple environments and functional shifts for each node, or (b) discovering a DAG per environment, which we can compare for structural differences. For discovering shifted nodes, MSG has a computational advantage of not needing a direct estimation of DAGs, but it would be interesting to see whether it also has an advantage in terms of accuracy. For discovering structural differences, MSG has an F1 score of around 0.5 (Fig. 11), thus it would be informative to see whether direct DAG estimation improves upon this.

Questions

- What is the best way to extend MSG to more than two environments? For example, is it still possible to estimate the score from the mixture distribution over multiple contexts, and if so, how does this depend on the number of mechanism shifts over all contexts? - Definition 3 seems to admit the case where the causal parent set is empty in a given environment, that is, where a hard intervention occurs. Given that this case is not considered in the paper (footnote 3), what problems does it cause for MSD? Regardless, it would be interesting to consider hard intervention in the experiments. - The authors mention the approach by Ghoshal et al. 21, which is more recent than and slightly outperforms DCI. Is there a reason that the experiments do not include it? - Why is the evaluation result for 10 nodes sometimes missing in Appendix D (Fig. 10, 11)? I would also be interested in the case of 10 nodes in the main experiment in Fig. 3, since it seems that MSD has lower precision on smaller graphs (e.g. 20 nodes). - Fig. 3 seems to suggest that shifted node discovery improves with increasing number of nodes d, whereas in Fig. 1 it degrades, why is this? - In the experiments on difference DAG discovery in Fig. 11, MSG has F1 scores of at most 0.5. What most likely causes this? For example, is it related to the estimation of the causal parent sets with Alg. 2? While Theorem 2 establishes the consistency of discovering the correct parent sets, is this also true in practice? - Can the hypothesis tests in Appendix E be extended to also accomodate changes in noise distributions? - *smaller comments*: Citation style in Section 2.2 (numbers as subjects), Precision and Recall missing in Fig. 11 (while included in Fig. 13 which has the same setting).

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

4 excellent

Presentation

3 good

Contribution

2 fair

Limitations

- *Types of Mechanism Shifts*: The setting is motivated in the context of both functional and structural differences in SCMs (Def. 3, 4). While Alg. 1 for discovering shifted nodes can deal with both of these shifts, the evaluation focuses only on a specific type of *functional* shifts. Alg. 3 for discovering the causal parents, on the other hand, is only evaluated for *structural* shifts (Appendix D). The authors discuss the theoretical aspects of using Alg. 3 under functional shifts in Appendix E, but it would be interesting to also see an evaluation. - *Experiments*: As elaborated under weaknesses, the evaluation is limited because the authors only consider the linear competitor DCI, as well as do not evaluate parts of the proposed algorithm (Alg. 2, Alg. 5) or only in specific settings (Alg. 1, Alg. 3).

Summary

The paper proposes an efficient method to identify causal mechanism shifts across various interventional environments. The method's objective is to identify changes not only in the mechanism itself but also in the causal structure across the environments, which has been evaluated in artificial and real-world data sets.

Strengths

* Excellent introduction and illustrative examples to familiarize readers without strong backgrounds in this field with the problem setting. * Notation is concisely introduced, and the assumptions are detailed thoroughly. * The work is a theoretically valuable extension of existing work. * The method is easily applicable, and the details are sufficiently outlined for implementation. * The complexities are discussed in the paper. Please see the questions section for additional points.

Weaknesses

* The paper primarily builds on existing work, but it extends them in a sufficiently novel manner. One of my concern is the claim of not requiring knowledge about the causal structure, which is solely due to the utilization of Rolland et al.‘s existing work that aims at identifying the structure. Thus, one still relies on this; the discovery is merely part of the initial step. * The experiments seem quite limited, particularly with too few baseline methods for comparison (see the questions section for some suggestions). * The assumption about invariant noise distributions across environments is rather strong, although the other assumptions seem reasonably fair. * The overall complexity is relatively high. * The paper lacks a conclusion section. Please see the questions section for additional points.

Questions

Overall, the paper is well written and easy to follow. The examples are very helpful. Here are some comments and questions: * While the overview of related work in the introduction is excellent, the actual related work section seems a bit thin. Consider adding literature such as “Conditional Distributional Treatment Effect with Kernel Conditional Mean Embeddings and U-Statistic Regression” by Park et al., and “Why did the distribution change?” by Budhathoki et al. Given that you build on previous work for inferring the graph structure, you could also frame this problem as comparing it node-wise, as suggested in these papers. * Line 112 seems to suggest that you do not support hard interventions. However, based on Eq. (3), it should be fine. Perhaps, you could clarify this more explicitly. * Assumption A seems to be a mix of the ‘independence of mechanism’ assumption and the ‘modularity/autonomy’ assumption. The former states that the input distribution has no information about the causal mechanism, i.e., the mechanism is independent of its input (see e.g. “Information-geometric approach to inferring causal directions” by Janzing et al. for a more intuitive explanation). The ‘modularity/autonomy’ assumption states that intervening on one mechanism does not change other mechanisms in the system. I assume you refer to the latter one. * In Remark 1, note that \tilde PA_j = PA_j from related literature could also include a node that became irrelevant post-interventions. As you mentioned below, an intervention can change the functional form. For instance, in a linear model, the coefficient can become 0 of a parent, i.e., the parent can remain in the set, it is just not a ‘minimal’ set anymore. Maybe you can emphasize that you aim for ‘causal minimality’ and then having only a subset of parents after the intervention would make sense. * Assumption B is a quite strong, especially seeing that two environments might only change because of changes in external factors (the noise changes or becomes anomalous). Here, you would exclude these cases. In that sense, you restrict the shifts in a causal mechanism to changes in the functional form, which is significantly less general. Would be helpful to add a brief discussion about this and also emphasize the type of shift you are interested in more clearly. * You introduce the probability mass w (line 164), but wouldn't we know with a probability of 1 from which environment an observation comes from? * Stating that you do not rely on the knowledge about the causal structure seems slightly misleading as you still utilize Rolland et al.'s method. Hence, one could also use other methods that depend on knowing the DAG after applying the same algorithm. Maybe add a brief discussion regarding this. * Theorem 1 is a good result. Adding some intuitive explanation as to why the variance would be greater than 0 if the node shifted would be helpful. * The variable selection step could be more explicitly referred to as an edge pruning problem. * For the variable selection, would one use all data points from all environments? * Algorithm 2 seems slightly out of place. It should suffice to refer to that paper. * The experiment section is quite brief, especially the comparison with related methods. A possible approach could be to use Rolland et al.'s method to infer the graph and then apply methods as in the previously mentioned works by Park et al. and Budhathoki et al. --Update after rebuttal-- I have read the rebuttal and further discussed with the authors. Most of my concerns have been addressed and I raised the score by 1.

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

4 excellent

Contribution

3 good

Limitations

No concerns about societal impact were raised. The authors have reasonably discussed the technical limitations.

Reply to rebuttle

It is good to see that Assumption B can be relaxed. Based on this, I would raise my score. If the elbow strategy is indeed a classic heuristic, please provide references to support it. For the statistics, the intuition sounds reasonable. But since it is an important component of the method, some rigorous results will make the method more convincing.