Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: The paper studies the influence of biases in training data that are due to distributional shifts on the use of GNNs for semi-supervised learning, and proposes a new method to tackle this bias issue, i.e., the Shift-robust GNN (SR-GNN). SR-GNN is shown to perform better than standard GNNs in the presence of distributional-related bias.
main_review: GNNs, as many ML approaches, suffer from overfitting to the distribution of the training data. This typically arises in graph-based approaches when the nodes used for labeling in SSL are not IID.

As the goal is to use GNNs for SSL, a discussion on the connectedness of the graph would be useful. In the example from the paper on spam detection, depending on the dataset size, the graph might not be fully connected if the two classes are very far apart in the representation space $Z$. Would that be a problem? If yes, how to avoid it?

There are many different types of distributional shift, but the one considered here seems to be tightly related to the covariate shift where only the distribution of the covariates (here one can think of the representation $Z$ instead of the input $X$) varies while the conditional stays the same. I don’t think there is any reference in the paper on this. Could the authors extend on this similarity, or if not, the differences? Would the authors have a reference for the representation shift as defined on L132-133? Could this approach be used for other types of distributional shifts?

The locality aspect is not very clear to me. Would this be equivalent to sampling in the presence of unbalanced classes? What is the difference between the two? The locality aspect makes me think in spatial terms rather than imbalance. 

Other comments:

•	L21: varying exactly – not straightforward, maybe “decide”

•	L23: difference

•	L26: most works

•	L27: which “this”?

•	Both distribution shift and distributional shift are used

•	L66: propose a

•	L87: why unlabeled in brackets?

•	L98: to

•	L102: F not defined

•	$M$ is used both for the training data size and the labeled data size. In SSL, I understand the training dataset to be larger than the labeled dataset so the two should be different. Maybe I am missing smth? 

•	L140: $K$ -> $k$

•	L148: $z_M$

•	Fig. 1: ideally add labels for the axis. For the Cora dataset it’s difficult to see that the performance degrades as a function of CMD, it looks fairly uniformly distributed to me.

•	CMD: why not combine all moments under the sum, why keep the first moment separate, it would be more intuitive to use $c_1$ instead of expectation. How easy/difficult is it to compute CMD?

•	L170: what do the ‘ represent?

•	L179: distinct different

•	L183: should it be $A^K$ instead of k?

•	Eq 8 and 10: is there a $\sum$ missing?

•	Eq 9 : missing $\beta_i$ in the second term? Should the min be over all $\beta$, not just $\beta_i$?

•	L198: sum is over i not $\alpha_i$?

•	L203: what is $l_i$? should it be $y_i$?

•	L223: repeatable -> reproducible?

•	L234-238: How is the number of nodes needed per label known in advance (=enough number of nodes per label)?

•	Could you describe a bit the APPNP model and ideally define all the acronyms before using (DGI, GAT, etc)?

•	L271: how is $h_i$ used here?

•	Define Micro-F1 and Macro-F1

•	Check spelling: lineared, ppr -> PPR

•	Notations: check for A, E, F, \Theta – sometimes bold, sometimes normal


Originality: the paper addresses an important aspect of generalization/extrapolation and suggests a solution to address the bias in SSL using GNNs. The work looks fairly original to me even though I am not an expert in the field.

Quality: the paper is of good quality with a clear explanation of the theory and clean and thorough experiments.

Clarity: the paper is mostly clearly written with a few exceptions as in my comments above

Significance: Biases and extrapolation are important challenges and solutions to address them as in the current paper are relevant 

limitations_and_societal_impact: The paper addresses certain general limitations of the method, but does not discuss societal impact. How unbalanced are the classes in the examples used? Could the authors add a last column in A.1 to show the percentage of labels per class?
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: Graph Neural Networks (GNNs) have been attracted much attention very recently because of surprising results in many applications. In general, GNNs assume that the training node labels follow the i.i.d. property. However, in practice, the labels could be very biased. To deal with the biased training nodes, the authors propose regularization methods that consider feature distance between training nodes and i.i.d sampled unlabeled nodes. CMD and KMM are key components of the regularization: CMD measures the distance between train nodes and general nodes, and KMM computes balanced weights of training loss functions. SR-GNN is the main framework that includes both CMD and KMM ideas. The experimental section shows that the biased data can hurt the performance, and SR-GNN can mitigate performance degradation.
main_review: Originality: 

This paper first considers the distributional shift for standard GNN models where training nodes are very biased. Since the problem is new, the proposed algorithm also has novelty. 

Quality: 

This paper is the first work that considers biased training nodes in GNN training. The proposed SR-GNN framework is intuitive, and the performance of SR-GNN is evaluated with three real graph data.  

However, the experimental setting has some limitations. 

First of all, the biased setting is artificial. To motivate this paper's bias problem, the authors should provide some real examples where the labeled nodes really have the biased property. 

The main component of the proposed framework is not fully justified. Eq. (10) is the objective function of the proposed framework. In the objective function, weight $\beta_i$ and distance $d$ are crucial for the performance. Although there are many possible candidates for computing $\beta_i$ and $d$, this paper did not compare with other methods for finding $\beta_i$ and $d$. 

As the authors also mentioned, it would be much nice to consider some more particular kinds of distribution shifts.

Clarity: 

This paper is easy to read. 

Significance: 

This paper is the first work considering training bias in GNNs. I think many follow-up works are likely to refer to this work.

limitations_and_societal_impact: The authors discussed their limitations. Please refer to the main review comments for more discussions.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: Distributional shift is a common issue in machine learning.
In this paper, the authors study this topic in graph representation learning and also found the similar phenomenon.
They propose a framework called SR-GNN that is able to reduce influence of biased training data.
The authors have also conducted evaluation based on some benchmark datasets to show the effectiveness of the proposed method.
main_review: In general, the paper is written well and easy to follow. However, there are still several concerns that the authors need to address:

1. The practicality of the topic.
(1) Is there really exist distributional shift in the real world graph dataset, such as Cora, Citeseer, PubMed, ogb-arxiv datasets?
If the answer is yes, please use the some metrics, such as your paper shows in line 134, to compute the differences on these four datasets. 
(2) All of the experiments in this paper were conducted on post-intervention datasets, which may not occur in real life.
In other words, I want to know whether using your method on the original Cora, Citeseer, PubMed and ogb-arxiv datasets can still improve performance.

2. The relationship between the label shift and the distributional shift.
Uneven labeling refers that there is no random or uniform labeling the training node on the graph.
Distributional shift means that there exits gap between training and test dataset distribution.
But is there any relationship between the above two? 
Why does the deviation of the label lead to the deviation of the training set? 
Please give detailed theoretical or experimental proofs.

3. Questions about the distributional shift.
(1) As shown in Figure1, I really want to know how to quantitatively change the difference between the distribution of the training set and the test set.
(2) What is the specific value of the distribution difference in the datasets in Table 1 and Table 2? Please give specific numerical indicators, such as CMD and so on.
(3) As shown in Figure3, does increasing alpha mean increasing the distribution gap?
If your answer is yes, please give some theoretical or experimental proofs.
If not, please add experiments similar to Figure 1, that is, when the distribution difference changes from small to large, your proposed method can alleviate the negative correlation between performance and distribution difference to a certain extent.
(4) Please refer to "GCN(IID)" in Table 2,3,4. I want to know how IID is guaranteed?

4. Other questions.
(1) In line 186: "Unfortunately, as there are no learnable layers at this stage in these models, one can not simply apply the distributional regularizer proposed in the previous section." 
Why we can not use the final representation like standard GNN models to make regularization as equation (5) ?

5. A few minor errors.
(1) Table below the box line is missing, such as Table 2, 3.
(2) The tensor or matrix in the equation should be bolded.
limitations_and_societal_impact: Please refer to the above questions.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper proposes the Shift-Robust GNNs (SR-GNN) which provide the robust graph neural network model under the distribution shift scenario where the data distributions of train set and test set differ. To solve such *domain adaptation* issues, the authors adopt the linearized GNN models and Central Moment Discrepancy (CMD) between (biased) training and i.i.d samples for regularization.
main_review: Strengths
====
The problem of addressing distributional shifts between training and test is important in machine learning but it is less addressed in the geometric (graph) machine learning. This paper has clear merit that tackles such problems with the simple approach SR-GNN and well-designed experiments. Experimental results show that the proposed SR-GNN clearly handles the problem of distribution shift in semi-supervised node classification tasks with imbalanced data.

Weakness
====
The only concern I have is about the fairness of evaluation. SR-GNN seems to use additional input $Z_{IID}$, which are the representations of unlabeled data sampled from the unifying set of training and test dataset. However, other baselines only consider input from the biased distribution. Is it a fair evaluation? I think authors should include additional baselines [1] that also consider features from unbiased samples to highlight the advantage of SR-GNN in the domain adaptation setting.

Suggestions
====
1. typo - line 62 (that that -> that)
2. It will be better to include axis labels in Figure 1. In addition, it seems ambiguous to see relations between F1 and CMD only with Figure 1. Would you consider adding any metric such as the Pearson correlation coefficient?

[1] Ganin et al., "Domain-Adversarial Training of Neural Networks", JMLR 2016.
limitations_and_societal_impact: Please consider addressing suggestions in the main review. In addition, I am willing to raise my score if the authors address my concern in the weakness section of the main review.
review_title: null

Meta-review: This paper studies the influence of biases in training data that are due to distributional shifts on the use of GNNs for semi-supervised learning. The key idea is to adopt the linearized GNN models and Central Moment Discrepancy (CMD) between (biased) training and i.i.d samples for regularization. This paper proposes a new method to tackle this bias issue, i.e., the Shift-robust GNN (SR-GNN). SR-GNN is shown to perform better than standard GNNs in the presence of distributional-related bias.

However, there exists some limitations as follows.

1) The practicality: does there really exist distributional shift in the real world graph dataset, such as Cora, Citeseer, PubMed, ogb-arxiv datasets? Meanwhile, all of the experiments in this paper were conducted on post-intervention datasets, which may not occur in real life.

2) The relationship: Uneven labeling refers that there is no random or uniform labeling the training node on the graph. Distributional shift means that there exits gap between training and test dataset distribution. Is there any relationship between the label shift and the distributional shift? Why does the deviation of the label lead to the deviation of the training set? 

3) The shift: how to quantitatively change the difference between the distribution of the training set and the test set. What is the specific value of the distribution difference in the datasets in Table 1 and Table 2? Does increasing alpha mean increasing the distribution gap? If your answer is yes, please give some theoretical or experimental proofs. If not, please add experiments similar to Figure 1, that is, when the distribution difference changes from small to large, your proposed method can alleviate the negative correlation between performance and distribution difference to a certain extent.

This paper is a boardline case according to the average rating. While the reviewers had some concerns on the significance, the authors did a particularly good job in their rebuttal. Thus, all of us have agreed to marginally accept this paper for publication! Please include the additional experimental results in the next version.
Decision: Accept (Poster)