Debiased Graph Neural Networks with Agnostic Label Selection Bias
Authors: Shaohua Fan
Xiao Wang
Chuan Shi
Kun Kuang
Nian Liu
Bai Wang
Venue:  (2021)
Keywords: GRAPH NEURAL NETWORKS
LABEL SELECTION BIAS

Abstract: Most existing Graph Neural Networks (GNNs) are proposed without considering the selection bias in data, i.e., the inconsistent distribution between the training set with test set. In reality, the test data is not even available during the training process, making selection bias agnostic. Training GNNs with biased selected nodes leads to significant parameter estimation bias and greatly impacts the generalization ability on test nodes. In this paper, we first present an experimental investigation, which clearly shows that the selection bias drastically hinders the generalization ability of GNNs, and theoretically prove that the selection bias will cause the biased estimation on GNN parameters. Then to remove the bias in GNN estimation, we propose a novel Debiased Graph Neural Networks (DGNN) with a differentiated decorrelation regularizer. The differentiated decorrelation regularizer estimates a sample weight for each labeled node such that the spurious correlation of learned embeddings could be eliminated. We analyze the regularizer in causal view and it motivates us to differentiate the weights of the variables based on their contribution on the confounding bias. Then, these sample weights are used for reweighting GNNs to eliminate the estimation bias, thus help to improve the stability of prediction on unknown test nodes. Comprehensive experiments are conducted on several challenging graph datasets with two kinds of label selection bias. The results well verify that our proposed model outperforms the state-of-the-art methods and DGNN is a flexible framework to enhance existing GNNs.

Under review as a conference paper at ICLR 2021
DEBIASED GRAPH NEURAL NETWORKS WITH AGNOSTIC LABEL SELECTION BIAS
Anonymous authors Paper under double-blind review
ABSTRACT
Most existing Graph Neural Networks (GNNs) are proposed without considering the selection bias in data, i.e., the inconsistent distribution between the training set with test set. In reality, the test data is not even available during the training process, making selection bias agnostic. Training GNNs with biased selected nodes leads to significant parameter estimation bias and greatly impacts the generalization ability on test nodes. In this paper, we first present an experimental investigation, which clearly shows that the selection bias drastically hinders the generalization ability of GNNs, and theoretically prove that the selection bias will cause the biased estimation on GNN parameters. Then to remove the bias in GNN estimation, we propose a novel Debiased Graph Neural Networks (DGNN) with differentiated decorrelation regularizer. The differentiated decorrelation regularizer estimates a sample weight for each labeled node such that the spurious correlation of learned embeddings could be eliminated. We analyze the regularizer in causal view and it motivates us differentiate the weights of the variables based on their contribution on the confounding bias. Then, these sample weights are used for reweighting GNNs to eliminate the estimation bias, thus help to improve the stability of predic- tion on unknown test nodes. Comprehensive experiments are conducted on several challenging graph datasets with two kinds of label selection bias. The results well verify that our proposed model outperforms the state-of-the-art methods and DGNN is a flexible framework to enhance existing GNNs.
INTRODUCTION
Graph Neural Networks (GNNs) are powerful deep learning algorithms on graphs with various applications (Scarselli et al. 2008 Kipf & Welling 2016 Veličković et 2017 Hamilton et a 2017). Existing GNNs mainly learn a node embedding through aggregating the features from its neighbors, and such passsage-passing framework is supervised by node label in an end-to-end manner. During this training procedure, GNNs will effectively learn the correlation between the structure pattern and node feature with node label, so that GNNs capable of learning the embeddings of new nodes and inferring their labels.
One basic requirement of GNNs making precise prediction unseen test nodes is that the distribution of labeled training and test nodes same, i.e., the structure and feature of labeled training and test nodes follow the similar pattern, that the learned correlation between the current graph and label can be well generalized to the new nodes. However, in reality, there are two inevitable issues. (1) Because it is difficult control the graph collection in an unbiased environment, the relationship between the collected real-world graph and the labeled nodes is inevitably biased. Training on such graph will cause biased correlation with node label. Taking a scientist collaboration network as an example, if most scientists with "machine learning" (ML) label collaborate with those with "computer vision" (CV) label, existing GNNs may learn spurious correlation, i.e., scientists who cooperate with CV scientist are MI scientists. If a new ML scientist only connects with ML scientists or the scientists in other areas, it will be probably misclassified. (2) The test node the real scenario is usually not available, implying that the distribution of new nodes is agnostic. Once the distribution is inconsistent with that in the training nodes, the performance of all the current GNNs will be hindered. 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. Therefore, the agnostic label selection bias greatly affects the generalization ability of GNNs unknown test data.

---

Under review as a conference paper at ICLR 2021
0.87
0.73
0.80
Accurary
Accurary
0.78
0.59
0.74
0.76
COLoard
Stree
Light (0.7)
Medium (0.5) Heavy (0.9)
0 (0./)
Medium (0.5)
Hesuy (0.9)
Light (0.7)
Medium (0.8)
Heavy (0.9;
Bles
(a) Cora
(b) Citeseer
(c) Pubmed
Figure 1: Effect of selection bias on GCN and GAT.
In order to observe selection bias in real graph data, we conduct an experimental investigation to validate the effect of selection bias on GNNs (details can be seen in Section 2.T). We select training nodes with different biased degrees for each dataset, making the distribution of training nodes and test nodes inconsistent. The results clearly show that selection bias drastically hinders the performance of GNNs on unseen test nodes. Moreover, with heavier bias, the performance drops more. Further, theoretically analyze how the data selection bias results in the estimation bias in GNN parameters (details can be seen in Section 2.2). Based on the stable learning technique (Kuang et al. 2020), we can assume that the learned embeddings consist of two parts: stable variables and unstable variables. The data selection bias will cause the spurious correlation between these two kinds of variables. Thereby we prove that with the inevitable model misspecification. the spurious correlation will further cause the parameter estimation bias. Once the weakness of the current GNNs with selection bias is identified, one natural question is "how to remove the estimation bias in GNNs?"
In this paper, we propose a novel Debiased Graph Neural Network (DGNN) framework for stable graph learning by jointly optimizing a differentiated decorrelation regularizer and a weighted GNN model. Specifically, the differentiated decorrelation regularizer is able to learn a set of sample weights under differentiated variable weights, so that the spurious correlation between stable and unstable variables would be greatly eliminated. Based on the causal view analysis of decorrelation regularizer, we theoretically prove that the weights of variables can be differentiated by the regression weights. Moreover, to better combine the decorrelation regularizer with GNNs, we prove that adding the regularizer to the embedding learned by the second to last layer could be both theoretically sound and flexible. Then the sample weights learned by decorrelation regularizer are used to reweight GNN loss so that the parameter estimation could be unbiased.
In summary, the contributions of this paper are three-fold: i) We investigate a new problem of learning GNNs with agnostic label selection bias. The problem setting is general and practical for real applications. ii) We bring the idea of variable decorrelation into GNNs to relieve bias influence on model learning and propose a general framework DGNN which could be adopted various GNNs. iii) We conduct the experiments on real-world graph benchmarks with two kinds of agnostic label selection bias, and the experimental results demonstrate the effectiveness and flexibility of our model.
EFFECT OF LABEL SELECTION BIAS ON GNNS
In this section, we first formulate our target problem as follows:
Problem 1 (Semi-superrised Learning on Graph with Agnostic Label Selection Bias). Given training graph Strain = (Atroins Xtraina Y train.. where Atrain R NxN (N nodes) represents the adjacency matrix, Xtrain E R. NxD (D features) refers to the node features and Y train B (n labeled nodes, C classes) refers to the available labels for training (n << N), the lask is to learn a GNN ()(+) with parameter 0 to precisely predict the label of nodes on test graph Great (Atest; Xiest, Yissth where distribution A (9 # T (Grest))
2.1 EXPERIMENTAL INVESTIGATION
We conduct an experimental investigation to examine whether the state-of-the-an GNNs are sensitive to the selection bias. The main idea is that will perform two representative GNNs: GCN (Kipf
2

---

Under review as a conference paper at ICLR 2021
& Welling 2016) and GAT Veličkovié et al. 2017) on three widely used graph datasets: Cora, Citeseer, Pubmed (Sen et al. 2008) with different degrees of bias. the performance drops sharply in comparison with the scenarios without selection bias, this will demonstrate that GNNs cannot generalize well in selection bias setting.
To simulate the agnostic selection bias scenario, we first follow the inductive setting in Wu al. (2019) that masks the validation and test nodes as the training graph Graan in the training phase, and then infer the labels of validation and test nodes with whole graph Gtest- In this way, the distribution of test node can be considered agnostic. Following Zadrozny (2004), we design a biased label selection method on training graph Graain The selection variable e introduced to control whether the node will be selected as labeled nodes, where e = means selected and O otherwise. For node i, we compute its neighbor distribution ratio: r, Kili E Nv yj * y: H/Hl where NG is neighborhood of node i in Strain and y # Y4 means the label of central node i is not the label of its neighborhood node j. And r; measures the difference between the label of central node with the labels of its neighborhood. Then we average all the nodes' r to get threshold t. For each node, the
=11-
Ti 2
probability to be selected is: P(e; = 11r,) = 1-c r; <t where E (0.5, 1) is used to control
the degree of selection bias and the larger e means heavier bias. We set (0.7, 0.8, 0.9) get three bias degrees for each dataset, termed as Light, Medium, Heavy, respectively. We select 20 nodes for each class for training and the validation and test nodes are same as Yang et al.] (2016). Furthermore, we take the unbiased datasets as baselines, where the labeled nodes are selected randomly.
Figure iis the results of GCN and GAT biased datasets. The dashed lines mean the performances of GCN/GAT on unbiased datasets and the solid lines refer to the results on biased datasets. We can find that: i) The dashed lines are all above the corresponding coloured solid lines, indicating that selection bias greatly affects the GNNs' performance. ii) All solid lines decrease monotonically with the increase of bias degree, demonstrating that heavier bias will cause larger performance decrease.
2.2 THFORETICAL ANALYSIS
The above experiment empirically verifies the effect of selection bias GNNs. Here we theoretically analyze the effect of selection bias on estimating the parameters in GNNs. First, because biased labeled nodes have biased neighborhood structure, GNNs will encode this biased information into the node embeddings. Based on stable learning technique (Kuang et al. 2020), we make following assumption:
Assumption 1. All the variables of embeddings learned by GNNs for each node can be decomposed as H = (S. V). where S represents the stable variables and V represents the unstable variables. Specifically, for both training and test environment, E(Y s, V = v) E(Y|S s). s).
Under Assumption [ the distribution shift between training set and test set is mainly induced by the variation in the joint distribution over (S, V), i.e., Prain V Vrain)
# P(Stest> Vieer). However, there is an invariant relationship between stable variable S and outcome in both training and test environments, which can be expressed as P( Y trein (rann)) | guaranteed by Y LVS. Thus, one can solve the stable prediction problem by developing a function f(-) based on However, one can hardly identify such variables in GNNs.
IP( Y teet I (Stee) Assumption I can be
Without loss of generality, we take Y as continuous variable for analysis and have the following assumption:
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.
Based the above assumptions, we formalize the label generation process follows:
Y = -(X A) + 9 (X, A; 0g)s33 I A;0)vv By + g( A 0,),)) +E,
(I)
where (X E 12 Nxp denotes unknown function of X and A that learns node embedding and it can be learned by a GNN, such as GCN and GAT, the output variables of (X, 0,y can be decomposed as stable variables 3 (X, A; Aggg) R Nxq (m + q p), 3y E mx! and By E g are the linear coefficients can be learned by the last layer of GNNs, is the independent random noise, and g(-) is the nonlinear transformation function
R." Nxm and unstable variables ( A: 0g;y)v E
3

---

Under review as a conference paper at ICLR 2021
of stable variables. According to Assumption | we know that coefficients of unstable variables 3 (X, A; fg)v are actually 0 (i.e., By=0).
For classical GNN model with linear regressor, its prediction function can be formulated as:
Y = = A:0g) + (X, A:g) +
Compared with Eq. I can find that the parameters of GNN could be unbiasedly estimated if the nonlinear term g( / XX 0g0))s O, because the GNN model will have the same label generation mechanism Eq. I However, limited by the nonlinear power of GNNs (Xu et al., 2019p. it is reasonable to assume that there is a nonlinear term g (X, A: (g)ss) # that cannot be fitted by the GNNs. Under this assumption, next, we taking a vanilla GCN (Kipf & Welling 2016) as an example to illustrate how the distribution shift will induce parameter estimation bias. A two-layer
GCN can be formulated as Ao ( (Ax)()) w where Å is the normalized adjacency matrix, W is the transformation matrix at each layer and (-)) is the Relu activation function. We decompose GCN two parts: one is embedding learning part Ao (AXX (o)) which can be decomposed as [S v"J, corresponding to g (X, A; 0y)s and & (X. A; A:0g) Eq. (). and the other part is w where the learned parameters can be decomposed as [$s, Iv corresponding to [âs, By] in Eq. 2)
We aim at minimizing the square loss: LCON Σ (S, B3 + By Y,)
According to the derivation rule of partitioned regression model, we have:
Bv Bv (
1
9(S))
Gr.
1 v v.) - 1 " Σ V. (s), (3)
Σ
1-1
1 3s - 33 ( _ G Σ s g g(S))) + G S. S.)
1
7 Σ S (3) - -Bv), (4)
where is labeled node size, S, is i-th sample of S, Σ. V B(V (()) (1).
E.= V.T.- E(V"S)) (1) and (1) is the error which is negligible. Ideally, By By =0 indicates that there is no bias between the estimated and the real parameter. However, if ( + or VEVVVTTT (S)) # 0 in Eq. B By will be biased, leading to the biased estimation on A3 in Eq. as well. Since the correlation between V and S (or s(S) might shift in test phase, the biased parameters learned in training set is not the optimal parameters for predicting testing nodes. Therefore, to increase the stability of prediction, we need to unbiasedly estimate the parameters of By by removing the correlation between V and S (or g (S) on training graph, making E(V*s) 0 or E(V" ((S) = O. Note that -.= S ((,)) in Eq. (4) can also cause estimation bias, but the relation between S and g(S) is stable across environments, which do not influence the stability to some extent.
3 PROPOSED MODEL
3.1 REVISITING ON VARIABLE DECORRELATION IN CAUSAL VIEW
To decorrelate and S (or (S)), we should decorrelate the output variables of A,0,) Kuang
al. 2020). They propose a Variable Decorrelation (VD) term with sample reweighting technıque to eliminate the correlation between each variable pair, which the sample weights are learned by jointly minimizing the moment discrepancy between each variable pair:
LVD(H) Σ IIHAAAHHHH H.wwnn w/nl11 J=1
(5)
where H E "XP means the variables needed be decorrelated, H is j-th variable of H. H. H H, y means all the remaining variables by setting the value of j-th variable in H as zero, w E R R are sample weights, Σn W; n and Aw = diag (w.. '",, w,.) is the corresponding diagonal matrix. As we can see, (H) can be reformulated as E, |I - H'/w/n- H. and it aims to let B( E(HH))((H,) for each variable pair j and k. LVD(H) decorrelates all
4

---

Under review as a conference paper at ICLR 2021
the variable pairs equally. However, decorrelating all the variables requires sufficient samples Kuang eet al. (2020), i.c., n + 0o, which hard to be satisfied, especially in the sumerviseee setting. In this scenario, cannot guarantee Lv O. Therefore the key challenge is how to remove the correlation influencing the unbiased estimation most when LV )) * O.
Inspired by confounding balancing technique in observational studies (Hainmueller, 2012 we revisit the variable decorrelation regularizer in causal view and show how to differentiate each variable pair. Confounding balancing techniques are often used for causal effect estimation of treatment T. where the distributions of confounders X are different between treated (T = 1) and control (T = 0) groups because of non-random treatment assignment. One could balance the distribution of confounders between treatment and control groups to unbiased estimate causal treatment effects ( Yao et al. 2020). Most balancing approaches exploit moments to characterize distributions, and balance them by adjusting sample weights w as follows: w = arg min |I Σ X; EeT,-o w; X,112
w After balancing, the treatment T' and confounders tend to be independent.
Given one targeted variable j. under the variables only have linear relation assumption relataion term, LVD, = || H. H Hfjw/n H."jw/nn (0--w/rll/5 is to make H.; independent of H.-j. which same as the confounding balancing term making treatment and confounders independent. Thereby, LVD, can also be viewed as confounding balancing term, where H, is treatment and H is confounders, illustrated in Fig. 2(a). Hence, our target can be explained as unbiasedly estimate causal effect of each variable which is invariant across training and test set. As different variable may contribute unequally to the confounding bias, it is necessary differentiate the confounders. The target of differentiating confounders exactly matches our target that removes the correlation of variables influencing the unbiased estimation most.
a its decor-
3.2 DIFFERETIATED VARIABLE DECORRELATION
Considering the continuous treatment, the causal effect of treatment can be measured by Marginal Treatment Effect Function (MTEF) (Kreif et al. 2015). and defined as: MTEF - where Y(()) represents the potential outcome of sample i with treatment status T E(-) refers the expectation function, and At denotes the increasing level of treatment. With the sample weights w decorrelating treatment and confounders, we can estimate the MTEF by:
Ar
EnTTEr Y,(t) -j W Y, At)
MTEF
A
Next we theoretically analyze how to differentiate confounders' weights with following theorem.
Theorem 1. In observational studies, different confounders make unequal confounding bias on Marginal Treatment Effect Function (MTEF) with their own weights, and the weights can be learned via regressing outcome Y on confounders X and treatment variable T.
We prove Theorem with the following assumption:
Assumption 3 (Linearity). The regression of outcome Y on confounders X and treatment variable T linear, that is Y Ekte = ag,x
+ a,T + c E, where a₁ is the linear coefficient.
Under Assumption we can write estimator of MTEF as:
MTEF EET Wi Yi(t) Σ -5: W Ytst- At)
Al
EiTTer W; X E Wj X,k
MTEF En.. kee an
+ d(E),
At
where MTEF is the ground truth, de) means the noise term, and ((E) = 0 with Gaussian noise. The detailed derivation can be found in Appendix A To reduce the bias of MTEF, we need
E -.---,-E,,,a at w.w W ). where E - X,,
regulate the term Σter an.
At
At
Nonlinnar relation hetween variables can he incorporated by considering high-order moments in Eq.
5

---

Under review as a conference paper at ICLR 2021
Aggreppll
Ingut
Diffocentiated confounder
Reviight
Neigtterr nodes
graph
Diflerattaed vedgits
Sample wiiightt
foew
(a) Decorrelation in Causal View
GNN-DVD Framework
Figure 2: (a) Diagram of decorrelating node embedding with confounding balance. H (K-1) is the node embedding to be decorrelated. T is the treatment, corresponding one target variable in ((K-1), X is the confounders, corresponding to the remaining variables of the target variable in H(K-)) Y is the outcome, corresponding to labels. (b) The framework of GNN-DVD. The same color in the two figures represents the same kind of variable.
means the difference of the k-th confounder between treated and control samples. The parameter ag represents the confounding bias weight of the k-th confounder, and it is the coefficient of X. Moreover, because target to learn the weight of each variable pair, i.e., between treatment and each confounder, we need to learn the weight on of treatment that is the coefficient T. Hence, the confounder weights and treatment weight can be learned from the regression of observed outcome Y on confounders X and treatment T under Linearity assumption.
Due to the connection between treatment effect estimation with variable decorrelation analyzed in Section 3.1, we utilize Theorem I to reweight the variable weight in variable decorrelation term. GNNs, the confounders X should be H.-, and treatment is H.j-
When apply the Theorem where the embedding H is learned by (X, A; (gg) in Eq. 2 And the variable weights a could be computed from the regression coefficients for H, hence is equal 3 in Eq. (2). Then the Differentiated Variable Decorrelation (DVD) term can be formulated as follows:
min (HV Σ (aT abs(HH) Aw AWWH -3/n H w///nn H ww/n))
X Σ i= w/ X2( E w; s.l.w 0
where abs(-) means the element-wise absolute value operation, preventing positive and negative values from eliminating. Term A1 E w² is added to reduce the variance of sample weights to achieve stability, and the formula 2₂ En w, w) avoids all the sample weights to be 0. The term z constrains each sample weight to be non-negative. After variable reweighting, the weighted w/nnnn-wiHHHHH H / and the weight for variable pair and & would be aja hence it considers both the weights of treatment and confounder. We prove the uniqueness property of w in Appendix B as follows:
n
decorrelation term Eq. (8) can rewritten as Σjss // H//
2
Theorem 2 (Uniqueness). If Xin p² + Az, p² >>> max(An M X2). |H c and |aæl c some
constant c, the solution w E (w |w,l s c} to minimize Eq. (8) is unique.
3.3 DEBIASED GNN FRAMEWORK
In this section, we describe the framework of Debiased GNN that incorporates DVD/VD term with GNNs in seamless way. As analyzed in Section 2.2 decorrelating Åo(Á Axw(") could make GCN stable. However, most GNNs follow a layer-by- bayer stacking structure, and the output embedding of each layer more easy to obtain in implementing. Since Ar ( Axw(") is the aggregation of

---

Under review as a conference paper at ICLR 2021
the first layer embedding a (AXW(()), decorrelating these variables may lack the flexibility that incorporates DVD/VD term with other GNN structure. Fortunately, we have the following theorem to identify more flexible way to combine variable decorrelation with GNNs.
Theorem 3. Given p pairwise uncorrelated variables Z = (Z, Zz. 2p), tion operator A, the variables ofY Y AZ are still pairwise uncorrelated.
with linear aggrega-
Proof can be found in Appendix C The theorem indicates that if the variables of embeddings Z are uncorrelated, after any form of linear neighborhood aggregation Å, e.g., average, attention sum, the variables of transformed embeddings Y would be also uncorrelated. Therefore, decorrelating o (AXW(() can also reduce the estimation bias. For K layers of GNN, can directly decorrelate the output of (K- - -- layer, i.e., (Axwo) ......((-3))) for a K layers of GCN.
The previous analysis finds flexible way to incorporate DVD/VD term with GNNs, however, recall that we analyze GNNs based on the least squares loss, and most existing GNNs are designed for classification. Therefore, in the following, we analyze that the previous conclusions in classification. We consider the cases that softmax layer is used as the output layer of GNNs and loss is the cross-entropy error function. We use the Newton- Rarioonnn update rule (Bishop 2006) to bridge the gap between linear regression and multi-clas multi-clasiificatinn. According to the Newton- Raphson update rule, the update formula for transformation matrix ((KK1), of the last layer of GCN can be derived:
still applicable
.f ((ew)) = w (H THTREE RH) 'H (HW (ok))
Y)
(H *(""HH (("RRH)"'RR " RHH 3 - H" (HW - ,))}= "HHR)""HH R2,
where R& En= H., W. (old) (1g H ( is a weighing matrix and I& is the element of (old) -R (Y, H) is an effective target value. Eq. (9) takes
the identity matrix, and HW oj the form of set of normal equations for weighted least-squares problem. As the weighing matrix R is not constant but depends on the parameter vector w(ald) we must apply the normal equations iteratively. Each iteration uses the last iteration weight vector w to compute a revised weighing
matrix R. and regresses the target value z with Hw Therefore, the variable decorrelation can also be applied to the GNNs with softmax classifier to reduce the estimation bias each iteration.
Figure b) is the framework of GNN-DVD, and we input the labeled nodes' embeddings H (K-) into the regularizer LDVD (H As GCN has the formula softmar(Án (K w
the variable weights of H (K1) used for differentiating LDV (F)((((H())) can be computed from
Var( (K-1) axis 1), where V 1) refers to calculating the variance of each row of some matrix and reflects each variable's weight for classification which is similar to the regression coefficients. Note that when incorporating VD term with GNNs, we do not need compute the variable weights. Then the sample weights w learned by DVD term have the ability to remove the correlation
in H (K11) We propose to use this sample weights to reweight softmax loss:
min La = Σ w. w.-winn (r.-In(((H)))) Y,). (E)2
(10)
where q(-) is the softmax function, V', is the set of labeled node indices and 0 is the set of parameters of GCN, The complexity analysis as well as the optimization of whole algorithm are summarized in
Appendix D
4 EXPERIMENTS
Datasets Here, we validate the effectiveness of our method on node classification with two kinds of selection biased data, i.e., label selection bias and small sample selection bias. For label selection bias, empoly three widely used graph datasets: Cora, Citeseer and Pubmed (Sen et al. 2008). As in Section 2.T, we make the inductive setting for each graph and get three biased degrees for each graph. For small sample selection bias, we conduct the experiments NELL dataset (Carlson)
7

---

Under review as a conference paper at ICLR 2021
Table I: Performance of three citation networks. The '** indicates the best results of the baselines.
Best results of all methods are indicated in bold. '% gain over GCN/GAT" means the improvement percent of GCN/GAT-DVD against GCN/GAT, respectively.
Method
Cora
Gieseer
Pubmed Medium
Light
Mediam
Heavy
Light
Medium
Hewvy
Light
Heavy
MLP
0.5621
0.5197
0.5087
0,4552
0.3757
0,3893
0.6852
0.5620
0.6378
Planetoid Yang et al. 2016
0.5890
0.5240
0.5180
0.5160
0,5140
0.4880
0.7160
0.6770
0.6680
Chebyshev
Dellemardd
0.7116
0.7006
0.6809
0.6542
0.6732
SGC Wa el a
2019
0.7800
0.7800
0.7530
0.6780
0.67300
0.6200
0.7880
0.7560
0.6800
APPNP
(Klggerr
2019
0.7913
0.7689
0.7629
0.6478
0,6052
0.7639
0.7369
0.6622
GNM-GCN Zlvu et al
2019
0.7425
0.7531
0.7196
0.5793
0.5717
0.5125
0.7552
0.7381
0.7072
GNM GAT
Zhou
0.7875
0.7638
0.7404
0.6524
0.6487
0.5865
0.7438
0.7568
0.6891
GCN (Kipl Weeling 2016
0.7851
0.7775
0.7412
U.6786
0.3952
0,3551
0.7673
0.7545
0.7247
UCN-VD
0.7951
0.7855
0.7522
0.6844
0.6676
0.6408
0.7727
0.7729
0.7399
GCN-DVD
0.7959
0.7555
0.6908
0.7746
0.7542
36 guin over GCN
1.38%
1.41%
1.79%
188%
14.2%
17.0%
0.89%
2.67%
4.07%
Voličković et all.p12122 2017
8.8
0.8019
0.7578
71333
0.6475
0.7665
0.7579
0,7068
UAI-VD
0.8146
O 1.8079
0.7708
0.7149
0.6833
0.6611
0,7783
0.7689
0.7149
GAT-DVD
0.8179
0.8119
0.7694
0.7172
0.6825
0.6627
0.7788
0,7723
0.7210
guin over
1.39%
1.26%
1.53%
1.97%
2.12%
1.6%
1.9%
2.0%
et al. 2010) that each class only has one labeled node for training. Due to the large scale of this dataset, the test nodes are easily to have distribution shift from training nodes. The details of the datasets and experimental setup are given in Appendix E
One can download codes and datasets for
all experiments from the supplementary material.
Under our proposed framework, we incorporate the VD/DVD term with GCN and GAT called GCN-VD/DVD and GAD-V (details in Appendix (.. and thus GCN and GAT are two basic baselines. We compare with GNM-GCN/GAT (Zhou et al., (019) that considers the label selection bias in transductive setting. Moreover, several state-of the-art art GNNs are included: Chebyshev filter (Kipf & Welling 2016). SGC (Wu et al. 2019) and APPNP (Klicpera et al. 2019). Additionally, we compare with Planetoid (Yang et al. 2016) and MLP trained on the labeled nodes.
Baselines
Results on Label Selection Bias Dataset The results are given in Table I and we have the following observations. First, the proposed models (i.c., GCN/GAT with VD/DVD terms) always achieve the best performances in most cases, which well demonstrates that the effectiveness of our proposed debiased GNN framework. Second, comparing with base models, our proposed models all achieve up to 17.0% performance improvements, and gain larger improvements under heavier bias scenarios. Since the major difference between our model with base models is the VD/DVD regularizer, we can safely attribute the significant improvements the effective decorrelation term and its seamless joint with GNN models. Moreover, GCN/GAT-DVD achieve better results that GCN/GAT- VD in most cases. validates the importance and effectiveness of differentiating variables' weights in semi-supervisee setting. Additional experimental results about the sample weight analysis and parameter sensitivity analysis can found in Appendix G
Results on Small Sample Selection Bias Dataset As NELL is large-scale graph, we cannot run GAT on a single GPU with 16GB memory. We only perform GCN- VDDDVD and compare with representative methods which can perform on this dataset. The results are shown in Table 2 First, GCN-VD/DVD achieve significant improvements over GCN. It indicates that selection bias could be induced by a small number of labeled nodes and proposed method can relieve the estimation bias. Moreover, GCN-DVD further improves GCN-VI VD with a large margin. It further validates that decorrelating all the variable pairs equally is suboptimal, and our differentiated strategy is effective when labeled nodes are scarce. The reason that GNM-GCN fails is the GNM relies on the accuracy of the IPW estimator that predicts the probability of a node to be selected, however, in this dataset, the ratio of positive and negative samples are extremely unbalanced influencing the performance of IPW.
Table 2: Performance of NELL
Dataset MLP
Planetoid
SGC
GNM-GCN
GCN
GCN-VD GCN-DVD
NELL
0.2385
0.3901
0.4128
0.1589
0.4416
0.4652 0.4734
8

---

Under review as a conference paper at ICLR 2021
5 RELATED WORKS
In the past few years, Graph Neural Networks (GNNs) Scarseelli et al., 2008 Kipf & Welling 2016
Veličković al. 2017 Xu et 2019 Klicpera al. 2019) have become the major technology to capture patterns encoded in the graph due to its powerful representation capacity. Although the current GNNs have achieved great success, when applied inductive setting, they assume that training nodes and test nodes follow the same distribution. However, this assumption does not always hold in real applications. GNM (Zhou et al. 2019) first pays attention on the label selection problem on graph learning, and it learns a IPW estimator to estimate the probability of each node to be selected and uses this probability reweight the labeled nodes. However, heavily relies on the accuracy of IPW estimator, which depends on the label assignment distribution of whole graph, hence it is more suitable for transductive setting.
To enhance the stability in unseen varied distributions, some literatures (Shen et al. 2020b Kuang et al. 2020) have revealed the connection between correlation and prediction stability under model misspecification. However, these methods are built the simple regressions, but GNNs have more complex structure and properties needed to be considered. We also notice that Shen et al. (2020a) propose differentiated variable decorrelation term for linear regression. However, this decorrelation term requires multiple environment with different correlations between stable variable and unstable variable available in the training stage while our method do not require.
CONCLUSION
In this paper, we investigate general and practical problem: learning GNNs with agnostic selection bias. The selection bias will inevitably cause the GNNs to learn the biased correlation between aggregation mode and class label and make the prediction unstable. We then propose novel differentiated decorrelated GNN, which combines the debiasing technique with GNNs in unified framework. Extensive experiments well demonstrate the effectiveness and flexibility of GNN-DVD.

---

Under review as a conference paper at ICLR 2021
REFERENCES
Christopher M Bishop. Pattern recognition and machine learning. springer, 2006.
Andrew Carlson, Justin Betteridge, Bryan Kisiel, Burr Settles, Estevam R Hruschka, and Tom M Mitchell. Toward architecture for never-ending language learning. In AAAI, 2010.
Michael Cogswell, Faruk Ahmed, Ross Girshick, Larry Zitnick, and Dhruv Batra. Reducing overfit- ting in deep networks by decorrelating representations. In ICLR, 2016.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst.
graphs with fast localized spectral filtering. In NeurIPS, Convolutional neural networks
3844-3852, 2016.
Jens Hainmueller. Entropy balancing for causal effects: A multivariate reweighting method to produce balanced samples in observational studies. Political analysis, pp. 25 46, 2012.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In NeurIPS, pp. 1024-1034, 2017.
Thomas Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In ICLR, 2016.
Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. In ICLR, 2019.
Noémi Kreif, Richard Grieve, Iván Díaz, and David Harrison. Evaluation of the effect of a continuous treatment: a machine learning approach with an application to treatment for traumatic brain injury. Health economics, 24(9):1213-122) 2015.
Kun Kuang, Ruoxuan Xiong, Peng Cui, Susan Athey, and Bo Li. Stable prediction with model misspecificattion and agnostic distribution shift. In AAAI, 2020.
Yuji Nakatsukasa. Absolute and relative weyl theorems for generalized eigenvalue problems. Linear Algebra and its Applications, 432(1)):42-244, 2010.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE Transactions on Neural Networks, 20(1):61-80, 2008
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad. Collective classification in network data. Al magazine, 29(3):93-93, 2008.
Zheyan Shen, Peng Cui, Jiashuo Liu, Tong Zhang, Bo Li, and Zhitang Chen. Stable learning via differentiated variable decorrelation. In KDD,, pp. 2185 8193,, 2020a.
Zheyan Shen, Peng Cui, Tong Zhang, and Kun Kuang. Stable learning via sample reweighting. In AAAI, pp. 5692-5699, 2020b.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. In ICLR, 2017.
Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Simplify- ing graph convolutional networks. In ICML, pp. 6861-6871. PMLR, 2019.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful graph neural networks? ICLR, 2019. URL htl.ittts///peereviiee net. http://wwweeee//eeeeeeeee www.:eeeeeorrrrreeeeeaaaaa.....
Zhilin Yang, William Cohen, and Ruslan Salakhutdinov. Revisiting semi-supervised learning with graph embeddings. In ICML, 2016.
Liuyi Yao, Zhixuan Chu, Sheng Li, Yaliang Li, Jing Gao, and Aidong Zhang. A survey on causal inference. arXiv preprint arXiv:2002.00 027700 2020.
Bianca Zadrozny. Learning and evaluating classifiers under sample selection bias. In ICML, pp. 114, 2004.
Fan Zhou, Tengfei Li, Haibo Zhou, Hongtu Zhu, and Ye Jieping. Graph-based semi-supervised learning with non-ignorable non-response. In NeurlPS, pp. 7015-7025, 2019.
10

---

Under review as a conference paper at ICLR 2021
A DERIVATION OF MTEF
EiTT We Yi(t) - Ei:T, Wy Y,(t At)
MTEF
At
L We (Ehee i + +aa++c+e) &t Wy (Ebre AxX5t + + - 21) + +c+
Al
Wyaltt EVTTOr Wjatt - Wi At)
Al
(ETT W; Eker Xi
-5 L w Enst 04 Xik)
+(E))
At
E Wi
Xik
LL W, X
MTEF + Σ
a4
d(E),
Al
(11)
where Eir, W,a,t EpTrec-ai (t-rtt)At)
is the ground truth of MTEF, Φ(E) means the noise term,
At and ())) = O with Gaussian noise.
B PROOF OF THEOREM 2
arg min
(a /n
d1
Σ
n
w; + A2
2
1 n
W w.-1) 1)²
i=1
i=1
(12)
Proof For simplicity, we denote &1 "
(a abs(H , Aw -3/n// H / (ff5/n-H"/w//i H/n)//n))²
C2 1 the Hessian matrix of F( (w). denoted as H., to prove the uniqueness of the optimal solution w, as follows:
n Ei 2
L3 @ E W; - 1)² and F(w) C, X X AzL2. We first calculate
8cc, 8L, + Aa
8c
H. Ow + A
Ow
Ow
For the term L1, rewrite it as:
C
Σ
a
a
H H.W, w. - ( Σ H w:)
H H(,:w))
j+k
Σ
a aiail
2
H H.
2
H H., 1 Σ H w:) 1 Σ H,w.,))
j*k
((
H wi)
nt > a=1
H. H.w w:))3
i=l
And
when |
S c, for any variable j and k. and |wal c. we have
0²
i- H H. ) O de ( Σ. H,, Σi_ H,,,,)) o( and
Ow
Em= H.
( Em H (= Σx Hw,))) = O( Then with |aæl s c,
we have a; 2 a
Σ s=1 H H,H,,, ( E s=1 H H,, Σx H,,,,))² 0 ) L is
sum of ppp 1) such terms. Then we have
0'c dw = 0 p
n?
With some algebras, we can also have
82Lr 1 I.
dw?
n

---

Under review as a conference paper at ICLR 2021
&Ls
1
11",
dw?
n²
thus,
\1
2
\ I o 2 + )22
H 0( n
1
11
n²
n²
Therefore, 21 > equivalent to A > p² +22
H. is an almost diagonal matrix. Hence, H is positive definite Nakatsukasa 2010). Then the function F(w) is convex on C = {w |w,] s c}. and has unique optimal solution W.
X2.
Moreover, because L1 is our major decorrelation term, we hope L1 to dominate the terms D2 and X2C3. On C, have L1 O(1), L2 = O(1, and ( n Σ H.y.H,,,, ( Ei_ H,y W Σ H,,:;;)) O(1). Thus &1 = O(p²). When p² >> max(A1, X2). L will dominate the regularization terms L2 and L3.
C PROOF OF THEOREM 3
Let Z (Z, Zz, Z,} be p pairwise uncorrelated variables. VZ, Z, E Z, (Z,)) -,,", m
(1)
and (Z (1) - ( are simple random samples drawn from Z; and Zj respectively, and have
same distribution with Z, and Zj. Given a linear aggregation matrix Å (a.y), Vs, (1,2, 21,2,.... ...,.)))) n),
let x! Eh= aa z (k) and x(()) Ei= an and we have following derivation:
Cov(Y x Cov( Σ ask Z
(A)
aul (1))
a. Cov(Z ) Σ
askantdij
k= 1=1
where 6, when # j. otherwise 6, = Therefore, when i j. we have Cov(Y, r (1) and Cov Y. Y,) O. Extended the conclusion multiple variable, Y (Y,, Ya, my Y pairwise uncorrelated. Proof completes.
=
D PSEUDOCODE OF GNN-DVD
Algorithm 1: GNN-DVD Algorithm
Input
Training graph Gerain = (A, X, Y), and indices of labeled nodes Vi: Max
iteration:mazlleer
Output
:GNN parameter 0 and sample weights w
Initialization
Let
w and initialize sample weights w with 1; Initialize GNN's parameters 0 with random uniform distribution; Iteration - 0
while not converged or < marIter do
Optimize g(t) to minimize Lgi Calculate variable weights (1) from (K-11),
Optimize (t) to minimize LDVD (
end
Return:
f and w = ww
To optimize our GNN-DVD algorithm, we propose iterative method. Firstly, let O to ensure non- noga-eiativity of w and initialize sample weight w; for each sample and GNN's parameters with random uniform distribution. Once the initial values given, in each iteration,
12

---

Under review as a conference paper at ICLR 2021
fix the sample weights and update the GNN's parameters by LG with gradient descent, then compute the confounder weights a from the linear transform matrix w(K-1), With a and fixing the GNN's parameters 0, we update the sample weights with gradient descent to minimize DDVD (OVD(((K: (H) We iteratively update the sample weights w and GNN's parameters until Lg converges.
Complexity Analysis Compared with base model (e.g.. GCN and GAT), the mainly incremental time cost is the complexity from DVD term. The complexity of DVD term (mp'') ). where n is the number of labeled nodes and p is the dimension of embedding. And it is quite smaller than the base model (e.g., the complexity of GCN is linear to the number of edges).
E DATASET DESCRIPTION AND EXPERIMENTAL SETUP
E.1 DATASET DESCRIPTION
Table 3: Dataset statistics
Dataset
Type
Nodes
Edges
Classes
Features
Bias degree (c)
Bius type
Cora
Citation network
2,708
5,429
1,433
0.7/0.8/0.9
Label selection bias
Citeseer
Citation network
3,327
4,732
6
3,703
0.7/0.8/0.9
Label selection bins
Puhmed
Citaion network
19,717
0.700.8/0.9
Label selection bias
NELL
Knowledge graph
65.755
266.144
210
5,414
One labeled node per class
Small sample selection bias
Some statisties of datasets used in paper are presented in Table including the number of nodes, the number of edges, the number of classes, the number of features, the bias degree e and bias type. For three citation networks, we conduct the biased labeled node selection process to get three degrees of datasets for each dataset to validate the effect of label selection bias, in which each class in each dataset contains 20 labeled nodes in training set and the validation set and test set are same as Yang itt al. 2016). For NELL, because it only has a single labeled node per class in training set, the training nodes are hard to cover all the neighborhood distribution happened in the test Hence, we use this dataset to validate the effectiveness of our method on the extreme small labeled nodes size bias. The data splits are also same as Yang al. (2016). A description of each of dataset given follows:
. Cora (Sen et al. 2008 is citation network of Machine Learning papers that collected from 7 classes: ( Theory, Case Based, Reinforcement Learning, Genetic Algorithms, Neural Networks, Probabilistic Methods, Rule Learning ). Nodes represent papers, edges refer to the citation relationship. and features are bag-of-words vectors for each paper.
Citeseer (Sen et al., 2008) a citation network of Machine Learning papers that collected from 6 classes: Agents, Artificial Intelligence, Database, Information Retrieval, Machine Learning, Human Computer Interaction J. Nodes represent papers, edges refer to the citation relationship, and features are bag-of-wordss vectors for each paper.
Pubmed (Sen et al.) 2008) is a citation network from the PubMed database, which contains set of articles (Nodes) related diabetes and the citation relationship among them. The node features are bag-of-words vectors, and the node label are the diabetes type researched in the articles.
NELL Carlson et al. (2010) is dataset extracted from the knowledge graph, which is set of entities connected with directed, labeled edges (relations). Our pre-processing scheme is same as Yang et al. (2016), where each entity pair (e,, e2) is assigned with separate relation nodes r and F2 as (e).r) and T2). We use text bag-of Wag-of-worde representation as feature vector of the entities.
E.2 EXPERIMENTAL SETUP
As the Section 2. has described, for all datasets, to simulate the agnostic selection bias scenario, we first follow the inductive setting in Wu et al. (2019) that masks the validation and test nodes in the training phase and validation and test with whole graph so that the test nodes will be agnostic. For GCN and GAT, we utilize the same two-layer architecture as their original paper (Kipf & Welling 2016. Veličkovié et al. 2017). We use the following sets of hyperparameters for GCN on Cora,
13

---

Under review as a conference paper at ICLR 2021
Citeseer, Pubmed: 0.5 (dropout rate). 5 100* (L. regularization) and 32 (numbder of hidden units); and for NELL: 0.1 (dropout rate), 1- 10 (1.2 regularization) and 64 (number of hidden units). For GAT on Cora, Citeseer, we use: 8 (first layer attention heads), 8 (features each head), (second layer attention head), 0.6 (dropout), 0.0005 (L2 regularization); and for Pubmed: 8 (second layer attention head), 0.001 (L2 regularization), other parameters are same with Cora and Citeseer. To fair comparison, the GNN part of our model uses the same architecture and base model and we grid search λ₁ and 2 from {0.01, 0.1, 1, 10, 1003. For other baselines, we use the optimal papper-paameetes in literatures on each dataset. For all the experiments, we run 10 times with different random seed and report its average Accuracy results.
with
F EXTEND TO GAT
We can easily incorporate VD/DVD term to other GNNs. We combine them with GAT and more extensions leave as future work. GAT utilizes attention mechanism to aggregate neighbor information. It also follows the linear aggregation and transformation steps. Similar with GCN, the hidden embedding (K is the input of VD/DVD term, and the variable weights a are calculated from the transformation matrix ((K-1) and the sample weights w are used to reweight the softmax loss.
Note that original paper utilizes same transformation matrix (KK11) for transforming embedding and learning attention values. Because a means the importance of each variable for classification, and it should be computed from transformation matrix (KK- for transforming emhedding, hence we use separate matrix for transforming embedding and learning attention values respectively. This modification does not change the performance of GAT in experiments.
G ADDITIONAL EXPERIMENTS
G.1 SAMPLE WEIGIIT ANALYSIS
Here we analyze the effect of sample weights w in our model. We compute the amount of correlation
in the labeled nodes' embeddings ( learned by standard GCN and the weighted embeddings of
the same layer learned by GCN-DVD. Note that, the weights are the last iteration of sample weights
of GCN-DVD. Following Cogswell et al. (2016), the amount of correlation of GCN and GCN-DVD
are measured by Frobenius norm of cross corvairace matrix computed from vectors of H K-1)
and weighted (K1) respectively. Figure shows the amount of correlation in unweighted and weight embeddings, and we can observe that the embeddings' correlation in all datasets are reduced, demonstrating that the weights learned by GCN-DVD can reduce the correlations between embedded variables. Moreover, one can observe that it is hard to reduce the correlation to zero. Therefore, the necessity of differentiating variables' weights will be further validated.
0.1
CON
OCN
5.15
OCH
03.04
1.09
56a4
0.22
0.000
1.00
0.2
Driwww
(a) Cora
(b) Citeseer
Pubmed
Figure 3: Embedding correlation analysis unweighted and weighted GCN.
G.2 PARAMETER SENSITIVITY
We study the sensitiveness of parameters and report the results of GCN-DVD on three citation networks in Fig. 4 The experimental results show that GCN-DVD is relatively stable A and X2 with wide ranges in most cases, indicating the robustness of our model.
14

---

Under review as a conference paper at ICLR 2021
FECUIRT
2.A
041
0.1
3.0
0.01
(a) Light
(b) Medium
(c) Heavy
Figure 4: Accuracy of GCN-DVD with different a and X2 on different biased Cora datasets.
94
0.3
0.1
4
4
(a) Light
(b) Medium
(c) Heavy
Figure 5: Accuracy of GCN-DVD with different A and X2 on different biased Citeseer datasets.
ACCUNEY
ACCLINY
022
0.7
100
10
831
0.22
12
1.11
4
(a) Light
(b) Medium
(c) Heavy
Figure 6: Accuracy of GCN-DVD with different A and X on different biased Pubmed datasets.
15


Reviews:
[{"review_id": "WBiU_ePJDWU", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 4, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "#### Goal\n\n- 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.\n\n- I like the experimental investigation (since I think the problem is very relevant). I am skeptical about the method and the results.\n\n#### Quality\n\n- I have many doubts about the validity of the claims. \n\n- 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.\n\n- “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?\n\n- 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? \n\n- “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.\n\n- “Hence the parameters of both stable variables and unstable variables would be biased.” This is a strong claim that requires a formal proof.\n\n- 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. \n\n- 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. \n\n- 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.\n\n#### Clarity\n\n- 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.\n\n- 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?\n\n- Can we precisely define the assumed covariate shift between train and test? No method can work for any covariate shift.\n\nTypos & Overall fixes:\n\n- “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”\n\n#### Originality\n\n- Removing GNN training sampling bias with counterfactual inference would be new.\n\n#### Significance\n\n- The task of removing GNN training sampling bias is very important.\n\n#### Pros\n\n- Important task.\n- Nice demonstration of the issues with biased training data.\n\n#### Cons\n\n- See “Quality”. I am unconvinced by the method.\n\n\n----\n\nAfter 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. \n\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "QcOPv6ZvrNE", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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. \nTo 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. \nThe 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. \n\nStrong points:\n1.\tThe 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.\n2.\tThe 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.\n3.\tThe 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.\n\nQuestion for rebuttal:\n1.\tIn 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?\n2.\tAlthough 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.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "KUYIGsCMNDA", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 2, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nPros:\n+ The studied problem is general and also practical for real-world applications.\n\nCons:\n+ 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.\n+ 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?\n+ 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.\n\nReference:\n[1] Stable Prediction with Model Misspecification and Agnostic Distribution Shift, AAAI 2020.", "extra_scores": {}, "extra_text": {}}, {"review_id": "IDzagb30jvZ", "reviewer": "AnonReviewer2", "summary": "", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\nThe 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.\n\nReasons for score: \nOverall, 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.\n\nStrong points:\n* The proposed regularizers are well motivated, theoretically supported and at the same time simple and easy to implement.\n* The causal view analysis of the proposed regularizers is insightful.\n* The regularized have a reasonably small computational complexity.\n\nWeak points:\n* 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.\n* 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).\n* 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).\n* 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. \n\nQuestion for the authors:\n1. How does the results change if we consider the average over a larger number (e.g. 10) of random validation/test splits?\n2. What is the performance of GCN/GAT-VD/DVD using uniformly sampled training nodes? Are there any trade-offs?\n3. 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)\n4. How well do the proposed methods perform in the transductive setting?\n5. 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?\n\nAdditional feedback that did not affect the decision:\n* 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).\n* 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.\n* 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.\n* Evaluating the effect of small sample selection bias on massive graphs from the Open Graph Benchmark (https://ogb.stanford.edu/) would be insightful. \n* 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.\n\n## After Rebuttal\nThank 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.\n\nReferences:\n1. Yang, Zhilin, William Cohen, and Ruslan Salakhudinov. \"Revisiting semi-supervised learning with graph embeddings.\"\n2. Shchur, Oleksandr, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. \"Pitfalls of graph neural network evaluation.\"\n3. Avrachenkov, Konstantin, Alexey Mishenin, Paulo Gonçalves, and Marina Sokol. \"Generalized optimization framework for graph-based semi-supervised learning.\"\n4. Zhu, Jiong, Ryan A. Rossi, Anup Rao, Tung Mai, Nedim Lipka, Nesreen K. Ahmed, and Danai Koutra. \"Graph Neural Networks with Heterophily.\"\n5. Zhu, Jiong, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. \"Generalizing graph neural networks beyond homophily.\"\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

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