FairGP: A Scalable and Fair Graph Transformer Using Graph Partitioning

Fairness in GNNs has gained substantial attention, particularly in efforts to identify and mitigate biases associated with specific sensitive features (Zhang et al. 2024c). Various fairness-aware GNN studies aim to preserve the independence of sensitive features through pre-processing and in-processing techniques (Dong et al. 2023; Luo et al. 2024c).

Graphair (Ling et al. 2023) is a recent pre-processing algorithm. It automatically identifies fairness-aware augmentations from input graph data, aiming to circumvent sensitive features while preserving the integrity of other valuable information. FairAC (Guo, Chu, and Li 2023) proposes a fairness feature completion approach. It completes missing information by adversarial learning and achieves fair node embeddings for graphs lacking certain features. Unlike GNN methods, GTs that depend on the attention score matrix face challenges in directly identifying sensitive features in the input, making it difficult to apply pre-processing techniques effectively. In-processing methods, on the other hand, focus on message-passing or convolution propagation. FairSIN (Yang et al. 2024) introduces a neutralization-based paradigm, which incorporates additional fairness-enhancing features into node features or representations before message-passing. FMP (Jiang et al. 2024) directly addresses the use of sensitive features during forward propagation for node classification tasks using cross-entropy loss, eliminating the need for data pre-processing. However, the global attention mechanism in GTs, which facilitates direct node-to-node interactions, differs from the message-passing or convolution used in GNNs (Yin and Zhong 2023). In-processing techniques may not be directly applicable to GTs.

Recent GT studies are shifting their focus to handling the large-scale graph (Xing et al. 2024). DIFFormer (Wu et al. 2023a) introduces a scalable GT framework guided by data-invariant functions, enabling efficient processing of large-scale graphs. Similarly, SGFormer (Wu et al. 2023b) simplifies the Transformer architecture to boost computational efficiency on large-scale graphs. Polynormer (Deng, Yue, and Zhang 2024) advances the field by developing a polynomial expressive GT that can capture features in complex graph structures more effectively.

Despite these advancements, existing GT methods often lack explicit consideration of algorithmic fairness. When applied to real-world datasets, they exhibit significant fairness issues. FairGT (Luo et al. 2024b) addresses the fairness problem within GT based on a sensitive feature complete graph. It faces challenges in deployment on large graphs due to its reliance on global attention in two whole graphs (original and sensitive feature complete graph). Scalable techniques such as mini-batch and graph partitioning are challenging to deploy in FairGT while ensuring guaranteed performance, because the sensitive feature complete graph relies on all edges. Addressing the fairness issues of GTs on large-scale graphs remains a pressing and current challenge.

Unless otherwise specified, we denote sets with copperplate uppercase letters (e.g., $\mathcal{A}$), matrices with bold uppercase letters (e.g., $\mathbf{A}$), and vectors with bold lowercase letters (e.g., $\mathbf{x}$). We denote the number of elements in the set $\mathcal{A}$ as $|\mathcal{A}|$. We denote a graph as $\mathcal{G}=\{\mathcal{V},\mathbf{A},\mathbf{H}\}$, where $\mathcal{V}$ is the set of nodes in the graph and $|\mathcal{V}|=n$, $\mathbf{A}\in\mathbb{R}^{n\times n}$ is the adjacency matrix, and $\mathbf{H}\in\mathbb{R}^{n\times d}$ is the node feature matrix.

We follow the convention of NumPy in Python for matrix and vector indexing: $\mathbf{A}[i,j]$ represents the entry of matrix $\mathbf{A}$ at the $i$-th row and the $j$-th column; $\mathbf{A}[i,:]$ and $\mathbf{A}[:,j]$ represent the $i$-th row and the $j$-th column of matrix $\mathbf{A}$, respectively. $\mathbf{H}[:,s]$ denotes a sensitive feature of nodes, and $\mathbf{H}[i,s]$ denotes a sensitive feature of node $v_{i}$.

We present two definitions of fairness for a binary ground truth label $y\in\{0,1\}$ and a binary sensitive feature $\mathbf{H}[i,s]\in\{0,1\}$. We use $\hat{y}\in\{0,1\}$ to represent the predicted label.

Definition 1. Statistical Parity (i.e., Demographic Parity, Independence)  (Dwork et al. 2012). Statistical parity requires the predictions to be independent of the sensitive features. The prediction can be formally written as:

$$\mathbb{P}(\hat{y}=1|\mathbf{H}[i,s]=0)=\mathbb{P}(\hat{y}=1|\mathbf{H}[i,s]=1).$$

(1)

When both the predicted labels and the sensitive features are binary, the extent of statistical parity can be quantified by $\Delta_{\text{SP}}$, defined as follows:

$$\Delta_{\text{SP}}=|\mathbb{P}(\hat{y}=1|\mathbf{H}[i,s]=0)-\mathbb{P}(\hat{y}=1|\mathbf{H}[i,s]=1)|.$$

(2)

The $\Delta_{\text{SP}}$ measures the acceptance rate difference between two sensitive subgroups with $\mathbf{H}[i,s]=0$ and $\mathbf{H}[i,s]=1$.

Definition 2. Equal Opportunity (Hardt, Price, and Srebro 2016). Equal opportunity necessitates that the likelihood of an instance belonging to a positive class leading to a positive outcome should be equitable for all members within subgroups. For individuals with positive ground truth labels, it is necessary for positive predictions to be devoid of any dependence on sensitive features. This principle can be formulated as follows:

		$\displaystyle\mathbb{P}(\hat{y}=1|y=1,\mathbf{H}[i,s]=0)$		(3)
	$\displaystyle=$	$\displaystyle\mathbb{P}(\hat{y}=1|y=1,\mathbf{H}[i,s]=1).$

Fairness-aware algorithms prevent the allocation of unfavourable predictions to individuals solely based on their sensitive subgroup affiliation. In particular, $\Delta_{\text{EO}}$ quantifies the extent of deviation in predictions from equal opportunity. To quantitatively assess equal opportunity:

	$\displaystyle\Delta_{\text{EO}}=|$	$\displaystyle\mathbb{P}(\hat{y}=1|y=1,\mathbf{H}[i,s]=0)$		(4)
	$\displaystyle-$	$\displaystyle\mathbb{P}(\hat{y}=1|y=1,\mathbf{H}[i,s]=1)|.$

Both $\Delta_{\text{SP}}$ and $\Delta_{\text{EO}}$ are evaluated on the test set.

The Transformer architecture consists of a composition of Transformer layers. Each Transformer layer has two parts: a self-attention module and a position-wise feed-forward network (FFN). Let $\mathbf{X}=[\mathbf{h}_{1}^{\top},...,\mathbf{h}_{i}^{\top}]^{\top}\in\mathbb{R}^{i\times d_{h}}$ be the input of the self-attention module where $d_{h}$ is the hidden dimension and $\mathbf{h}_{j}\in\mathbb{R}^{1\times d_{h}}$ is the hidden representation at position $j$. The input $\mathbf{X}$ is projected by three matrices $\mathbf{W}_{\text{Q}}\in\mathbb{R}^{d_{h}\times d_{K}}$, $\mathbf{W}_{\text{K}}\in\mathbb{R}^{d_{h}\times d_{K}}$, and $\mathbf{W}_{\text{V}}\in\mathbb{R}^{d_{h}\times d_{V}}$ to the corresponding representations Q, K, V. The self-attention is then calculated as:

		$\displaystyle\text{Attn}(\mathbf{X})=\text{Softmax}\left(\frac{\text{Q}\text{K}^{\top}}{\sqrt{d_{K}}}\right)\text{V},$		(5)
		$\displaystyle\text{Q}=\mathbf{X}\mathbf{W}_{\text{Q}},\text{K}=\mathbf{X}\mathbf{W}_{\text{K}},V=\mathbf{X}\mathbf{W}_{V}.$

To simplify the discussion, we consider single-head self-attention and assume $d_{K}=d_{V}=d_{h}$. The extension to multi-head attention is straightforward, and we omit the bias terms for simplicity.

The attention score matrix is denoted as $\hat{\mathbf{A}}\in\mathbb{R}^{n\times n}$, which contains the attention scores for all node pairs:

$\displaystyle\hat{\mathbf{A}}=\text{Softmax}\left(\frac{\text{Q}\text{K}^{\top}}{\sqrt{d_{K}}}\right).$

(6)

$\hat{\mathbf{A}}[u,v]$ represents the attention score between nodes $u$ and $v$. Due to the Softmax function, we have $\sum^{n}_{i=1}\hat{\mathbf{A}}[i,:]=1$ and $\sum^{n}_{i=1}\hat{\mathbf{A}}[:,j]=1$.

We empirically show how the global attention mechanism in GT tends to favour higher-order nodes. The experimental settings are detailed in Appendix A.2. We focus on the proportion of different sensitive features across different nodes, analyzing how these distributions are affected by GT training. This analysis includes the proportion of different sensitive features among all nodes, higher-order nodes, and prediction results. We normalize the minority subgroups as $1$. Thus, if $|\mathbf{H}[i,s]=1|>|\mathbf{H}[i,s]=0|$, for $i\in\{1,2,\dots,n\}$:

		$\displaystyle\textbf{All Nodes}(\mathbf{H}[i,s]=1)=\frac{|\mathbf{H}[i,s]=1|}{|\mathbf{H}[i,s]=0|},$		(7)
		$\displaystyle\textbf{All Nodes}(\mathbf{H}[i,s]=0)=1,$

and, if $|\mathbf{H}[i,s]=0|>|\mathbf{H}[i,s]=1|$:

		$\displaystyle\textbf{All Nodes}(\mathbf{H}[i,s]=1)=1,$		(8)
		$\displaystyle\textbf{All Nodes}(\mathbf{H}[i,s]=0)=\frac{|\mathbf{H}[i,s]=0|}{|\mathbf{H}[i,s]=1|}.$

The definition is similar in higher-order nodes and prediction results, and the details are shown in Appendix B.

In Table 1, higher proportions of sensitive features will be highlighted in red ($\mathbf{H}[i,s]=1$) and blue ($\mathbf{H}[i,s]=0$) for clarity. When the overall distribution of sensitive features among all nodes differs from that of higher-order nodes, GTs tend to learn to predict based on the distribution of higher-order nodes. It may even lead to the opposite prediction. The majority population in both distributions is the same, the proportion of sensitive features in the prediction result will align more closely with the higher-order nodes. Consequently, the proportions of sensitive features among higher-order nodes can affect the GT fairness.

We denote the similarity between the distribution of original sensitive features and the distribution of sensitive features when they are mapped to node embeddings as sensitive feature similarity. Node embeddings are computed by the global attention mechanism. We select the Euclidean Norm to measure similarity. A higher similarity indicates greater independence of sensitive attributes during training, aligning with algorithmic fairness. This analysis helps us understand how the attention mechanism impacts the preservation or alteration of sensitive feature distributions during the embedding process. By comparing these distributions, we can assess whether a GT model introduces or mitigates bias, thereby uncovering the underlying causes of fairness issues in GTs.

Theorem 1 The sensitive feature similarity is bounded by the attention scores between nodes with different sensitive features.

$$\|\mathbf{H}[:,s]-\hat{\textbf{A}}\mathbf{H}[:,s]\|_{2}\leq\sum_{u,v\in\mathcal{V}}\sum_{\mathbf{H}[u,s]\neq\mathbf{H}[v,s]}\hat{\mathbf{A}}[u,v]$$

(9)

Proof. Based on the Triangle Inequality:

		$\displaystyle\|\mathbf{H}[:,s]-\hat{\textbf{A}}\mathbf{H}[:,s]\|_{2}$
	$\displaystyle=$	$\displaystyle\sqrt{\sum_{u\in\mathcal{V}}(\mathbf{H}[u,s]-\sum_{v\in\mathcal{V}}\hat{\mathbf{A}}[u,v]\mathbf{H}[v,s])^{2}}$
	$\displaystyle\leq$	$\displaystyle\sum_{u\in\mathcal{V}}\sqrt{(\mathbf{H}[u,s]-\sum_{v\in\mathcal{V}}\hat{\mathbf{A}}[u,v]\mathbf{H}[v,s])^{2}}$
	$\displaystyle=$	$\displaystyle\sum_{u\in\mathcal{V}}\|\mathbf{H}[u,s]-\sum_{v\in\mathcal{V}}\hat{\mathbf{A}}[u,v]\mathbf{H}[v,s]\|_{2}$
	$\displaystyle=$	$\displaystyle\sum_{u\in\mathcal{V}}\|\sum_{v\in\mathcal{V}}\hat{\mathbf{A}}[u,v](\mathbf{H}[u,s]-\mathbf{H}[v,s])\|_{2}$
	$\displaystyle\leq$	$\displaystyle\sum_{u,v\in\mathcal{V}}\hat{\mathbf{A}}[u,v]\|\mathbf{H}[u,s]-\mathbf{H}[v,s]\|_{2}$
	$\displaystyle=$	$\displaystyle\sum_{u,v\in\mathcal{V}}\sum_{\mathbf{H}[u,s]\neq\mathbf{H}[v,s]}\hat{\mathbf{A}}[u,v].$

$\square$

Since global attention tends to concentrate on higher-order nodes (Xing et al. 2024), the fairness of the algorithm is predominantly influenced by these higher-order nodes with different sensitive features.

Next, we consider GT with partitioning. We denote $\hat{\mathbf{A}}^{\prime}$ as the GT attention score matrix with graph partitioning. We assume even partitions, and the number of partitions (i.e. clusters) is $c$. Let $\alpha_{pq}$ represent the attention score between clusters $p$ and $q$. Then the approximate attention score between node $u$ and $v$ (in different clusters) with graph partitioning can be expressed as $\hat{\mathbf{A}}^{\prime}[u,v]=\frac{\alpha_{pq}}{n/c}$ (Xing et al. 2024). Thus,

$$\hat{\mathbf{A}}^{\prime}[u,v]=\left\{\begin{aligned} &\hat{\mathbf{A}}[u,v],\quad&u\in\mathcal{V}_{p},v\in\mathcal{V}_{p}\\ &\frac{\alpha_{pq}}{n/c},&u\in\mathcal{V}_{p},v\in\mathcal{V}_{q}\end{aligned}\right.$$

(10)

Lemma 1 The sensitive feature similarity are lower than $\sqrt{n}$, whether using a vanilla GT or a GT with graph partitioning.

		$\displaystyle\|\mathbf{H}[:,s]-\hat{\textbf{A}}\mathbf{H}[:,s]\|_{2}\leq\sqrt{n},$		(11)
		$\displaystyle\|\mathbf{H}[:,s]-\hat{\textbf{A}}^{\prime}\mathbf{H}[:,s]\|_{2}\leq\sqrt{n}.$

The proof of Lemma 1 is shown in Appendix C.

Theorem 2 Compared to vanilla GT, the change in sensitive feature similarity in GT with graph partitioning is constrained by the attention mechanism between different clusters.

		$\displaystyle\big{|}\|\mathbf{H}[:,s]-\hat{\textbf{A}}\mathbf{H}[:,s]\|_{2}-\|\mathbf{H}[:,s]-\hat{\textbf{A}}^{\prime}\mathbf{H}[:,s]\|_{2}\big{|}$		(12)
	$\displaystyle\geq$	$\displaystyle\frac{1}{2\sqrt{n}}|\sum_{u\in\mathcal{V}_{p}}(\sum_{v\in\mathcal{V}_{q}}\hat{\mathbf{A}}[u,v](\mathbf{H}[u,s]-\mathbf{H}[v,s])^{2}$
	$\displaystyle-$	$\displaystyle\sum_{u\in\mathcal{V}_{p}}(\sum_{v\in\mathcal{V}_{q}}\hat{\mathbf{A}}^{\prime}[u,v](\mathbf{H}[u,s]-\mathbf{H}[v,s])^{2}|,$

where $p\neq q$.

Proof. Based on Lemma 1,

$$\|\mathbf{H}[:,s]-\hat{\textbf{A}}\mathbf{H}[:,s]\|_{2}+\|\mathbf{H}[:,s]-\hat{\textbf{A}}^{\prime}\mathbf{H}[:,s]\|_{2}\leq 2\sqrt{n}.$$

In addition,

		$\displaystyle\|\mathbf{H}[:,s]-\hat{\textbf{A}}\mathbf{H}[:,s]\|_{2}\geq 0,$
		$\displaystyle\|\mathbf{H}[:,s]-\hat{\textbf{A}}^{\prime}\mathbf{H}[:,s]\|_{2}\geq 0.$

Thus,

		$\displaystyle\big{|}\|\mathbf{H}[:,s]-\hat{\textbf{A}}\mathbf{H}[:,s]\|_{2}-\|\mathbf{H}[:,s]-\hat{\textbf{A}}^{\prime}\mathbf{H}[:,s]\|_{2}\big{|}$
	$\displaystyle=$	$\displaystyle\frac{\big{|}\|\mathbf{H}[:,s]-\hat{\textbf{A}}\mathbf{H}[:,s]\|^{2}_{2}-\|\mathbf{H}[:,s]-\hat{\textbf{A}}^{\prime}\mathbf{H}[:,s]\|^{2}_{2}\big{|}}{\|\mathbf{H}[:,s]-\hat{\textbf{A}}\mathbf{H}[:,s]\|_{2}+\|\mathbf{H}[:,s]-\hat{\textbf{A}}^{\prime}\mathbf{H}[:,s]\|_{2}}$
	$\displaystyle\geq$	$\displaystyle\frac{1}{2\sqrt{n}}\big{|}\|\mathbf{H}[:,s]-\hat{\textbf{A}}\mathbf{H}[:,s]\|^{2}_{2}-\|\mathbf{H}[:,s]-\hat{\textbf{A}}^{\prime}\mathbf{H}[:,s]\|^{2}_{2}\big{|}$
	$\displaystyle=$	$\displaystyle\frac{1}{2\sqrt{n}}\left|\Big{(}\sum_{u\in\mathcal{V}}\big{(}\sum_{v\in\mathcal{V}}\hat{\mathbf{A}}[u,v](\mathbf{H}[u,s]-\mathbf{H}[v,s])\big{)}^{2}\right.$
	$\displaystyle-$	$\displaystyle\left.\sum_{u\in\mathcal{V}}\big{(}\sum_{v\in\mathcal{V}}\hat{\mathbf{A}}^{\prime}[u,v](\mathbf{H}[u,s]-\mathbf{H}[v,s])\big{)}^{2}\Big{)}\right|.$

Because,

	$\displaystyle\sum_{u\in\mathcal{V}_{p}}\sum_{v\notin\mathcal{V}_{p}}\hat{\mathbf{A}}[u,v](\mathbf{H}[u,s]-\mathbf{H}[v,s])=0,$
	$\displaystyle\sum_{u\in\mathcal{V}_{p}}\sum_{v\notin\mathcal{V}_{p}}\hat{\mathbf{A}}^{\prime}[u,v](\mathbf{H}[u,s]-\mathbf{H}[v,s])=0.$

In addition, based on equation (10), if $u\in\mathcal{V}_{p},v\in\mathcal{V}_{p}$:

$$\hat{\mathbf{A}}[u,v]=\hat{\mathbf{A}}^{\prime}[u,v].$$

Thus,

		$\displaystyle\left|\|\mathbf{H}[:,s]-\hat{\textbf{A}}\mathbf{H}[:,s]\|_{2}-\|\mathbf{H}[:,s]-\hat{\textbf{A}}^{\prime}\mathbf{H}[:,s]\|_{2}\right|$
	$\displaystyle\geq$	$\displaystyle\frac{1}{2\sqrt{n}}\left|\Big{(}\sum_{u\in\mathcal{V}_{p}}\big{(}\sum_{v\in\mathcal{V}_{p}}\hat{\mathbf{A}}[u,v](\mathbf{H}[u,s]-\mathbf{H}[v,s])\right.$
	$\displaystyle+$	$\displaystyle\sum_{v\notin\mathcal{V}_{p}}\hat{\mathbf{A}}[u,v](\mathbf{H}[u,s]-\mathbf{H}[v,s])\big{)}^{2}$
	$\displaystyle-$	$\displaystyle\big{(}\sum_{u\in\mathcal{V}_{p}}(\sum_{v\in\mathcal{V}_{p}}\hat{\mathbf{A}}^{\prime}[u,v](\mathbf{H}[u,s]-\mathbf{H}[v,s])$
	$\displaystyle+$	$\displaystyle\left.\sum_{v\notin\mathcal{V}_{p}}\hat{\mathbf{A}}^{\prime}[u,v](\mathbf{H}[u,s]-\mathbf{H}[v,s])\big{)}^{2}\Big{)}\right|$
	$\displaystyle=$	$\displaystyle\frac{1}{2\sqrt{n}}\left|\sum_{u\in\mathcal{V}_{p}}\big{(}\sum_{v\in\mathcal{V}_{q}}\hat{\mathbf{A}}[u,v](\mathbf{H}[u,s]-\mathbf{H}[v,s])\big{)}^{2}\right.$
	$\displaystyle-$	$\displaystyle\left.\sum_{u\in\mathcal{V}_{p}}\big{(}\sum_{v\in\mathcal{V}_{q}}\hat{\mathbf{A}}^{\prime}[u,v](\mathbf{H}[u,s]-\mathbf{H}[v,s])\big{)}^{2}\right|.$

$\square$

The sensitive feature similarity bound is maximized when $\sum_{u\in\mathcal{V}_{p}}\sum_{v\in\mathcal{V}_{q}}\hat{\mathbf{A}}^{\prime}[u,v]=0$ ($p\neq q$). Thus, setting inter-cluster attention scores to zero enhances GT fairness.

The node feature matrix is essential for graph mining tasks. We select the eigenvectors corresponding to the $t$ largest eigenvalues to construct the structure matrix $\mathbf{S}\in\mathbb{R}^{n\times t}$. Then, We combine the original feature matrix $\mathbf{H}$ with the structure matrix $\mathbf{S}$ to preserve both node features and structural information:

$$\mathbf{H}^{\prime}=\mathbf{H}||\mathbf{S},$$

(13)

where $||$ represents the concatenation operator, and $\mathbf{H}^{\prime}\in\mathbb{R}^{n\times(d+t)}$ denotes the fused feature matrix. FairGT (Luo et al. 2024b) shows that the largest eigenvalues are closely tied to structural information, which tends to be fairer. Thus, the feature matrix contributes to a fairer encoding.

According to the empirical observations and Theorem 1, graph partitioning improves the fairness of GT by reducing the biased influence of higher-order nodes. FairGP partitions the graph into $c$ non-overlapping clusters using METIS (Karypis and Kumar 1998). Let $\mathcal{G}_{p}=\{\mathcal{V}_{p},\mathcal{E}_{p}\}$ represents a subgraph of $\mathcal{G}$, satisfying $\bigcup^{c}_{p=1}\mathcal{G}_{p}=\mathcal{G}$ and $\bigcap^{c}_{p=1}\mathcal{G}_{p}=\emptyset$.

Existing Graph Transformers utilize the global attention mechanism to capture information between all node pairs, causing the higher-order node bias. To obtain the updated hidden representations $\mathbf{I}\in\mathbb{R}^{n\times n}$.

		$\displaystyle\mathbf{I}=\text{FFN}\left(\text{Softmax}\left(\frac{\text{Q}\text{K}^{\top}}{\sqrt{n}}\right)\text{V}\right),$		(14)
		$\displaystyle\text{Q}=\mathbf{H}^{\prime}W^{\text{Q}},\text{K}=\mathbf{H}^{\prime}W^{\text{K}},V=\mathbf{H}^{\prime}W^{\text{V}},$

where $W^{\text{Q}}$, $W^{\text{K}}$, and $W^{\text{V}}\in\mathbb{R}^{n\times n}$. The $W^{\text{Q}}$, $W^{\text{K}}$, and $W^{\text{V}}$ are trainable weights of the linear layers in the Transformer, and FFN represents a Feed-Forward Neural Network.

FairGP separates the attention into inter-cluster and intra-cluster. For the intra-cluster attention $\hat{\mathbf{A}}^{\prime}[u,v]$ where $u,v\in\mathcal{V}_{p}$, the attention is the same as the whole attention score:

$\displaystyle\hat{\mathbf{A}}^{\prime}[u,v]=\hat{\mathbf{A}}[u,v].$

(15)

According to Theorem 2, the attention between different clusters is zero, which helps improve fairness. To achieve this goal, we optimize the attention mechanism accordingly:

$\displaystyle\hat{\mathbf{A}}^{\prime}[u,v]=0,\quad u\in\mathcal{V}_{p}\quad\text{and}\quad v\in\mathcal{V}_{q}.$

(16)

This effectively nullifies the attention between different clusters, thereby enhancing the GT fairness. By focusing on intra-cluster attention and eliminating inter-cluster attention, FairGP ensures a fairer representation of the graph’s structural information.

By dividing the graph into smaller, more manageable clusters, we reduce the computational burden while preserving essential structural information. For each cluster, the time and space complexity is $O\big{(}(\frac{n}{c})^{2}\big{)}$, leading to time and space complexity of FairGP being $O(\frac{1}{c^{2}}n^{2})$. This makes our approach both scalable and efficient, ensuring that FairGP can handle large-scale graphs effectively.

For the experimental study, node classification serves as the downstream task, with four real-world datasets: Credit, Pokec-z, Pokec-n, and Income. Specifically, the datasets are labelled as Pokec-z-R and Pokec-n-R when living region is the sensitive feature, and Pokec-z-G and Pokec-n-G when gender is the sensitive feature. The details of datasets and implementation details are shown in Appendix D.

We use three classes of baselines: GNNs, fairness-aware GNNs, and scalable GTs.

• •

  GNNs: We use three GNNs: GCN (Kipf and Welling 2017), GAT (Velickovic et al. 2018), and APPNP (Klicpera, Bojchevski, and Gunnemann 2019).

• •

  Fairness-aware GNNs: We use four fairness-aware GNNs: FairGNN (Dai and Wang 2023), FairSIN (Yang et al. 2024), FMP (Jiang et al. 2024), and FUGNN (Luo et al. 2024a).

• •

  GTs: We use four scalable GTs and one fairness-aware GT: DIFFormer (Wu et al. 2023a), SGFormer (Wu et al. 2023b), Polynormer (Deng, Yue, and Zhang 2024), CoBFormer (Xing et al. 2024), and FairGT (Luo et al. 2024b).

There are multi-class sensitive features in dataset AMiner-L. The previous fairness evaluation metrics are formulated for binary scenarios, but they can be easily extended into multi-class sensitive feature scenarios following previous work (Jiang et al. 2023). The main idea is to guarantee fairness across all pairs of sensitive subgroups. Quantification strategies can be applied by leveraging either the variance across different sensitive subgroups.

Specifically, the fairness evaluation metrics in multi-class sensitive features are defined as follows:

		$\displaystyle\Delta_{\text{SP}}=\text{Var}_{i=1}^{m}\big{(}|\mathbb{P}(\hat{y}=1|s=i)\big{)},$		(17)
		$\displaystyle\Delta_{\text{EO}}=\text{Var}_{i=1}^{m}\big{(}|\mathbb{P}(\hat{y}=1|y=1,s=i)\big{)},$

where class number denotes $m$.

Table 2 offers a detailed comparison of the fairness evaluation metrics for our proposed FairGP method against various baseline models across four real-world datasets. Further comparison results for other datasets are included in Appendix E. Notably, Pokec-z-R and Pokec-z-G are the same datasets examined under two different sensitive features. FairGP effectively addresses the multi-sensitive feature issue, as confirmed by the correlation results. We present metrics such as overall Accuracy, AUC, $\Delta_{\text{SP}}$, and $\Delta_{\text{EO}}$. The table clearly indicates that FairGP consistently achieves superior fairness, validating the efficacy of our approach in fairness-aware node classification. FairGP not only improves fairness compared to traditional GTs but also surpasses existing fairness-aware GNN methods in fairness metrics. This highlights its effectiveness in addressing fairness-related issues in scalable GTs, demonstrating the practicality of FairGP for real-world applications.

FairGP as a fair scalable GT achieves its objectives through three key components: feature matrix, graph partitioning and attention optimization. To comprehensively assess the contributions of these three elements, we conducted an ablation study. Specifically, we aim to examine the extent to which feature matrix, graph partitioning and attention optimization contribute to improving prediction fairness. In this analysis, we systematically remove each component independently to assess their individual impact.

The FairGP without graph partitioning is denoted as w/o GP. Since GT without graph partitioning encounters out-of-memory issues in large-scale graphs, we employ mini-batch processing, a typical scalable technique, to keep it running. Even when compared to results using the mini-batch technique, FairGP shows a significant improvement in fairness, with enhancements of at least 25% across all datasets, and in some instances, exceeding 90%. These results validate our findings that graph partitioning improves GT fairness.

The FairGP with a feature matrix that excludes structural features is denoted as w/o FM, and without attention optimization is denoted as w/o AO. Notably, when comparing w/o FM, and w/o AO, FairGP consistently outperforms them in terms of accuracy and fairness. The results shown in Table 3 reinforce the necessity of graph partitioning and attention optimization within FairGP. More ablation experiments for other datasets are shown in Appendix F.

FairGP, partitioning a graph into clusters, exhibits efficiency compared to GTs. To validate the efficiency of FairGP, we compare its training time with GT baselines. For a fair comparison, we standardize key parameters across all methods, setting the number of hidden dimensions to 128, the number of layers to 1, and the number of heads to 1. In addition, all models are evaluated with a runtime of 100 epochs, and the units are in seconds. The runtimes of different sensitive features in the same dataset are identical. Therefore, we combine the results of Pokec-z-R and Pokec-z-G into Pokec-z. The same approach is applied to Pokec-n. The runtimes of FairGP and GT baselines are shown in Table 4, and the runtimes of computing $\mathbf{S}$ are shown in Appendix G.