Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: In this paper, the authors proposed a causal structure learning algorithm based on the "sparse mechanism shift hypothesis" which says that distribution shifts across environments occur due to a small number of changes in the causal conditions. They introduced the "Mechanism Shift Score" which is the number of causal conditions changing across all pairs of environments, showing that the true causal graph minimizes this score. Furthermore, they showed that with enough changes across environments, the true causal graph can be identified. 
strengths_and_weaknesses: In this paper, the same augmented graph in [25] is constructed. However, instead of pooling all data, pairwise comparison among environments is considered which might give more information as shown in Figure 1. The paper is generally well written and the assumptions are clearly mentioned. However, it seems that some of the related works are missed. For instance, in [Brouillard et al. 2020], a score function for the setting of multi-environment with unknown target interventions has been proposed where the true causal graph can be identified up to an I-Markov equivalence class. There, it is assumed that the distribution of one of the environments is observational and there is no intervention on any variable, and we are aware of which environment has this property. Later, [Jaber et al. 2020] relaxed this assumption and defined an equivalence class for the setting of multi-environment with unknown target interventions (called $\Psi$-Markov equivalence) and characterized this class. Furthermore, they proposed an algorithm that is sound and complete. I believe the submitted paper should compare the results here both theoretically (whether it can recover causal structures that cannot be identified with previous work) and also experimentally. 


[Brouillard et al. 2020] Brouillard, P., Lachapelle, S., Lacoste, A., Lacoste-Julien, S., & Drouin, A. (2020). Differentiable causal discovery from interventional data. Advances in Neural Information Processing Systems, 33, 21865-21877.

[Jaber et al. 2020] 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.
questions: 1- The class of graphs that are identified by the proposed method should be characterized. Is it equivalent to I-Markov or $\Psi$-Markov class? I think the results in Theorem 5.3 is fairly straightforward.

2- I think one of the main issues of the proposed approach (and also the one in [25]) is that we need many environments to perform accurate conditional independence tests. 

3- Can this work be extended to the case that we have latent confounders? For instance, the result in [Jaber et al. 2020] allows the latent confounders.

4- In the experiments, it is better to compare different methods (including the missing references) in terms of F1 score and SHD.
limitations: I think it is a theoretical work and the authors clearly mentioned the assumptions in their work.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper focuses on the identifiability of causal graphs up to CPDAG in heterogeneous environments. Specifically, they explore the assumption of minimal changes in causal conditionals across different environments. This assumption of sparse mechanism shift is a non-parametric extension of the Principle of Minimal Changes [1]. With this as the hypothesis, a score-based method that identifies the entire causal structures with high probability has been proposed.

-------

[1] Amir Emad Ghassami, Negar Kiyavash, Biwei Huang, and Kun Zhang. Multi-domain Causal
Structure Learning in Linear Systems. In Advances in Neural Information Processing Systems,
volume 31. Curran Associates, Inc., 2018.
strengths_and_weaknesses: Pros:

1. The idea of exploring sparse mechanism shifts in a non-parametric setting is original and of interest to the community.
2. The theoretical results and assumptions have been rigorously stated.
3. The background and related works have been well introduced, which make the general picture clearer.
4. The writing is very clear.

Cons:

1. From Fig. 6, one could observe that MSS (KCI), which is based on the proposed score, doesn't outperform other baselines w.r.t. precision. More discussion about the reason would be appreciated.

2. I didn't find a clear statement/discussion of the limitation of the model. In the checklist, the limitation part has been pointed to the third paragraph of Sec. 7. However, it seems that no limitation has been clearly discussed in this Section. The most related part is the paragraph of 'Empirical performance and the validity of the sparse mechanism shift hypothesis.', but I still fail to see the discussion of limitations. Perhaps a direct discussion of them could be helpful?

3. Regarding [2], it has been mentioned in the manuscript that, compared to the proposed method, the disadvantage of [2] is that it is not suited for sparsely-detectable changes. Since the sparse change is basically the assumption made in this manuscript but not in [2], I'm wondering whether it is a valid/fair point in general cases.



-----------------

[2] Biwei Huang, Kun Zhang, Jiji Zhang, Joseph Ramsey, Ruben Sanchez-Romero, Clark Glymour, and Bernhard Schölkopf. Causal discovery from heterogeneous/nonstationary data. Journal of Machine Learning Research, 21(89):1–53, 2020.

questions: Please let me know if the points/questions listed as the cons are due to my misunderstanding of the manuscript.
limitations: It seems that there is no obvious discussion of limitations. Please let me know if I missed anything.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper proposes a score-based approach for causal discovery (Mechanism Shift Score) using non-iid data from multiple environments under spare mechanism shifts. It provides theoretical analysis for the proposed approach, as well as empirical experiments.
strengths_and_weaknesses: Although the Sparse Mechanism Shift hypothesis and its application for causal discovery is not new, this paper provides a sound method for using it by designing a score and analyzing it theoretically.

Pros: 
-The presentation is clear and easy to follow.
-The problem is significant in many areas of science.

Cons:
-Evaluation in the main body is limited to only a synthetic data generation mechanism.
questions: -In evaluation, why do you use a data generation mechanism where the effect of parents and noise is additive? Does this method not work for a more general data generation mechanism? Why?

-Comparison with "https://arxiv.org/abs/1910.01075" would be interesting.

-Why don't you show F-1 scores for evaluation?

Line 285: rates' instead of rates
Line 234: Corollary 4.4 instead of Lemma 4.3
limitations: Yes
review_title: null

Meta-review: metareview: The decision is to accept the paper.

The paper proposes a method for causal structure discovery that leverages an assumption about sparse mechanism shifts across multiple environments. The authors show that access to multi-environment data that satisfy this assumption can provide identification beyond standard equivalence classes. Based on reviewer / author discussions, the method seems novel, and is now well-contextualized within other literature in this area. The authors have thoroughly investigated near-alternatives, and while there are not direct comparisons in the paper, the authors cite good reasons for why this is the case. The paper is a solid contribution.
confidence: Certain
Decision: Accept