Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 4: Ok but not good enough - rejection
review_content: #### Goal

- This work presents an experimental investigation that shows the impact of training selection bias in GNNs (bias with respect to the test data). It also proposes a decorrelation approach to eliminate the spurious correlation in the node representations that come from this training bias.

- I like the experimental investigation (since I think the problem is very relevant). I am skeptical about the method and the results.

#### Quality

- I have many doubts about the validity of the claims. 

- Assumption 1 gives us a statistical model not a causal model. In order to claim “causal effects”, one needs to give a structural causal model. The linear models presented later are not linear on the observed variables. “Specifically, for both training and test environment, E(Y∣S = s, V = v) = E(Y∣S = s).” is a covariate shift question, not exactly a counterfactual question if not given with a specific structural causal model.

- “Assumption 2. The true generation process of target variable Y contains not only the linear combination of stable variables S, but also the nonlinear transformation of stable variables.” it is unclear what the authors mean by this statement. That the transformation over S is arbitrary?

- Equation (1): Since the node embeddings can be arbitrary, why do we need an extra function g()? Could that be incorporated into \mathcal{G}(X, A; θg)_S β_S? 

- “However, limited by the nonlinear power of GNNs (Xu et al., 2019), it is reasonable to assume that there is a nonlinear term g(G (X, A; θg)_S) ≠ 0 that cannot be fitted by the GNNs.”  This is not at all what (Xu et al., 2019) says. It says that there are some topologies that cannot be represented exactly. While other topologies can be represented exactly. It is entirely dependent on the input data, not a broad general statement for any graph dataset.

- “Hence the parameters of both stable variables and unstable variables would be biased.” This is a strong claim that requires a formal proof.

- The entire procedure is predicated on the linear models of Kuang et al., 2020, since the X in Kuang et al. (in, say, Eq (8) of Kuang et al.) is the observed data (not some learned representation). In this paper, the corresponding variables are H representations obtained by a GNN. The model is no longer linear on the input. The distinction between H_S and H_V is, hence, hypothetical, non-existent, and changes during training, since it depends on the GNN parameters. 

- How do we know that the decorrelation of H is not restricted to the training data? How do we know that in the test data, the same decorrelation holds? Any statement of decorrelation carrying over to the test data must be formally shown. 

- In section 3.2, all results are for linear models. Then, at some point, the observables X suddenly become hidden H and, it is stated (without proof) that the results carry over?!?!? If this were true, why are most works in the literature limiting their counterfactual evaluations to linear models? I highly doubt one can prove this is true for this scenario.

#### Clarity

- The paper uses very convoluted reasoning to arrive at conclusions that are not at all supported by theory. It uses a lot of results from linear models into a proposed nonlinear model. How can the results in the literature possibly carry over? It is hard to believe any of the claims.

- How can the distinction between S and V be clear in the model, since they are the outputs of a GNN we have not been trained yet?

- Can we precisely define the assumed covariate shift between train and test? No method can work for any covariate shift.

Typos & Overall fixes:

- “Even transfer learning is able to solve the distribution shift problem, however, it still needs the prior of test distribution, which actually cannot be obtained beforehand.” => “Even tough transfer learning is able to solve the distribution shift problem, it still needs the prior of test distribution, which cannot be obtained beforehand”

#### Originality

- Removing GNN training sampling bias with counterfactual inference would be new.

#### Significance

- The task of removing GNN training sampling bias is very important.

#### Pros

- Important task.
- Nice demonstration of the issues with biased training data.

#### Cons

- See “Quality”. I am unconvinced by the method.


----

After rebuttal: My main concerns about (a) no counterfactual model and (b) the linear / nonlinear requirements of the method remain. Generally, bias assumptions are made about the data, not the output of a representation learning procedure.  "The nonlinear relationship between raw input with the outcome can be encoded into the learned embedding" yes, but it does not mean H_S and H_V will meaningfully encode anything related to the input bias in any meaningful way. The method needs to precisely describe the structural causal model to be properly evaluated. 



review_title: Important task, unconvincing theory

final_score: rating: 5: Marginally below acceptance threshold
review_content: Summary:
The authors propose two different regularization terms to help mitigate the effect of label selection bias. The regularizers are well motivated and can be applied to different GNN models.

Reasons for score: 
Overall, I recommend a weak reject. While the theoretical analysis is interesting, the experimental evaluation is inconclusive and the performance improvement is marginal (see weak points). If the authors show stronger empirical evidence (see questions) I will consider increasing the score. Moreover, it is not clear whether the type of selection bias studied in the paper is actually relevant in practice.

Strong points:
* The proposed regularizers are well motivated, theoretically supported and at the same time simple and easy to implement.
* The causal view analysis of the proposed regularizers is insightful.
* The regularized have a reasonably small computational complexity.

Weak points:
* There are no results in the paper which show how the proposed method performs for a standard (non biased) labeling scenario. It is not clear whether the performance of GCN/GAT-VD/DVD in the standard setting is worse, roughly the same or better, and whether there are any trade-off which are incurred by the proposed regularizers. In other words, while the proposed method helps when there is a difference in the distribution of labels between the train and validation/test nodes it is not clear how it performs when there is no difference.
* It is not clear whether the highlighted label selection bias is actually present in practice. From the definition of r_i we see that this captures the notion of heterophily, i.e. neighboring nodes have dissimilar labels. In most real-world graphs however, we tend to observe homophily (opposite of heterophily), i.e. neighboring nodes tend to have the same labels. Homophily is often either explicitly or implicitly assumed in many GNN models, so it is not surprising that the performance drops when it is not present. Moreover, it is reasonable to assume that in practice the nodes for labeling are selected uniformly at random (or using active learning) in which case we would likely not observe heavy bias (due to underlying homophily).
* The performance improvement in most cases is marginal and does not seem to effectively mitigate the highlighted issue. In most cases the improvement is between 1% and 2%, and the results for heavy bias are still significantly worse (e.g. >5%) compared to the results for light bias (or no bias, not shown). The two outliers corresponding to 14% and 17% gain might be due to using a fixed data split (see next point).
* The paper uses the Planetoid data splits from [1] to form the validation/test set. Previous work [2] strongly argues against using a fixed split to evaluate the performance of GNNs since considering different splits of the data leads to dramatically different rankings of models. As far as I understood the results in the paper are averaged over 10 random seeds for selecting the training set, but the validation/test set is keep fixed. For a robust evaluation results show be reported as average of several different random validation/test splits. 

Question for the authors:
1. How does the results change if we consider the average over a larger number (e.g. 10) of random validation/test splits?
2. What is the performance of GCN/GAT-VD/DVD using uniformly sampled training nodes? Are there any trade-offs?
3. What is the empirical selection bias for standard (uniform sampling) train/validation/test splits, i.e. how large is the difference between the distributions of r_i scores? (For Cora, Citeseer, Pubmed we expect the difference to be small)
4. How well do the proposed methods perform in the transductive setting?
5. How does the performance gain of GCN/GAT-VD/DVD over GCN/GAT on the NELL dataset change as we increase the number of labeled nodes from 1 to some large number?

Additional feedback that did not affect the decision:
* The paper could benefit from a discussion of how the specified notion of label selection bias is similar or different from the notion of homophily/heterophily (see also weak points).
* Another potential selection bias is related to the degree of labeled nodes. For simpler models such as Label Propagation previous work has shown that different variants perform better depending on whether we label high or low degree nodes (see e.g. [3]). It would be interesting to discuss whether this also affects GNNs and whether the proposed approach can help mitigate such bias.
* It would be insightful to investigate whether recent GNN models which can handle heterophily [4, 5] can deal with the label selection bias studied in the paper. The reviewer acknowledges that these papers were made public after the ICLR submission deadline.
* Evaluating the effect of small sample selection bias on massive graphs from the Open Graph Benchmark (https://ogb.stanford.edu/) would be insightful. 
* It would be interesting to evalute whether we still observe a strong drop in performance if the training set is chosen in a standard fashion (i.e. the training nodes have high homophily) but the test nodes are selected using e.g. the heavy bias sampling.

## After Rebuttal
Thank you for addressing my questions. Since the performance improvement is still marginal and based on the other reviews I have decided to keep the same score.

References:
1. Yang, Zhilin, William Cohen, and Ruslan Salakhudinov. "Revisiting semi-supervised learning with graph embeddings."
2. Shchur, Oleksandr, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. "Pitfalls of graph neural network evaluation."
3. Avrachenkov, Konstantin, Alexey Mishenin, Paulo Gonçalves, and Marina Sokol. "Generalized optimization framework for graph-based semi-supervised learning."
4. Zhu, Jiong, Ryan A. Rossi, Anup Rao, Tung Mai, Nedim Lipka, Nesreen K. Ahmed, and Danai Koutra. "Graph Neural Networks with Heterophily."
5. Zhu, Jiong, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. "Generalizing graph neural networks beyond homophily."

review_title: Marginal improvement and inconclusive evaluation

final_score: rating: 4: Ok but not good enough - rejection
review_content: This paper presents a novel method to remove the selection bias of graph data, which is neglected by previous methods. Specifically, the authors suspect that all variables observed by GNNs can be decomposed into two parts, stable variables and unstable variables.  Then, DGNN, a differentiable decorrelation regularization is proposed to reweight each variable pair to eliminate estimation bias. Experiments on three datasets confirm its effectiveness.

Pros:
+ The studied problem is general and also practical for real-world applications.

Cons:
+ The novelty of this work is limited. Although the authors claim it is the first work to solve agnostic label selection bias problem, I in person believe this work can be regarded as a special case of DWR [1]. Therefore, on the basis of DWR, this paper presents not much theoretical contribution to this problem.
+ The presentation of this paper is somewhat confusing and not well-motivated. For example, it is not clear to understand the connection between the example presented in Section 2.1 and the proposed method. Also, why does this paper consider the Newton-Raphson update rule in Equation (9)? Besides, how do you efficiently compute the inversion of matrices?
+ The studied datasets are known to have unstable performance and are also of small scales. Even so, the performance improvement seems to be marginal with new baselines missing. Larger datasets such as OGB are strongly encouraged.

Reference:
[1] Stable Prediction with Model Misspecification and Agnostic Distribution Shift, AAAI 2020.
review_title: Official review

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: The paper proposes an important and unexplored problem in GNNs, i.e., the inconsistent distribution between the training set with test set caused by agnostic label selection bias. I believe that studying this problem is very important for generalizing GNNs on unseen test nodes. The paper first conducts an investigated experiment to show the great impact of agnostic selection bias on test performance. Moreover, the theoretical analysis is provided to identify how the label selection bias leads to the estimation bias in GNN parameters. 
To remove the estimation bias in parameter estimation, the paper proposes a novel DGNN framework by jointly optimizing a differentiated decorrelation regularizer (DVD) and a weighted GNNs model. The DVD regularizer is designed based on the causal view of variable decorrelation terms. I personally like the idea of analyzing variable decorrelation by the casual view. Furthermore, the paper theoretically proves that how to combine variable decorrelation terms with GNNs would be a more flexible framework for most GNNs and how to extend the theory to the multi-classification scenario. Overall, the proposed method is theoretical sound, where some basic claims are all supported by the clear and sound theoretical analysis. 
The paper conducts extensive experiments on four benchmark datasets with two kinds of selection bias, well showing the effectiveness of the proposed model. Basically, the paper is well motivated and well-organized. 

Strong points:
1.	The agnostic label selection bias problem in GNNs proposed by this paper is very important but seldom studied. And the paper shows the effect of label selection bias on the generalization of GNN in both experimental and theoretical way. In practice, the selection bias widely exists, I think this work may attract more attention in this direction, which makes GNNs more robust and stable in unseen environments.
2.	The technique of the proposed method is sound. The differentiated variable decorrelation is well motivated. This is a general framework for enhancing most existing GNNs under label selection bias setting. The idea of analysis and design model is novel, for example, analyze the estimation bias with stable learning theory, differentiated variable decorrelation in causal view, prove how to combine DVD with GNNs is more flexible, and extend the method to the multi-classification setting. I think these ideas are instructive.
3.	The experiment part is comprehensive and convincing. The experiments are conducted on two kinds of selection bias data, i.e., label selection bias and small sample selection bias. These two kinds of selection bias usually happen in real-world scenarios. And the results clearly show that the proposed methods make larger improvements with heavier bias.

Question for rebuttal:
1.	In section 3.3, the variable weight \alpha is computed from Var(W^(K−1), axis = 1), and \alpha_i can only be a positive value, however, in linear regression, the coefficients could also be a negative value. Hence, how to keep the \alpha computed from Var(W^(K−1), axis = 1) has the same meaning of linear regression coefficients?
2.	Although we can find the hyperparameters for each method from the experiment part and the corresponding paper of baselines, it is better to list all the hyperparameters used in the paper in the Appendix to improve reproducibility.

review_title: An innovative work for an interesting problem

Meta-review: This paper explores a very challenging problem of biased label selection and its effect on graph neural networks. It highlights that GNNs are indeed vulnerable to this issue, and then proposes a regularizer to reduce the learning of spurious correlations from the node embeddings. All of the reviews agree that the problem is relevant and important, but that there are still some outstanding issues.

It’s unclear the degree to which this problem occurs in the real world. It is also important to establish the effectiveness of the method across a range of datasets. The four datasets presented in the paper (and the rebuttal) are a good start, but the reviewers feel that more is still needed to present a convincing argument.

On the theory side, the reviewers are concerned about the linearity assumptions in the theory, and how this will translate into the more realistic nonlinear setting. Even though the authors state that they do not rely on a causal model, the paper and their responses really do seem to point in that direction. This could simply be a clarity issue, in which case I would encourage the authors to revisit this framing this to avoid confusion.

Overall, the paper is promising, but the reviewers feel that more work is needed to provide a comprehensive and convincing case.

Decision: Reject