Towards Label Position Bias in Graph Neural Networks
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.
Haoyu Han, Xiaorui Liu, Feng Shi, MohamadAli Torkamani, Charu C. Aggarwal, Jiliang Tang
# Towards Label Position Bias

###### 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.

## 1 Introduction

Graph is a foundational data structure, denoting pairwise relationships between entities. It finds applications across a range of domains, such as social networks, transportation, and biology. (Wu et al., 2020; Ma and Tang, 2021) Among these diverse applications, semi-supervised node classification has emerged as a crucial and challenging task, attracting significant attention from researchers. Given the graph structure, node features, and a subset of labels, the semi-supervised node classification task aims to predict the labels of unlabeled nodes. In 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 (Zhou et al., 2020). A typical GNN model usually follows the message-passing scheme (Gilmer et al., 2017), which mainly contains two operators, i.e., 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. (Jiang et al., 2022) demonstrated that the message-passing scheme could amplify sensitive node attribute bias. A series of studies (Agarwal et al., 2021; Kose and Shen, 2022; Dai and Wang, 2021) have endeavored to mitigate this sensitive attribute bias in GNNs and ensure fair classification. In terms of graph topology, Tang et al. (Tang et al., 2020) 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 (Kang et al., 2022; Liu et al., 2023; Liang et al., 2022).
In addition to node features and graph topology, the label information, especially the position of labeled nodes, also plays a crucial role in GNNs. However, the potential bias in label information has been largely overlooked. In practice, with an equal number of training nodes, different labeling can result in significant discrepancies in test performance [14, 15, 16, 17]. For instance, Ma et al. [14] study 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 provided deep understanding or solutions. The investigation of the influence of labeled nodes' position on unlabeled nodes remains under-explored.

In this work, we discover the presence of a new bias in GNNs, namely the label position bias, which indicates that the nodes "closer" to the labeled nodes tend to receive better prediction accuracy. We propose a 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 [13] and shortest path distance [14], which suggests that the proposed Label Proximity Score might be a more intrinsic measurement of label position bias.

Addressing the label 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 backbone 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 to 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 as \(\mathbf{X}\) to denote matrices. \(\mathbf{X}_{i}\) denotes its \(i\)-th row and \(\mathbf{X}_{ij}\) indicates the \(i\)-th row and \(j\)-th column element. We use bold lower-case letters such as \(\mathbf{x}\) to denote vectors. \(\mathbf{1}_{\mathbf{n}}\in\mathbb{R}^{n\times 1}\) is all-ones column vector. The Frobenius norm and the trace of a matrix \(\mathbf{X}\) are defined as \(\|\mathbf{X}\|_{F}=\sqrt{\sum_{ij}\mathbf{X}_{ij}^{2}}\) and \(tr(\mathbf{X})=\sum_{i}\mathbf{X}_{ii}\), respectively. Let \(\mathcal{G}=(\mathcal{V},\mathcal{E})\) be a graph, where \(\mathcal{V}\) is the node set and \(\mathcal{E}\) is the edge set. \(\mathcal{N}_{i}\) denotes the neighborhood node set for node \(v_{i}\). The graph can be represented by an adjacency matrix \(\mathbf{A}\in\mathbb{R}^{n\times n}\), where \(\mathbf{A}_{ij}>0\) indices that there exists an edge between nodes \(v_{i}\) and \(v_{j}\) in \(\mathcal{G}\), or otherwise \(\mathbf{A}_{ij}=0\). Let \(\mathbf{D}=diag(d_{1},d_{2},\ldots,d_{n})\) be the degree matrix, where \(d_{i}=\sum_{j}\mathbf{A}_{ij}\) is the degree of node \(v_{i}\). The graph Laplacian matrix is defined as \(\mathbf{L}=\mathbf{D}-\mathbf{A}\). We define the normalized adjacency matrix as \(\tilde{\mathbf{A}}=\mathbf{D}^{-\frac{1}{2}}\mathbf{A}\mathbf{D}^{-\frac{1}{2}}\) and the normalized Laplacian matrix as \(\tilde{\mathbf{L}}=\mathbf{I}-\tilde{\mathbf{A}}\). Furthermore, suppose that each node is associated with a \(d\)-dimensional feature \(\mathbf{x}\) and we use \(\mathbf{X}=[\mathbf{x}_{1},\ldots,\mathbf{x}_{n}]^{\top}\in\mathbb{R}^{n\times d}\) to denote the feature matrix. In this work, we focus on the node classification task on graphs. Given a graph \(\mathcal{G}=\{\mathbf{A},\mathbf{X}\}\) and a partial set of labels \(\mathcal{Y}_{L}=\{\mathbf{y}_{1},\ldots,\mathbf{y}_{l}\}\) for node set \(\mathcal{V}_{L}=\{v_{1},\ldots,v_{l}\}\), where \(\mathbf{y}_{i}\in\mathbb{R}^{c}\) is a one-hot vector with \(c\) classes, our goal is to predict labels of unlabeled nodes. For convenience, we reorder the index of nodes and use a mask matrix \(\mathbf{T}=\begin{bmatrix}\mathbf{I}_{l}&0\\ 0&0\end{bmatrix}\) 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 a novel metric, namely the Label Proximity Score, to quantify the closeness between test nodes and training nodes with label information. Specifically, the proposed Label Proximity Score (LPS) is defined as follows:

\[\textit{LPS}=\mathbf{PT1}_{\mathbf{n}},\ \ \text{and}\ \ \mathbf{P}=\left( \mathbf{I}-(1-\alpha)\tilde{\mathbf{A}}\right)^{-1}, \tag{1}\]
where \(\mathbf{P}\) represents the Personalized PageRank matrix, \(\mathbf{T}\) is the label mask matrix, \(\mathbf{1_{n}}\) is an all-ones column vector, and \(\alpha\in(0,1]\) stands for the teleport probability. \(\mathbf{P}_{ij}\) represents the pairwise node proximity between node \(i\) and node \(j\). For each test node \(i\), its LPS represents the sum of its node proximity values to all labeled nodes, i.e., \((\mathbf{PT1}_{n})_{i}=\mathbf{P}_{i,:}\mathbf{T}\mathbf{1}_{n}=\sum_{j\in \mathcal{V}_{L}}\mathbf{P}_{ij}\).

**Sensitive Groups.** In addition to the proposed LPS, we also explore two existing metrics such as node degree (Tang et al., 2020) and shortest path distance to label nodes (Ma et al., 2021a) for comparison since they could be related to the label position bias. For instance, the node with a 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, we 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 (Kipf and Welling, 2016) and APPNP (Gasteiger et al., 2018), which cover both coupled and decoupled architectures. We also provide the evaluation on Label Propagation (LP) (Zhou et al., 2003) 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 1, 2, and 3 respectively. Due to the space limitation, we put more details and results of other datasets and labeling rates into Appendix A.
**Observations.** From the results presented in Figure 1, 2, and 3, we can observe the following:

* Label Position bias is prevalent across all GNN models and datasets. The classification accuracy can notably vary between different sensitive groups, and certain trends are discernible. To ensure fairness 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 fully reflect the Label Position bias. For instance, degree bias is not pronounced in the APPNP model as shown in Figure 1, as APPNP can capture the global structure. Moreover, SPD fails to effectively evaluate relatively low homophily graphs, such as CiteSeer (Ma et al., 2021b). Consequently, there is a need to identify a 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 in 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 is 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 LPS serves as a 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 suggest 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 a 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 a 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 is 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 is more rational to address the bias by learning a label position unbiased graph structure.

However, there are mainly two challenges: (1) How can we define a 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 to avoid excessive memory consumption? In the following subsections, we aim to address these challenges.

### Label Position Unbiased Graph Structure Learning

Based on our preliminary studies, the Label Proximity Score (LPS) can consistently reflect performance 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 LPSs. 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:

\[\begin{split}&\operatorname*{arg\,min}_{\mathbf{B}}\|\mathbf{I}- \mathbf{B}\|_{F}^{2}+\lambda\mathrm{tr}(\mathbf{B}^{\top}\tilde{\mathbf{L}} \mathbf{B})\\ &\text{s.t.}\quad\mathbf{BT1}_{n}=c\mathbf{1}_{n},\end{split} \tag{2}\]

where \(\mathbf{B}\in\mathbb{R}^{n\times n}\) represents the debiased graph structure matrix. \(\mathrm{tr}(\mathbf{B}^{\top}\tilde{\mathbf{L}}\mathbf{B})=\sum_{(v_{i},v_{j}) \in\mathcal{E}}\|\mathbf{B}_{i}/\sqrt{d_{i}}-\mathbf{B}_{j}/\sqrt{d_{j}}\|_{2} ^{2}\) measures the smoothness of the new structure based on the original graph structure. The proximity to identity matrix \(\mathbf{I}\in\mathbb{R}^{n\times n}\) encourages self-loops and avoids trivial over-smoothed structures. \(\lambda\) is a hyperparameter that controls the balance between smoothness and self-loop. \(\mathbf{T}\) is the mask matrix indicating the labeled nodes, \(\mathbf{1_{n}}\) is the all-ones vector, and \(c\) is a hyperparameter serving as the uniform Label Proximity Score for all nodes.

Notably, if we ignore the constraint, then the optimal solution for this primary problem is given by \(\mathbf{B}=(\mathbf{I}+\lambda\mathbf{L})^{-1}=\alpha(\mathbf{I}-(1-\alpha \tilde{\mathbf{A}}))^{-1}\), where \(\alpha=\frac{1}{1+\lambda}\). This solution recovers the Personalized 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 as \(c\). The constraint encourages fair label proximity scores for all nodes so that the learned graph structure mitigates the label position bias.

The constrained optimization problem in Eq. (2) is a convex optimization problem, and it can be solved by the Lagrange Multiplier method (Boyd and Vandenberghe, 2004). The augmented Lagrange function can be written as:

\[L_{\rho}(\mathbf{B},\mathbf{y})=\|\mathbf{I}-\mathbf{B}\|_{F}^{2}+\lambda \mathrm{tr}(\mathbf{B}^{\top}\tilde{\mathbf{L}}\mathbf{B})+\mathbf{y}^{\top} (\mathbf{BT1}_{n}-c\mathbf{1}_{n})+\frac{\rho}{2}\|\mathbf{BT1}_{n}-c\mathbf{1 }_{n}\|_{2}^{2}, \tag{3}\]

where \(\mathbf{y}\in\mathbb{R}^{n\times 1}\) is the introduced Lagrange multiplier, and \(\rho>0\) represents the augmented Lagrangian parameter. The gradient of \(L_{\rho}(\mathbf{B},\mathbf{y})\) to \(\mathbf{B}\) can be represented as:

\[\frac{\partial L_{\rho}}{\partial\mathbf{B}}=2(\mathbf{B}-\mathbf{I})+2 \lambda\tilde{\mathbf{L}}\mathbf{B}+\mathbf{y}(\mathbf{T1}_{n})^{\top}+\rho( \mathbf{BT1}_{n}-c\mathbf{1}_{n})(\mathbf{T1}_{n})^{\top}. \tag{4}\]

Then, the problem can be solved by dual ascent algorithm (Boyd et al., 2011) as follows:

\[\mathbf{B}^{k+1} =\operatorname*{arg\,min}_{\mathbf{B}}L_{\rho}(\mathbf{B}^{k}, \mathbf{y}^{k})\] \[\mathbf{y}^{k+1} =\mathbf{y}^{k}+\rho(\mathbf{B}^{k}\mathbf{T1}_{n}-c\mathbf{1}_{n }),\]

where \(k\) is the current optimization step, and \(\mathbf{B}^{k+1}\) can be obtained by multiple steps of gradient descent using the gradient in Eq. (4).

### Understandings

In this subsection, we provide the understanding and interpretation of our proposed LPSL, establishing its connections with the message passing in GNNs.

_Remark 3.1_.: The feature aggregation using the learned graph structure \(\mathbf{B}\) directly as a propagation matrix, i.e., \(\mathbf{F}=\mathbf{B}\mathbf{X}\), is equivalent to applying the message passing in GNNs using the original graph if \(\mathbf{B}\) is the approximate or exact solution to the primary problem defined in Eq. 2 without constraints.

The detailed proof can be found in Appendix B. Remark 3.1 suggests that we can directly substitute the propagation matrix in GNNs with the learned structure \(\mathbf{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-passing scheme. Following the definition in (Xu et al., 2018), the influence of node \(j\) on node \(i\) can be represented by \(I_{i}(j)=sum\left[\frac{\partial\mathbf{h}_{i}}{\partial\mathbf{x}_{j}}\right]\), where \(\mathbf{h}_{i}\) is the representation of node \(i\), \(\mathbf{x}_{j}\) is the input feature of node \(j\), and \(\left[\frac{\partial\mathbf{h}_{i}}{\partial\mathbf{x}_{j}}\right]\) represents the Jacobian matrix. Afterward, we have the following Proposition based on the influence scores:

**Proposition 3.1**.: _The influence scores from all labeled nodes to any unlabeled node \(i\) will be the equal, i.e., \(\sum_{j\in\mathcal{V}_{L}}I_{i}(j)=c\), when using the unbiased graph structure \(\mathbf{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 an equivalent influence from all the labeled nodes, thereby mitigating the label position bias issue.

### \(\ell_{1}\)-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 \(\mathbf{B}\in\mathbb{R}^{n\times n}\). This is a memory-intensive outcome, especially when the number of nodes \(n\) 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 \(\ell_{1}\)-regularized Label Position Unbiased Sparse Structure Learning optimization problem:

\[\begin{split}\operatorname*{arg\,min}_{B}\|\mathbf{I}- \mathbf{B}\|_{F}^{2}+\lambda\mathrm{tr}(\mathbf{B}^{\top}\mathbf{L}\mathbf{B} )+\beta\|\mathbf{B}\|_{1}\\ \text{s.t.}\quad\mathbf{B}\mathbf{T}\mathbf{1}_{n}=c\mathbf{1}_ {n},\end{split} \tag{5}\]

where \(\|\mathbf{B}\|_{1}\) represents the \(\ell_{1}\) regularization that encourages zero values in \(\mathbf{B}\). \(\beta>0\) is a hyperparameter to control the sparsity of \(\mathbf{B}\). The primary problem in Eq. (5) is proved to have a strong localization property and can guarantee the sparsity (Ha et al., 2021; Hu, 2020). 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 (Tseng, 2001) in conjunction with the proximal gradient approach, particularly due to the presence of the \(\ell_{1}\) regularization. Specifically, we split \(\mathbf{B}\) into column blocks, and \(\mathbf{B}_{\cdot:j}\) represents the \(j\)-th block. The gradient of \(L_{\rho}\) with respect to \(\mathbf{B}_{\cdot:j}\) can be written as:

\[\frac{\partial L_{\rho}}{\partial\mathbf{B}_{\cdot:j}}=2(\mathbf{B}_{\cdot:j}- \mathbf{I}_{\cdot:j})+2\lambda\tilde{\mathbf{L}}\mathbf{B}_{\cdot:j}+\mathbf{y }(\mathbf{T}\mathbf{1}_{n})_{j}^{\top}+\rho(\mathbf{B}\mathbf{T}\mathbf{1}_{n }-c\mathbf{1}_{n})(\mathbf{T}\mathbf{1}_{n})_{j}^{\top}, \tag{6}\]

where \((\mathbf{T}\mathbf{1}_{n})_{j}\in\mathbb{R}^{d\times 1}\) is the corresponding block part with block size \(d\). After updating the current block \(\mathbf{B}_{\cdot:j}\), we apply a soft thresholding operator \(S_{\beta/\rho}(\cdot)\) based on the proximal mapping. The full algorithm is detailed in Algorithm 1. Notably, lines 6-8 handle the block updates, line 9 performs the soft thresholding operation, and line 11 updates Lagrange multiplier \(\mathbf{y}\) through dual ascent update.

**Input:** Laplacian matrix \(\tilde{\mathbf{L}}\), Label mask matrix \(\mathbf{T}\), Hyperparamters \(\lambda,c,\beta,\rho\), learning rate \(\gamma\)

**Output:** Label position unbiased graph structure \(\mathbf{B}\)

```
1:Input: Laplacian matrix \(\tilde{\mathbf{L}}\), Label mask matrix \(\mathbf{T}\), Hyperparamters \(\lambda,c,\beta,\rho\), learning rate \(\gamma\)
2:Output: Label position unbiased graph structure \(\mathbf{B}\)
3:Initialization: \(\mathbf{B}^{0}=\mathbf{I}\) and \(\mathbf{y}^{0}=\mathbf{0}\)
4:while Not converge do
5:for each block \(j\)do
6:for\(i=0\)to update steps \(t\)do
7:\(\mathbf{B}_{\cdot:j}=\mathbf{B}_{\cdot:j}-\gamma*\frac{\partial L_{\rho}}{ \partial\mathbf{B}_{\cdot:j}}\)
8:endfor
9:\(\mathbf{B}_{\cdot:j}=S_{\beta/\rho}(\mathbf{B}_{\cdot:j})\)
10:endfor
11:\(\mathbf{y}=\mathbf{y}+\rho(\mathbf{B}\mathbf{T}\mathbf{1}_{n}-c\mathbf{1}_ {n})\)
12:endwhile
13:return\(\mathbf{B}\)
```

**Algorithm 1** Algorithm of LPSL

### 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.e., GCN (Kipf and Welling, 2016) and APPNP (Gasteiger et al., 2018). For the GCN model, each layer can be represented by:

\[\mathbf{H}^{l+1}=\sigma\left(\mathbf{B}_{\lambda}\mathbf{H}^{l}\mathbf{W}^{l} \right),\]

where \(\mathbf{H}^{0}=\mathbf{X}\), \(\sigma\) is the non-linear activation function, \(\mathbf{B}_{\lambda}\) is the unbiased structure with parameter \(\lambda\), and \(\mathbf{W}^{l}\) is the weight matrix in the \(l\)-th layer. We refer to this model as LPSL\({}_{\text{GNN}}\). For the APPNP model, we directly use the learned \(\mathbf{B}_{\lambda}\) as the propagation matrix, and the prediction can be written as:

\[\mathbf{Y}_{\text{pred}}=\mathbf{B}_{\lambda}f_{\theta}(\mathbf{X}),\]

where \(f_{\theta}(\cdot)\) is any machine learning model parameterized by the learnable parameters \(\theta\). We name this model as LPSL\({}_{\text{APPNP}}\). The parameter \(\lambda\) provides a high flexibility when applying \(\mathbf{B}_{\lambda}\) to different GNN architectures. For decoupled GNNs such as APPNP, which only propagates once, a large \(\lambda\) 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, a smaller \(\lambda\) can be used to encode a more local structure with a higher sparsity.
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)

### 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 (Sen et al., 2008), two co-authorship datasets, i.e., Coauthor CS and Coauthor Physics, two co-purchase datasets, i.e., Amazon Computers and Amazon Photo (Shchur et al., 2018), and one OGB dataset, i.e., ogbn-arxiv (Hu et al., 2020). 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 (Liu et al., 2021). 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 (Kipf and Welling, 2016), GAT (Velickovic et al., 2017), and APPNP (Gasteiger et al., 2018), two Non-GNNs, MLP and Label Propagation (Zhou et al., 2003), as baselines. Furthermore, we also include GRADE (Wang et al., 2022), a method designed to mitigate degree bias. Notably, SRGNN (Zhu et al., 2021) 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 is also included as a baseline.

**Hyperparameters Setting.** We follow the best hyperparameter settings in their original papers for all baselines. For the proposed LPSL\({}_{\text{GCN}}\), we set the \(\lambda\) in range [1,8]. For LPSL\({}_{\text{APPNP}}\), we set the \(\lambda\) 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 (Kingma and Ba, 2014) is used in all experiments. More details about the hyperparameters setting for all methods can be found in Appendix D.

### Performance Comparison on Benchmark Datasets

In this subsection, we test the learned unbiased graph structure by the proposed LPSL 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 1. 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 on 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 LPSL shows greater performance improvement with a 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.
### 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 use three representative group bias measurements - Weighted Demographic Parity (WDP), Weighted Standard Deviation (WSD), and Weighted Coefficient of Variation (WCV) - to quantify the bias. These are defined as follows:

\[\text{WDP}=\frac{\sum_{i=1}^{D}N_{i}\cdot|A_{i}-A_{\text{avg}}|}{N_{\text{ total}}},\text{WSD}=\sqrt{\frac{1}{N_{\text{total}}}\sum_{i=1}^{D}N_{i}\cdot(A_{i}-A_ {\text{avg}})^{2}},\text{WCV}=\frac{\text{WSD}}{A_{\text{avg}}},\]

where \(D\) is the number of groups, \(N_{i}\) is the node number of group \(i\), \(A_{i}\) is the accuracy of group \(i\), \(A_{\text{avg}}\) is the weighted average accuracy of all groups, i.e., the overall accuracy, and \(N_{\text{total}}\) is the total number of nodes. We choose six representative models, i.e., Label Propagation (LP), GRADE, GCN, APPNP, LPSL\({}_{\text{GCN}}\), and LPSL\({}_{\text{APPNP}}\), in this experiment. The results of the label proximity score, degree, and shortest path on the Cora and Citeseer datasets are shown in Tabel 2, 3, and 4, 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 a 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 metrics. For instance, it significantly increases the label proximity score bias on the CiteSeer dataset.

\begin{table}
\begin{tabular}{c|c c c c|c c c} \hline Dataset & Label Rate & GCN & APPNP & GRADE & SRGNN & LPSL\({}_{\text{GCN}}\) & LPSL\({}_{\text{APPNP}}\) \\ \hline \multirow{4}{*}{Cora} & 5 & \(70.68\pm 2.17\) & \(75.86\pm 2.34\) & \(69.51\pm 6.79\) & \(70.77\pm 1.82\) & \(76.58\pm 2.37\) & \(\mathbf{77.24\pm 2.18}\) \\  & 10 & \(76.50\pm 1.42\) & \(80.29\pm 1.00\) & \(74.95\pm 2.46\) & \(75.42\pm 1.57\) & \(80.39\pm 1.17\) & \(\mathbf{81.59\pm 0.98}\) \\  & 20 & \(79.41\pm 1.30\) & \(82.34\pm 0.67\) & \(77.41\pm 1.49\) & \(78.42\pm 1.75\) & \(82.74\pm 1.01\) & \(\mathbf{83.24\pm 0.75}\) \\  & 60\% & \(88.60\pm 1.19\) & \(88.49\pm 1.28\) & \(86.84\pm 0.99\) & \(87.17\pm 0.95\) & \(\mathbf{88.75\pm 1.21}\) & \(88.62\pm 1.69\) \\ \hline \multirow{4}{*}{CiteSeer} & 5 & \(61.27\pm 3.85\) & \(63.92\pm 3.39\) & \(63.03\pm 3.61\) & \(64.84\pm 3.41\) & \(65.65\pm 2.47\) & \(\mathbf{65.70\pm 2.18}\) \\  & 10 & \(66.28\pm 2.14\) & \(67.57\pm 2.05\) & \(64.20\pm 3.23\) & \(67.83\pm 2.19\) & \(67.73\pm 2.57\) & \(\mathbf{68.76\pm 1.77}\) \\  & 20 & \(69.60\pm 1.67\) & \(70.85\pm 1.45\) & \(67.50\pm 1.76\) & \(69.13\pm 1.99\) & \(70.73\pm 1.32\) & \(\mathbf{71.25\pm 1.14}\) \\  & 60\% & \(76.88\pm 1.78\) & \(77.42\pm 1.47\) & \(74.00\pm 1.87\) & \(74.57\pm 1.57\) & \(77.18\pm 1.64\) & \(\mathbf{77.56\pm 1.44}\) \\ \hline \multirow{4}{*}{PubMed} & 5 & \(69.76\pm 6.46\) & \(72.68\pm 5.68\) & \(66.90\pm 6.49\) & \(69.38\pm 6.48\) & \(73.46\pm 4.64\) & \(\mathbf{73.57\pm 5.30}\) \\  & 10 & \(72.79\pm 3.58\) & \(75.53\pm 3.85\) & \(73.31\pm 3.75\) & \(72.69\pm 3.49\) & \(75.67\pm 4.42\) & \(\mathbf{76.18\pm 4.05}\) \\  & 20 & \(77.43\pm 2.66\) & \(76.83\pm 2.11\) & \(75.12\pm 2.37\) & \(77.09\pm 1.68\) & \(78.75\pm 2.45\) & \(\mathbf{79.26\pm 2.32}\) \\  & 60\% & \(\mathbf{88.48\pm 0.46}\) & \(87.56\pm 0.52\) & \(86.90\pm 0.46\) & \(88.32\pm 0.55\) & \(87.75\pm 0.57\) & \(87.96\pm 0.57\) \\ \hline CS & 20 & \(91.73\pm 0.49\) & \(92.38\pm 0.38\) & \(89.43\pm 0.67\) & \(89.43\pm 0.67\) & \(91.94\pm 0.54\) & \(\mathbf{92.44\pm 0.36}\) \\ \hline Physics & 20 & \(93.29\pm 0.80\) & \(93.93\pm 0.67\) & \(91.44\pm 1.41\) & \(93.16\pm 0.64\) & \(93.56\pm 0.51\) & \(\mathbf{93.65\pm 0.50}\) \\ \hline Computers & 20 & \(79.17\pm 1.92\) & \(79.07\pm 2.34\) & \(79.01\pm 2.36\) & \(78.54\pm 2.15\) & \(\mathbf{80.05\pm 2.92}\) & \(79.58\pm 2.31\) \\ \hline Photo & 20 & \(89.94\pm 1.22\) & \(90.87\pm 1.14\) & \(90.17\pm 0.93\) & \(89.36\pm 1.02\) & \(90.85\pm 1.16\) & \(\mathbf{90.93\pm 1.40}\) \\ \hline ogbn-arxiv & 54\% & \(71.91\pm 0.15\) & \(71.61\pm 0.30\) & OOM & \(68.01\pm 0.35\) & \(\mathbf{72.04\pm 0.12}\) & \(69.20\pm 0.26\) \\ \hline \end{tabular}
\end{table}
Table 1: Semi-supervised node classification accuracy (%) on benchmark datasets.

\begin{table}
\begin{tabular}{c|c c c|c c c} \hline Dataset & \multicolumn{4}{c|}{Cora} & \multicolumn{4}{c}{CiteSeer} \\ \hline Method & WDP \(\downarrow\) & WSD \(\downarrow\) & WCV \(\downarrow\) & WDP \(\downarrow\) & WSD \(\downarrow\) & WCV \(\downarrow\) \\ \hline 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 \\ LPSL\({}_{\text{GCN}}\) & **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 \\ LPSL\({}_{\text{APPNP}}\) & 0.0390 & 0.0476 & 0.0562 & 0.0275 & 0.0349 & **0.0474** \\ \hline \end{tabular}
\end{table}
Table 2: Comparison of Methods in Addressing Label Proximity Score Bias.
### Ablation Study

In this subsection, we explore the impact of different hyperparameters, specifically the smoothing term \(\lambda\) 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 \(\lambda\) values for LPSL\({}_{\text{APPNP}}\) and LPSL\({}_{\text{GCN}}\) on the Cora and CiteSeer datasets are illustrated in Figure 4.4.

From our analysis, we note that the proposed LPSL is not highly sensitive to the \(\lambda\) within the selected regions. Moreover, for the APPNP model, the best \(\lambda\) is higher than that for the GCN model, which aligns with our discussion in Section 3 that the decoupled GNNs require a larger \(\lambda\) to encode the global graph structure. The results for hyperparameter \(c\) can be found in Appendix F with similar observations.

## 5 Related Work

Graph Neural Networks (GNNs) serve as 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 (Kipf and Welling, 2016), GraphSAGE (Hamilton et al., 2017), and GAT (Velickovic et al., 2017), entwine feature transformation and propagation within each layer. In contrast, recent models like APPNP (Gasteiger et al., 2018) represent Decoupled GNNs (Liu et al., 2021, 2020, Zhou et al., 2021) that separate transformation and propagation. While Graph Neural Networks (GNNs) have achieved notable success across a range of domains (Wu et al., 2020), they often harbor various biases tied to node features and graph topology (Dai et al., 2022). For example, GNNs may generate predictions skewed by sensitive node features (Dai and Wang, 2021; Agarwal et al., 2021), leading to potential unfairness in diverse tasks such as recommendations (Buyl and De Bie, 2020) and loan fraud detection (Xu et al., 2021). Numerous studies have proposed different methods to address feature bias, including adversarial training (Dai and Wang, 2021; Dong et al.,

\begin{table}
\begin{tabular}{c|c c c|c c c} \hline DataSet & \multicolumn{3}{c|}{Cora} & \multicolumn{3}{c}{CiteSeer} \\ \hline Method & WDP \(\downarrow\) & WSD \(\downarrow\) & WCV \(\downarrow\) & WDP \(\downarrow\) & WSD \(\downarrow\) & WCV \(\downarrow\) \\ \hline 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 \\ LPSL\({}_{\text{GCN}}\) & **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 \\ LPSL\({}_{\text{APPNP}}\) & 0.0166 & 0.0253 & 0.0295 & 0.0265 & **0.0490** & **0.0654** \\ \hline \end{tabular}
\end{table}
Table 4: Comparison of Methods in Addressing Shortest Path Distance Bias.

Figure 4: The accuracy of different \(\lambda\) for LPSL\({}_{\text{APPNP}}\) and LPSL\({}_{\text{GCN}}\) on Cora and CiteSeer datasets.

\begin{table}
\begin{tabular}{c|c c|c c c c} \hline Dataset & \multicolumn{3}{c|}{Cora} & \multicolumn{3}{c}{CiteSeer} \\ \hline Method & WDP \(\downarrow\) & WSD \(\downarrow\) & WCV \(\downarrow\) & WDP \(\downarrow\) & WSD \(\downarrow\) & WCV \(\downarrow\) \\ \hline 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 \\ LPSL\({}_{\text{GCN}}\) & 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 \\ LPSL\({}_{\text{APPNP}}\) & **0.0349** & **0.0395** & **0.0467** & **0.0316** & **0.0487** & **0.0665** \\ \hline \end{tabular}
\end{table}
Table 3: Comparison of Methods in Addressing Degree Bias.
2022, Masrour et al., 2020), and fairness constraints (Agarwal et al., 2021; Dai and Wang, 2022; Kang et al., 2020). Structural bias is another significant concern, where low-degree nodes are more likely to be falsely predicted by GNNs (Tang et al., 2020). Recently, there are several works aimed to mitigate the degree bias issue (Kang et al., 2022; Liu et al., 2023; Liang et al., 2022). Distinct from these previous studies, our work identifies a new form of bias - label position bias, which is prevalent in GNNs. To address this, we propose a novel method, LPSL, specifically designed to alleviate the label position bias.

## 6 Conclusion and Limitation

In this study, we shed light on a previously unexplored bias in GNNs, the label position bias, which suggests that nodes closer to labeled nodes typically yield superior performance. To quantify this bias, we introduce a new metric, the Label Proximity Score, which proves to be a more intrinsic measure. To combat this prevalent issue, we propose a novel optimization framework, LPSL, to learn an 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, we address the label position bias only from a structure learning perspective. Future research could incorporate feature information, which might lead to improved performance. Besides, we have primarily examined homophily graphs. It would be interesting to 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 fairness in GNNs.
