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: The paper investigates a new research problem of learning invariant graph representations under distribution shifts by considering the latent environment labels. The proposed method, graph invariant learning (GIL), is a joint learning framework combing three different GNNs of various functions. With good empirical results on several datasets and related theoretical analyses, the paper justifies the effectiveness of the proposed GIL. 
strengths_and_weaknesses: Pros

- The investigated problem is new and challenging, especially for real-world graph learning scenarios. With the well-defined research problem, the paper proposed to take the latent environment labels into consideration, which sheds an interesting direction on the current graph learning area.
- The gained empirical improvement is quite significant with the proposed GIL framework. Several ablation studies are shown.
- The paper is with good mathematical groundings for its provided theoretical analysis. Complexity analysis is also presented, including every single module of the proposed GIL framework.

Cons

- The importance of the latent environment labels is not fully justified, which should be the major contribution of the paper. It seems unclear for its motivation and significance and what benefits it can bring. In addition to the hyper-parameter study, there lacks instruction to extract, utilize, and analyze the latent environment labels.
- The technical novelty and contributions of the paper are neutral. The designed yet complicated framework seems to be the combination of several existing methods like the k-means and the invariance regularizer without presenting more insights into the new problem.
questions: 1. It might be somehow confusing for the invariance property in Assumption 3.1 for its connection with the true labels of graphs. Two graphs of different environments are likely to be classified correctly even though they are not perfectly samples. So, what is the main difference between the invariance property and  $P^e(\Phi^*(G))=P^{e^{\prime}}(\Phi^*(G))$ as in the last condition of Theorem 4.1? Is it harder to be achieved? Or, can it provide a better guarantee?
2. The optimization process of the three used GNNs is unclear, which could be an essential design of the proposed system. I.e., how do the GNN$^M$, GNN$^V$, and GNN$^I$ be jointly optimized? 
3. Besides, since the adjacent matrixes $A_I$ and $A_V$ are discrete, how are the gradients calculated and back propagated among these GNNs in an end-to-end manner?
4. The clustering effectiveness in Figure 5 seems quite perfect for its accurate partition, but the Score in Figure 4 is lower than 0.75. So, where is the gap come from? It would be better for the paper to introduce more about the Silhouette score, e.g., its basic calculation and range of values.
5. Regarding the prediction of latent environment labels are one of the main contributions, I would suggest the paper show the clustering cases without environment inference to better justify the effectiveness of such a designed module.
limitations: The READOUT functions, which shall be important for the proposed method, are not fully discussed and compared in the paper, including in the appendix part. Since the paper has mentioned the usage and the desired properties of READOUT functions many times, it would be better for the paper to provide a further discussion and related ablations. Besides, the influence of different GNN architectures, which served as backbones in the paper, is also missing.
review_title: null

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: This paper studies OOD generalization with a mixture of graph environments without environment labels. The method first generates the invariant subgraph and the variant subgraph based using a graph generator model. It then infers the environment labels by conducting k-means clustering on the variant subgraphs. This step assumes that the environment labels are correlated with variant subgraphs and are irrelevant to the invariant subgraph. The method then conducts invariant learning optimization across the different inferred environments.
strengths_and_weaknesses: This paper firstly studies OOD generalization for graphs without environment labels. The problem is clearly defined and discussed in the paper. Based on the assumptions, the author proposes a method that aligns with the identified challenges. The method later shows significant improvement over the baselines.

As for the weakness, I find gaps between the steps in theoretical analysis. In Equation (7), the optimization uses the ground truth environment $\mathcal{E}$, while Equation (8) uses the inferred environments $\mathcal{E}\_{infer} $ . The difference between $\mathcal{E}$ and $\mathcal{E}\_{infer} $ should be discussed to understand the proposed algorithm. The discussion should answer questions like "does $\mathcal{E}\_{infer}$ approximate $\mathcal{E}$?" and "what are the properties of $\mathcal{E}_{infer}$ for good OOD generalization performance?"
questions: As shown in [1], the ground truth environment partition does not always lead to the best OOD generalization performance. Is this also true in the graph domain? If yes, how does the proposed kmeans clustering lead to better environment partitions for OOD generalization? 

Reference:
[1] Environment Inference for Invariant Learning. In ICML 2021.
limitations: The authors have well addressed the limitations in the paper.
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: In this work the authors propose a three part method for learning graph representations that are robust to distribution shifts. First their method identifies _invariant_ subgraphs, then clusters the _variant_ complements to the invariant subgraphs to infer latent environment codes, and finally learns a representation function and linear predictor over the extracted invariant subgraphs and latent environment codes. This system is optimized end to end and they perform an empirical evaluation over synthetic and real world data to demonstrate the effectiveness of the approach.
strengths_and_weaknesses: ### Strengths

**Quality**: The empirical evaluation is well scoped in its choice of datasets as well as the diversity of the shift parameter settings and types of analysis showcased. In particular the SP-Motif and OGB selections are well suited to their method's focus on shared subgraph structures. The agreement between the performance rankings of GIL/DIR on SP-Motif and MOLHIV is a good sign since shared subgraphs and scaffolds are similar concepts. The finding that ERM generally outperforms most methods matches prior work for MOLHIV and this then underscores the performance of GIL (and the competitor DIR). Finally, the fact that the performance of the method is also demonstrated on datasets derived from different underlying signals (MNIST and SST2) that are not molecule based, serves as a good generality sanity check.

**Clarity**: The combination of Figure 2 and Section 3 describing their method and training procedures is well presented and easy to understand. Section 5 is broken down well into its subsections and the figures 6 and 7 are appreciated as visual references of the in/variant structures being identified.

**Significance**: Performance suggests that the approach is minimally competitive, and potentially SOTA pushing on the OGB data, though the way in which SP-Motif is used at the sweep of parameter settings makes it slightly harder to directly compare to other work. Method is simpler than some competitor approaches for OOD generalization, which is preferred.

### Weaknesses

**Clarity**: Theorems in Section 4, especially Thm 4.2 can likely be moved to the Appendix, as they don't add very much to the impact of the work compared to the empirical results. Further, Thm 4.1, especially the RHS, is stated very generally rather than in the specific setting of subgraph-based inter-environment invariance, which is not the _only_ kind of environment differentiation one expects in real world data (i.e. feature shift or label imbalance etc. are also options - these are in fact explored in the empirical results).

Work would generally benefit from a close editing pass from a native english speaker, _but this does not factor into my assessment_.

**Originality/Significance**: The three components of the method are not particularly novel on their own - in particular, the invariant regularized learner is very derivative of IRM in its objective. As such the work overall feels like a DL engineering solution for an E2E system, which is not without value by any means, but overall not very methodologically novel.


questions: 1. Relating to the comment above about environments sharing subgraph structure, this is very much a broad assumption in the entire work. It is _fine_ because though it is a narrow focus it is a fundamental type of distribution shift for graphs. However, it feels like conditions such as $P^{e}(\phi(G)) = P^{e'}(\phi(G))$ would generally be too strong in practical settings. Especially for the real world data, did you attempt to empirically verify that some of the conditions for Thm 4.1 approximately hold?

2. Can you elaborate on why the number of clusters for the k-means component was limited to $[2,4]$? Having to explicitly choose this parameter is one of the obvious points of difficulty for the model with datasets comprising an unknown number of latent environments.
limitations: The few limitations are relatively minor:

1. Methodological focus on shared subgraph/scaffold structure between environments
2. System bottleneck on the effectiveness of the unsupervised environment identification module. Ideally they would explore different choices for the clustering algorithm.
3. The analysis in Figures 4 and 5 of Silhouette score and the TSNE projection of clusters should be extended beyond the synthetic dataset where the environments are perfectly separable, as the claims they were used to support may not be very generalizable.
4. Hyperparameter sensitivity analysis should be extended beyond the synthetic dataset, even though it is plausible that the trends generalize.
review_title: null

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: This paper studies the out-of-distribution (OOD) generalization problem on graphs under a mixture of environments. 

It proposes a graph invariant learning (GIL) solution to learn a maximally invariant graph predictor, which composes an environment inference module and an invariant subgraph identification module. 
strengths_and_weaknesses: Strengths:

1. The problem this paper studied is important, i.e.,  OOD generalization of GNNs, and it proposes an out-of-distribution generalization framework for GNNs, which composes environment inference and invariant subgraph identification/generalization.
2. The presentation logic flow is clear.

Weaknesses:

1. The novelty and significance of this paper are a concern as some important literature is not discussed in this paper. There are several works also studying OOD generalization on graphs but corresponding discussions are missing in the paper. 
	1. Wu et al. 2022 [1] study the OOD generalization in node classification, and takes similar assumptions and solutions in this paper.
	2. Miao et al., 2022 [2] also discussed the application of graph information bottleneck criteria for OOD generalization.
2. Especially, in the literature on invariant learning, the key method in this paper shares many similarities with HRM[3], which should be discussed and compared substantially.
3. In experiments, [1,2] should all be included as baselines, and direct applying [3] to graph data should also be included as a baseline.


[1] Qitian Wu, Hengrui Zhang, Junchi Yan, David Wipf. Handling Distribution Shifts on Graphs: An Invariance Perspective. ICLR 2022.

[2] Siqi Miao, Miaoyuan Liu and Pan Li. Interpretable and Generalizable Graph Learning via Stochastic Attention Mechanism. ICML 2022.

[3] Jiashuo Liu, Zheyuan Hu, Peng Cui, Bo Li, and Zheyan Shen. Heterogeneous risk minimization. ICML 2021.
questions: As mentioned above, the main concern is about the novelty and lack of adequate literature discussions. 
limitations: No obvious potential negative societal impact. This paper should also discuss a bit about the applicability of the assumptions made in this paper.
review_title: null

Meta-review: metareview: This paper focuses on a new research problem of learning invariant graph representations under distribution shifts, which considers the latent environment labels. The proposal is a joint learning framework called graph invariant learning (GIL), combing three different GNNs of various functions. The philosophy behind sounds quite interesting to me, namely, learning a maximally invariant graph predictor, which composes an environment inference module and an invariant subgraph identification module. The proposed method GIL has good empirical results on several datasets and related theoretical analyses, which further justify its effectiveness.

The clarity and novelty are clearly above the bar of NeurIPS. While the reviewers had some concerns on the significance and complexity, the authors did a particularly good job in their rebuttal. Thus, all of us have agreed to accept this paper for publication! Please include the additional experimental results in the next version.
confidence: Certain
Decision: Accept