Towards Label Position Bias in Graph Neural Networks
Authors: Haoyu Han
Xiaorui Liu
Feng Shi
MohamadAli Torkamani
Charu C. Aggarwal
Jiliang Tang
Venue: NeurIPS 2023 poster (2023)
Keywords: Graph Neural Networks
Label Position Bias
Graph Structure Learning

Abstract: Graph Neural Networks (GNNs) have emerged as a powerful tool for semi-supervised node classification tasks. However, recent studies have revealed various biases in GNNs stemming from both node features and graph topology. In this work, we uncover a new bias - label position bias, which indicates that the node closer to the labeled nodes tends to perform better. We introduce a new metric, the Label Proximity Score, to quantify this bias, and find that it is closely related to performance disparities. To address the label position bias, we propose a novel optimization framework for learning a label position unbiased graph structure, which can be applied to existing GNNs. Extensive experiments demonstrate that our proposed method not only outperforms backbone methods but also significantly mitigates the issue of label position bias in GNNs.

Towards Label Position Bias in Graph Neural Networks
Haoyu Han', Xiaorui Liu?, Feng Shi
MohamadAli Torkamani Charu C. Aggarwal Jiliang Tang'
Michigan State University North Carolina State University TTigerGraph
Amazon "IBM T.J. Watson Research Center
(hanhaoy] stangiiii @msu.edu, xliu96@
bill.shi@ billsthi@tgeergaaph.comm alitor @ amazon.com, Staru@us.ibm.com
Abstract
Graph Neural Networks (GNNs) have emerged powerful tool for semi- supervised node classification tasks. However, recent studies have revealed various biases in GNNs stemming from both node features and graph topology. In this work, we uncover a new bias label position bias, which indicates that the node closer the labeled nodes tends perform better. We introduce new metric, the Label Proximity Score, to quantify this bias, and find that is closely related to performance disparities. To address the label position bias, we propose a novel optimization framework for learning label position unbiased graph structure, which can be applied existing GNNs. Extensive experiments demonstrate that our proposed method not only outperforms backbone methods but also significantly mitigates the issue of label position bias GNNs.
Introduction
Graph is foundational data structure, denoting pairwise relationships between entities. It finds applications across a range of domains, such as social networks, transportation, and biology. 2 Among these diverse applications, semi-supervised node classification has emerged as crucial and challenging task, attracting significant attention from researchers. Given the graph structure, node features, and subset of labels, the semi-supervised node classification task aims to predict the labels of unlabeled nodes. recent years, Graph Neural Networks (GNNs) have demonstrated remarkable success in addressing this task due to their exceptional ability to model both the graph structure and node features [ A typical GNN model usually follows the message saaugggg scheme [4), which mainly contains two operators, i.c., feature transformation and feature propagation, to exploit node features, graph structure, and label information.
Despite the great success, recent studies have shown that GNNs could introduce various biases from the perspectives of node features and graph topology. In terms of node features, Jiang et al. demonstrated that the peessage-passing scheme could amplify sensitive node attribute bias. A series of studies 6
have endeavored mitigate this sensitive attribute bias in GNNs and ensure fair classification. In terms of graph topology, Tang et al. [9] investigated the degree bias in GNNs, signifying that high-degree nodes typically outperform low-degree nodes. This degree bias has also been addressed by several recent studies [T0] 12).
In addition to node features and graph topology, the label information, especially the position of labeled nodes, also plays crucial role in GNNs. However, the potential bias in label information has been largely overlooked. practice, with an equal number of training nodes, different labeling can result in significant discrepancies in test performance
[3] [4 15]
For instance, Ma et al. [16 study
"This work docs not relate to the author's position at Amazon
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

the subgroup generalization of GNNs and find that the shortest path distance to labeled nodes can also affect the GNNs' performance. but they haven't 't provided deep understanding or solutions. The investigation of the influence of labeled nodes' position on unlabeled nodes remains under-explored.
In this work, discover the presence of indicates that the nodes "closer" to the labeled nodes tend to receive better prediction accuracy. We propose novel metric called Label Proximity Score (LPS) to quantify and measure this bias. Our study shows that different node groups with varied LPSs can result in a significant performance gap, which showcases the existence of label position bias. More importantly, this new metric has a much stronger correlation with performance disparity than existing metrics such as degree [9] and shortest path distance [16), which suggests that the proposed Label Proximity Score might be more intrinsic measurement of label position bias.
bias in GNNs, namely the label position bias, which
Addressing the lahel position bias in GNNs is greatly desired. First, the label position bias would cause the fairness issue to nodes that are distant from the labeled nodes. For instance, in a financial system, label position bias could result in unfair assessments for individuals far from labeled ones, potentially denying them access to financial resources. Second, mitigating this bias has the potential to enhance the performance of GNNs, especially if nodes that are distant can be correctly classified. In this work, we propose a Label Position unbiased Structure Learning method (LPSL) to derive a graph structure that mitigates the label position bias. Specifically, our goal is to learn a new graph structure in which each node exhibits similar Label Proximity Scores. The learned graph structure can then be applied across various GNNs. Extensive experiments demonstrate that our proposed LPSL. not only outperforms backhone methods but also significantly mitigates the issue of label position bias in GNNs.
2 Label Position Bias
In this section, we provide an insightful preliminary study reveal the existence of label position bias in GNNs. Before that, we first define the notations used in this paper.
Notations. We use bold upper-case letters such X to denote matrices. X, denotes its i-th row and X.y indicates the i-th row and j-th column element. We use bold lower-case letters such as x to denote vectors. 1n E nx1 1 is all-ones column vector. The Frobenius norm and the trace of a matrix X are defined as || r = v Exj Xi, and ir tr(X)= - E; X.,, respectively. Let G = (V,E) be graph, where V is the node set and E is the edge set. N₁ denotes the neighborhood node set for node uy- The graph be represented by adjacency matrix A Roxa where A.j > 0 indices that there exists an edge between nodes U; and 05 in G. or otherwise Aij = 0. Let D = diog (1, d2..... da)) be the degree matrix, where de Σ3 Aij is the degree of node Us. The graph Laplacian matrix is
defined L = D A A. We define the normalized adjacency matrix as À - AD- 1 and the normalized Laplacian matrix as L = I Á. Furthermore, suppose that each node is associated with d-dimensional feature x and we use X = [x....., x,] E R' to denote the feature matrix. In this work, focus the node classification task graphs. Given graph g = {A, X} and partial set of labels V>= = {y1,.... } for node set V2= = {oI...., } where y; E IR' is a one-hot vector with classes, goal is to predict labels of unlabeled nodes. For convenience, we reorder the index
of nodes and use mask matrix T = I 07 0]
to represent the indices of labeled nodes.
Label Proximity Score. In this study, we aim to study the bias caused by label positions. When studying prediction bias, we first need to define the sensitive groups based on certain attributes or metrics. Therefore, we propose novel metric, namely the Label Proximity Score, quantify the closeness between test nodes and training nodes with label information. Specifically, the proposed Label Proximity Score (LPS) is defined follows:
LPS = PT1,, and P P= PI(1-11-)AA)*
where P represents the Personalized PageRank matrix, T is the label mask matrix, 1, an all-ones column vector, and E (0, stands for the teleport probability. P.j represents the pairwise node proximity between node and node j. For each test node i, its LPS represents the sum of its node proximity values to all labeled nodes, i.c., (PT1,); P TI, = Ejev, P.j.

---

Sensitive Groups. In addition to the proposed LPS, we also explore two existing metrics such as node degree [9 and shortest path distance to label nodes []6] for comparison since they could be related to the label position bias. For instance, the node with high degree is more likely to connect with labeled nodes, and the node with a small shortest path to a labeled node is also likely "closer" to all labeled nodes if the number of labeled nodes is small. According to these metrics, we split test nodes into different sensitive groups. Specifically, for node degree and shortest path distance to label nodes, use their actual values to split them into seven sensitive groups, as there are only very few nodes whose degrees or shortest path distances are larger than seven. For the proposed LPS, we first calculate its value and subsequently partition the test nodes evenly into seven sensitive groups, each having an identical range of LPS values.
Experimental Setup. We conduct the experiments on three representative datasets used in semi- supervised node classification tasks, namely Cora, CiteSeer, and PubMed. We also experiment with three different labeling rates: 5 labels per class, 20 labels per class, and 60% labels per class. The experiments are performed using two representative GNN models, GCN [17 and APPNP [18] which cover both coupled and decoupled architectures. We also provide the evaluation on Label Propagation (LP) [9 to exclude the potential bias caused by node features. For GCN and APPNP, we adopt the same hyperparameter setting with their original papers. The node classification accuracy on different sensitive groups {1, 2, 3, 4, 5. 6, 7} with the labeling rate of 20 labeled nodes per class under APPNP, GCN. and LP models is illustrated in Figure 2 and respectivvel. Due to the space limitation, put more details and results of other models, datasets, and labeling rates into Appendix A.
0.95
0.90
0.90
0.85
0.85
0.85
Accuracy
0.75
0.75
0.75
0.65
0.65
0.65
0.60
1234567
17
1234567
1234567
(a) Degree
(b) Shortest Path Distance
(c) Label Proximity Score
Figure 1: APPNP with 20 labeled nodes per class on Cora and CiteSeer datasets.
0.95
0.95
0.95
0.90
0.85
0.85
0.85
Accuracy
Accuracy
Accuracy
0.80
0.80
0.80
0.75
0.70
0.70
0.70
0.60
3
6
1234567
0.60
2
4
1234567
0.60
2
4567
1 4
(a) Degree
(b) Shortest Path Distance
(c) Label Proximity Score
Figure 2: GCN with 20 labeled nodes per class Cora and CiteSeer datasets.
0.9
0.9
0.8
0.8
Accuracy
0.7
Accuracy
0.7
Accuracy
0.7
0.6
0.6
0.5
0.5
0.5
0.4
0.4
0.3
0.3
0.3
0.2
1234567
1234567
0.2
1234567
(a) Degrec
(b) Shortest Path Distance
(c) Label Proximity Score
Figure 3: LP with 20 labeled nodes per class on Cora and CiteSeer datasets.
Observations. From the results presented in Figure and we can observe the following:
Label Position bias prevalent across all GNN models and datasets. The classification accuracy can notably vary between different sensitive groups, and certain trends are discernible. To
3

---

ensure faimess and improve performance, addressing this bias is a crucial step in improving GNN models.
While Degree and Shortest Path Distance (SPD) can somewhat reflect disparate performance, indicating that nodes with higher degrees and shorter SPDs tend to perform better, these trends lack consistency, and they can't 't fully reflect the Label Position bias. For instance, degree bias is not pronounced in the APPNP model as shown in Figure [T APPNP can capture the global structure. Morcover, SPD fails to effectively evaluate relatively low homophily graphs, such as CiteSeer (0)] Consequently, there is need to identify more reliable metric.
The Label Proximity Score (LPS) consistently exhibits a strong correlation with performance disparity across all datasets and models. Typically, nodes with higher LPS scores perform better. In addition, nodes with high degrees and low Shortest Path Distance (SPD) often have higher LPS, as previously analyzed. Therefore. LPS is highly correlated with label position bias.
The Label Propagation, which solely relies on the graph structure, demonstrates a stronger label position bias compared to GNNs as shown Figure 3 Moreover, the label position bias becomes less noticeable in all models when the labeling rate is high, as there typically exist labeled nodes within the two-hop neighborhood of each test node (detailed in Appendix A). These observations suggest that the label position bias is predominantly influenced by the graph structure. Consequently, this insight motivates us to address the Label Position bias from the perspective of the graph structure.
In conclusion, label position bias indeed present in GNN models, and the proposed Label Proximity Score accurately and consistently reflects the performance disparity over different sensitive groups for different models across various datasets. Overall, the label proximity score exhibits more consistent and stronger correlations with performance disparity compared with node degree and shortest path distance, which suggests that L.PS serves as better metric for label position bias. Further, through the analysis of the Label Propagation method and the effects of different labeling rates, we deduce that the label position bias is primarily influenced by the graph structure. This understanding paves us a way to mitigate label position bias.
3 The Proposed Framework
The studies in Section 2 Juggest that Label Position bias is a prevalent issue in GNNs. In other words, nodes far away from labeled nodes tend to yield subpar performance. Such unfairness could be problematic, especially in real-world applications where decisions based on these predictions can have substantial implications. As result, mitigating label position bias has the potential to enhance the fairness of GNNs in real-world applications, as well as improve overall model performance. Typically, there are two ways to address this problem, i.e., from a model-centric or data-centric perspective. In this work, we opt for a data-centric perspective for two primary reasons: (1) The wide variety of GNN models in use in real-world scenarios, each with its unique architecture, makes it challenging to design a universal component that can be seamlessly integrated into all GNNs to mitigate the label position bias. Instead, the graph structure universal and can be applied to any existing GNNs. (2) Our preliminary studies indicate that the graph structure is the primary factor contributing to the label position bias. Therefore, it more rational address the bias by learning a label position unbiased graph structure.
However, there are mainly two challenges: (1) How can we define label position unbiased graph structure, and how can we learn this structure based on the original graph? (2) Given that existing graphs are typically sparse, how can we ensure that the learned data structure is also sparse avoid excessive memory consumption? In the following subsections, we aim to address these challenges.
3.1 Label Position Unbiased Graph Structure Learning
Based on our preliminary studies, the Label Proximity Score (LPS) can consistently reflect perfor- mance disparity across various GNNs and indicate the label position bias. Therefore, to mitigate the label position bias from the structural perspective, our objective is to learn a new graph structure in which each node exhibits similar L.SSs. Meanwhile, this learned unbiased graph structure should maintain certain properties of the original graph. To achieve this goal, we formulate the Label Position

---

Unbiased Structure Learning (LPSL) problem as follows:
arg min | BIl LLB(BBLB)
s.t. BT1, cl,, Bi 0 Vi,j
where B E R represents the debiased graph structure matrix. tr((B LB) E(m.ay)e [B//dd - /d,l2 measures the smoothness of the new structure based on the original graph structure. The proximity to identity matrix I R encourages self-loops and avoids trivial over-smoothed structures. À is hyperparameter that controls the balance between smoothness and self-loop. T the mask matrix indicating the labeled nodes, I the all-ones vector, and is hyperparameter serving as the uniform Label Proximity Score for all nodes. Due to the B represents the graph structure, we have the constraint that all elements in B should be non-negative.
Notably, if we ignore the constraint, then the optimal solution for this primary problem is given by B = =I (I+ PageRank (PPR) matrix which measures pairwise node proximity. Furthermore, the constraint in Eq. 2 ensures that all nodes have the same Label Proximity Score, denoted c. The constraint
XL) ax(I - (1 aA)))=, where a = --x This solution recovers the Personalized
encourages fair label proximity scores for nodes so that the learned graph structure mitigates the label position bias.
The constrained optimization problem in Eq. 2 solved by the Lagrange Multiplier method with the projected gradient descent (21]. The augmented Lagrange function can be written as:
a convex optimization problem, and it can be
Lp = -- BI + Atr(B LB) +y (BT1, - ccl,) + P BT1, - cc1,
(3)
where Rxx1 is the introduced Lagrange multiplier, and p 0 represents the augmented Lagrangian parameter. The gradient of (B. to B can be represented as:
aLp = + 2λLB + (TT,) (BTI,, clT)(TT,)
(4)
Then, the problem can be solved by dual ascent algorithm 22 as follows:
* arg min (B* .y*
B max(0, B++1)
y y* + p( (B T1,, cln),
where & is the current optimization step, and B ++1 can be obtained by multiple steps of gradient descent using the gradient in Eq. (4)
3.2 Understandings
In this subsection, we provide the understanding and interpretation our proposed LPSS., establish- ing its connections with the message passing in GNNs.
Remark 3.1. The feature aggregation using the learned graph structure B directly as a propagation matrix, i.e., F = BX, is equivalent to applying the message passing in GNNs using the original graph if B the approximate or exact solution the primary problem defined in Eq. without constraints.
The detailed proof can be found in Appendix B. Remark 3.1 suggests that can directly substitute the propagation matrix in GNNs with the learned structure B. The GNNs are trained based on the labeled nodes, and the labeled nodes would influence the prediction of unlabeled nodes because of the message- passsigg scheme. Following the definition in (23), the influence node j on node can be represented by I,i) sur
Th dx
where h, is the representation of node i, X5 is the input feature
of node j. and ab.
0x, represents the Jacobian matrix. Afterward, we have the following Proposition
based on the influcence scores:
5

---

Proposition 3.1. The influence scores from all labeled nodes to any unlabeled node will be the equal, i.e. Ejev, [ C, when using the unbiased graph structure B obtained from the optimization problem in Eq. 2 as the propagation matrix in GNNs.
The proof can be found in Appendix B. Proposition 3.1 suggests that by using the unbiased graph structure for feature propagation, each node can receive equivalent influence from all the labeled nodes, thereby mitigating the label position bias issue.
3.3 l1-regularized Label Position Unbiased Sparse Structure Learning
One challenge of solving the graph structure learning problem in Eq. 2 is that it could result in a dense structure matrix B E R"x", This is memory-intensive outcome, especially when the number of nodes is large. Furthermore, applying this dense matrix to GNNs can be time-consuming for downstream tasks, which makes it less practical for real-world applications. To make the learned graph structure sparse, we propose the following L f-rregularzed Label Position Unbiased Sparse Structure Learning optimization problem:
min I B + Atr(B LB) 8 B|I
B
(5)
s.t. BT1, cl, B,y 2 Vi,j,
where |[B|| represents the & regularization that encourages zero values in B. is a hyper- parameter to control the sparsity of B. The primary problem in Eq. (5) is proved to have strong localization property and can guarantee the sparsity 24 25 The problem in Eq. (5) can also be solved by the Lagrange Multiplier method. However, when the number of nodes n is large, solving this problem using conventional gradient descent methods becomes computationally challenging. Therefore, we propose to solve the problem in Eq. (5) efficiently by Block Coordinate Descent (BCD) method [26] in conjunction with the proximal gradient approach, particularly due to the presence of the & regularization. Specifically, we split B into column blocks, and B.,; represents the j-th block. The gradient of Lp with respect to B., can be written as:
ÖLp 2 I.j) 2ALB.. + +Y(TN)) (BB1, (TL.)) UB
(6)
where (T1,); E Rdx1 is the corresponding block part with block size d. After updating the current block B.j;, we apply a soft thresholding operator (.) based on the proximal mapping. The full algorithm is detailed in Algorithm [ soft thresholding operation, and line updates Lagrange multiplier y through dual ascent update.
Notably, lines 6-8 handle the block updates, line 9 performs the
3.4 The Model Architecture
The proposed LPSL learns an unbiased graph structure with respect to the labeled nodes. Therefore, the learned graph structure can be applied to various GNN models to mitigate the Label Position bias. In this work, we test LPSL on two widely used GNN models, i.c., GCN [17] and APPNP [18]. For the GCN model, each layer can be represented by:
Algorithm 1 Algorithm of LPSI.
1: Input: Laplacian matrix L, Label mask matrix
T. Hyperparamters X, c, B, p. learning rate y
2: Output: Label position unbiased graph struc- ture B
3: Initialization: B and y = 0
4: while Not converge do
5: for each block j do
H H1+1 a (B,H'W').
6: for i 0 to update steps do
B.j B.j * dhp. end for
where H = X, a is the non-linear activation
7:
BB
function, B2 is the unbiased structure with pa- permeter X, and W is the weight matrix in the 1-th layer. We refer this model as LPSLGCN. 10:
8:
9:
B. S5/p
end for
For the APPNP model, we directly use the learned B as the propagation matrix, and the prediction can be written as:
11:
y + (BT1, cl.))
12: end while
13: return B
Y pred (X)x
where fo(-) any machine learning model parameterized by the learnable parameters 0. We name this model as LPSLAPPNP. The parameter À provides a high flexibility when applying B, to different

---

GNN architectures. For decoupled GNNs such as APPNP, which only propagates once, a large À is necessary to encode the global graph structure with a denser sparsity. In contrast, for coupled GNNs, such as GCN, which apply propagation multiple times, smaller À can be used to encode a more local structure with a higher sparsity. Our code is available at: http://gthub..com/haayaaaa
4 Experiment
In this section, we conduct comprehensive experiments to verify the effectiveness of the proposed LPSL. In particular, we try to answer the following questions:
Q1: Can the proposed LPSL improve the performance of different GNNs? (Section 4.2)
Q2: Can the proposed LPSL mitigate the label position bias? (Section 4.3)
Q3: How do different hyperparameters affect the proposed LPSL? (Section 4.4)
4.1 Experimental Settings
Datasets. We conduct experiments on 8 real-world graph datasets for the semi-supervised node classification task, including three citation datasets, i.e., Cora, Citeseer, and Pubmed [27], two co- authorship datasets, i.e., Coauthor CS and Coauthor Physics, two co-purchase datasets. i.c. Amazon
Computers and Amazon Photo [28. and one OGB dataset, i.e., oghn-arxiv 29]. The details about these datasets are shown in Appendix C.
We employ the fixed data split for the ogbn-arxiv dataset, while using ten random data splits for all other datasets to ensure more reliable results [30]. Additionally, for the Cora, CiteSeer, and PubMed datasets, we experiment with various labeling rates: low labeling rates with 5, 10, and 20 labeled nodes per class, and high labeling rates with 60% labeled nodes per class. Each model is run three times for every data split, and we report the average performance along with the standard deviation.
Baselines, To the best of our knowledge, there are no previous works that aim to address the label position bias. In this work, we select three GNNs, namely, GCN (17), GAT (31], and APPNP [8)) two Non-GNNs, MLP and Label Propagation [9). as baselines. Furthermore, we also include GRADE 332, method designed to mitigate degree bias. Notably, SRGNN 33 demonstrates that if labeled nodes are gathered locally, it could lead to an issue of feature distribution shift. SRGNN aims to mitigate the feature distribution shift issue and also included baseline.
Hlpperparameters Setting. We follow the best hyperparameter settings in their original papers for all baselines. For the proposed LPSLGGN, we set the À in range [1,8]. For LPSLAPPNE, we set the À in the range [8, 15]. For both methods, c is set in the range [0.5, 1.5]. We fix the learning rate 0.01, dropout 0.5 or 0.8, hidden dimension size 64, and weight decay 0.0005, except for the ogbn-arxiv dataset. Adam optimizer (34] is used in all experiments. More details about the hyperparameters
setting for all methods can be found in Appendix D.
4.2 Performance Comparison on Benchmark Datasets
In this subsection, we test the learned unbiased graph structure by the proposed L.SLL on both GCN and APPNP models. We then compare these results with seven baseline methods across all eight datasets. The primary results are presented in Table I Due to space limitations, we have included the results from other baselines in Appendix E. From these results, we can make several key observations:
The integration of our proposed LPSL to both GCN and APPNP models consistently improves their performance almost all datasets. This indicates that a label position unbiased graph structure can significantly aid semi-supervised node classification tasks.
Concerning the different labeling rates for the first three datasets, our proposed LPSI. shows greater performance improvement with low labeling rate. This aligns with our preliminary study that label position bias is more pronounced when the labeling rate is low.
SRGNN, designed to address the feature distribution shift issue, does not perform well on most datasets with random splits instead of locally distributed labels. Only when the labeling rate is very low, SRGNN can outperform GCN. Hence, the label position bias cannot be solely solved by addressing the feature distribution shift.
The GRADE method, aimed at mitigating the degree-bias issue, also fails to improve overall performance with randomly split datasets.
7

---

Table 1: Semi-supervised node classification accuracy (%) on benchmark datasets.
Dataset
Label Rate
GCN
APPNP
GRADE
SRGNN
GPSL
LPPP-APPM
70.68
2.17
75.86 2.34
69.51
6.79
70.77
1.82
76.58 2.37
77.24
10
76.50
1.42
80.29
1.00
74.95
2.46
75.42
1.57
80.39 + 1.17
Cora
20
79,41 1.30
0.67
1..41
78.42 1.75
82.74 1.01
83.24
60%
88.60 # 1.19
88.49 + 1.28
86.8
87.17
88.75 1.21
88.62 1.69
5
61.27 3.85
63.03#3.61 3.39
64.84
65.70 65.65
10
66.28 + 2.14
67.57 + 2.05
64,20
67.83
67.73 2.57
68.76 #
CiteSeer
69,60 1.67
70.85
1.45
67.50 1.76
69.13 1.99
70.73 1.32
71.25
60%
76.88
77.42 1.47
74.00
1.57
77.18
77,56
6.44
72.68
6..90
69.38 6.448
4.64
73.57 5.30
10
75.53
73.31
72.69 3.49
75.67 + 4.42
76.18 4.05
PubMed
20
77,43 2.66
78.93 2.11
77.09 1.68
79.26 2.32
60%
88.48 + 0.46
87.56 4: 0.52
86.90 +: 0.46
88.32 + 0.55
87.75 + 0.57
87.96 + 0.57
CS
20
91.73 + 0.49
92.38 # 0.38
89.43
89.43
0.67
91.94
92.44 = 0.36
Physics
20
93.29 + 0.80
93.49 0.67
91.44 1.41
93.16 0.64
0
93.65 = 0.50
Computers
20
19.17
79.07 + 2.34
79.01 # 2.36
7..54
80.05
2.92
79.58 2.31
Photo
89.94
90.87 + 1.14
90.17 0.99
89.36
1.02
1.16 90.85
90.93 = 1.40
ogbn-arxiv
54%
71.91
71.61 = 0.30
OOM
68.01 = 0.35
72.04
69.20 0.26
4.3 Evaluating Bias Mitigation Performance In this subsection, we aim to investigate whether the proposed LPSL can mitigate the label position bias. We employ all three aforementioned bias metrics, namely label proximity score, degree, and shortest path distance, on Cora and CiteSeer datasets. We first group test nodes into different sensitive groups according to the metrics, and then three representative group bias measurements Weighted Demographic Parity (WDP), Weighted Standard Deviation (WSD), and Weighted Coefficient of Variation (WCV)- quantify the bias. These defined follows:
WDP EP1 No |A
Aavgl
Σ N (Ai - Anvg) WCV WSD 1=1
WSD
Nuval
N
Aavg
where D is the number of groups, N; is the node number group i, A; the accuracy of group Aagg is the weighted average accuracy of all groups. i.e., the overall accuracy, and Nuoial is the total number of nodes. We choose six representative models, i.e., Label Propagation (LP), GRADE, GCN, APPNP, LPSLGCN. and LPSLAPPNP. in this experiment. The results of the label proximity score, degree, and shortest path on the Cora and Citeseer datasets are shown Tabel and respectively. It can be observed from the tables:
The Label Propagation method, which solely utilizes the graph structure information, exhibits the most significant label position bias across all measurements and datasets. This evidence suggests that label position bias primarily stems from the biased graph structure, thereby validating our strategy of learning an unbiased graph structure with LPSL.
The proposed LPSL not only enhances the classification accuracy of the backbone models, but also alleviates the bias concerning Label Proximity Score, degree, and Shortest distance.
The GRADE method, designed to mitigate degree bias, does exhibit lesser degree bias than GCN and APPNP. However, it still falls short when compared to the proposed LPSL. Furthermore, GRADE may inadvertently heighten the bias evaluated by other metries. For instance, significantly increases the label proximity score bias on the CiteSeer dataset.
Table 2: Comparison of Methods in Addressing Label Proximity Score Bias.
Dataset
Cora
CiteSeer WSD +
Method
WDP +
WSD
WCV
WDP
WCV +
LP
0.1079
0.1378
0.1941
0.2282
0.2336
0.4692
GRADE
0.0372
0.0489
0.0615
0.0376
0.0467
0.0658
GCN
0.0494
0.0618
0.0758
0.0233
0.0376
0.0524
LPSLGGN
0.0361
0.0438
0.0518
0.0229
0.0346
0.0476
APPNP
0.0497
0.0616
0.0732
0.0344
0.0426
0.0594
LPSLLPPNP
0.0390
0.0476
0.0562
0.0275
0.0349
0.0474

---

Table 3: Comparison of Methods in Addressing Degree Bias.
Dataset
Cora
CiteSeer
Method
WDP 4
WSD
WCV
WDP
WSD 4
WCV 4
LP
0.0893
0.1019
0.1447
0.1202
0.1367
0.2773
GRADE
0.0386
0.0471
0.0594
0.0342
0.0529
0.0744
GCN
0.0503
0,0566
0.0696
0,0466
0.0643
0.0901
LPSLGCN
0.0407
0.0468
0.0554
0.0378
0.0538
0.0742
APPNP
0.0408
0,0442
0.0527
0.0499
0.0688
0.0964
LPSLAPPNP
0.0349
0.0395
0.0467
0.0316
0.0487
0.0665
Table Comparison of Methods in Addressing Shortest Path Distance Bias.
DataSet
Cora
CiteSeer
Method
WDP +
WSD
WCV +
WDP
WSD 4
WCV +
LP
0.0562
0.0632
0.0841
0.0508
0.0735
0.109
GRADE
0.0292
0.0369
0.0459
0.0282
0.0517
0.0707
GCN
0.0237
0.0444
0.0533
0.0296
0.0553
0.0752
LPSLGGN
0.0150
0.0248
0.0289
0.0246
0.0526
0.0714
APPNP
0.0218
0.0316
0.0369
0.0321
0.0495
0.0668
LPSLAPPNP
0.0166
0.0253
0.0295
0.0265
0.0490
0.0654
4.4 Ablation Study
In this subsection, first explore the impact of different hyperparameters, specifically the smoothing term and the constraint c, on our model. We conducted experiments on the Cora and CiteSeer datasets using ten random data splits with 20 labels per class. The accuracy of different À values for LPSLAPPNP and LPSLGGN on the Cora and CiteSeer datasets are illustrated in Figure
From the results, we note that the proposed LPSL is not highly sensitive to the À within the selected regions. Moreover, for the APPNP model, the best À higher than that for the GCN model, which aligns with our discussion in Section 3 that the decoupled GNNs require a larger À to encode the global graph structure. The results for hyperparameter can be found in Appendix F with similar observations.
85
Accuracy
80
Accuraioy
80
75
95
70
Dora CruSew
Day Dadlerr
Lambda
Lambda
(a) LPSLAPPNP
(b) LPSLGCN
Figure 4: The accuracy of different À for LPSLAPPNP and LPSLGGN on Cora and CiteSeer datasets.
In addition, investigate the impact of the sparse graph structure matrix B generated using 4 regularization, as described in Eq. []] on the performance different models. For this purpose, we utilize the Cora dataset and select an appropriate 3 value to produce the sparse graph structure matrix B at sparsity levels of 80%, 90%, and 95%. This means that 80%, 90%, and 95% the entries the matrix B are zero, respectively.
The results are presented in Table We observe that the accuracy 80% and 90% sparsity closely aligned with that of the dense matrix. However, when sparsity reaches 95%, there is slight drop in accuracy, mirroring the findings of PPRGo 35 Notably, fairness appears be relatively unaffected by the varying levels of sparsity.

---

Table 5: Performance comparison using different sparsity levels of B on the Cora dataset.
LPSLAPPNP
LPSLGGN
Sparsity
15%(B 0)
80%
90%
95%
15%(B
80%
90%
95%
ACC
83.24
83.20
82.67
81.90
82.74
82.66
82.70
81.78
WDP
0.033
0.0345
0.0323
0.0322
0.0347
0.0346
0.0347
0.0337
WSD
0.042
0.0444
0,0417
0.0411
0.0443
0.0439
0.0425
0.0433
WCV
0.0505
0.0534
0.0504
0.0503
0.0536
0.0532
0.0515
0.053
Related Work
Graph Neural Networks (GNNs) serve an effective framework for representing graph-structured data, primarily employing two operators: feature transformation and propagation. The ordering of these operators classifies most GNNs into two categories: Coupled and Decoupled GNNs. Coupled GNNs, such as GCN 17.. GraphSAGE [36], and GAT [1I, entwine feature transformation and propagation within each layer. contrast, recent models like APPNP [T8] represent Decoupled
GNNs (30 37 38) that separate transformation and propagation. While Graph Neural Networks
(GNNs) have achieved notable success across a range domains []]. they often harbor various biases tied to node features and graph topology [39]. For example, GNNs may generate predictions skewed by sensitive node features 6 leading to potential unfairness diverse tasks such as recommendations 440 and loan fraud detection
4 Numerous studies have proposed different and fairness constraints [6] 44 45). Structural bias is another significant concern, where low-degree nodes are more likely to be falsely predicted by GNNs [9]. Recently, there are several works aimed to mitigate the degree bias issue [10 [2] Distinet from these previous studies, work identifies new form of bias label position bias, which is prevalent GNNs. To address this, we propose novel method, LPSL., specifically designed alleviate the label position bias.
methods to address feature bias, including adversarial training 8
6 Conclusion and Limitation
In this study, we shed light on previously unexplored bias in GNNs, the label position bias, which suggests that nodes closer labeled nodes typically yield superior performance. To quantify this bias, we introduce new metric, the Label Proximity Score, which proves to be more intrinsic measure. To combat this prevalent issue, we propose a novel optimization framework, LPSL, to learn unbiased graph structure. Our extensive experimental evaluation shows that LPSL not only outperforms standard methods but also significantly alleviates the label position bias in GNNs. In our current work, address the label position bias only from structure learning perspective. Future research could incorporate feature information, which might lead improved performance. Besides, we have primarily examined homophily graphs. It would be interesting investigate how label position bias affects heterophily graphs. We hope this work will stimulate further research and development of methods aimed at enhancing label position faimess in GNNs.
7
Acknowledgement
This research is supported by the National Science Foundation (NSF) under grant numbers CNS 2246050, IISI 1850881,, IIS221 2032, IIS2212144, I182153326, IIS2212145, IOS2107215, DUE 2234015, DRL 2025244 and IOS2035472, the Army Research Office (ARO) under grant num- ber W91 the Home Depot, Cisco Systems Inc, Amazon Faculty Award, John- son&Johnson, JP Morgan Faculty Award and SNAP.
References
[1] Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Yu Philip. comprehensive survey on graph neural networks. IEEE transactions on neural networks and learning systems, 32(1):4-22 24, 2020.
[2] Yao Ma and Jiliang Tang. Deep learning graphs. Cambridge University Press, 2021.
10

---

[3] Jie Zhou, Ganqu Cui, Shengding Hu, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, Lifeng Wang, Changcheng Li, and Maosong Sun. Graph neural networks: A review of methods and applications. Al open, 1:57-81, 2020.
[4] Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International conference on machine learning, pages 1263-122 1272. PMLR, 2017.
[5] Zhimeng Jiang, Xiaotian Han, Chao Fan, Zirui Liu, Na Zou, Ali Mostafavi, and Xia Hu. Fmp: Toward fair graph message passing against topology bias. arXiv preprint arXiv:2202.04187, 2022.
[6] Chirag Agarwal, Himabindu Lakkaraju, and Marinka Zitikk Towards a unified framework for fair and stable graph representation learning. In Uncertainty in Artificial Intelligence, pages 21 2114-2122 2124. PMLR, 2021.
[7] Deniz Kose and Yanning Shen. Fair node representation learning via adaptive data augmenta- tion. arXiv preprint arXiv:2201.08549, 2022.
[8] Enyan Dai and Suhang Wang. Say no the discrimination: Learning fair graph neural networks with limited sensitive attribute information. In Proceedings of the 14th ACM International Conference Web Search and Data Mining, pages 680-688, 2021.
[9] Xianfeng Tang, Huaxiu Yao, Yiwei Sun, Yiqi Wang, Jiliang Tang. Charu Aggarwal, Prasenjit Mitra, and Suhang Wang. Investigating and mitigating degree-related biases in graph convoltu- ional networks. In Proceedings of the 29th ACM International Conference on Information & Knowledge Management, pages 1435-1444 2020.
[10] Jian Kang, Yan Zhu, Yinglong Xia, Jiebo Luo, and Hanghang Tong. Rawlsgen: Towards rawlsian difference principle on graph convolutional network. In Proceedings of the ACM Web Conference 2022, pages 1214-1225, 2022.
[11] Zemin Liu, Trung- Kien Nguyen, and Yuan Fang. On generalized degree faimess in graph neural networks. arXiv preprint 233iv:2302.03888 2023.
[12] Langzhang Liang, Zenglin Xu, Zixing Song, Irwin King, and Jieping Ye. Resnorm: Tackling long-tailed degree distribution issue in graph neural networks via normalization. arXiv preprint 2261122006.88111, 2022.
[13] Jiaqi Ma, Ziqiao Ma. Joyce Chai, and Qiaozhu Mei. Partition-based active learning for graph neural networks. arXiv preprint arXiv:2201.09391, 2022.
[14] Hongyun Cai, Vincent W Zheng, and Kevin Chen-Chuan Chang. Active learning for graph embedding. arXiv preprint arXiv: 000.07005..0.... 2017.
[15] Shengding Hu, Zheng Xiong, Meng Qu, Xingdi Yuan, Marc-Alexandre Côté, Zhiyuan Liu, and Jian Tang. Graph policy network for transferable active learning on graphs. Advances in Neural Information Processing Systems, 13:10174-1018: 2020.
[16] Jiaqi Ma, Junwei Deng, and Qiaozhu Mei. Subgroup generalization and fairness of graph neural networks. Advances in Neural Information Processing Systems, 34: 104810611, 2021.
[17] Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint
2016.
[18] Johannes Gasteiger, Aleksandar Bojchevski, and Stephan Günnemano. Predict then propagate: Graph neural networks meet personalized pagerank. arXiv preprint arXiv:1810.0599) 2018.
[19] Dengyong Zhou, Olivier Bousquet, Thomas Lal, Jason Weston, and Bernhard Schölkopf. Learning with local and global consistency. Advances in neural information processing systems, 16, 2003.
[20] Yao Ma, Xiaorui Liu, Neil Shah, and Jiliang Tang. homophily a necessity for graph neural networks? arXiv preprint arXiv:2106.060 061444 2021.

---

[21] Stephen P Boyd and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.
[22] Stephen Boyd, Neal Parikh, Eric Chu, Borja Peleato, Jonathan Eckstein, et al. Distributed opti- mization and statistical learning via the alternating direction method of multipliers. Foundations and Trends@ in Machine learning, 1(1):1-122, 2011.
[23] Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks, In International conference on machine learning, pages 5453-5462. PMLR, 2018.
[24] Wooseok Ha, Kimon Fountoulakis, and Michael W Mahoney. Statistical guarantees for local graph clustering. The Journal of Machine Learning Research, 22(():6538 (3(1)66538-6511, 2021.
[25] Chufeng Hu. Local graph clustering using 11 I1-regularized pagerank algorithms. Master's 's thesis, University of Waterloo, 2020.
[26] Paul Tseng. Convergence of block coordinate descent method for nondifferentiable minimiza- tion. Journal of optimization theory and applications, 10953):475, 2001.
[27] Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi- Rad. Collective classification in network data. Al magazine, 29(3):33-93, 2008.
[28] Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski. and Stephan Günnemann. Pitfalls of graph neural network evaluation. arXiv preprint arXiv:1871.0586. 2018.
[29] Weihua Hu, Matthias Fey, Marinka Zitmik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. Advances neural information processing systems, 33:22118 12-1333,, 2020.
[30] Xiaorui Liu, Wei Jin, Yao Ma, Yaxin Li, Hua Liu, Yiqi Wang, Ming Yan, and Jiliang Tang. Elastic graph neural networks. In International Conference on Machine Learning, pages 6837-6849. PMLR, 2021.
[31] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pictro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv: 2017.
[32] Ruijia Wang, Xiao Wang, Chuan Shi, and Le Song. Uncovering the structural fairness in graph contrastive learning, arXiv preprint arXiv:2210.03011 2022.
[33] Qi Zhu, Natalia Ponomareva, Jiawei Han, and Bryan Perozzi. Shift-robust gnns: Overcoming the limitations of localized graph training data. Advances in Neural Information Processing Systems, 34:27965- -29977, 2021.
[34] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint 14Xiv:1412.6980, 2014.
[35] Aleksandar Bojchevski, Johannes Gasteiger, Bryan Perozzi, Amol Kapoor, Martin Blais, Benedek Rózemberczki, Michal Lukasik, and Stephan Günneemann. Scaling graph neural networks with approximate pagerank. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 2464-244444 2464-2473, 2020.
[36] Will Hamilton, Zhitao Ying. and Jure Leskovec. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017.
[37] Meng Liu, Hongyang Gao, and Shuiwang Ji. Towards deeper graph neural networks. In Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery & data mining, pages 338-348, 2020.
[38] Kaixiong Zhou, Xiao Huang, Daochen Zha, Rui Chen, Li Li, Soo-Hyun Choi, and Xia Hu. Dirichlet energy constrained learning for deep graph neural networks. Advances in Neural Information Processing Systems, 34, 2021.
12

---

[39] Enyan Dai, Tianxiang Zhao, Huaisheng Zhu, Junjie Xu. Zhimeng Guo, Hui Liu. Jiliang Tang. and Suhang Wang. comprehensive survey on trustworthy graph neural networks: Privacy, robustness, fairness, and explainability. arXiv preprint urXiv:2204.085777 2022.
[40] Maarten Buyl and Tijl De Bie. Debayes: bayesian method for debiasing network embeddings. In International Conference on Machine Learning, pages 1220-1229, PMLR, 2020.
[41] Bingbing Xu, Huawei Shen, Bingjie Sun, Rong An, Qi Cao, and Xueqi Cheng. Towards consumer loan fraud detection: Graph neural networks with role-constrained conditional random field. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 4537- 4545, 2021.
[42] Yushun Dong, Ninghao Liu, Brian Jalaian, and Jundong Li. Edits: Modeling and mitigating data bias for graph neural networks. In Proceedings of the ACM Web Conference 2022, pages 2022.
[43] Farzan Masrour, Tyler Wilson, Heng Yan, Pang-Ning Tan, and Abdol Esfahanian, Bursting the filter bubble: Fairness-aware network link prediction. In Proceedings of the AAAI conference on artificial intelligence, volume 34, pages 841-848, 2020.
[44] Enyan Dai and Suhang Wang. Learning fair graph neural networks with limited and private sensitive attribute information. IEEE Transactions on Knowledge and Data Engineering, 2022.
[45] Jian Kang. Jingrui He, Ross Maciejewski, and Hanghang Tong. Inform: Individual fairness on graph mining. In Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery & data mining, pages 379-389, 2020.
[46] Deli Chen, Yankai Lin, Guangxiang Zhao, Xuancheng Ren, Peng Li, Jie Zhou, and Xu Sun. Topology-imbalance learning for semi-supervised node classification. Advances in Neural Information Processing Systems, 34:29885-29897, 2021.
[47] Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks. In International conference machine learning, pages 1725-1735. PMLR, 2020.
[48] Guangtao Wang, Rex Ying, Jing Huang, and Jure Leskovec. Multi-hop attention graph neural network. arXiv preprint arXiv:2009.1 14302, 2020.
[49] Qitian Wu, Wentao Zhao, Zenan Li, David P Wipf, and Junchi Yan. Nodeformer: A scalable graph structure learning transformer for node classification. Advances in Neural Information Processing Systems, 35:27387-27400 2022.
[50] Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with pytorch geometric. arXiv preprint arXiv: 090302428, 2019.
[51] Meiqi Zhu, Xiao Wang, Chuan Shi, Houye Ji, and Peng Cui. Interpreting and unifying graph neural networks with an optimization framework. In Proceedings of the Web Conference 2021, pages 1215-1226. 2021.
[52] Yao Ma, Xiaorui Liu, Tong Zhao, Yozen Liu, Jiliang Tang, and Neil Shah. A unified view graph neural networks as graph signal denoising. In Proceedings of the 30th ACM International Conference on Information & Knowledge Management, pages 1202-1211, 1, 2021.
[53] Liang Yang, Chuan Wang, Junhua Gu, Xiaochun Cao, and Bingxin Niu. Why do attributes propagate in graph convolutional neural networks? In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 4590-4598, 2021.
13

---

Appendix
A Preliminary Study
In this section, we first present comprehensive of experimental results, showcasing the per- formance disparity across various GNNs concerning three metrics related to Label Distance Bias: Degree, Shortest Path Distance, and Label Proximity Score. Subsequently, nation of label position bias to additional GNNs, including ReNode [46], GCNII [47]. JKNet (23) MAGNA 48). and NodeFormer [49. We begin with an introduction to the first study.
extend exami-
A.1 The performance disparity of GNNs across three metrics
Datasets. We selected three representative datasets for our experiments: Cora, CiteSeer, and PubMed. For each of these datasets, worked with three different labeling rates: labels per class, 20 labels per class, and 60% labels per class. For the data splits consisting of and 20 labels per class, we adopted commonly used setting (50) that randomly selects 500 nodes for validation and 1000 labels for testing. When dealing with a labeling rate of 60%, we randomly selected 20% nodes for validation and another 20% for testing.
Models. Our study also incorporates three representative models: APPNP [8], GCN 17 and Label Propagation [9]. APPNP, a decoupled GNN, directly leverages the PPR matrix for feature propagation. On the other hand, GCN, coupled GNN, uses the original adjacency matrix for feature propagation across each layer. Label Propagation relies solely graph structure and labeled nodes for prediction. For all the models, we select their best hyperparameters based on the search space in their original papers.
Experimental Setup. For both Degree and Shortest Path Distance metrics, we employ their actual values, [1, 2, 3, 4, 5, 6, 7], to segregate nodes into separate sensitive groups, considering only handful of nodes possess a degree or shortest path Distance greater than seven. We delete the groups with only few nodes. For the Label Proximity Score (LPS), we divided the test nodes evenly into seven sensitive groups based on their LPS,, each group possessing a uniform range. It's important to note that also filtered out outliers, particularly those with significantly larger LPS than the rest. Additionally, if group contained only a few nodes, we merged it with adjacent groups.
0.95
1.0
0.95
0.9
0.85
0.8
0.85
Accuracy
Accura a
0.7
Accuracy
066
0.75
0.75
0.5
0.4
0.65
0.65
0.60
1234567
1234567
1234567
0.2
1234567 1234567 1234567
0.60
1234567
1234567 1234567
(a) Degree
(b) Shortest Path Distance
(c) Label Proximity Score
Figure APPNP with 20 labeled nodes per class.
0.90
0.90
Ciwer
Accuracy
Accuracy
0.7
Accuracy
0.80
0.80
0.6
0.5
0.70
0.70
0.60
1234567
1234567
1234567
02
1234567 1234567 1234567
0.60
3234567
1234567 1234567
(a) Degree
(b) Shortest Path Distance
(c) Label Proximity Score
Figure 6: GCN with 20 labeled nodes per class,
14

---

0.9
0.9
0.8
0.8
Accuracy
Accuracy
0.7
Accuracy
0.7
0.6
0.6
0.8
0.3
0.5
0.4
0.4
0.3
03
0.2
1234567
1234567
1234567
1234567
1234567 1234567
0.2
1234567
1234567 1234567
(a) Degree
(b) Shortest Path Distance
(c) Label Proximity Score
Figure 7: LP with 20 labeled nodes per class.
1.0
1.00
0.95
LAve
0.90
0.90
Accuracy
0.8
Accurac
0.85
Accuracy
0.85
0.80
0.80
0.7
0.75
0.75
0.70
0.70
0.6
0.55
0.65
0.5
1234567
1234567 1234567
0.60
1234567
1234567 1234567
0.60
1234567
1234567 1234567
(a) Degree
(b) Shortest Distance
(c) Label Proximity Score
Figure 8: APPNP with 5 labeled nodes per class.
1.0
1.00
1.00
0.95
0.95
0.9
0.90
0.90
Accuracy
0.8
0.85
0.85
0.80
0.80
0.75
0.75
0.70
0.70
0.6
0.65
0.65
0.5
1234567
1234567
1234567
0.60
1234567
1234567 1234567
0.60
1234567
1234567 1234567
(a) Degree
(b) Shortest Path Distance
(c) Label Proximity Score
Figure 9: GCN with 5 labeled nodes per class.
0.9
0.8
Accuracy
0.7
Accuracy
0.6
0.6
0.5
0.5
0.4
0.4
0.3
0.2
1234567
1234567
(a) Degree
(b) Shortest Path Distance
(c) Label Proximity Score
Figure 10: LP with labeled nodes per class.
1.0
1.0
0.9
0.9-
Accuracy
0.8
0.7
Accuracy
0.8
0.7
0.7
1234567
1234567 1234567
1234567 1234567 1234567
12345678
1234567 1234567
(a) Degree
(b) Shortest Path Distance
(c) Label Proximity Score
Figure 11: APPNP with 60% labeled nodes per class.
15

---

1.0
1.0
1.0
0.9
0.9
0.9
0.8
Accuracy
Accurag
0.7
Accuracy
0.8
0.6
0.3
0.4
0.6
0.6
0.5
1234567
1234567
1234567
02
1234567
1234567 1234567
0.5
1234567 1234567 1234567
(a) Degree
(b) Shortest Path Distance
(c) Label Proximity Score
Figure 12: GCN with 60% labeled nodes per class.
0.9
Padka
Accuracy
Accuracy
0.8
B
0.8
0.7
0.5
0.7
0.6
0.6
0.5
1234567
1234567
1234567
1234567 1234567 1234567
0.5 1234567
1234567 1234567
(a) Degree
(h) Shortest Path Distance
(c) Label Proximity Score
Figure 13: LP with 60% labeled nodes per class.
Our analysis of the results above leads us to the following key observations:
Label Position Bias is a widespread phenomenon across all GNN models and datasets. Classifi- cation accuracy exhibits substantial variation between different sensitive groups, with discernible patterns.
When contrasted with Degree and Shortest Path Distance, the proposed Label Proximity Score consistently shows a robust correlation with performance disparity across all datasets and models. This underscores its efficacy
measure of Label Position Bias.
The severity of Label Position Bias more prominent when the labeling rate low, such as with 5 or 20 labeled nodes per class. However, with labeling rate of 60% labeled nodes per class, the bias becomes less noticeable. This evident from the fact that the shortest path distance is either or for all datasets, implying that all test nodes have least labeled node within their two-hop neighbors.
A.2 Label Position Bias of different GNNS
We further select 4 more GNNs, i.e., ReNode 46 GCNII 47 transformer-based model, i.e., and NodeFormer to further verify the Label Position Bias.
JKNet 23 and MAGNA 48 and
0.90
Tank
1.0
JOWN
0.85
0.80
NAOIA
Accuracy
0.9
Accuracy
0.75
0.70
0.8
0.65
0.60
0.55
0.6
1234567 1234567 1234567 1234567 1234567
0.50
1234567
1234567 1234567 1234567 1234567
Label Proximal Score Group
Label Proximal Score Group
(a) Cora
(b) CiteSeer
Figure 14: The label position bias of different GNNs.
16

---

From the above results, we can find all the selected GNNs suffer from the label position bias issue. However, the graph transformer model, i.c., NodeFormer, demonstrates small label position bias on the CiteSeer dataset.
These findings highlight the importance of further exploring Label Position Bias and developing strategies to mitigate its impact on GNN performance.
B Understandings
Remark 3.1 The feature aggregation using the learned graph structure B directly as a propagation matrix, i.e., F = BX, is equivalent to applying the message passing in GNNs using the original graph if B is the approximate exact solution the primary problem defined in Eq. without constraints.
Proof. There are several recent studies [5] 52 53 unified the message passing in different GNNs under an optimization framework. For instance, Ma et al. [52 demonstrated that the message-passe passing scheme of GNNs, such as GCN [17, GAT [31], PPNP and APPNP [8], can be viewed as optimizing the following graph signal denoising problem:
arg min L = |X - -IP A Ar(F (LFF. FERexd
where E gnxd is the node features, F is the optimal node representations after applying GNNs, and À are used control the feature smoothness. The gradient of ac be represented as: OF
Uc OF
2(F X) + 2XLF.
Here, we provide two examples of using the Eq. 7 to derive APPNP and GCN. For APPNP, we can adopt multiple-step gradient descent solve the Eq. 77:
OL
F = F
(1
2A 2 + 2X-AFt +2
OF
If we set the stepsize y 2(1 then we have the following update steps:
1 1+X
F
A A
X
which is the message passing scheme of APPNP. Then, if we propagate K layers, then
FK
À
ÄFK-L
X
I+x
ÁFK-2
X
x
1+I
1+1
I+
(8)
-(G
AK
K-1
Σ
14
A 1
)
For GCN, we can use one step gradient to solve the Eq.
X
7 OF
= --12 27AAX.
F-X
we set the step size XX then the F Ax, which is the message passing of GCN.
The primary problem defined in Eq. (2) without constraints can be represented as:
arg min L = I + Atr LB).
(9)
B
Comparing Eq. with Eq. ( the only difference lies the first term, where the feature matrix X is set to be identity matrix I. Then, we can follow the same steps to solve the Eq. (9)
17

---

If we use the multiple-step gradient descent with the stepsize 2(1+A) then we have the following
update steps:
B A
AB*11
I.
1+1
1+
Then, for K steps iteration, BK will be:
B ((+t)
K
AK
K-1
Σ Y+1
)
(10)
which is the propagation matrix of APPNP in Eq. As result, the message passing of APPNP can be written as F BX.
If we use one-step gradient descent to solve Eq. (9), then B can be represented as:
0L
- 2- 2y
ÖB B-1
If we set the step size 1 represented by F BX.
then the B = Å. As result, the aggregation in GCN can also be
2X.
Proposition B.1. The influence scores from all labeled nodes to any unlabeled node will be the equal,
i.e., EjEv, I()) = c, when using the unbiased graph structure B obtained from the optimization
problem in Eq. 2 as the propagation matrix in GNNs.
Proof. Following the definition in 23 the influence of node j on node can represented by where h, is the representation of node i, xj is the input feature of node j. and 8xy
I,())
Sh,
0h: 0x,
represents the Jacobian matrix.
If we use the unbiased graph B as the propagation matrix, then H = BX. Thus, b.j EE B
The Jacobian matrix
8hg Ox,
can be written as:
Th,
Diag (B.j. B.j...., Bū]]),
(1I)
0x,
where Diag represents the diagonal matrix. As result, 4(5) sum
ah. 8x,
nBB...
Suppose the constraint BT1, is satisfied, then the influence scores from all labeled nodes to the unlabeled node i can be represented as:
Σ
L() Σ nB rBT1,
(12)
JEVI
JEV.
Finally, the influence scores from all labeled nodes to any unlabeled node equal.
C Datasets Statistics
In the experiments, the data statistics used in Section are summarized in Table For Cora, CiteSeer and PubMed dataset, we adopt different label rates, i.e., 5, 10, 20, and 60% labeled nodes per class, to get a more comprehensive comparison. For label rates 5, 10, and 20, we use 500 nodes for validation and 1000 nodes for testing. For label rates of 60% labeled node per class, we use half of the rest nodes for validation and the remaining half for the test. For each labeling rate and dataset, we adopt 10 random splits for each dataset. For the ogbn-arxiv dataset, follow the original data split.
18

---

Table 6: Dataset Statistics.
Dataset
Nodes
Edges
Features
Classes
Cora
2,708
5,278
1,433
CiteSeer
3,327
4,552
3,703
PubMed
19,717
44,324
500
Coauthor CS
18,333
81,894
6,805
15
Coauthor Physics
34,493
247.962
8,415
Amazon Computer
13,381
245,778
767
10
Amazon Photo
7,487
119,043
745
Ogbn-Arxiv
169,343
1,166,243
128
D Hyperparamters Setting
In this section, we describe in detail the search space for parameters of different experiments.
For all deep models, we use transformation layers with 256 hidden units the ogbn-arxiv dataset and 2 transformation layers with 64 hidden units for other datasets. For all methods, the following common hyperparameters are tuned based on the loss and validation accuracy from the following search space:
Learning Rate: [0.01, 0.05)
Dropout Rate: {0, 0.5, 0.8)
Weight Decay: (0, 5e-5, 5c-4]
For APPNP and Label Propagation, we tune the teleport probability a in (0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8. 0.9). For GRADE we set the hidden dimension 256, the temperature (0.2, 0.5, 0.8, 1.1, 1.5, 1.7, 2), which covers all the best values in their original paper. For SRGNN we set the weight of CMD loss (0.1, 0.5, 1, 1.5, 2).
For the proposed LPSL, we set the c in the range [0.7, 1.31, P in {0.01, 0.001), ), in (0.01, 0.001). B in (le-4, le-5, 5e-5, le-6, 5e-6, le-7). For the LPSLAPPNP we À in (8, 10, 11, 12, 13, 14, 15). For the LPSLGCN, we set À in (1, 2, 3, 4, 5, 6, 7, 8).
E Node Classification Results
For the semi-supervised node classification task, we choose nine common used datasets including three citation datasets, i.e., Cora, Citeseer and Pubmed [27], two coauthors datasets, i.e., CS and
Physics, two Amazon datasets, i.e., Computers and Photo 28 and one OGB datasets, i.e., ogbn-arxiv
229]
To the best of our knowledge, there are no previous works that aim to address the label position bias. In this work, we select three GNNs, namely. GCN [17], GAT (3I) and APPNP [18] two Non-GNNs. MLP and Label Propagation [19]. as baselines. Furthermore, we also include GRADE (2), method designed mitigate degree bias. Notably, SRGNN (33 demonstrates that if labeled nodes are gathered locally, it could lead to an issue of feature distribution shift. SRGNN aims to mitigate the feature distribution shift issue and also included baseline. The overall performance are shown in Table 7
F Ablation Study
In this subsection, explore the impact of different hyperparameters, specifically the smoothing term and the constraint c, on our model. We conducted experiments on the Cora and CiteSeer datasets using ten random data splits with 20 labels per class. The accuracy of different and values for APSL and LPSL on the Cora and CiteSeer datasets are illustrated in Figure
19

---

Table 7: The overall results of the node classification task.
OCN
APNN
GRADE
SKONN
Lareer
59.23
2.52
67.87
79.1
$2.34 0.67
81
1.41
a 1:49
78,2 1.775
82.74
1.01
83.24
60%
76.49
1.13
M6.5
1:35
18.00
88.8 1.13
26.82
W7.17 0795
58.75
M8.22
41:05
m 2.84
10.06
+ 1.53
61.27 1.85
63.92
62,00 3.34
63.03 361
3414+1411
2.46
65.70
2.15
Cisckeer
20
10
41.99 2.71
56.96
= 1880
4:229
2.31
06.28
69:00 1.67
2:111
67.57 2.05
70.85 145
2..8
69:66.11.47
6.22
67.50 1.76
27.9
69.13
61.73
70.73 1.32
68.76
71.15
1.77
1.14
80%
73.15 1.66
6 2:01
76.88 6
77.42.
7
74,00
74.57 1:55
77.18 1.64
77.56
1.44
PohMed
75.67
23.12:22.77
0
0.4
0.
90.86
0.45
80.45+067
89
Physas
88.30
1.39
36.00
03.25
0.380
1144
01.3+033
9306 11.50
Compulers
20
60.66
2.98
19.17
79.07
2:34
1..28
2:30
76.5122155
00.05:22
19.38
Plato
20
15 1.91
44
WART 1.14
0017
89.66
90.85
1.66
WOTTT1
7000
70.1
71.110000
OOST
DOM
09:0010:25
and Figure F respectively. From the results, find both APSL and LPSL,GN not very sensitive to À and at the chosen regions.
85
Accuracy
80
Accuracy
75
75
Cora Gaten
Car Older
Lambda
Lembda
(a) LPSLAPPNP
(b) LPSLGEN
Figure 15: The accuracy of different for LPSL and LPSLGGN on Cora and CiteSeer datasets.
85
Accuracy
Accuracy
75
70
0.7
0.8
0.9
1.1
1.2
1.3
0.7
08
0.9
1.1
1.2
1.3
Lambda
Lambda
(a) I.PSL
(b) LPSL
Figure 16: The accuracy of different for LPSLAPPNP and LPSLGCN Cora and CiteSeer datasets.
20


Reviews:
[{"review_id": "gg6MXql59B", "reviewer": "Reviewer_VK13", "summary": "This paper presents a new bias problem on graph neural networks: label position bias, which implies that nodes perform better closer to labeled nodes. A new metric - the Label Proximity Score(LPS) is proposed to quantify this bias, and a new optimization framework is proposed to learn a new unbiased graph structure. This framework motivates all nodes to have the similar LPSs and is experimentally shown to alleviate the label position bias problem and improve model performance.\n", "questions": "Please see the above", "limitations": "In the paper, the authors mention that the existing methods may not scale to heterophily graphs.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1) This paper mines a novel problem on GNNs: label position bias. This is a valuable problem, which can help us better understand the role of labeled nodes for test nodes.\n2) The newly proposed metric label proximity score can measure the importance and influence of test nodes and labeled nodes, and the experiments in the paper show that certain trends can be identified by the label similarity score compared to the degree and shortest path distance.\n3) The extensive experimental evaluation shows that LPSL not only outperforms standard methods but also significantly alleviates the label position bias in GNNs. This work could stimulate further research and development of methods aimed at enhancing label position fairness in GNNs.\n", "weaknesses": "1) The proposed label position bias problem is similar to Topology-Imbalance Node Representation Learning, which has not been mentioned in related works, and I do not understand the difference between the two problems.\n\nChen, Deli, et al. \"Topology-imbalance learning for semi-supervised node classification.\" Advances in Neural Information Processing Systems 34 (2021): 29885-29897.\n\n2) In the design of the framework only the new unbiased graph structure is calculated and its contribution may not be sufficient enough to even do ablation experiments to verify the role of the different parts.\n3) The authors believe that the graph structure can solve the label position bias problem by ensuring that the LBS of each node is similar in the proposed framework, in order to fairness of all nodes. But there is confusion about this, is it possible that unfair LBS will get better results? Each node has different structural characteristics and has different relationships with labeled nodes. For example, for nodes with high degree and strong association with labeled nodes, or nodes with high degree and weak association with labeled nodes, is it necessary to distinguish between the former type of nodes, whose labels are more credible. Does the model get better performance if the degree or the shortest path distance is taken into account together with the label position bias problem?\n\nTypos:\n1) Reuse of symbols. The lowercase letter c is defined as the number of classes in Section 2, which in turn is defined as the hyperparameter serving as the uniform Label Proximity Score in Equation 2.\n2) In line 312 the reference of the figure should be 4 instead of 4.4.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear reviewer,\n\nWe appreciate your constructive feedback. We are pleased to provide detailed responses to address your concerns. \n\n**Q1: What is the difference between the Topology-Imbalance Node Representation Learning (TINL) and our proposed Label Position Bias (LPB) problem?**\n\n**A1:**  **TINL** operates on the premise that the labeled nodes have different importance with respect to the decision boundaries.\nSpecifically, if two nearby labeled nodes belong to different classes, they might exert conflicting influences. The ReNode method will decrease the weight of these nodes. However,  **LPB** doesn’t hinge on the classes of the labeled nodes or the different importance of labeled nodes. Instead, it focus on the performance disparity of different groups of test node with different proximal distance to the labeled nodes.\n\nAlthough both TINL and LPB consider the influence of labeled nodes, they focus on different perspectives. TINL\ngrapples with influence conflicts due to class disparities of neighboring labeled nodes. Conversely, LPB delves into biases\ntriggered by varying levels of influence from the labeled nodes.\n\nWe also conduct experiments using the proposed ReNode method for TINL. In Figure 1 of the rebuttal pdf file, the ReNode method still suffers from the label position bias problem.\n\n**Q2: The contribution is insufficient only with the new unbiased graph structure learning.**\n\nIn this work, we first identify a novel bias in GNNs: the Label Position Bias (LPB), quantifiable using our introduced label proximal score. This bias results in unequal predictions for distinct test nodes, which could lead to an unfairness issue. To alleviate the problem, we propose a\nsimple yet efficient method to learn an unbiased graph structure. However, graph structure learning would lead to a dense matrix, which limits the graph scale. We design an efficient sparse graph structure learning algorithm, which can be applied to large graphs. The learned unbiased graph structure can be easily incorporated into different GNNs. We add more GNN backbones, i.e., GCNII and JKNet. From the results in Tabel 2 of the main paper and Table 1 of the rebuttal pdf file, our method not only can improve the overall performance but also alleviate the label position bias and improve fairness over different GNNs.  \n\n**Q3: Is it possible that unfair LPS will get better results?**\n\n**A3:** Yes, it is possible that an unfair label proximal score (LPS) could have a higher performance. The LPS can measure the proximal distance of a test node to all labeled nodes, which can be understood as the influence from labeled nodes. A fair LPS means the graph structure is fair with respect to the position of labeled nodes. However, a fair graph structure can't guarantee better performance. For example, a fully connected graph may not work well, although it is fair. During our experiments, we found some graph structures can lead to lower label position bias, but result in a worse performance. Here is one example:\n\n|             | ACC          | WDP    | WSD    | WCV    |\n|-------------|--------------|--------|--------|--------|\n| Original    | 82.34 ± 0.67 | 0.0497 | 0.0616 | 0.0732 |\n| FairGraph 1 | 81.90 ± 1.13 | 0.0322 | 0.0411 | 0.0503 |\n| FairGraph 2 | 83.24 ± 0.75 | 0.039  | 0.0476 | 0.0562 |\n\nThe learned FairGraph1 perform worse than the original unfair graph but has a better fairness respect to the label position bias.\n\n**Q4: Does the model get better performance if the degree or the shortest path distance\nis taken into account together with the label position bias problem?**\n\n**A4:** It is highly possible that our model can perform better, incorporating some methods that can alleviate the degree or the shortest path distance. However, there is no work to address the shortest path distance bias. And the works related to degree bias all need the discrete degree. Thus, it is hard to combine the proposed LPSL with these methods.\n\nIndeed, the proposed label proximal score already takes the degree and shortest path distance into account. The node with a higher degree and shorter distance to labeled nodes tends to have a higher label proximal score. Our proposed method can make sure each node has the same label proximal score, which implicitly addresses the degree and shortest path distance bias. Experimental results in Tables 3 \\&4 of the main paper demonstrate our method can mitigate the degree and shortest path distance bias.\n\n**Q5: Typos.**\n\n**A5*:* Thank you for highlighting the Typos. We appreciate the feedback and will thoroughly review and revise our paper to address them.\n\nWe hope that we have addressed the concerns in your comments, and please\nkindly let us know if there is any further concern, and we are happy to clarify.\n\n\n\n\n"}, {"review_id": "rK95hoMKIS", "reviewer": "Reviewer_Lj4a", "summary": "This paper pointed out that message-pass based GNNs training usually suffers from label position bias problem for semi-supervised node classification especially for quite few-shot settings. That is, the unlabeled nodes which far away from the labeled ones might suffer from performance degradation. \n\nThe paper first proposed a new metric named “Label Proximity Score” based on PPR matrix to measure label position bias, and then put forward a label unbiased graph learning method by learning a dense graph structure to guide the graph representation learning, the dense matrix will mitigate the label position bias.", "questions": "1.Introducing l1 norm will sparse the induced matrix B and increase the computation efficiency, however, it seems that sparsity also diffs different nodes. Does sparsity make a tradeoff to relieve label position bias? Does this sparsity find better aggregation patterns? Does unbiased graph structure mean a dense induced matrix?\n2. How to get the sensitive groups with respect to different bias metrics (Degree, Shortest Path Distance and Label Proximity scores)? Is the distribution of labeled node number balance among different groups?\n3.The performance of GNNs over graph with few node labels heavily depends on the graph split, how to split the graphs to conduct experiments in this paper?", "limitations": "1.Backbone GNNs are limited and lack of deep insight of the cause of label position bias.\n2.Some important references are missing. For example, it is noted that GNNs might be not sensitive to position representation learning (Position-aware Graph Neural Networks). This is another kind of position bias, what is the connection of label position bias to such position embedding learning?", "rating": 5, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1.Induced bias in GNNs for graph representation learning is one challenge problem which affects the fairness or robustness of down-streaming supervised learning tasks. The paper first found out the phenomenon that label position bias in GNNs (especially for one-hop neighbor message passing based GNNs) for node classification task. A quantified metrics is proposed to measure label position bias.\n\n2.A position unbiased graph representation learning framework is proposed by learning a dense matrix to guide feature aggregation to mitigate the position bias. Meanwhile, the paper also gave analysis of the induced dense matrix to connect with existing PPR based APPNP.", "weaknesses": "1.Lack of the analysis of the root to cause label position bias in GNNs over node classification. For example, the nodes being far away from the labeled ones requires deep GNNs to receive label information. The performance degradation might due to shallow GNNs with limited receipt field or deep GNNs suffering from over-smoothing or over-squashing. \n\n2.More backbone GNNs should be evaluated to support the phenomena of Label Position Bias. GCN is a kind of one-hop neighboring based message passing which might suffer from over-smoothing to multi-hop neighbor information aggregation. Although APPNP can aggregate multi-hop neighbor information, it is sensitive to selection of iteration number K and re-start probability parameter alpha. \n\nIt is better to select some GNNs (such as JKNet, Multi-hop Attention Neural Networks etc.) which is robust to over-smoothing or other dense matrix based GNNs (such as Graph Transformer)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear reviewer,\n\nWe appreciate your constructive feedback. We are pleased to provide detailed responses to address your concerns.\n\n**Q1: What is the root to cause the label position bias in GNNs? The performance degradation might due to shallow GNNs or deep GNNs suffering from over-smoothing or over-squashing.**\n\n**A1:** Thanks for your thorough consideration. We attribute the root cause of label position bias to the inherent message passing in most GNNs. Please refer to the **Common Concern 1** in our global response.\n\nBesides, the performance degradation may not be due to the shallow GNNs or the deep GNNs with over-smoothing. First, both shallow and deep GNNs suffer from label position bias. Second, deep GCNII and JKNet are not suffering from over-smoothing, but they still have bias issues. Whether the reason is due to the over-squashing is still under exploration. However, the message passing with the unfair graph structure should be one of the reasons. \n\n**Q2: More backbone GNNs should be evaluated to support the phenomena of Label Position Bias.**\n\n**A2:** We've selected 4 more GNNs, i.e., ReNode, GCNII, JKNet, and MAGNA (Multi-hop Attention Neural Networks),  and 1 transformer-based model, i.e., NodeFomer. From Figure 1 in our rebuttal pdf file, all GNNs suffer from the label position bias issue. However, the NodeFomer has a small label position bias. More explanation can be found in the **Common Concern 1**.\n\n**Q3: Does sparsity make a tradeoff to relieve label position bias?**\n\n**A3:** Thanks for this great suggestion that motivates us to explore the relationship between sparsity and label position bias by conducting experiments using both APPNP and GCN models on the Cora datasets, varying the sparsity of matrix B.\nTable 2 of our rebuttal pdf file shows that fairness metrics remained consistent across all sparsity levels. This suggests that the sparsity introduced by the l1 norm doesn’t significantly impact our method’s efficacy in addressing\nlabel position bias.\n\n**Q4: Does this sparsity find better aggregation patterns?Does unbiased graph structure mean a dense induced matrix?**\n\n**A4:** In Table 2 of the rebuttal pdf file, we can conclude that sparsity may affect the model performance. The\naccuracy with 80\\% and 90\\% sparsity closely aligns with that of the dense matrix. However, as sparsity approaches 95\\%,\nthere’s a minor decline in accuracy, similar to the results of PPRGo [1].\n\nA sparse structure matrix can also be an unbiased graph structure. We can use the difference of the label position score among different nodes to measure whether a graph structure is fair or not. During the experiments, we find the loss $\\|\\mathbf{B T} \\mathbf{1}_n -c \\mathbf{1}_n\\|^2 < 0.05$ on Cora dataset, which is comparable to the dense B matrix.\n\n\n[1] Bojchevski, Aleksandar, et al. \"Scaling graph neural networks with approximate pagerank.\" KDD 2020.\n\n**Q5: How to get the sensitive groups? Is the distribution of labeled node numbers balanced among different groups? **\n\n**A5:** We categorize nodes into sensitive groups based on the same interval length related to the specific metrics. For both degree and shortest path distance, we employ an interval of 1 as the criterion. This means that nodes sharing the same degree or shortest path distance are grouped together, forming a distinct sensitive group. For the Label Proximal Score (LPS), which is a continuous value, we also adopt a uniform interval approach. Specifically, we determine the maximum and minimum LPS values and divide this range into equal-length intervals, placing nodes into groups accordingly.\n\nWe kindly point out that labeled nodes are not categorized into sensitive groups. Our primary objective in utilizing sensitive groups is to assess the performance of test nodes. Moreover, due to our use of equal-length intervals, the distribution of unlabeled nodes across different groups is not balanced.\n\n\n**Q6: How to split the graphs to conduct experiments?**\n\n**A6:** The choice of data splits can indeed influence models' performance. As a result, we employ 10 random data splits for each dataset in our experiments. For every data split, we train the model 3 times to ensure robust and consistent results.\n\n**Q7: What is the connection of label position bias to position embedding learning?**\n\n**A7:** The position embedding learning aims to distinct nodes with the same structure, which may get the same representations by GNNs. It can improve the expressiveness of GNNs and is useful for tasks that require unique representations for node pairs, such as link prediction. The label position bias zeroes in on the unfairness introduced due to the positions of labeled nodes in the node classification task. It is mainly due to the unfair graph structure and unrelated to the expressive power of GNNs.\n\nWe hope that we have addressed the concerns in your comments, and please\nkindly let us know if there is any further concern, and we are happy to clarify."}, {"review_id": "zUCaPlACiN", "reviewer": "Reviewer_fFnJ", "summary": "This paper demonstrates a new bias in GNN models called label position bias. A metric called the Label Proximity Score is introduced to quantify the bias. The paper proposes a framework to learn an unbiased graph structure, which can be applied to existing GNN models.", "questions": "1. In the LPSL problem in (2), is there any constraint that the entries of B have to be non-negative? How do you interpret negative entries?\n\n2. The constraint in (2) mimics (1) but the optimal solution B is not equal to P (unless the constraint is absent). How does B mitigate the LPS issue identified in Figure 3? There are no experimental results (taking the optimal B found as the adjacency matrix) showing this, which is the motivation for the paper.\n\n3. The definition of the influence I_i(j) is incorrect. From [23], it should be the sum of the absolute values of the entries of the Jacobian. How does this affect the proof in the appendix? Furthermore, it is difficult for the reader to guess what \"sum\" notation means. \n\n4. Same issue in (5) as Q1.\n\n5. Is label position bias apparent in heterophily graph datasets like Chameleon and Squirrel? \n\n", "limitations": "N.A.", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Label position bias is an interesting phenomenon uncovered by the authors. This has important fairness implications in GNN model training. ", "weaknesses": "1. The label position bias is demonstrated empirically. It would be good if the authors can give an explanation for why this phenomenon occurs. Is this issue present in *all* GNN models inherently?\n\n1. There are no statistical significance tests done to verify that the observed label position bias is indeed statistically significant. \n\n1. More insights can be gained if the LPSL unbiased B can be tested using more diverse GNN models.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear reviewer,\n\nWe appreciate your constructive feedback. We are pleased to provide detailed responses to address your concerns.\n\n**Q1: Why the label position bias phenomenon occurs?**\n\n**A1:** Thanks for your thorough consideration. We attribute the root cause of label position bias to the inherent message passing in most GNNs. Please refer to the **Common Concern 1** in our global response.\n\n**Q2: Whether the observed label position bias is indeed statistically significant?**\n\n**A2:** To validate the statistical significance of the observed label position bias, we undertook rigorous testing. Experiments were conducted using GCN and APPNP models on both the Cora and CiteSeer datasets, with each experiment being executed\n10 times. Subsequently, a t-test was performed for each pair of groups. Figure 2 of our rebuttal document shows that the\nmajority of p-values fall below the 0.05 threshold. Only a few of adjacent groups deviated from this trend. These results strongly affirm that the label position bias is indeed statistically significant.\n\n**Q3: More insights can be gained if the LPSL unbiased B can be tested using more diverse GNN models.**\n\n**A3:** Thanks for the suggestions. We add the GCNII and JKNet backbones. Please refer to the **Commen Concern 2** in our global response.\n\n\n**Q4: Does the matrix B in Eq. (2) have negative entries?**\n\n**A4:** Thank you for your thoughtful question. The matrix B should be non-negative as it represents a fair graph structure. And the non-negative constraint should be added to our problem. However, in our practical observations, most B matrices do not contain negative entries. For instance, within our explored hyperparameter space for the Cora dataset, no instances of B had negative values. In the case of the CiteSeer dataset, negative entries in B were exceedingly rare, occurring only when the coefficient c in Eq.(2) was particularly small. Even then, the largest negative value observed was a mere -0.002. For a clearer perspective, we present the following results comparing scenarios with and without negative values:\n\n|        | With Negative | Without Negative |\n|--------|---------------|------------------|\n| Case 1 | 70.82 ± 1.50  | 70.79 ± 1.55     |\n| Case 2 | 70.45 ± 1.48  | 70.60 ± 1.57     |\n\nThe performance gap between scenarios with and without negative values is minimal.\n\n**Q5: How does B mitigate the LPS issue?**\n\n**A5:** The learned fair graph structure B can ensure each test node possesses an identical LPS. By utilizing the optimal B during the propagation process, we ensure that each node receives consistent influence from all labeled nodes, thereby addressing the LPS issue. \n\nTo verify that the learned B can mitigate the LPS issue, we adopt three representative group bias measurements, i.e., WDP, WSD, and WCV. The small value means that the performance difference between groups is small, which is more fair. From the results in Table 2 of our main paper and Table 1 of the rebuttal pdf, our proposed method can alleviate the LPS for all GNNs, including GCN, APPNP, GCNII, and JKNet.\n\n**Q6: How does the lack of absolute operator for the Jacobian affect the proof in the appendix? The \"sum\" notation is confusing.**\n\n**A6:} We appreciate your observation regarding the definition of the influence $I_i(j)$. However, as stated in $A4$, the B should be non-negative. With a positive B matrix, the omission of the absolute operator does not impact the proofs provided. \n\nWe will ensure clarity in our revision to avoid any confusion regarding the \"sum\" notation or other aspects.\n\n**Q7: Is label position bias apparent in heterophily graph datasets like Chameleon and Squirrel?**\n\n**A7:** We undertook tests to assess the label position bias on both the Chameleon and Squirrel datasets. The findings, as detailed in Figure 3 of our rebuttal document, are quite interesting.\n\nFor the Chameleon dataset, nodes exhibiting higher LPS paradoxically tend to underperform, aligning with the heterophily hypothesis. Conversely, nodes with a lower LPS also demonstrate diminished performance. This suggests that the label position bias is indeed conspicuous within the Chameleon dataset. However, such a bias is not obvious in the Squirrel dataset as all groups have similar performances. We will do further explorations for the LPS issue on the heterophily datasets.\n\nWe hope that we have addressed the concerns in your comments, and please\nkindly let us know if there is any further concern, and we are happy to clarify.\n"}, {"review_id": "WdpDTqAiRy", "reviewer": "Reviewer_tP9u", "summary": "This paper presents a study on Label Distance Bias in Graph Neural Networks (GNNs). The authors investigate the performance disparity across various GNN models on three datasets and analyze three metrics related to Label Distance Bias. The study reveals that Label Position Bias is a significant factor affecting the performance of GNNs. The proposed Label Proximity Score consistently exhibits a robust correlation with performance disparity. The findings highlight the importance of further exploring Label Position Bias and developing strategies to mitigate its impact on GNN performance. The paper provides valuable insights into the performance variation of GNNs and underscores the need for addressing Label Distance Bias to enhance the effectiveness of GNN models.", "questions": " 1. Can the proposed method effectively mitigate label position bias in datasets with imbalanced class distributions?\n\n2.  What are the limitations of the selected baseline models (GCN, GAT, APPNP, MLP, Label Propagation) in addressing label position bias?\n\n3.  How does the proposed method compare to existing methods in terms of computational efficiency?\n\n 4. Can the proposed method be applied to larger and more complex datasets, and if so, how does its performance scale?\n\n \n\n \n", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper offers three key advantages in its study on Label Distance Bias in Graph Neural Networks (GNNs). \n\nFirstly, it identifies Label Position Bias as a widespread phenomenon across all GNN models and datasets, highlighting the importance of understanding and addressing this bias in GNN performance. \n\nSecondly, the paper introduces the Label Proximity Score as a metric that consistently shows a robust correlation with performance disparity. This score proves to be an effective measure of Label Position Bias, outperforming Degree and Shortest Path Distance metrics. \n\nLastly, the study demonstrates that the severity of Label Position Bias is more prominent at lower labeling rates, but becomes less noticeable when 60% of nodes per class are labeled. This finding provides insights into the impact of labeling rates on bias and suggests strategies for mitigating its effects. ", "weaknesses": "\nAlthough your paper presents well and the proposed method seems to be very targeted towards relevant issues, I cannot determine the actual performance of your work as you have not provided any code.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear reviewer,\n\nWe appreciate your constructive feedback. We are pleased to provide detailed responses to address your concerns.\n\n**Q1: I cannot determine the actual performance of your work as you have not provided any code.**\n\n**A1:** Thank you for highlighting your concern. We apologize for any confusion. While the code was not directly included in the Supplementary Material, we have provided an anonymous link to the code in Appendix D of our paper.\n\n**Q2: Can the proposed method effectively mitigate label position bias in datasets with imbalanced class distributions?**\n\n**A2:** Thanks for your thoughtful consideration. Our method is primarily designed to address biases stemming from the positions of labeled nodes rather than the categories to which these nodes belong. As such, the class distribution, whether balanced or imbalanced, should not directly impact our method's efficacy in mitigating label position bias.\n\nTo empirically validate this claim, we conducted tests on datasets with imbalanced class distributions, specifically Cora and CiteSeer. Adhering to the setup described in [1], we designated half of the classes as major classes, endowing them with five times as many labeled nodes as the minor classes. The outcomes of these tests are detailed in Table 3 of our rebuttal document. The results consistently show that our method not only enhances overall performance but also effectively curtails label position bias, even in imbalanced scenarios.\n\n\n[1] Chen, Deli, et al. ”Topology-imbalance learning for semi-supervised node classification, NeurIPS 2021.\n\n**Q3: What are the limitations of the selected baseline models in addressing label position bias?**\n\n**A3:** Our investigation has revealed that label position bias is prevalent across a variety of GNNs. (More results can be found in Figure 1 of the rebuttal document) Notably, prior GNN models, including but not limited to GCN, GAT, APPNP, and Label Propagation, exhibit this bias. These models, in their original formulations, do not provide mechanisms to specifically address or mitigate label position bias.\n\n\n**Q4: How does the proposed method compare to existing methods in terms of computational efficiency?**\n\n**A4*:* The essence of our proposed method is to produce a fair graph structure that is seamlessly integrable with existing GNNs. Our method won't change the inherent computational processes of the backbone models. However, if the B is a dense matrix, then it would affect the computational efficiency. As a result, we design a $l_1$-regularized Label Position Unbiased Sparse Structure Learning method to generate a sparse matrix. With the sparse matrix B, there's no significant impact on the backbone models' computational efficiency. \n\n\n**Q5: Can the proposed method be applied to larger and more complex datasets, and if so, how does its performance scale?**\n\n**A5*:* Yes, our proposed method can be applied to larger datasets. For instance, it has been tested and found applicable on the Ogbn-Arxiv dataset. However, it's worth noting that the formulation in Eq. 2 of our paper tends to produce a dense matrix, which might not be optimal for large-scale graphs. To address this challenge, we've introduced the $l_1$-regularized Label Position Unbiased Sparse Structure Learning. To further bolster efficiency, especially for large graphs, we employ the Block Coordinate Descent (BCD) method. This approach is particularly advantageous as it allows us to update just a segment of the structure matrix at any given time, enhancing scalability for larger datasets.\n\nWe hope that we have addressed the concerns in your comments, and please\nkindly let us know if there is any further concern, and we are happy to clarify.\n"}]

Author rebuttal:
# Global Response

We thank the reviewers for the valuable comments and suggestions. We carefully revise our paper and provide responses to address the concerns. In this global response, we are willing to provide information about tables and figures in the rebuttal pdf file and some common concerns.

* Figure 1 is designed to elucidate the label position bias across various models. We've selected a mix of five models for this demonstration: four GNNs—ReNode[1], GCNII[2], JKNet[3], and MAGNA[4]—that adhere to the message-passing scheme, and one graph transformer model, NodeFormer[5]. Our evaluations span both the Cora and CiteSeer datasets. 
* Table 1 showcases the performance and label position bias when using the GCNII and JKNet backbones. We conduct experiments on both Cora and CiteSeer datasets.
* Table 2 illustrates how the performance and label position bias would be affected if using the proposed $l_1$-regularized Label Position Unbiased Sparse Structure Learning. We conduct experiments
    for the GCN and APPNP backbones, utilizing the learned graphs with varying sparsity levels on the Cora dataset. As sparsity intensifies, there's a slight dip in model performance. However, the label position bias remains consistent irrespective of the sparsity level.
* Figure 2 visualizes the results of significance tests conducted to confirm the statistical significance of the observed label position bias. For each experiment, we ran it 10 times and subsequently apply the t-test between every pair of groups. The outcomes reveal that most of the p-values are beneath the 0.05 threshold, a conventional benchmark for statistical significance. It's worth noting that only a minor fraction of adjacent groups did not adhere to this trend. These findings substantiate that the label position bias is statistically significant.
* Figure 3 is designed to explore the presence of label position bias in heterophily graphs. We observe a label position bias for the Chameleon dataset, but its pattern diverges from what we typically see in homophily graphs. Specifically, nodes in close proximity to labeled nodes tend to underperform, aligning with expectations based on the heterophily principle. Conversely, the Squirrel dataset doesn't exhibit a pronounced label position bias.
* Table 3 presents the performance and label position bias of our proposed method when faced with imbalanced class distributions. The results affirm that our method maintains its efficacy and performs commendably in such scenarios.

### **Common Concern 1: What is the root cause of the label position bias in GNNs?**

**Answer:** We attribute the main reason for label position bias to the inherent message passing in GNNs.

**Experimental evidence 1**: From Figure 1 in the rebuttal pdf file and Figure 1, 2, and 3 in our main paper, all 7 models with message passing, such as GCN, APPNP, GCNII, etc, all suffer from label position bias. However, the graph transformer-NodeFormer, which excludes message passing, has a small label position bias.

**Theoretical evidence 1**: The message passing intrinsically ties the representation of test nodes to labeled nodes. As established in [3], the influence score $I_i(j)$ can be employed to gauge the influence from node j to node i. [3] further shows that for a k-layer GCN, the influence distribution $I_x$ for any node corresponds to the k-step random walk distribution initiating from node x. Our conceptualized label proximal score is essentially a sum of the random walk probabilities from all labeled nodes directed toward the target node. An unfair graph structure can then produce inconsistent influences from labeled nodes to different test nodes. 

**Experimental evidence 2:** As highlighted in Proposition 3.1 of our paper, by learning a fair graph structure, we can ensure uniform influence from training nodes to every test node. The experimental results in Table 2 of the main paper and Table 1 of the rebuttal pdf file demonstrate that this equitable influence significantly diminishes the label position bias in various GNNs, such as GCN, APPNP, GCNII, and JKNet.

Based on the above evidence, we believe that message passing with the unfair graph structure should be one of the main reasons.


### **Common Concern 2: More backbone models should be added to verify the proposed LPSL method.**

**Answer:**  We test our proposed LPSL with both the GCNII and JKNet backbones. The results in Table 1 of the rebuttal file indicate that our proposed LPSL method not only amplifies the performance of these backbone models but also effectively mitigates the label position bias. 


[1] Chen, Deli, et al. "Topology-imbalance learning for semi-supervised node classification." NeurIPS 2021.

[2] Chen, Ming, et al. "Simple and deep graph convolutional networks." ICML 2020.

[3] Xu, Keyulu, et al. "Representation learning on graphs with jumping knowledge networks." ICML 2018.

[4] Wang, Guangtao, et al. "Multi-hop attention graph neural network." 

[5] Wu, Qitian, et al. "Nodeformer: A scalable graph structure learning transformer for node classification." NeurIPS 2022.

Meta-review: After the rebuttal and the added experiments, all reviewers voted for acceptance. 
Please include the additional results as well as the proposed changes in the revised version of the manuscript.
Decision: Accept (poster)