Shift-Robust GNNs: Overcoming the Limitations of Localized Graph Training data
Authors: Qi Zhu
Natalia Ponomareva
Jiawei Han
Bryan Perozzi
Venue: NeurIPS 2021 Poster (2021)
Keywords: graph semi-supervised learning
distributional shifts
transfer learning

Abstract: There has been a recent surge of interest in designing Graph Neural Networks (GNNs) for semi-supervised learning tasks. Unfortunately this work has assumed that the nodes labeled for use in training were selected uniformly at random (i.e. are an IID sample). However in many real world scenarios gathering labels for graph nodes is both expensive and inherently biased -- so this assumption can not be met. GNNs can suffer poor generalization when this occurs, by overfitting to superfluous regularities present in the training data. In this work we present a method, Shift-Robust GNN (SR-GNN), designed to account for distributional differences between biased training data and the graph's true inference distribution. SR-GNN adapts GNN models for the presence of distributional shifts between the nodes which have had labels provided for training and the rest of the dataset. We illustrate the effectiveness of SR-GNN in a variety of experiments with biased training datasets on common GNN benchmark datasets for semi-supervised learning, where we see that SR-GNN outperforms other GNN baselines by accuracy, eliminating at least (~40%) of the negative effects introduced by biased training data. On the largest dataset we consider, ogb-arxiv, we observe an 2% absolute improvement over the baseline and reduce 30% of the negative effects.

Shift-Robus GNNs: Overcoming the Limitations of Localized Graph Training Data
Qi Zhu"
Natalia Ponomareva
Jiawei Han'
Bryan Perozzit
University of Illinois Airana-CChamaiinn
t: Google Research
* *qqi3, hanjh edu, hippooomareeaaaeeroooii/ g/g///
Abstract
There has been a recent surge of interest in designing Graph Neural Networks (GNNs) for semi-supervised learning tasks. Unfortunately this work has assumed that the nodes labeled for use in training were selected uniformly at random (i.e. are an IID sample). However in many real world scenarios gathering labels for graph nodes is both expensive and inherently biased so this assumption met. GNNs can suffer poor generalization when this occurs, by overfitting to superfluous regularities present in the training data. In this work present a method, Shift-Robust GNN (SR JSRGGNN), designed to account for distributional differences between biased training data and graph's 'sssss true inference distribution. SR-GNN adapts GNN models to the presence of distributional shift between the nodes labeled for training and the of the dataset. We illustrate the effectiveness of SR-GNN in variety of experiments with biased training datasets on common that SR- GNN outperforms other GNN baselines accuracy, addressing at least ~40% the negative effects introduced by biased training data. On the largest dataset we consider, ogb-arxiv, we observe a 2% absolute improvement over the baseline and able mitigate 30% of the negative effects from training data bias
not
GNN benchmark datasets for semi-supervised learning, where
Introduction
The goal of graph-based semi supervipe learning (SSL) is to use relationships between data (its graph inductive bias), along with small set of labeled items, to predict the labels for the rest of dataset. Unsurprisingly, varying exactly which nodes are labeled can have a profound effect on the generalization capability of a SSL classifier. Any bias the sampling process to select nodes for training can create distributional differences between the training set and the rest of the graph. During inference any portion of the graph can be used, so any uneven labeling for training data can cause training and test data to have different distributions. An SSI. classifier may then overfit to training data irregularities, thus hurting the performance at inference time.
Recently, GNNs have emerged as a way to combine graph structure with deep neural networks. Surprisingly, most work on semi-supervised learning using GNNs for node classification [15
have ignored this critical problem, and even the most recently proposed GNN benchmarks 12 assume that an independent and identically distributed (IID) sample possible for training labels.
1 Coode and processed data are available
35th Conference on Neural Information Processing Systems (NcurIPS 2021), Online.

---

This problem of biased training labels can be quite pronounced when GNNs are applied for semi- supervised learning in practice. It commonly happens when the size of the dataset so large that only subset of it can afford to be labeled - the exact situation where graph-based SSL is supposed to have value proposition! While the specific source of bias can vary, we have encountered it in many different settings. For example, sometimes fixed heuristics are used to select a subset of data (which shares some characteristics) for labeling. Other times, human analysts individually choose data items for labeling, using complex domain knowledge. However, even this can be rooted in shared characteristics of data. In yet another scenario, a label source may have some latency, causing temporal mismatch between the distribution of data at time of labeling and at the time of inference. In all of these cases, the core problem is that the GNN overfits to spurious regularities as the subset of labeled data could not be created in an IID manner.
One particular area where this can apply is the spam and abuse domain, common area of application for GNNs [8] 10 33.. However, the labels in these problems usually come from explicit human annotations, which are both sparse (as human labelling is expensive), and also frequently biased. Since spam and abuse problems typically have very imbalanced label distributions (e.g. in many problems there are relatively few abusers typically less than 1:100), labeling nodes IID results in discovering very few abusive labels. In this case choosing the points to request labels for in an IID manner is simply not a feasible option one wants to have a reasonable number of data items from the rare class.
In this paper, we seek to quantify and address the problem of localized training data in Graph Neural Networks. We frame the problem as that of transfer learning seeking to transfer the model's s performance from small biased portion of the graph to the entire graph itself. Our proposed framework for addressing this problem, Shift-Robur GNN (SR-GNN), strives to adapt biased sample of labeled nodes to more closely conform to the distributional characteristics present in an IID sample of the graph. It can handle two kinds of bias that occur in both deeper GNNs and more recent linearized (shallow) versions of these models.
First we consider the case of addressing distributional shift for standard GNN models such as GCNs [5]. MPNNS (7], and many more [5]. These models create deep networks which iteratively convolve information over graph structure. SR-GNN addresses this variety of distributional shift via a regularization over the hidden layers of the network. Second, we consider a class of linearized models (APPNP [16]. SimpleGCN 34 etc) which decouple GNNs into non-linear feature encoding and linear message passing. These models present an interesting challenge for debiasing, as the graph can introduce bias over the features after all learnable layers. In cases like this, SR-GNN can use an instance reweighting paradigm to ensure that the training examples are as representative as possible over the graph data.
We illustrate the effectiveness of our proposed method on both paradigms with an experimental framework that introduces bias to the train/test split in GNN, which lets us simulate the 'localized discovery' pattern observed in real applications on fully-labeled academic datasets. With these experiments we show that that our method SR-GNN can recover at least 40% of the performance lost when training a GCN on the same biased input.
Specifically, our contributions are the following:
1. We provide the first focused discussion on the distributional shift problem in GNNs.
2. We propose generalized framework, Shift-Robust GNN (SR-GNN), which can address shift in both shallow and deep GNNs.
3. We create an experimental framework which allows for creating biased train/test sets for graph learning datasets.
4. We run extensive experiments and analyze the results, proving that our methods can mitigate distributional shift.
2 Related Work
2.1 Distributional shift and Domain adaption work
Standard learning theory (i.e. PAC, empirical risk minimization, etc.) assumes that training and inference data is drawn from the same distribution, but there many practical cases where this

---

does not hold. The question of dealing with different distributions has been widely explored as a part of the transfer learning literature. In transfer learning, the domain adaptation problem deals with transferring knowledge from the source domain (used for learning) to the target domain (the ultimate inference distribution).
One of the first theoretical works on domain adaptation [3] developed a distance function between a model's performance on the source and target domains to describe how similar they are. To obtain a final model, training then happens on a reweighed combination of source and target data, where weights are function of the domain's distance. Much additional theoretical (e.g. (22]) and practical work expanded this idea and explored models which are co- vo-trained on both source and target data. These models seek to optimize utility while minimizing the distance between extracted features distributions on both domains; this in turn led to the field of Domain Invariant Representation Learning (DIR) 66. DIR is commonly achieved via co-training on labeled source and (unlabeled) target data. A modification to the loss either uses an adversarial head or adds additional regularizations.
More recently, various regularizations using discrepancy measures have been shown to be more stable to hyperparameters and result in better performance than adversarial heads, faster loss convergence and easier training. Maximum mean discrepancy (MMD) 19 20 is metric that measures difference between means of distributions in some rich Hilbert kernel space. Central moment discrepancy (CMD) 38 extends this idea and matches means and higher order moments in the original space (without the projection into the kernel). CMD has been shown to produce superior results and is less susceptible to the weight with which CMD regularization is added to the loss (20).
is important to point out that MMD and CMD regularizations are commonly used with non-linear networks some hidden layer (e.g. on extracted features). For linear models or non-differentiable models, prior work for domain adaptation often employed importance-reweightenn the appropriate weights, the same MMD distance was often used: in kernel mean matching (KMM) to find the appropriate weights one essentially minimizes MMD distance w.r.t the instance weights
instead. To find
2.2 GNNs
Given a graph = E,), the nodes V are associated with their features (X E RIVXF)) and the set of edges E (i.e. adjacency matrix A, A E R V[ which form connections between them. Graph neural networks [15] are neural networks that operate on both node features and graph structures. The core assumption of GNNs is that the structure of data (A) can provide a useful inductive bias for many modeling problems. GNNs output node representations Z which are used for unsupervised (30 or semi-supervised 15
learning. We denote the labels for SSL as {vi}.
The general architecture & of a GNN consists of K neural network layers which encode the nodes and their neighborhood information using some learnable weights 0. More specifically the output of layer k of a GNN contains a row (ht)) which can be used as a representation for each node i, i.e. * h/ Successive layers mix the node representations using graph information, for example:
H = a 1000
where À is appropriately normalized adjacency matrix? is the activation function, and H = X. For brevity's ' sake, we refer to the final latent representations z simply as Z throughout the work.
Although no existing work studies the distributional shift problem in GNNs, transfer learning of has explored different node-level and graph-level pre-training tasks across different graphs. Alternatively, domain adaption methods have been used to optimize domain classifier between source and target graphs 35). J. In addition, distribution discrepancy minimization (MMD) has been adopted to train network embedding across domains (28]. Other regularizations for the
GNNs 13, 39)
latent state of GNNs have been proposed for domains like fairness (23] We are the first to notice the
importance of distributional shift on the same graph in realistic setting and analyze its influence
different kinds of GNNs.
"The exact use of the adjacency matrix varies with specific GNN methods. For instance, the GCN [SS] performs mean vrean-pooling using matrix multiplication: À = Dー & (A + 1)D where I is the identity matrix, and D is the degree matrix of (A + 1), Da E,(A + 1)55-
3

---

3 Distributional shift in GNNs
To learn an SSL classifier, cross-entropy loss function / commonly used,
M
L
Uyi, 21),
M
where 2, is the node representation for the node learned from graph neural network, and M is the number of training examples. When the training and testing data come from the same domain (i.e. Primii X, Y)= (X, (X,Y)) Y)), optimizing the cross entropy loss over the training data ensures that classifier is well-calibrated for performing inference on the testing data.
3.1 Data shift as representation shift
However, mismatch between the training and testing distributions (i.e. Primin (X, Y) Pres Y)) is a common challenge for machine learning [25] [9]]
In this paper, we care about the distributional shift between training and test datasets present in Z, the output of the last activated hidden layer. Given that the foundation of standard learning theory assumes mrimi (Yl
Prisu (Y|2) the main cause of distribution shift is the representation shift, i.e. Primin Z, Y) * Priest (Z.Y) Y) + Primii (Z) * Prieat (Z). To measure such shift, discrepancy
metrics such as MMD 8 or CMD 37 can be used. CMD measures the direct distance between
distributions p and q as the following
llce (p) -
2 Σ bb-a
CMD
F. (p) (0)12
ca (4)l12,
k=
where is k-th order moment and b denotes the joint distribution support of the distributions. In practice, only limited number of moments is usually included (e.g. k=5). In this work we focus on the use of CMD [37 as a distance metric to measure distributions discrepancy for efficiency.
0.5
0.61
0.70
0.63
0.75
0582
0.5
0
0.55
033
0.2
3.24
CMQ
CHD
CMD
(a) Cora
(b) Citeseer
(c) Pubmed
Figure 1: Distribution shift lowers performance on GNN datasets. For each dataset, we show the performance (Fliy-axis) vs their distribution shift (CMDs for 100 biased training set samples.
We note that GNNs (Eq (T) are different from traditional neural networks, where the output for a layer K is defined as H = HH* g²). Instead, the multiplication of the normalized adjacency matrix RH* a Á ) essentially changes the output distribution of the hidden representation via the graph's 's inductive bias. Hence, in semi-supervised GNN, a biased training sample can lead to large representation shift due both the graph's inductive bias in addition 'normal' shift between non-lID sampled feature vectors.
Formally, start the analysis of distributional shift follows.
Definition 3.1 (Distribution shift in GNNs). Assume node representations Z = {21 . 3nd E are given as an output of the last hidden layer of a graph neural network on graph G with n nodes. Given labeled data {Z F:} of size M, the labeled node representation Z; = (Z1..... 2m) ) is subset of the nodes that are labeled, Zi Z. Assume Z and Zi are drawn from two probability distributions p and q. The distribution shift in GNNs is then measured via distance metric d d(Z Zi).
Interestingly, can empirically shown that the effects of distribution shift due to sample bias directly lower the performance of models. To illustrate this, we plot the distribution shift distance values (x-axis) and corresponding model accuracy (y-axis) for three common GNN benchmarks using the classic GCN model (15) in Figure I The results demonstrate that the performance of GNNs for

---

A
K,A)
(e.g.,
(...).A)
(e.g. PPR)
Fg(F,.B.A
(8, Kz-1.4)
4
A
%
head
head
1CY,44
((F.2x)
(IY,22)) 2.)
P Zz)
Feedforward
Traditional GNN
Linearized GNN
SR-GNN (Deep)
SR-GNN (Linearized)
Backgrosspriinn
Figure 2: A comparison between traditional GNN, linearized GNN and our framework (SR-GNN).
node classification on these datasets is inversely related to the magnitude of distributional shift and motivates our investigation into distribution shift.
Shift-Robust Graph Neural Networks
In this section, we will address the distributional shift problem (Pruain (2) (2) * Prest ( in GNNs by
proposing ways mitigate the shift for two different GNN models (Section 4.1 and 4.2 respectively). Subsequently, we introduce SR-GNN (Fig 2 as general framework that reduces distributional shifts for both differentiable and non-differentiable (e.g. graph inductive bias) sources simultaneously
in Section 4.3
4.1 Scenario 1: Traditional GNN models
We begin by considering a traditional GNN model 4, learnable function with parameters θ over some adjacency matrix A:
= F(O, A).
(4)
In the original GCN [1),, the graph inductive bias is multiplicative each layer and gradients back propagated through all of the layers. In the last activated hidden layers, we denote a bounded node representation as Z& ((,, Zx, A), Ze E [a, 6)" Zo- X.
Let us denote the training samples as {x; 1M the node representations are Zuain ( For the test samples, we sample an unbiased IID sample from unlabeled data XIDD = {x. { and denote the output representations as ZnD {-
In order to mitigate the distributional shift between training and testing, we propose a regularizer d: (a, bj"h (a, 6)nh R++ that is added the cross entropy loss. Since + is fully differentiable, can use distributional shift metric as a regularization to directly minimize the discrepancy between biased and unbiased IID sample like so:
L
Σ Uyys, 2.) A dl d(Zuain Zud) M
(5)
Here consider the central moment discrepancy regularizer, dEMD:
dCMD Zurin Zud) 1
E Zurinn)
E(ZuD) | + Σ bb al* ||ce (Zuiia) C& (Zuv)ll
(6)
k=2
where E(Z)= Σ 2 and (2) E(Z - E(Z))* & is the k-th order moment. In practice, moments up to the 5th order.
We use bounded activation function here, e.g. tanh sigmoid.
5

---

4.2 Scenario 2: Linearized GNN Models
Another family of recently proposed models for GNNs uses two distinct different functions one for non-linear feature transformation, and another for a linear graph spreading stage,
+ F2( (A) X).
Tinear function
In such linearized GNN model, the graph inductive bias is combined with node features by a linear function F1. which is decoupled from multi-layer neural network feature encoder F2- SimpleGCN 34 is an example of linearized model when F, (A) X Another branch of
linearized models [6 4 36) employs personalized pagerank to pre-compute the information diffusion in graph ei.e. (A) = a (1 - -)) and apply it on encoded node features F(O,X)
In both models, the graph inductive bias is provided an input feature linear F1. 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. In this case, we can view training and testing samples as row-wise samples h2 from (A). The problem of distribution shift Preain (2) A Prea(22 (Z) can then be transformed into matching the training and testing graph inductive bias feature space h2 R" (where n is the number of the nodes in the graph). Then to generalize from training data to testing, we can adopt an instance reweighting scheme correct the bias, such that biased training sample (he ) will be similar to an IID sample (1/ 1M The resulting cross entropy loss is then
L M 3,1(m, P(h:)),
(8)
where 3; be the weight for each training instance, and I is the cross-entropy loss. We can then compute the optimal B via kernel mean matching (KMM) [9] by solving a quadratic problem,
M (.)
M
1 M
Σ (0O),, s.t. B, < Ba
min 8%
M'
It tries to match the mean elements in kernel space k(-,-) on the domain R" x R". Specifically, db R" - H. denotes the feature map to the reproducing kernel Hilbert space(RKHS) introduced by kernel k. In our experiment, we use a mixture of gaussian kernel k(zz, y) = Ea, exp(osll || elll), a, = 1. 0.1, 0.01. The lower BJ and upper bound B,, constraints are there to make sure that most of the instances get some reasonable weight, as opposed to only few instances getting non zero weight. In practice, we have multiple classes in the label space. To prevent label imbalance introduced by 8, we further require that the sum of 3 for specific class e remains the same before
and after the correction, ΣM 3, I144 = c) = Σ I(4 = c), Vc.
4.3 Shift-Robust GNN Framework
Now propose Shift-Robust GNN (SR-GNN) our general training objective for addressing distributional shift in GNNs:
LSR-GNN 1
M 3,1(y,, ( A)) + A d(Zuran Zud).
(10)
The framework consists of both regularization for addressing distributional shift in learnable layers (Section 4. and an instance reweighting component which is capable of handling situations where a graph inductive bias is added after feature encoding (Section 4.2).
We will now discuss a concrete instance of our framework, by applying to the APPNP 16 model. The APPNP model is defined as:
T APPNP
(1 (1- + Σ (1 (1-0)'A F(O,X). 2=0
(11)
approximated personalized page runk
first applies feature encoder F on node features X and approximated personalized pagerank matrix linearly. Thereby, we have hy ,,..P where nT. is the personalized pagerank vector. For this, we mitigate distributional shifts from graph inductive bias via instance weighting. Moreover, let Z = F(O,X) X) and we can further reduce the distributional shifts from non-linea networks by the

---

proposed discrepancy regularizer d. In our experiments, we show the application of SR-GNN on two other representative GNN models: GCN [[]] and DGI 32
5 Experiments
In this section we first describe how we create training set with a controllable amount of bias, then discuss experiment design, demonstrate the efficacy our proposed framework for handling bias as well as its advantages over domain adaptation baselines, and finally, present a study on sensitivity to the hyperparameters.
5.1 Biased Training Set Creation
In order to study distribution shift GNNs, we require a repeatable process which can generate graph- biased training sets. The core aspect of creating a biased sample for graph learning tasks requires an efficient method for finding 'nearby' nodes in the graph for a particular seed node. In this work, we use
the Personalized PageRank (PPR) vectors to find such nearby nodes, IIP (I (1 - a))
PPR
vectors are well suited for this case for a number of reasons. First, several previous studies 36 16 have shown strong correlations between the information diffusion in GNNs and PPR vectors. Second, PPR vector can be computed for an individual node in time sublinear to the size of the graph 2 so biased training samples can be easily generated, even for large datasets. This local algorithm provides sparse approximation [IPP((e) (e) with guaranteed truncation error e, such that can efficiently compute the top-y entries of a ppr vector with controllable residuals. Therefore, using PPR we can generate stable localized training data that can effectively challenge GNN models.
We obtain biased sample from our scalable personalized pagerank sampler (PPR-S) as follows. For certain label ratio we compute the number of training nodes needed per label in advance. Then we repeatedly randomly select nodes that have enough neighbors in their sparse personalized pagerank vector - (c). We add both the seed nodes and their neighbors with the same label into the training data until we have enough number of nodes for each label.
5.2 Experimental settings
Datasets. In experiments, perform semi-supervisee node classification tasks five popular benchmark datasets: Cora, Citeseer, Pubmed (27). ogb-arxiv (26) and Reddit [[T]. We use the same validation and test splits in the original GCN paper [15] and OGB benchmark. We the remaining nodes for training. For the unbiased baseline's performance numbers, we use a random sample from this training data. Similarly, for biased training sample, we apply our biased sampler PPR-S on the training nodes to obtain a biased training sample and report its performance. The dataset statistics can be found in Appendix A.I.
Baselines. Following the two scenarios outlined in Section 4 we consider the following methods to
investigate their performance under distributional shifts: (1) Traditional GNN Models: GCN [[5],
GAT (31. (2) Linearized GNNs: SGC (34] and APPNP [6 We also include methods based on unsupervised node representation learning Walk 24 and DGI (32) ) as a third category (3). For these methods,
linear classifier learned top of pretrained node embeddings.
Scalable biased sampler. Our scalable biased sampler uses Personalized PageRank to efficiently create biased training samples in large graphs. Details are omitted for brevity here, but a full description can be found in Appendix A.2.
Our Method. If not otherwise specified, consider the APPNP [16] instance of Shift-Robur as base model, and also provide two ablations of These ablations independently use the shift-robust techniques introduced in Section 4.1 and 4.2 to validate the effectiveness of SR-GNN.
Hyperparameters. The main hyper parameters in our sampler PPR-S are 0.1,y = 100. When the graph is large, we set e = 0.001 in the local algorithm for sparse PPR approximation. In SR- GNN, X = 1.0 is the penalty parameter for the discrepancy regularizer d, the lower bound for the instance weight B, is 0.2. For all of the GNN methods except DGI, we set the hidden dimension as 32 for Cora, Citeseer, Pubmed and 256 for ogb-arxiv, with dropout of 0.5. In order learn effective
7

---

Table I: Semi-supervised classification on three different citation networks using biased training samples. Our proposed framework ER-GNN) outperforms all basclines on biased training input.
Cora
Citeseer Macro-F11 FFf
PubMed Macro
Method
Micro-
Macro-
AFI L
Micro-Fi Flf
AFI
Micro-F11
AFI
GCN (IID)
80.8 + 1.6
80.1 + 1.3
70.3
1.9
66.8
+ 1.3
0
79.8 = 1.4
78.8 14
0
Meat.
49.7 2.5
48.1 + 2.2
31.1
55.1 + 1.3
52.7
+ 1.3
25.2
51.3 + 2.8
41.8 +-2
28.5
Emb+MLP
3..6
56.2 + 3.0
23.2
38.5
1.2
38.6
L.1
31.8
60.4 2.1
36.6222
19,4
DGI
4.2
69.2 + 3.7
9.1
62.6
1.6
60.0
+ 1.6
766
58.0 + 5,3
52.4 8.3
21.8
GCN
6..6
66.4300
13.2
62.7 = 1.8
60.4
1.6
7.6
60.6
= 3.8
56,0
19.2
GAT
58.4
58.5
22.4
58.0 = 3.5
55.0
+ 2.7
12.3
55.2
3.7
46.0 6.4
14.6
SGC
70.2
68.0 3.8
10.6
65.4 = 0.8
62.5
1 0.8
4.9
61.8
1: 4.5
$7.4 1.22
18.0
APPNP
71.3
69.2
+ 3,4
9.5
63.4
1.8
61.2
+ 1.6
6.9
63.4
4.2
58.7 7.0
16.4
SR GNN w.o. IR
72.1
69.8 1 3.7
8.7
63.9 0.7
61.8 1 0.6
6.4
69.4 3.4
64.0 4,0
10.4
SR- GNN w.o. Reg.
72.0++3.2
3.7
0.9
63.4 0.9
66.4
13.4
SR-GNN (Ours)
3.3
71.4 3
7.3
67.1
0.9
64.0 + 0.9
3.2
713
70.2 + 2.4
8.5
representations, DGI [32] usually needs a higher dimensional hidden space and so, following the DGI paper we set it as 512 across all of our experiments. We use Adam [14] as an optimizer, and set the learning rate to 0.01 and L regularization to 5e-4.
Scalability, In this paper, we introduce two shift-robust techniques for GNN training: discrepancy
regularization and instance reweighting. Let (()) be the time some GNN & takes to compute a single node embedding, and M be the number of training examples. The IID sample in Eq (5) introduces M extra forward passes and 2M extra backward propagation in total. Overall, the extra cost is therefore linear to and does not increase the existing asymptotic complexity. The Gaussian kernel computation in Eq (9) (for instance reweighting) takes ((MPn) time before training, where hy E TR.". The total complexity of SR-GNN therefore ((M + M2 Our experiments were run on single machine with 8 CPU and 1 Nvidia T4 GPU.
5.3 Experiment results
We first show the performance comparison of SR-GNN (ours) and other baselines on three well- known citation GNN benchmarks in Table 6 We report the Micro-Fl, and Macro-Fl for each method, We compare each method trained on biased sample to GCN trained on an unbiased sample, and report its performance drop in Micro-FI (AF1). We begin by noting that when the training sample is biased, every method suffers a substantial performance drop (as indicated by the column AFI). However, SR-GNN consistently reduces the influence of distributional shift and decreases the performance drop (AFI) relative to a GCN model trained on biased input by at least 40%. We note that on these three datasets, the largest decrease performance occurs on PubMed, where of the existing methods experience more than 10% absolute drop in their performance due to the biased samples. However we note that in this challenging case, the improvements of SR-GNN against APPNP (base model) also grow when the shift is larger. Finally, that the combination of both the regularization and instance reweighting appears to work better than either bias correction its own. Our results demonstrate that our shift-robust framework is effective at minimizing the effects of distributional shift in GNN training data.
from the ablation models
On two large benchmarks in Table 2 we see that the performance loss from biased sample is smaller but still significant. Even in a dense network like reddit, the localized training data still affect the GNN model performance. Compared with baselines, SR-GNN can effectively mitigate the 30% of the negative effect (A) relative to an unbiased GCN. When more training data is provided (5%) we can further minimize this performance gap.
Finally, we also study how our Shift-Robust framework can be applied to two other representative models - GCNs [15]. and DGI B2 For the GCN model, we apply the regularized loss from the Equation (4) to the final node representations. For DGI, the embeddings are first trained via unsupervised learning over the entire graph. In this case, as we are optimizing a simple logistic regression over the DGI representations we can use only the instance reweighting regularization that the the Shift-Robust framework successfully improves task
from Equation g Table performance in the face of biased training labels, and that it can be easily applied to a variety of different GNN models.
8

---

Table 2: Semi-supervised classification ogb-arxiv and reddit varying label ratio.
ogb-arxiv
reddit
label(5)
1 %
%
%
5
Method
Accuracy
A 4
Accuracy
A
Accuracy
A
Accuracy
A
GCN (IID)
66.0+ 0.6
0
69.1= 0.6
0
93.8 + 0.3
0
94.0 + 0.1
MeP
45.5.1 0.6
21.5
43.71
0.3
25.4
46.610.6
47.2
57.2.10.2
36.8
EmP.
51.1# 1.3
14.9
56.9= 0.8
13.2
89.6 0.8
4.2
90.9 + 0.3
3.1
DGI
44.8 3.0
21.2
49.7= 3.3
19.4
83.7+1.2
10.1
85.4=0.6
8.6
GCN
59.3.1 1.2
6.7
65.3
0.6
3.8
89.7.1.0
4.1
90.910.3
3.1
58.6:: 1.0
7.4
63.4
1.0
5.7
80.5+5.4
13.3
82.043.6
12.0
SGC
59.0+ 0.7
7.0
64.2
1.3
8..6
5.2
90.6++02
APPNP
59.8+ 1.1
6.2
65.1
2.6
4.0
88.4+1.0
5.4
88.9+-0.8
5.1
SR-GNN
60.6:1: 0.2
5.4
65.1
4.0
90.4: 0.6
3,4
91.2+ 0.2
SR-GNN w.o, Reg.
61.0+ 0.3
5.0
65.8+2.0 2.
3.3
89.4+ 0.8
4.4
91.9 0.1
2.1
SR-GNN (Ours)
61.610..6
4.4
6..5
2.6
91.51
0.5
2.3
92.11
0.3
1,9
Table 3: Comparison baseline our SR(Shift Robust) version (A(%) relative with biased sample).
Corn
Citeseer
PubMed Macro F11
Method
Miern F11
Macro-Fi Fif
(%)
Micro F1
Macr-FF1
A(%)
Micro F1f
A(%)
GCN (IID)
80.8
80.1
0%
70.3
66.8
0%
79.8
78.8
0%
GCN
-12%
611.6
-19
SR-GCN
69.6
68.2
-10%
64.7
62.0
-6%
67.0
65.2
-13%
DGI (IID)
80.6
79.3
0%
70.8
66.7
0%
77.6
77.0
0%
DGI
71.7
69.2
-9%
62.6
-8%
58.0
52.4
-20%
SR-DGI
74.3
72.6
65.8
62.6
-6%
62.0
57.8
-16%
5.4
Comparison with other domain invariant learning methods
In SR-GNN, we utilize the unlabeled data ZnD sampled from the unifying set of training and test dataset. domain invariant learning 6 (7], unlabeled data from target domain is also used to regularize latent space between source and target domain. DANN (6) is method that uses an adversarial domain classifier to encourage similar feature distributions between different domains. In our case, the domains are biased training data (source) and IID unlabeled data (target). We compare the CMD regularizer and DANN regularizer using the same GNN architectures (i.e. GCN (15), APPNP (6).. The hyper parameter À is used to weight the domain loss and the CMD regularization respectively. We tune this hyper parameter on the validation set and report models' performance under the best À (1 for Cora and Citeseer, 0.1 I for PubMed). In Table as discussed in the related work, the discrepancy measures generally perform better than adversarial domain invariant learning (and CMD has been shown to be less sensitive to the regularizer weight). Especially under semi-supervised setting, the performance of DANN is more sensitive to the domain loss. Notice that CMD (Ours) the ablation (SR-GNN performance can be further boosted using instance reweighting.
IR) in the main paper note that have already shown its
Table 4: Comparison of with biased training data.
Neural Network (DANN) and CMD regularizer used in SR-GNN
Cora Micro-F11
Citeseer Micro-F1f
PubMed Micro-F1f
Method
Macro-F1f
Macro-F1
Macro-PP F1
GCN
68.3
67.2
62.4
60.2
59.2
53.8
DANN
69,8
68.5
63.8
61.0
64.8
61.8
CMD (Ours)
71.0
69.4
65.0
62.3
67.5
APPNP
71.3
69.2
63.9
61.6
64.8
60.4
DANN
71.6
69.5
64.3
61.8
67.8
65.4
CMD (Ours)
72.4
70.1
65.0
62.4
70.4
5.5
Parameter sensitivity of SR-GNN
In this section we study how varying some of our peraaeparseeters affects the performance. We perform 20 runs for each parameter and fix the initialization for all the models per run. Studies on SR-GNN with more layers (deeper models) and different biased samples are in Appendix A.3.

---

Performance with different in PPR-S. Previously, we set a = 0.1 in the biased sampler PPR-S. In Figure 3 we vary between [0.05, 0.3) evaluate the performance of APPNP and SR-GNN as the bias of the sample changes. While the absolute accuracy varies with different a, SR-GNN consistently beats its base model by clear margin. The different patterns across three datasets are expected, since as a grows, the PeR-neighbors can have different topological properties and structure.
0.7
0.70
0.73
Acorery
0.65
0.61-
0.4
087
0.55
015
0.29
022
0.2
0.25
0.2
0.2
0.5
3.23
(a) Cora
(b) Citeseer
(c) Pubmed
Figure 3: Varying a of biased sampler on three benchmarks.
Performance with different B₁, À in SR-GNN. In our framework, there are three major hyper parameters: the regularization strength X. the number of moments used in CMD and the bounds of instance weights: B,, Bu. In Figure 4aj the performance of SR-GNN with different & and X is reported. Even when only one moment is used for the CMD estimation, the method can still perform well with a reasonable penalty A. We study different choices of B₁ (for constant B,) in Figure The result shows smaller B₁ is better for training since larger values limit the expressive range.
Ce 2002
0.775
0,750
0,750
Acouracy
0.725
0.700
0.100
0.50
0.550
0.355
0.835
0.800
camoper
5.0mes
chmieer
F-0meed
(a) Varying A, & in regularization
(b) Varying Bj in instance weighting
Figure 4: Parameter sensitivity of SR-GNN.
Conclusion
In this paper we were the first to demonstrate that unbiased training data very important for performance of GNNs. We argued that biased training data is extremely common in real world scenarios and can arise due to a variety of reasons including: difficulties of labelling large amount of data, the various heuristics inconsistent techniques that are used to choose nodes for labelling, delayed label assignment, and other constraints from real world problems. We presented a general framework (SR-GNN) that is able to reduce influence of biased training data and can be applied to various types of GNNs, including both deeper GNNs and more recent linearized (shallow) versions of these models. With number of experiments, we demonstrated both GNNs susceptibility to biased data and the success our method in mitigating performance drops due to this bias: our method outperforms other GNN baselines on biased data and eliminates between (30 50%) of the negative effects introduced by training a GCN on biased training data.
However, there is still much to do. For instance, while we have considered the general problem of distributional shift GNNs, there is much specific work that can (and should) done in specific domains! Future work in this area should include regularizations to maximize performance for particular kinds of distribution shift (e.g. in spam & abuse detection) and to ensure constraints (e.g. fairness) in the presence of imbalanced training data.
10

---

Acknowledgments and Disclosure of Funding
Research was supported in part by US DARPA KAIROS Program No. FA8750-19-2-100- SocialSim Program No. W911NF-17-C-0099, and INCAS Program No. HR001121 National Science Foundation IIS-19-5615,, IIS-17-41317, and IIS 17-04532, and the Molecule Maker Lab Institute: An AI Research Institutes program supported by NSF under Award No. 2019897. Any opinions, findings, and conclusions recommendations expressed herein are those of the authors and do not necessarily represent the views, either expressed or implied, of DARPA or the U.S. Government. We would like to thank AWS Machine Learning Research Awards program for providing computational resources for the experiments in this paper.
References
[1] Sami Abu-El-Haija, Bryan Perozzi, Amol Kapoor, Nazanin Alipourfard, Kristina Lerman, Hrayr Harutyunyan, Greg Ver Steeg, and Aram Galstyan. MixHop: Higher-order graph convolutional architectures via sparsified neighborhood mixing. In Proceedings of the 36th International Conference on Machine Learning, pages 21-29. PMLR, 2019.
[2] Reid Andersen, Fan Chung. and Kevin Lang. Local graph partitioning using pagerank vectors. In 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS pages 475-486. IEEE, 2006.
[3] Shai Ben-David, John Blitzer, Koby Crammer, Alex Kulesza, Fernando Pereira, and Jen- nifer Wortman Vaughan.
theory of learning from different domains. Mach. Learn.,
79(1-2):151-175, May 2010.
[4] Aleksandar Bojchevski. Johannes Klicpera, Bryan Perozzi, Amol Kapoor, Martin Blais, Benedek Rózemberezki, Michal Lukasik, and Stephan Günnemann. Scaling graph neural networks with approximate pagerank. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 2464-2473, 2020.
[5] Ines Chami, Sami Abu-El-Haija, Bryan Perozzi, Christopher Ré, and Kevin Murphy, Machine learning on graphs: model and comprehensive taxonomy. arXiv preprint SxXi::2005.06675 2020.
[6] Yaroslav Ganin, Evgeniya Ustinova, Hana Ajakan, Pascal Germain, Hugo Larochelle, Franccois Laviolette, Mario Marchand, and Victor Lempitsky. Domain-adversarial training of neural networks, 2016.
[7] Justin Gilmer, Samuel S Schoenholz, Patrick Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International Conference on Machine Learning, pages 1263-1272. PMLR, 2017.
[8] Arthur Gretton, Karsten M Borgwardt, Malte J Rasch, Bernhard Schölkopf, and Alexander Smola. kernel two-sample test. The Journal of Machine Learning Research, 13(1):723-773, 2012.
[9] Arthur Gretton, Alex Smola, Jiayuan Huang, Marcel Schmittfull, Karsten Borgwardt, and Bernhard Schölkopf. Covariate shift by kernel mean matching. Dataset shift in machine learning, 3(4):5, 2009.
[10] Jonathan Halcrow, Alexandru Mosoi, Sam Ruth, and Bryan Perozzi. Grale:
Designing networks for graph learning. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 2523-2532, 2020.
[11) Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems, pages 1024-1034, 2017.
[12] Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. arXiv preprint arXiv:2005.00663 2020.
[13] Weihua Hu, Bowen Liu, Joseph Gomes, Marinka Zitnik, Percy Liang, Vijay Pande, and Jure Leskovec. Strategies for pre-training graph neural networks. In International Conference on Learning Representationss 2019.
[14] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.600 2014.

---

[15] Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations, 2017.
[16] Johannes Kliepera, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. arXiv preprint arXiv:1810.0599: 2018.
[17] Wouter M. Kouw. An introduction to domain adaptation and transfer learning. CoRR, abs/1812. 1806, 2018.
[18] Ziqi Liu, Chaochao Chen, Xinxing Yang, Jun Zhou, Xiaolong Li, and Le Song. Heterogeneous graph neural networks for malicious account detection. In Proceedings of the 27th ACM International Conference on Information and Knowledge Management, pages 2077-2085, 2018.
[19) Mingsheng Long, Yue Cao, Jianmin Wang, and Michael I. Jordan. Learning transferable features with deep adaptation networks. Proceedings of the 32nd International Conference on International Conference on Machine Learning Volume 37, ICML' 15, page 97-105. JMLR.org. 2015.
[20] Mingsheng Long, Han Zhu, Jianmin Wang, and Michael I. Jordan. Deep transfer learning with joint adaptation networks. In Proceedings of the 34th International Conference Machine Learning- Volume 70, ICML' 17, page 2208-2217. oML..org, 2017.
[21] Xinhong Ma, Tianzhu Zhang, and Changsheng Xu. Gcan: Graph convolutional adversarial network for unsupervised domain adaptation. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 8266-8276, 2019.
[22] Yishay Mansour, Mehryar Mohri, and Afshin Rostamizadeh. Domain adaptation: Learning bounds and algorithms. CoRR, abs/0902.3430, 2009.
[23] John Palowitch and Bryan Perozzi. Debiasing graph representations via metadata-orthogonal training. In 2020 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM), pages 435-442. IEEE, 2020.
[24] Bryan Perozzi, Rami Al- and Steven Skiena. Deepwalk: Online learning of social repre- sentations. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 701-710. ACM, 2014.
[25] Joaquin Malhonero-Candela Masashi Sugiyama, Neil D Lawrence, and Anton Schwaighofer. Datasel shift in machine learning. Mit Press, 2009.
[26] Marinka Zitmik Yuxiao Dong Hongyu Ren, Bowen Liu Michele Catasta Jure Leskovec, Weihua Hu, and Mathhis Fey. Open graph benchmark: Datasets for machine learning on graphs. arXiv preprint (rXi:2205500668/ 2020.
[27] Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi- Rad. Collective classification in network data. Al magazine, 29(3):93 (03),,9393,,10 2008.
[28] Xiao Shen, Quanyu Dai, Sitong Mao, Fu-lai Chung, and Kup-Sze Choi. Network together: Node classification via cross-network deep network embedding. IEEE Transactions on Neural Networks and Learning Systems, 2020.
[29] Hidetoshi Shimodaira. Improving predictive inference under covariate shift by weighting the ligeliiel function. Journal of statistical planning and inference, 90(2):227-244, 2000.
[30] Anton Tsitsulin, John Palowitch, Bryan Perozzi, and Emmanuel Müller. Graph clustering with graph neural networks. arXiv preprint arXiv:2006.1699 16904, 2020.
[31] Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pictro Lio, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations, 2018.
[32] Petar Velickovic, William Fedus, William L Hamilton, Pietro Liò, Yoshua Bengio, and R Devon Hjelm. Deep graph infomax. In International Conference on Learning Representations, 2019.
[33] Daixin Wang, Jianbin Lin, Peng Cui, Quanhui Jia, Zhen Wang, Yanming Fang, Quan Yu, Jun Zhou, Shuang Yang. and Yuan Qi. A semi-supervised graph attentive network for financial fraud detection. In 2019 IEFE International Conference on Data Mining (ICDM), pages 598-607, IEEE, 2019.
12

---

[34] Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Simplifying graph convolutional networks. In International conference on machine learning. pages 6861-6871. PMLR, 2019.
[35] Man Wu, Shirui Pan, Chuan Zhou, Xiaojun Chang, and Xingquan Zhu. Unsupervised domain adaptive graph convolutional networks. In Proceedings of The Web Conference 2020, 2020.
[36] Louis-Pascal Xhonneux, Meng Qu, and Jian Tang. Continuous graph neural networks. In International Conference on Machine Learning, pages 10432-10441. PMLR, 2020.
[37] Werner Zellinger, Thomas Grubinger, Edwin Lughofer, Thomas Natschläger, and Susanne Saminger-Platz. Central moment discrepancy (emd) for domain-invariant representation learn- ing. arXiv preprint arXiv: 700.0080 1, 2017.
[38] Werner Zellinger, Bernhard A. Moser, Thomas Grubinger, Edwin Lughofer, Thomas Natschläger, and Susanne Saminger-Platz. Robust unsupervised domain adaptation for neural networks via moment alignment. Information Sciences, 483:174-191, May 2019.
[39] Qi Zhu, Carl Yang, Yidan Xu, Haonan Wang, Chao Zhang, and Jiawei Han. Transfer learning of graph neural networks with ego-graph information maximization. In NewrIPS, 2021.
13


Reviews:
[{"review_id": "ZEaYz7Kkhc6", "reviewer": "Reviewer_6hbj", "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths\n====\nThe 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.\n\nWeakness\n====\nThe 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.\n\nSuggestions\n====\n1. typo - line 62 (that that -> that)\n2. 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?\n\n[1] Ganin et al., \"Domain-Adversarial Training of Neural Networks\", JMLR 2016.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}, {"review_id": "8uix2U7beo2", "reviewer": "Reviewer_RfY9", "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\nAs 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?\n\nThere 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?\n\nThe 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. \n\nOther comments:\n\n•\tL21: varying exactly – not straightforward, maybe “decide”\n\n•\tL23: difference\n\n•\tL26: most works\n\n•\tL27: which “this”?\n\n•\tBoth distribution shift and distributional shift are used\n\n•\tL66: propose a\n\n•\tL87: why unlabeled in brackets?\n\n•\tL98: to\n\n•\tL102: F not defined\n\n•\t$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? \n\n•\tL140: $K$ -> $k$\n\n•\tL148: $z_M$\n\n•\tFig. 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.\n\n•\tCMD: 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?\n\n•\tL170: what do the ‘ represent?\n\n•\tL179: distinct different\n\n•\tL183: should it be $A^K$ instead of k?\n\n•\tEq 8 and 10: is there a $\\sum$ missing?\n\n•\tEq 9 : missing $\\beta_i$ in the second term? Should the min be over all $\\beta$, not just $\\beta_i$?\n\n•\tL198: sum is over i not $\\alpha_i$?\n\n•\tL203: what is $l_i$? should it be $y_i$?\n\n•\tL223: repeatable -> reproducible?\n\n•\tL234-238: How is the number of nodes needed per label known in advance (=enough number of nodes per label)?\n\n•\tCould you describe a bit the APPNP model and ideally define all the acronyms before using (DGI, GAT, etc)?\n\n•\tL271: how is $h_i$ used here?\n\n•\tDefine Micro-F1 and Macro-F1\n\n•\tCheck spelling: lineared, ppr -> PPR\n\n•\tNotations: check for A, E, F, \\Theta – sometimes bold, sometimes normal\n\n\nOriginality: 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.\n\nQuality: the paper is of good quality with a clear explanation of the theory and clean and thorough experiments.\n\nClarity: the paper is mostly clearly written with a few exceptions as in my comments above\n\nSignificance: Biases and extrapolation are important challenges and solutions to address them as in the current paper are relevant \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4h"}, "extra_text": {}}, {"review_id": "85lTfIAAueQ", "reviewer": "Reviewer_i1qQ", "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality: \n\nThis 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. \n\nQuality: \n\nThis 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.  \n\nHowever, the experimental setting has some limitations. \n\nFirst 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. \n\nThe 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$. \n\nAs the authors also mentioned, it would be much nice to consider some more particular kinds of distribution shifts.\n\nClarity: \n\nThis paper is easy to read. \n\nSignificance: \n\nThis paper is the first work considering training bias in GNNs. I think many follow-up works are likely to refer to this work.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors discussed their limitations. Please refer to the main review comments for more discussions. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "16"}, "extra_text": {}}, {"review_id": "4Qo2I5AX-vm", "reviewer": "Reviewer_HELz", "summary": "Distributional shift is a common issue in machine learning.\nIn this paper, the authors study this topic in graph representation learning and also found the similar phenomenon.\nThey propose a framework called SR-GNN that is able to reduce influence of biased training data.\nThe authors have also conducted evaluation based on some benchmark datasets to show the effectiveness of the proposed method.", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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:\n\n1. The practicality of the topic.\n(1) Is there really exist distributional shift in the real world graph dataset, such as Cora, Citeseer, PubMed, ogb-arxiv datasets?\nIf 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. \n(2) All of the experiments in this paper were conducted on post-intervention datasets, which may not occur in real life.\nIn other words, I want to know whether using your method on the original Cora, Citeseer, PubMed and ogb-arxiv datasets can still improve performance.\n\n2. The relationship between the label shift and the distributional shift.\nUneven labeling refers that there is no random or uniform labeling the training node on the graph.\nDistributional shift means that there exits gap between training and test dataset distribution.\nBut is there any relationship between the above two? \nWhy does the deviation of the label lead to the deviation of the training set? \nPlease give detailed theoretical or experimental proofs.\n\n3. Questions about the distributional shift.\n(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.\n(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.\n(3) As shown in Figure3, does increasing alpha mean increasing the distribution gap?\nIf your answer is yes, please give some theoretical or experimental proofs.\nIf 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.\n(4) Please refer to \"GCN(IID)\" in Table 2,3,4. I want to know how IID is guaranteed?\n\n4. Other questions.\n(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.\" \nWhy we can not use the final representation like standard GNN models to make regularization as equation (5) ?\n\n5. A few minor errors.\n(1) Table below the box line is missing, such as Table 2, 3.\n(2) The tensor or matrix in the equation should be bolded.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Please refer to the above questions.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5h"}, "extra_text": {}}]

Author rebuttal:

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)