Year: 2020

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.

heading: 1 INTRODUCTION
text: Graph Neural Networks (GNNs) are powerful deep learning algorithms on graphs with various applications (Scarselli et al., 2008; Kipf & Welling, 2016; Veličković et al., 2017; Hamilton et al., 2017). Existing GNNs mainly learn a node embedding through aggregating the features from its neighbors, and such message-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 are capable of learning the embeddings of new nodes and inferring their labels.
One basic requirement of GNNs making precise prediction on unseen test nodes is that the distribution of labeled training and test nodes is same, i.e., the structure and feature of labeled training and test nodes follow the similar pattern, so 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 to 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 ML 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 in 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 on unknown test data.
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.1). 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, we 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 to 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.

heading: 2 EFFECT OF LABEL SELECTION BIAS ON GNNS
text: In this section, we first formulate our target problem as follows: Problem 1 (Semi-supervised Learning on Graph with Agnostic Label Selection Bias). Given a training graph Gtrain = {Atrain,Xtrain,Ytrain}, where Atrain ∈ RN×N (N nodes) represents the adjacency matrix, Xtrain ∈ R N×D (D features) refers to the node features and Ytrain ∈ R n×C (n labeled nodes, C classes) refers to the available labels for training (n ≪ N ), the task is to learn a GNN gθ(⋅) with parameter θ to precisely predict the label of nodes on test graph Gtest = {Atest,Xtest,Ytest}, where distribution Ψ(Gtrain) ≠ Ψ(Gtest).

heading: 2.1 EXPERIMENTAL INVESTIGATION
text: We conduct an experimental investigation to examine whether the state-of-the-art GNNs are sensitive to the selection bias. The main idea is that we will perform two representative GNNs: GCN (Kipf
& Welling, 2016) and GAT (Veličković et al., 2017) on three widely used graph datasets: Cora, Citeseer, Pubmed (Sen et al., 2008) with different degrees of bias. If 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 et al. (2019) that masks the validation and test nodes as the training graph Gtrain 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 Gtrain. The selection variable e is introduced to control whether the node will be selected as labeled nodes, where e = 1 means selected and 0 otherwise. For node i, we compute its neighbor distribution ratio: ri = ∣{j∣j ∈ Ni, yj ≠ yi}∣/∣Ni∣, where Ni is neighborhood of node i in Gtrain and yj ≠ yi means the label of central node i is not the label of its neighborhood node j. And ri measures the difference between the label of central node i with the labels of its neighborhood. Then we average all the nodes’ r to get a threshold t. For each node, the probability to be selected is: P (ei = 1∣ri) = { ri ≥ t
1 − ri < t , where ∈ (0.5, 1) is used to control the degree of selection bias and the larger means heavier bias. We set as {0.7, 0.8, 0.9} to 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 1 is the results of GCN and GAT on 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.

heading: 2.2 THEORETICAL ANALYSIS
text: The above experiment empirically verifies the effect of selection bias on 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 = s,V = v) = E(Y∣S = s).
Under Assumption 1, the distribution shift between training set and test set is mainly induced by the variation in the joint distribution over (S, V), i.e., P(Strain,Vtrain) ≠ P(Stest,Vtest). However, there is an invariant relationship between stable variable S and outcome Y in both training and test environments, which can be expressed as P(Ytrain∣Strain) = P(Ytest∣Stest). Assumption 1 can be guaranteed by Y⊥V∣S. Thus, one can solve the stable prediction problem by developing a function f(⋅) based on S. However, one can hardly identify such variables in GNNs. 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 on the above assumptions, we formalize the label generation process as follows:
Y = f(X,A) + ε = G (X,A; θg)SβS + G (X,A; θg)V βV + g(G (X,A; θg)S) + ε, (1)
where G (X,A; θg) ∈ RN×p denotes an 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 G (X,A; θg) can be decomposed as stable variables G (X,A; θg)S ∈ RN×m and unstable variables G (X,A; θg)V ∈ R N×q (m + q = p), βS ∈ R m×1 and βV ∈ R q×1 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
of stable variables. According to Assumption 1, we know that coefficients of unstable variables G (X,A; θg)V are actually 0 (i.e., βV =0). For a classical GNN model with linear regressor, its prediction function can be formulated as:
Ŷ = Ĝ (X,A; θg)S β̂S + Ĝ (X,A; θg)V β̂V + ε. (2) Compared with Eq. (1), we can find that the parameters of GNN could be unbiasedly estimated if the nonlinear term g(G (X,A; θg)S) = 0, because the GNN model will have the same label generation mechanism as Eq. (1). 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. 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 Âσ(ÂXW(0))W(1), where Â is the normalized adjacency matrix, W is the transformation matrix at each layer and σ(⋅) is the Relu activation function. We decompose GCN as two parts: one is embedding learning part Âσ(ÂXW(0)), which can be decomposed as [ST,VT], corresponding to Ĝ (X,A; θg)S and Ĝ (X,A; θg)V in Eq. (2), and the other part is W(1), where the learned parameters can be decomposed as [β̃S , β̃V ], corresponding to [β̂S , β̂V ] in Eq. (2). We aim at minimizing the square loss: LGCN = ∑ni=1(STi β̃S +VTi β̃V −Yi)2. According to the derivation rule of partitioned regression model, we have:
β̃V − βV = ( 1 n
n
∑ i=1 V T i Vi)−1( 1 n
n
∑ i=1 V T i g(Si)) + ( 1 n
n
∑ i=1 V T i Vi)−1( 1 n
n
∑ i=1 V T i Si)(βS − β̃S), (3)
β̃S − βS = ( 1 n
n
∑ i=1 S T i Si)−1( 1 n
n
∑ i=1 S T i g(Si)) + ( 1 n
n
∑ i=1 S T i Si)−1( 1 n
n
∑ i=1 S T i Vi)(βV − β̃V ), (4)
where n is labeled node size, Si is i-th sample of S, 1 n ∑ni=1 VTi g(Si) = E(VTg(S)) + op(1), 1 n ∑ni=1 VTi Si = E(VTS) + op(1) and op(1) is the error which is negligible. Ideally, β̃V − βV = 0 indicates that there is no bias between the estimated and the real parameter. However, if E(VTS) ≠ 0 or E(VTg(S)) ≠ 0 in Eq. (3), β̃V will be biased, leading to the biased estimation on β̃S in Eq. (4) as well. Since the correlation between V and S (or g(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 β̃V by removing the correlation between V and S (or g(S)) on training graph, making E(VTS) = 0 or E(VTg(S)) = 0. Note that 1
n ∑ni=1 STi g(Si) 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.

heading: 3 PROPOSED MODEL

heading: 3.1 REVISITING ON VARIABLE DECORRELATION IN CAUSAL VIEW
text: To decorrelate V and S (or g(S)), we should decorrelate the output variables of Ĝ (X,A; θg) (Kuang et al., 2020). They propose a Variable Decorrelation (VD) term with sample reweighting technique to eliminate the correlation between each variable pair, in which the sample weights are learned by jointly minimizing the moment discrepancy between each variable pair:
LV D(H) = p
∑ j=1 ∣∣HT.jΛwH.−j/n −HT.jw/n ⋅HT.−jw/n∣∣22, (5)
where H ∈ Rn×p means the variables needed to be decorrelated, H.j is j-th variable of H, H.−j = H\H.j means all the remaining variables by setting the value of j-th variable in H as zero, w ∈ Rn×1 are sample weights, ∑ni=1 wi = n and Λw = diag(w1,⋯,wn) is the corresponding diagonal matrix. As we can see, LV D(H) can be reformulated as ∑j≠k ∣∣HT.jΛwH.k/n−HT.jw/n ⋅HT.kw/n∣∣22, and it aims to let E(HT.iH.j) = E(HT.i)E(H.j) for each variable pair j and k. LV D(H) decorrelates all
the variable pairs equally. However, decorrelating all the variables requires sufficient samples Kuang et al. (2020), i.e., n→∞, which is hard to be satisfied, especially in the semi-supervised setting. In this scenario, we cannot guarantee LV D(H) = 0. Therefore the key challenge is how to remove the correlation influencing the unbiased estimation most when LV D(H) ≠ 0. 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
w ∣∣∑i∶Ti=1 Xi −∑i∶Ti=0 wi ⋅Xi∣∣ 2 2.
After balancing, the treatment T and confounders X tend to be independent.
Given one targeted variable j, under the variables only have linear relation assumption1, its decorrelataion term, LV Dj = ∣∣H T .jΛwH.−j/n −HT.jw/n ⋅HT.−jw/n∣∣22, is to make H.j independent of H.−j , which is same as the confounding balancing term making treatment and confounders independent. Thereby, LV Dj can also be viewed as a confounding balancing term, where H.j is treatment and H.−j 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 to differentiate the confounders. The target of differentiating confounders exactly matches our target that removes the correlation of variables influencing the unbiased estimation most.

heading: 3.2 DIFFERETIATED VARIABLE DECORRELATION
text: 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 = E[Yi(t)]−E[Yi(t−∆t)]
∆t , where Yi(t) represents the potential outcome of sample i with treatment status
T = t, E(⋅) refers to the expectation function, and ∆t denotes the increasing level of treatment. With the sample weights w decorrelating treatment and confounders, we can estimate the MTEF by:
M̂TEF = ∑i∶Ti=twi ⋅ Yi(t) −∑j∶Tj=t−∆twj ⋅ Yj(t −∆t)
∆t . (6)
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 1 with the following assumption: Assumption 3 (Linearity). The regression of outcome Y on confounders X and treatment variable T is linear, that is Y = ∑k≠t αkX.k + αtT + c + ε, where αk ∈ α is the linear coefficient.
Under Assumption 3, we can write estimator of M̂TEF as:
M̂TEF = ∑i∶Ti=twi ⋅ Yi(t) −∑j∶Tj=t−∆twj ⋅ Yj(t −∆t)
∆t
=MTEF +∑ k≠t
αk( ∑i∶Ti=twi ⋅Xik −∑j∶Tj=t−∆twj ⋅Xjk
∆t ) + φ(ε),
(7)
where MTEF is the ground truth, φ(ε) means the noise term, and φ(ε) ≃ 0 with Gaussian noise. The detailed derivation can be found in Appendix A. To reduce the bias of M̂TEF , we need regulate the term ∑k≠t αk( ∑i∶Ti=t wi⋅Xik−∑j∶Tj=t−∆t wj ⋅Xjk ∆t ), where ∑i∶Ti=t wi⋅Xik−∑j∶Tj=t−∆t wj ⋅Xjk ∆t
1Nonlinear relation between variables can be incorporated by considering high-order moments in Eq. (5).
H
(K−1). X is the confounders, corresponding to the remaining variables of the target variable in H
(K−1). 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 αk represents the confounding bias weight of the k-th confounder, and it is the coefficient of X.k. Moreover, because our target is to learn the weight of each variable pair, i.e., between treatment and each confounder, we need to learn the weight αt of treatment that is the coefficient of 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 as analyzed in Section 3.1, we utilize Theorem 1 to reweight the variable weight in variable decorrelation term. When apply the Theorem 1 to GNNs, the confounders X should be H.−j and treatment is H.j , where the embedding H is learned by Ĝ (X,A; θg) in Eq. (2). And the variable weights α could be computed from the regression coefficients for H, hence α is equal to β̂ in Eq. (2). Then the Differentiated Variable Decorrelation (DVD) term can be formulated as follows:
min w
LDVD(H) =∑ p j=1 (αT ⋅ abs(HT.jΛwH.−j/n −HT.jw/n ⋅HT.−jw/n))2
+ λ1 n ∑ n i=1 w 2 i + λ2( 1 n∑ n i=1 wi − 1)2, s.t.w ⪰ 0
(8)
where abs(⋅) means the element-wise absolute value operation, preventing positive and negative values from eliminating. Term λ1
n ∑ni=1 w2i is added to reduce the variance of sample weights to
achieve stability, and the formula λ2( 1n ∑ n i=1 wi−1) 2 avoids all the sample weights to be 0. The term w ⪰ 0 constrains each sample weight to be non-negative. After variable reweighting, the weighted decorrelation term in Eq. (8) can be rewritten as ∑j≠k α2jα2k∣∣HT.jΛwH.k/n−HT.jw/n⋅HT.kw/n∣∣22, and the weight for variable pair j and k would be α2jα 2 k, hence it considers both the weights of treatment and confounder. We prove the uniqueness property of w in Appendix B, as follows:
Theorem 2 (Uniqueness). If λ1n≫ p 2+λ2, p 2 ≫ max(λ1, λ2), ∣Hi,j∣ ≤ c and ∣αi∣ ≤ c for some constant c, the solution ŵ ∈ {w ∶ ∣wi∣ ≤ c} to minimize Eq. (8) is unique.

heading: 3.3 DEBIASED GNN FRAMEWORK
text: In this section, we describe the framework of Debiased GNN that incorporates DVD/VD term with GNNs in a seamless way. As analyzed in Section 2.2, decorrelating Âσ(ÂXW(0)) could make GCN stable. However, most GNNs follow a layer-by-layer stacking structure, and the output embedding of each layer is more easy to obtain in implementing. Since Âσ(ÂXW(0)) is the aggregation of
the first layer embedding σ(ÂXW(0)), decorrelating these variables may lack the flexibility that incorporates DVD/VD term with other GNN structure. Fortunately, we have the following theorem to identify a more flexible way to combine variable decorrelation with GNNs. Theorem 3. Given p pairwise uncorrelated variables Z = (Z1,Z2,⋯,Zp), with a linear aggregation operator Â, the variables of Y = ÂZ are still pairwise uncorrelated.
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 Â, e.g., average, attention or sum, the variables of transformed embeddings Y would be also uncorrelated. Therefore, decorrelating σ(ÂXW(0)) can also reduce the estimation bias. For aK layers of GNN, we can directly decorrelate the output of (K − 1)-th layer, i.e., σ(Â⋯σ(ÂXW(0))⋯W(K−2)) for a K layers of GCN. The previous analysis finds a 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 are still applicable 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-Raphson update rule (Bishop, 2006) to bridge the gap between linear regression and multi-classification. According to the Newton-Raphson update rule, the update formula for transformation matrix W(K−1) of the last layer of GCN can be derived:
W (new) .j =W (old) .j − (H T RH)−1HT(HW(old).j −Y.j)
= (HTRH)−1{HTRHW(old).j −H T(HW(old).j −Y.j)} = (H T RH)−1HTRz,
(9)
where Rkj = −∑Nn=1 HnW (old) .k (Ikj −HnW (old) .j ) is a weighing matrix and Ikj is the element of the identity matrix, and z = HW(old).j −R −1(Y.j −W.jH) is an effective target value. Eq. (9) takes the form of a set of normal equations for a weighted least-squares problem. As the weighing matrix R is not constant but depends on the parameter vector W(old).j , we must apply the normal equations iteratively. Each iteration uses the last iteration weight vector W(old).j to compute a revised weighing matrix R and regresses the target value z with HW(new).j . Therefore, the variable decorrelation can also be applied to the GNNs with softmax classifier to reduce the estimation bias in each iteration.
Figure 2(b) is the framework of GNN-DVD, and we input the labeled nodes’ embeddings H̃(K−1) into the regularizer LDVD(H̃(K−1)). As GCN has the formula softmax(ÂH(K−1)W(K−1)), the variable weights of H̃(K−1) used for differentiating LDVD(H̃(K−1)) can be computed from α = Var(W(K−1), axis = 1), where Var(⋅, axis = 1) refers to calculating the variance of each row of some matrix and it 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̃(K−1). We propose to use this sample weights to reweight softmax loss:
min θ LG = ∑ l∈YL wl ⋅ ln(q(H̃ (K) l ) ⋅Yl), (10)
where q(⋅) is the softmax function, YL is the set of labeled node indices and θ is the set of parameters of GCN. The complexity analysis as well as the optimization of whole algorithm are summarized in Appendix D.

heading: 4 EXPERIMENTS
text: 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, we empoly three widely used graph datasets: Cora, Citeseer and Pubmed (Sen et al., 2008). As in Section 2.1, 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 on NELL dataset (Carlson
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.
Baselines Under our proposed framework, we incorporate the VD/DVD term with GCN and GAT called GCN-VD/DVD and GAT-VD/DVD (details in Appendix F), and thus GCN and GAT are two basic baselines. We compare with GNM-GCN/GAT (Zhou et al., 2019) that considers the label selection bias in transductive setting. Moreover, several state-of-the-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.
Results on Label Selection Bias Dataset The results are given in Table 1, and we have the following observations. First, the proposed models (i.e., 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 to 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. It validates the importance and effectiveness of differentiating variables’ weights in semi-supervised setting. Additional experimental results about the sample weight analysis and parameter sensitivity analysis can be found in Appendix G.
Results on Small Sample Selection Bias Dataset As NELL is a large-scale graph, we cannot run GAT on a single GPU with 16GB memory. We only perform GCN-VD/DVD 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 our proposed method can relieve the estimation bias. Moreover, GCN-DVD further improves GCN-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.

heading: 5 RELATED WORKS
text: In the past few years, Graph Neural Networks (GNNs) (Scarselli et al., 2008; Kipf & Welling, 2016; Veličković et al., 2017; Xu et al., 2019; Klicpera et 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 to inductive setting, they all 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 to reweight the labeled nodes. However, it 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 on the simple regressions, but GNNs have more complex structure and properties needed to be considered. We also notice that Shen et al. (2020a) propose a 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.

heading: 6 CONCLUSION
text: In this paper, we investigate a 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 a novel differentiated decorrelated GNN, which combines the debiasing technique with GNNs in a unified framework. Extensive experiments well demonstrate the effectiveness and flexibility of GNN-DVD.

heading: A DERIVATION OF M̂TEF
text: M̂TEF = ∑i∶Ti=twi ⋅ Yi(t) −∑j∶Tj=t−∆twj ⋅ Yj(t −∆t)
∆t
= ∑i∶Ti=twi ⋅ (∑k≠t αkXik + αtt + c + ) −∑j∶Tj=t−∆twj ⋅ (∑k≠t αkXjk + αt(t −∆t) + c + )
∆t
= ∑i∶Ti=twiαtt −∑j∶Tj=t−∆twjαt(t −∆t)
∆t
+ (∑i∶Ti=twi∑k≠t αkXik −∑j∶Tj=t−∆twj∑k≠t αkXik)
∆t + φ( )
=MTEF +∑ k≠t
αk( ∑i∶Ti=twi ⋅Xik −∑j∶Tj=t−∆twj ⋅Xjk
∆t ) + φ( ),
(11)
where ∑i∶Ti=t wiαtt−∑j∶Tj=t−∆t wjαt(t−∆t)
∆t is the ground truth of MTEF , φ( ) means the noise term,
and φ( ) ≃ 0 with Gaussian noise.

heading: B PROOF OF THEOREM 2
text: ŵ = arg min w
p
∑ j=1 (αT⋅abs(HT.jΛwH.−j/n−HT.jw/n⋅HT.−jw/n))2+ λ1 n
n
∑ i=1 w 2 i +λ2( 1 n
n
∑ i=1 wi−1)2
(12)
Proof For simplicity, we denote L1 = ∑pj=1(αT ⋅ abs(HT.jΛwH.−j/n −HT.jw/n ⋅HT.−jw/n))2, L2 = 1n ∑ n i=1 w 2 i , L3 = ( 1n ∑ n i=1 wi − 1)
2 and F(w) = L1 + λ1L1 + λ2L2. We first calculate the Hessian matrix of F(w), denoted as He, to prove the uniqueness of the optimal solution ŵ, as follows:
He = ∂ 2L1 ∂w2 + λ1 ∂ 2L2 ∂w2 + λ2 ∂ 2L3 ∂w2
For the term L1, we can rewrite it as:
L1 = ∑ j≠k α 2 iα 2 k( 1 n
n
∑ i=1 Hi,jHi,kwi − ( 1 n
n
∑ i=1 Hi,jwi)( 1 n
n
∑ i=1 Hi,kwi))2
= ∑ j≠k α 2 iα 2 k(( 1 n
n
∑ i=1 Hi,jHi,kwi)2 − ( 2 n
n
∑ i=1 Hi,jHi,kwi)( 1 n
n
∑ i=1 Hi,jwi)( 1 n
n
∑ i=1 Hi,kwi)
+ (( 1n n
∑ i=1 Hi,jwi)( 1 n
n
∑ i=1 Hi,kwi))2)
And when ∣Hi,j∣ ≤ c, for any variable j and k, and ∣wi∣ ≤ c, we have ∂ 2
∂w2 ( 1 n ∑ni=1 Hi,jHi,kwi)2 = O( 1n2 ), ∂
2
∂w2 ( 1 n ∑ni=1 Hi,jwi)( 1n ∑ n i=1 Hi,kwi) = O( 1n2 ) and
∂ 2
∂w2 (( 2 n ∑ni=1 Hi,jHi,kwi)( 1n ∑ n i=1 Hi,jwi)( 1n ∑ n i=1 Hi,kwi)) = O( 1n2 ). Then with ∣αi∣ ≤ c, we have α2iα 2 k ∂ 2 ∂w2 ( 1 n ∑ni=1 Hi,jHi,kwi − ( 1n ∑ n i=1 Hi,jwi)( 1n ∑ n i=1 Hi,kwi)) 2 = O( 1 n2
). L1 is sum of p(p − 1) such terms. Then we have
∂ 2L1 ∂w2 = O( p 2 n2 ).
With some algebras, we can also have ∂
2L2 ∂w2 = 1 nI,
∂ 2L3 ∂w2 = 1 n2 11 T ,
thus,
He = O( p
2
n2 ) + λ1n I + λ2 n2 11 T = λ1 n I +O( p 2 + λ2 n2 ).
Therefore, if λ1 n ≫ p 2+λ2 n2 , equivalent to λ1n≫ p 2+λ2, He is an almost diagonal matrix. Hence, He is positive definite (Nakatsukasa, 2010). Then the function F(w) is convex on C = {w ∶ ∣wi∣ ≤ c}, and has unique optimal solution ŵ.
Moreover, because L1 is our major decorrelation term, we hope L1 to dominate the terms λ1L2 and λ2L3. On C, we have L1 = O(1), L2 = O(1), and α2iα2k( 1n ∑ n i=1 Hi,jHi,kwi − ( 1 n ∑ni=1 Hi,jwi)( 1n ∑ n i=1 Hi,kwi))
2 = O(1). Thus L1 = O(p2). When p2 ≫ max(λ1, λ2), L1 will dominate the regularization terms L2 and L3.

heading: C PROOF OF THEOREM 3
text: Let Z = {Z1,Z2,⋯,Zp} be p pairwise uncorrelated variables. ∀Zi,Zj ∈ Z, (Z (1) i ,Z (2) i ,⋯,Z (n) i ) and (Z(1)j ,Z (2) j ,⋯,Z (n) j ) are n simple random samples drawn from Zi and Zj respectively, and have same distribution with Zi and Zj . Given a linear aggregation matrix Â = (aij),∀s, v ∈ (1, 2,⋯, n), let Y(s)i = ∑nk=1 askZ (k) i and Y (v) j = ∑nl=1 avlZ (l) j , and we have following derivation:
Cov(Y(s)i ,Y (v) j ) = Cov(
n
∑ k=1 askZ (k) i ,
n
∑ l=1 avlZ (l) j )
= n
∑ k=1
n
∑ l=1 askavlCov(Z (k) i ,Z (l) j ) =
n
∑ k=1
n
∑ l=1 askavlδij ,
where δij = 0 when i ≠ j, otherwise δij = 1. Therefore, when i ≠ j, we have Cov(Y (s) i ,Y (v) j ) = 0 and Cov(Yi,Yj) = 0. Extended the conclusion to multiple variable, Y = (Y1,Y2,⋯,Yn) are pairwise uncorrelated. Proof completes.

heading: D PSEUDOCODE OF GNN-DVD
text: Algorithm 1: GNN-DVD Algorithm Input :Training graph Gtrain = {A,X,Y}, and indices of labeled nodes YL; Max iteration:maxIter Output :GNN parameter θ and sample weights w Initialization :Let w = ω ⊙ ω and initialize sample weights ω with 1; Initialize GNN’s
parameters θ with random uniform distribution; Iteration t← 0
1 while not converged or t < maxIter do 2 Optimize θ(t) to minimize LG; 3 Calculate variable weights α(t) from W(K−1); 4 Optimize ω(t) to minimize LDVD(H̃(K−1)); 5 t = t + 1; 6 end 7 Return: θ and w = ω ⊙ ω
To optimize our GNN-DVD algorithm, we propose an iterative method. Firstly, we let w = ω ⊙ ω to ensure non-negativity of w and initialize sample weight ωi = 1 for each sample i and GNN’s parameters θ with random uniform distribution. Once the initial values are given, in each iteration,
we fix the sample weights ω and update the GNN’s parameters θ by LG with gradient descent, then compute the confounder weights α from the linear transform matrix W(K−1). With α and fixing the GNN’s parameters θ, we update the sample weights ω with gradient descent to minimize LDVD(H(K−1)). 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 is O(np2), 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).

heading: E DATASET DESCRIPTION AND EXPERIMENTAL SETUP
text: E.1 DATASET DESCRIPTION
Some statistics of datasets used in our paper are presented in Table 3, including the number of nodes, the number of edges, the number of classes, the number of features, the bias degree 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 et 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 set. 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 et al. (2016). A description of each of dataset is given as follows:
• Cora (Sen et al., 2008) is a 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) is a citation network of Machine Learning papers that collected from 6 classes:{Agents, Artificial Intelligence, Database, Information Retrieval, Machine Learning, Human Computer Interaction }. Nodes represent papers, edges refer to the citation relationship, and features are bag-of-words vectors for each paper.
• Pubmed (Sen et al., 2008) is a citation network from the PubMed database, which contains a set of articles (Nodes) related to 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 a dataset extracted from the knowledge graph, which is a set of entities connected with directed, labeled edges (relations). Our pre-processing scheme is same as Yang et al. (2016), where each entity pair (e1, r, e2) is assigned with separate relation nodes r1 and r2 as (e1, r1) and (e2, r2). We use text bag-of-words representation as feature vector of the entities.
E.2 EXPERIMENTAL SETUP
As the Section 2.1 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; Veličković et al., 2017). We use the following sets of hyperparameters for GCN on Cora,
Citeseer, Pubmed: 0.5 (dropout rate), 5 ⋅ 10−4 (L2 regularization) and 32 (numbder of hidden units); and for NELL: 0.1 (dropout rate), 1 ⋅ 10−5 (L2 regularization) and 64 (number of hidden units). For GAT on Cora, Citeseer, we use: 8 (first layer attention heads), 8 (features each head), 1 (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 hyper-parameters with base model and we grid search λ1 and λ2 from {0.01, 0.1, 1, 10, 100}. For other baselines, we use the optimal hyper-parameters in literatures on each dataset. For all the experiments, we run 10 times with different random seed and report its average Accuracy results.

heading: F EXTEND TO GAT
text: 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 H̃(K−1) is the input of VD/DVD term, and the variable weights α are calculated from the transformation matrix W(K−1) and the sample weights w are used to reweight the softmax loss. Note that original paper utilizes same transformation matrix W(K−1) for transforming embedding and learning attention values. Because α means the importance of each variable for classification, and it should be computed from transformation matrix W(K−1) for transforming embedding, hence we use separate matrix for transforming embedding and learning attention values respectively. This modification does not change the performance of GAT in experiments.

heading: G ADDITIONAL EXPERIMENTS
text: G.1 SAMPLE WEIGHT ANALYSIS
Here we analyze the effect of sample weights w in our model. We compute the amount of correlation in the labeled nodes’ embeddings H̃(K−1) 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-corvairance matrix computed from vectors of H̃(K−1) and weighted H̃(K−1) respectively. Figure 3 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.
G.2 PARAMETER SENSITIVITY
We study the sensitiveness of parameters and report the results of GCN-DVD on three citation networks in Fig. 4-6. The experimental results show that GCN-DVD is relatively stable to λ1 and λ2 with wide ranges in most cases, indicating the robustness of our model.

Review summaries:
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.