1 Introduction↩︎

Graph-structured data, consisting of graph topology and node features, is ubiquitous in real-world scenarios, including social networks [1], traffic networks [2], and molecular structures [3]. While graph neural networks (GNNs) [4]–[6] have emerged as a powerful approach for modeling such data, recent studies [7]–[9] reveal a critical concern: GNNs yield biased predictions against demographic groups defined by sensitive attributes, e.g., gender and race. This phenomenon is referred to as group unfairness and poses significant ethical risks, hindering the deployment of GNNs in high-stakes applications.

To alleviate this phenomenon, a number of studies have been conducted to improve the fairness of trained GNNs. A popular paradigm is adversarial training [7], [10], [11], which seeks to learn fair representations by ensuring that node embeddings are invariant to sensitive attributes through minimax optimization. In addition to adversarial approaches, diverse strategies have been employed to mitigate bias, including group distribution distance minimization [12], disentanglement [13], re-balancing [14], neutralization [15], and alignment [16]. In summary, the core idea behind these methods is to eliminate sensitive attribute information from model outcomes through well-designed fairness constraints. Despite their success, these methods rely heavily on the availability of sensitive attributes, as shown in the pink areas of Fig. 1. However, in real-world scenarios, sensitive attributes, also known as demographics, may be unavailable due to stringent privacy regulations. For example, the General Data Protection Regulation (GDPR) [17] strictly mandates the protection of personal data concerning racial origin, political opinions, or religious beliefs. Consequently, developing fairness-aware GNNs in the absence of demographics has emerged as a critical and urgent challenge for real-world applications.

To bridge this gap, recent studies [18], [19] attempt to achieve fairness without demographics. As shown in the blue areas of Fig. 1, existing methods can be categorized into two streams based on whether they use predicted demographic information. The first and more popular stream, e.g., Fairwos [20], follows a predict-then-constrain pipeline, which first predicts demographics and then enforces fairness constraints based on this predicted information. However, the inevitable discrepancy between inferred demographics and the ground truth often renders such constraints ineffective or counterproductive. To avoid this limitation, a second line of work, including FairGKD [21] and our proposed method, seeks to mitigate bias without explicit demographic inference. While FairGKD [21] explores the relationship between biases and partial data training, e.g., using only node features, it primarily targets high-level bias mitigation. As a result, addressing fairness-related biases is often treated as a byproduct rather than a primary objective, ultimately leading to marginal improvements in fairness.

A recent study [22] suggests that gradients are more effective in representing sensitive attributes, a phenomenon which has been primarily validated on tabular data but remains under-explored in the graph domain. Motivated by this, we investigate the gradient behavior of misclassified samples in graph-structured data. As shown in Fig. 2, we conduct a statistical analysis of gradient distributions and observe that different demographic groups exhibit distinct gradient distributions within the subset of misclassified nodes. Remarkably, in some cases, these gradient profiles possess sufficient discriminative power to allow for the accurate inference of demographic labels. Further details regarding this empirical observation are provided in Section 4. Consequently, exploiting the demographic signals naturally embedded within gradients offers a principled approach to enhancing algorithmic fairness.

In this work, we explore achieving fairness through gradients in the absence of demographic information. First, we introduce GradDist, a bias evaluation metric that quantifies the degree of unfairness by measuring the distributional divergence between peaks in the gradient density distributions. Second, we propose a simple yet effective approach named Gradient-to-Fairness (Grad2Fair) to ensure fairness without demographics. Specifically, Grad2Fair consists of two stages: bias amplification and upweighting via gradient. The first stage intentionally leverages shortcut learning to amplify inherent model biases. Building upon these amplified signals, the second stage mitigates bias through upweighting training based on gradients. Through this design, Grad2Fair maintains a minimal architectural footprint, offering a high-performance yet computationally efficient solution for fair GNNs. Our contributions are as follows:

• We introduce GradDist, an empirically driven metric for bias evaluation in the absence of demographics. Based on the insights from Fig. 2, GradDist quantifies algorithmic bias by measuring the inter-modal distance between the peaks of gradient density distributions.

• We propose Grad2Fair, a novel approach for fairness without demographics. Inspired by the discovered correlation between gradient distributions and demographics, Grad2Fair adaptively reweights the training objective to prioritize informative yet challenging samples.

• We first provide an empirical validation of GradDist, followed by a systematic evaluation of Grad2Fair from both theoretical and empirical standpoints. Experimental results demonstrate that Grad2Fair outperforms state-of-the-art baselines in most cases, while maintaining superior computational efficiency.

The remainder of this paper is organized as follows. Section 2 provides a brief overview of related literature. Section 3 introduces the necessary notations and formalizes the problem definition. Section 4 presents an empirical investigation and introduces a bias evaluation metric for fairness without demographics. Section 5 introduces details of our proposed approach Grad2Fair, followed by the complexity analysis. Section 6 presents experimental results to verify the effectiveness of Grad2Fair. Finally, Section 7 summarizes this paper and highlights its limitations.

2 Related Work↩︎

In this section, we provide a brief overview of related literature, including group fairness in graph learning and fairness without demographic information.

2.1 Group Fairness in Graph Learning↩︎

Group fairness methods in graph learning aim to develop fair graph algorithms that provide equitable outcomes across groups defined by sensitive attributes, such as race or age. While early research focused on traditional graph mining [23], the emergence of GNNs [5], [24] has shifted the focus toward ensuring fairness within deep graph models. These studies can be categorized into pre-processing and in-processing methods. Pre-processing methods focus on mitigating biases within the data itself to provide clean inputs for training. For example, FairDrop [9] utilizes a biased edge dropout algorithm to reduce homophily with respect to the sensitive attribute. EDITS [12] minimizes the Wasserstein distance between groups to debias node attributes and topology. Similarly, Graphair [11] employs adversarial learning to guide data debiasing, and FairAGG [25] reweights edges based on their fairness contributions via Shapley values. In contrast, in-processing methods integrate fairness constraints directly into the training process. FairGNN [7] and FairVGNN [10] leverage adversarial learning to learn representations that are independent of sensitive attributes. NIFTY [8] incorporates counterfactual contrastive learning to ensure model invariance, while FairGB [14] employs counterfactual node mixup and contribution alignment loss to rebalance groups during training. FairINV [26] reframes group fairness as invariant learning and employs an invariant objective. To address the potential utility degradation caused by fairness-aware training, FairSAD [13], FUGNN [27], and FairSIN [15] investigate the trade-off between utility and fairness. Beyond these core areas, research has also expanded into fairness under distribution shifts [28], fair graph transformers [29], [30], fair federated graph learning [31], and fairness considering false positives [32].

Despite significant progress, most existing pre-processing and in-processing methods rely on the strong assumption that demographic information is fully available. In practice, however, such information is frequently inaccessible due to stringent privacy regulations and legal constraints. To address this, Grad2Fair aims to achieve fairness without demographic information, thereby providing a solution for this practical scenario.

2.2 Fairness without Demographics↩︎

Driven by strict privacy regulations, fairness without demographics [33] has emerged as a pivotal research frontier in machine learning. One prominent research trajectory exploits the relationship between non-sensitive features and sensitive attributes. Recognizing that features highly correlated with sensitive attributes act as proxies, several studies, e.g., FairRF [34], minimize the correlation between non-sensitive features and final predictions to achieve fairness. Meanwhile, another line of studies focuses on Rawlsian Max-Min fairness [35] without demographics, which maximizes the performance of the worst-off groups. For example, distributionally robust optimization (DRO) [36] employs a robust optimization framework to enhance performance for high-loss subpopulations. To address the susceptibility of DRO to noise, adversarial reweighted learning (ARL) [37] identifies and improves computationally identifiable groups via adversarial training. Additionally, recent advancements [38] have further integrated paradigms like invariant representation learning and knowledge distillation to improve Rawlsian Max-Min fairness without demographics. However, these methods have been predominantly validated on tabular data, leaving their effectiveness on graph-structured data under-explored.

In graphs, research on fairness without demographics can be classified into two paradigms, depending on whether predicted demographics are used. The first paradigm follows a two-stage approach, i.e., initially predicting demographics and subsequently enforcing fairness constraints based on these surrogates. Representative methods, including Fairwos [20], fairGNN-WOD [18], and Themis [19], fall into this paradigm. However, these methods inevitably suffer from inaccurate demographic predictions, which limits their effectiveness in improving fairness. The second paradigm bypasses explicit demographic predictions by learning fair GNNs directly. For example, building upon the insight that partial data training can mitigate bias, FairGKD [21] leverages a knowledge distillation framework, guiding a student model via a fair teacher trained on partial data. Nevertheless, FairGKD [21] treats group fairness as a collateral benefit of high-level bias mitigation, which frequently results in suboptimal fairness gains. In contrast, Grad2Fair belongs to this latter paradigm but introduces a more principled approach. By delving into the relationship between gradients and unknown sensitive attributes, Grad2Fair performs bias mitigation tailored for fairness-related bias, significantly outperforming FairGKD in terms of fairness performance.

3 Preliminaries↩︎

3.1 Notations↩︎

For clarity, we provide a brief introduction to the notations related to our work. We focus on the node classification task and denote \(Y\in \{0,1\}^n\) as the node label vector. Let \(\mathcal{G} = (\mathcal{V}, \mathcal{E}, X)\) denote an undirected attributed graph, where \(\mathcal{V}\) is a set of \(|\mathcal{V}| = n\) nodes and \(\mathcal{E}\) is a set of \(|\mathcal{E}| = m\) edges. \(X\in \mathbb{R}^{n \times d}\) represents the node feature matrix with \(d\) dimensions. The adjacency matrix \(A\in \{0,1\}^{n\times n}\) describes the graph topology, where \(A_{uv}=1\) if an edge \(e_{uv}\in \mathcal{E}\) connects node \(u\) and \(v\), and \(A_{uv}=0\) otherwise. \(S\in\{0,1\}^{n}\) represents the binary sensitive attribute, where \(S_{u}=S_{v}\) indicates that nodes \(u\) and \(v\) belong to the same demographic group. \(\tilde{X}\in \mathbb{R}^{n \times (d-1)}\) is the node feature matrix without \(S\).

3.2 Group Fairness in GNNs↩︎

Group fairness in GNNs focuses on the equity of model predictions across demographic groups. For clarity, we take binary classification as an example to describe group fairness in GNNs. Given an undirected attributed graph \(\mathcal{G} = (\mathcal{V}, \mathcal{E}, X)\), a GNN classifier \(f(\cdot)\) takes \(\mathcal{G}\) as input and predicts node labels \(\hat{Y}\in \{0,1\}^{n}\). The group fairness can be evaluated using demographic parity (DP) [39] and equal opportunity (EO) [40]. Specifically, demographic parity requires predictions to be independent of the sensitive attribute \(S\), and equal opportunity ensures the same true positive rate for each demographic group. Group fairness of GNNs is commonly measured by the DP and EO differences between two demographic groups, which can be defined as follows: \[\label{eq:metric} {!}{ \begin{align} \Delta_{DP} &= \lvert P(\hat{Y}_v=1 \mid S_v=0) - P(\hat{Y}_v=1 \mid S_v=1) \rvert, \\ \Delta_{EO} &= \lvert P(\hat{Y}_v=1 \mid Y_v=1, S_v=0) - P(\hat{Y}_v=1 \mid Y_v=1, S_v=1) \rvert, \end{align} }\tag{1}\] where small \(\Delta_{DP}\) and \(\Delta_{EO}\) indicate fairer GNN models.

3.3 Problem Definition↩︎

In this work, we investigate the problem of graph fairness without demographics, which requires trained models to make fair predictions without access to demographic information during the training, validation, and testing phases. Specifically, given an undirected attributed graph \(\tilde{\mathcal{G}}=(\mathcal{V}, \mathcal{E}, \tilde{X})\) without the sensitive attribute \(S\), along with the node label ground truth \(Y\), our goal is to learn a fair GNN classifier \(f(\cdot)\) on \(\tilde{\mathcal{G}}\). Thus, the optimization problem for group fairness without demographics can be defined as follows: \[\begin{align} \label{definition} \hat{Y} &= f_{\theta}(\tilde{\mathcal{G}}), \\ \theta^{*} &= \arg\min_{\theta}\;\mathcal{L}_{\mathrm{cls}}\!\big(\hat{Y}, Y\big) \quad \text{s.t.} \quad \mathcal{C}_{\mathrm{fair}}\!\big(\hat{Y}; \tilde{\mathcal{G}}\big) \le \epsilon, \end{align}\tag{2}\] where \(\theta\) is the trainable parameter of the model \(f(\cdot)\) and \(\theta^{*}\) is the optimal parameter. \(\mathcal{L}_{\mathrm{cls}}(\cdot,\cdot)\) represents the loss function for the node classification task, and \(\mathcal{C}_{\mathrm{fair}}(\cdot;\cdot)\) represents a fairness constraint function. \(\epsilon\) represents a fairness tolerance threshold, indicating the maximum tolerable fairness disparity.

4 Empirical Investigation and Our Proposed Metric↩︎

Existing methods to improve group fairness without demographics first predict demographic information, which is employed to enforce fairness constraints. However, these predicted demographic attributes often deviate from the true demographic distribution, resulting in suboptimal fairness improvements or even fairness degradation. To bridge this gap, a natural approach is to avoid the utilization of predicted demographics. Consequently, in this section, we conduct a preliminary study to obtain more insights into fairness without demographics. Then, we introduce a metric named GradDist for the bias evaluation without demographics.

4.1 Empirical Investigation↩︎

A recent study [22] reveals that gradients are effective cues for representing demographic information. While this phenomenon has been verified on tabular data, it remains under-explored on graph-structured data. Motivated by this, we conduct a gradient investigation to analyze the correlation between gradients and demographics. Our investigations can be summarized into two parts, i.e., experiments on synthetic and real-world datasets. We first conduct a qualitative experiment on synthetic datasets with varying bias levels. Subsequently, we further verify our observations through an experiment on real-world datasets.

For the experiment on synthetic datasets, we follow the settings in [41] to generate synthetic datasets with different bias levels. Specifically, these synthetic datasets have binary sensitive attributes and node labels. We set the probability \(p_{00}\) of \(S=0, Y=0\) to vary from 0.25 to 0.07 with an interval of 0.03, where \(p_{11}=p_{00}\), \(p_{01}=p_{10}\), \(p_{11}+p_{00}+p_{01}+p_{10}=1\). Meanwhile, we fix other parameters to align the settings of Syn-1 in [41]. For clarity, the seven generated synthetic datasets are referred to as “SynFair0” to “SynFair6”. According to Syn-2 in [41], the larger unbalanced group ratio, i.e., larger \(|p_{00}-p_{01}|\), indicates a more significant unfair prediction and a higher bias level. Consequently, the unfairness degree of “SynFair0/1/2/3/4/5/6” varies from low to high. Based on these synthetic datasets, we train a 2-layer graph convolution network (GCN) classifier and then calculate differences \(\Delta_{grad}\) of average gradient between two demographic groups within misclassified nodes on the training set. As shown in Table 1, we report three types of correlation results: the correlation between the unbalanced group ratio \(\Delta_{|p_{00}-p_{01}|}\) and \(\Delta_{grad}\), and the correlation between the fairness performance \(\Delta_{DP}\) and \(\Delta_{grad}\). According to the definition in [42]–[44], the experimental results demonstrate that \(\Delta_{grad}\) exhibits strong positive correlations with \(\Delta_{|p_{00}-p_{01}|}\) and \(\Delta_{DP}\), respectively. \(\Delta_{|p_{00}-p_{01}|}\) and \(\Delta_{DP}\) are similar metrics for indicating bias levels, with higher values indicating greater bias. Motivated by these strong correlation results, a natural question arises: Do the gradient distributions of misclassified nodes within the training set reveal demographic information? To this end, we visualize gradient distributions on various synthetic datasets, as shown in Fig. 3. As the degree of unfairness of synthetic datasets increases, i.e., from SynFair0 to SynFair6, the gradient distribution between different demographic groups exhibits less overlap, indicating the potential demographic information within the gradient distribution.

For the experiment on real-world datasets, we visualize the gradient distribution of misclassified nodes on two commonly used real-world datasets, i.e., German and Pokec-Z datasets. As shown in Fig. 4, we observe distinct gradient distributions on these two datasets. On the German dataset, the gradient distributions of different demographic groups exhibit little overlap. Conversely, a complete overlap occurs for the gradient distributions between two demographic groups on the Pokec-z dataset, indicating less demographic information.

In summary, we observe that gradient average differences between two demographic groups exhibit strong correlations with the degree of unfairness of datasets. Furthermore, the gradient distribution of misclassified nodes within the training set includes potential demographic information, paving the way to achieve fairness without demographic information.

4.2 Bias Evaluation Metric↩︎

Inspired by our observation on the correlation between \(\Delta_{grad}\) and bias levels, we introduce a bias evaluation metric for bias measurement without demographics, named GradDist. When demographic information is available, bias can be measured by calculating the average gradient difference \(\Delta_{grad}\) between two demographic groups. However, calculating \(\Delta_{grad}\) is infeasible when such information is unavailable. As demonstrated by the results on SynFair4 and 6 in Fig. 3, gradient density curves for different demographic groups exhibit distinct peaks. Furthermore, the overlap between these peaks diminishes as the bias within the dataset increases. The core idea behind GradDist is that a biased model often exhibits distinct learning behaviors across different demographic subgroups, which manifest as distinct clusters (modes) in the gradient space. Thus, given the number of demographic groups, we can search for the position of peaks within gradient density curves and then calculate the difference between peaks.

For simplicity, we take binary sensitive attributes as an example. Considering a set of observed discrete gradients \(\mathcal{Q}_{g} = \{g_1, g_2, \dots, g_M\}\) extracted from a specific layer or loss function during training, we first seek to recover the underlying continuous probability density function (PDF) from these gradient observations. Since the true distribution is a priori unknown, we employ Kernel Density Estimation (KDE) to produce a non-parametric estimate. The estimated PDF \(\hat{f}(g)\) is defined as: \[\hat{f}(g) = \frac{1}{Mh} \sum_{i=1}^{M} K\left(\frac{g - g_i}{h}\right),\] where \(M\) represents the number of nodes in the observed discrete gradient set. \(K(\cdot)\) denotes the standard Gaussian kernel \(K(u) = \frac{1}{\sqrt{2\pi}} e^{-\frac{1}{2}u^2}\) and \(h > 0\) is the smoothing bandwidth. The infinite differentiability of the Gaussian kernel ensures that the resulting density curve is smooth, allowing for rigorous derivative-based analysis of the distribution’s topography. In our implementation, we adopt a bandwidth of \(h=0.15\) to strike an optimal balance between capturing local modalities and suppressing stochastic noise.

Upon obtaining the continuous PDF \(\hat{f}(g)\), the next step involves characterizing the local modes that signify group-specific gradient concentrations. These peaks represent the most frequent gradient magnitudes, physically corresponding to the feature clustering centers of different latent populations. To identify these modes, we treat the peak-finding task as a constrained optimization problem. Specifically, a point \(g^*\) is identified as a representative peak (local maximum) if it satisfies the following calculus-based criteria: \[\frac{d}{dg} \hat{f}(g) \bigg|_{g=g^*} = 0 \quad \text{and} \quad \frac{d^2}{dg^2} \hat{f}(g) \bigg|_{g=g^*} < 0.\]

The first-order condition (stationarity) ensures that the point is a critical point, where the summation \(\sum_{i=1}^{M} K(\frac{g - g_i}{h}) \cdot (g - g_i)\) vanishes. The second-order condition (concavity) distinguishes local maxima from minima or saddle points, ensuring that the density curve is locally downward-opening. By solving these conditions, we obtain a set of candidate peaks \(\mathcal{P} = \{g^*_j\}\). To capture the most significant bias-induced divergence between opposing subgroups, we extract the two most dominant peaks based on their density magnitudes: \[\text{TopPeaks} = \{g^*_1, g^*_2\} \in \arg \text{top-2}_{g^* \in \mathcal{P}} \left( \hat{f}(g^*) \right),\]

Building upon these identified peak coordinates, we define a distance-based metric to quantify the degree of polarization in a scale-invariant manner. We introduce GradDist, which measures the separation between the dominant modes relative to the total empirical range of the observed gradient: \[\texttt{GradDist}= \frac{|g^*_1 - g^*_2|}{\max(\mathcal{Q}_{g}) - \min(\mathcal{Q}_{g})},\] where the denominator serves as a normalization factor that eliminates the influence of varying gradient magnitudes across different tasks or training stages, allowing for cross-model comparisons. A lower GradDist value indicates that the gradients of different samples are concentrated within a unified manifold, suggesting consistent optimization paths for different demographic groups. Conversely, a high GradDist indicates that the model updates are significantly disparate for different demographic groups. In summary, GradDist serves as a robust indicator for measuring algorithmic bias.

5 Methodology↩︎

In this section, we first propose Grad2Fair, followed by a theoretical analysis demonstrating how it improves fairness without demographics. Subsequently, we present the algorithm and complexity analysis to detail our proposed method. As shown in Fig. 5, the core idea of Grad2Fair is to amplify bias and then debias by minimizing gradient disparity between demographic groups. Specifically, Grad2Fair consists of two stages: bias amplification and upweighting via gradients. The bias amplification stage leverages shortcut learning to guide the model to focus on high-confidence samples. This makes the trained model more biased towards the majority group, thereby amplifying bias. Building upon the gradients obtained from the bias amplification stage, the upweighting via the gradient stage upweights the loss contribution of misclassified samples, which steers the model’s focus toward the minority group, thereby improving overall fairness.

5.1 Bias Amplification↩︎

As revealed by our empirical investigation in Section 4.1, the gradient distribution disparity (\(\Delta_{grad}\)) of misclassified nodes exhibits a strong positive correlation with both the dataset’s inherent bias levels and the resulting fairness metrics, e.g., \(\Delta_{DP}\). However, as illustrated in Fig. 4, certain real-world graph datasets, e.g., Pokec-z, exhibit significant overlap in the gradient distributions of different demographic groups. In such scenarios, the demographic information included within the gradient signals is insufficient, making it challenging for the model to effectively identify and mitigate latent biases through gradient information.

To address this challenge, we introduce a bias amplification strategy. Specifically, the core idea behind this strategy is that since the discriminative power of gradient disparity depends on the degree of bias, we can artificially amplify the initial biases captured by the model during the early stages of training. This strategy induces a more distinct gradient distribution that serves as a clear upweighting signal for subsequent debiasing.

As observed in prior studies [45], models initially fit bias-aligned samples before addressing bias-conflicting ones during the training stage. This process reflects the capture of data shortcuts. Consequently, models predict labels for bias-aligned samples with high confidence. We leverage this shortcut learning mechanism to develop a bias amplification strategy. Specifically, we select high-confidence samples to optimize the trained model during the initial training phase, thereby reinforcing the model’s reliance on these shortcuts.

Let \(f_{\theta_{amp}}\) denote a GNN classifier with trainable parameters \(\theta_{amp}\). Given an undirected attributed graph \(\tilde{\mathcal{G}}=(\mathcal{V},\mathcal{E},\tilde{X})\), for each node \(u \in \mathcal{V}_{tr}\), the prediction confidence is defined as \(c_u = \max(f_{\theta_{amp}}( \tilde{\mathcal{G}})_u)\). After a specific number of warm-up epochs, we select a subset of samples \(\mathcal{V}_{sub}\) consisting of those with the highest confidence scores: \[\mathcal{V}_{sub} = \{u \in \mathcal{V}_{tr} \mid c_u > \text{percentile}(c, 1-\tau) \},\] where \(\tau\) is a hyperparameter representing the selection ratio, e.g., 0.25. The optimization objective for this stage is defined as: \[\mathcal{L}_{amp} = \sum_{u \in \mathcal{V}_{sub}} \ell(f_{\theta_{amp}}(\tilde{\mathcal{G}})_u, Y_u),\] where \(\ell(\cdot)\) denotes the cross-entropy loss. By iteratively optimizing \(\mathcal{L}_{amp}\), the model is forced to overfit the shortcut patterns present in the high-confidence samples, thereby amplifying inherent bias.

Theoretical Analysis of Bias Amplification. We provide a theoretical justification for why optimizing \(\mathcal{L}_{amp}\) on the high-confidence subset \(\mathcal{V}_{sub}\) amplifies the inherent bias. Specifically, we model the training dynamics under the shortcut learning paradigm. Let the training nodes be partitioned into two underlying disjoint sets based on the dataset’s latent bias: the bias-aligned (majority) group \(\mathcal{V}_{A}\) and the bias-conflicting (minority) group \(\mathcal{V}_{C}\).

Assumption 1 (Confidence Disparity via Shortcut Learning). Due to the shortcut mechanisms during the warm-up epochs, the GNN model fits the bias-aligned samples much faster than the bias-conflicting ones. Consequently, the confidence distribution is heavily skewed, satisfying: \[P(u \in \mathcal{V}_{A} \mid c_u > \tau) \gg P(u \in \mathcal{V}_{C} \mid c_u > \tau).\]

This implies that the selected subset \(\mathcal{V}_{sub}\) is overwhelmingly dominated by \(\mathcal{V}_{A}\), such that \(|\mathcal{V}_{sub} \cap \mathcal{V}_{A}| \approx |\mathcal{V}_{sub}|\) and \(|\mathcal{V}_{sub} \cap \mathcal{V}_{C}| \approx 0\). Based on Assumption 1, we can define the severity of the model’s bias as the expected loss disparity between the bias-conflicting and bias-aligned groups, denoted as \(\Delta_{loss}(\theta) = \mathbb{E}_{v \in \mathcal{V}_{C}}[\ell_v(\theta)] - \mathbb{E}_{u \in \mathcal{V}_{A}}[\ell_u(\theta)]\). The amplification of bias is equivalent to the strict increase of \(\Delta_{loss}(\theta)\) during the optimization of \(\mathcal{L}_{amp}\).

Theorem 1 (Bias Amplification via Skewed Gradient Flow). Given a sufficiently small learning rate \(\eta > 0\) and the optimization step \(\theta_{t+1} = \theta_t - \eta \nabla_{\theta} \mathcal{L}_{amp}(\theta_t)\), optimizing the model on the high-confidence subset \(\mathcal{V}_{sub}\) strictly increases the bias severity, i.e., \(\Delta_{loss}(\theta_{t+1}) > \Delta_{loss}(\theta_t)\).

Proof Sketch. Following Assumption 1, the gradient of the average amplification loss \(\mathcal{L}_{amp}\) is dominated by the bias-aligned samples: \[\nabla_{\theta} \mathcal{L}_{amp}(\theta_t) \approx \frac{1}{|\mathcal{V}_{sub}|} \sum_{u \in \mathcal{V}_{sub} \cap \mathcal{V}_{A}} \nabla_{\theta} \ell_u(\theta_t).\]

Assuming the loss function \(\ell\) is \(L\)-smooth, applying the Taylor expansion to the loss of an arbitrary node \(x\) at step \(t+1\) gives: \[\ell_x(\theta_{t+1}) = \ell_x(\theta_t) - \eta \langle \nabla_{\theta} \ell_x(\theta_t), \nabla_{\theta} \mathcal{L}_{amp}(\theta_t) \rangle + R_x,\] where the remainder \(R_x\) is uniformly bounded by \(|R_x| \le \frac{L}{2} \eta^2 \|\nabla_{\theta} \mathcal{L}_{amp}(\theta_t)\|^2\).

Because the optimization direction is dominated by \(\mathcal{V}_{A}\), we assume there exist constants \(\alpha > 0\) and \(\beta \ge 0\) with \(\alpha > \beta\) such that the expected gradient correlations satisfy: \[\mathbb{E}_{u \in \mathcal{V}_{A}}[\langle \nabla_{\theta} \ell_u(\theta_t), \nabla_{\theta} \mathcal{L}_{amp}(\theta_t) \rangle] \ge \alpha \|\nabla_{\theta} \mathcal{L}_{amp}(\theta_t)\|^2,\] \[\mathbb{E}_{v \in \mathcal{V}_{C}}[\langle \nabla_{\theta} \ell_v(\theta_t), \nabla_{\theta} \mathcal{L}_{amp}(\theta_t) \rangle] \le \beta \|\nabla_{\theta} \mathcal{L}_{amp}(\theta_t)\|^2.\]

Taking the expectation of the loss difference for both demographic groups, we obtain: \[\begin{align} \begin{aligned} \mathbb{E}_{u \in \mathcal{V}_{A}}[\ell_u(\theta_{t+1}) - \ell_u(\theta_t)] \le &-\eta \alpha \|\nabla_{\theta} \mathcal{L}_{amp}(\theta_t)\|^2 \\ &+ \frac{L}{2} \eta^2 \|\nabla_{\theta} \mathcal{L}_{amp}(\theta_t)\|^2, \end{aligned} \end{align}\] \[\begin{align} \begin{aligned} \mathbb{E}_{v \in \mathcal{V}_{C}}[\ell_v(\theta_{t+1}) - \ell_v(\theta_t)] \ge &-\eta \beta \|\nabla_{\theta} \mathcal{L}_{amp}(\theta_t)\|^2 \\ & - \frac{L}{2} \eta^2 \|\nabla_{\theta} \mathcal{L}_{amp}(\theta_t)\|^2. \end{aligned} \end{align}\]

Subtracting the expected change of the bias-aligned group from that of the bias-conflicting group yields the change in bias severity: \[\begin{align} \begin{aligned} \Delta_{loss}(\theta_{t+1}) - \Delta_{loss}(\theta_t) \ge &\eta (\alpha - \beta) \|\nabla_{\theta} \mathcal{L}_{amp}(\theta_t)\|^2\\ &- L \eta^2 \|\nabla_{\theta} \mathcal{L}_{amp}(\theta_t)\|^2. \end{aligned} \end{align}\]

For a sufficiently small learning rate satisfying \(\eta < \frac{\alpha - \beta}{L}\), the first-order inner product terms strictly dominate the remainder bounds. Consequently, we obtain: \[\Delta_{loss}(\theta_{t+1}) - \Delta_{loss}(\theta_t) > 0\] which directly implies \(\Delta_{loss}(\theta_{t+1}) > \Delta_{loss}(\theta_t)\). In summary, the theoretical analysis above proves the effectiveness of our bias amplification strategy, which provides a foundation for the subsequent debiasing. \(\hfill \blacksquare\)

5.2 Upweighting via Gradient↩︎

The bias amplification strategy described in Section 5.1 successfully bridges the gap between latent demographic groups and observable gradient signals. Specifically, under the bias-amplified model \(f_{\theta_{amp}}\), different demographic groups exhibit distinct gradient distributions, even without explicit access to sensitive attributes \(S\). This enables the gradient space to serve as an effective proxy for identifying latent minority groups, providing a novel pathway for achieving fairness without relying on demographics. Unlike existing methods that rely on latent variable discovery via auxiliary models, e.g., VAEs, which are prone to error propagation, our approach utilizes the amplified gradient sensitivity as a sample-specific weighting signal.

Given an undirected attributed graph \(\tilde{\mathcal{G}}=(\mathcal{V}, \mathcal{E}, \tilde{X})\), the bias-amplified model \(f_{\theta_{amp}}\) quantifies the fitting difficulty and feature sensitivity of each node. To derive a node-specific importance score, we compute the gradient of the loss function with respect to the input features \(\tilde{X}\) for each node \(u \in \mathcal{V}_{tr}\): \[g_u = \nabla_{\tilde{X}_u} \ell(f_{\theta_{amp}}(\tilde{\mathcal{G}})_u, Y_u), \quad k_u = \|g_u\|_2.\]

We adopt the gradient norm relative to input features rather than model parameters because the former directly captures the local geometry of the decision boundary around each specific sample. As shown in Theorem 1, since the bias amplification stage forces the decision boundary to overfit the majority group’s shortcut patterns, nodes from the minority group (bias-conflicting samples) are pushed into regions with high loss and sharp gradient transitions, resulting in larger \(k_u\) values.

To balance the contributions across groups while maintaining the model’s overall utility, we focus on the set of misclassified nodes \(\mathcal{M} = \{u \in \mathcal{V}_{tr} \mid \text{argmax}(f_{\theta_{amp}}(\tilde{\mathcal{G}})_u) \neq Y_u\}\), as these nodes are most likely to be victims of model bias. We apply min-max normalization to the gradient norms within \(\mathcal{M}\) to ensure stability across different datasets: \[\tilde{k}_u = \frac{k_u - \min_{v \in \mathcal{M}}(k_v)}{\max_{v \in \mathcal{M}}(k_v) - \min_{v \in \mathcal{M}}(k_v) + \epsilon},\] where \(\epsilon\) is a small constant for numerical stability. We then assign an importance weight \(w_u\) to each node \(u\): \[\label{eq:upweight} w_u = \begin{cases} 1 + \lambda \cdot \tilde{k}_u, & \text{if } u \in \mathcal{M}, \\ 1, & \text{otherwise}, \end{cases}\tag{3}\] where \(\lambda > 0\) is a hyperparameter controlling the strength of the debiasing. Finally, the model is trained by minimizing the weighted objective function: \[\mathcal{L}_{upweight} = \sum_{u \in \mathcal{V}_{tr}} w_u \cdot \ell(f_{\theta}(\tilde{\mathcal{G}})_u, Y_u).\]

By assigning higher weights to misclassified nodes with larger gradient norms, the model is guided to refine its decision boundary for the minority group, thereby improving fairness.

Theoretical Analysis of Upweighting via Gradient. We extend our theoretical framework in Section 5.1 to formally demonstrate how minimizing \(\mathcal{L}_{upweight}\) mitigates the bias amplified in the previous stage. Recall that \(\mathcal{V}_{A}\) and \(\mathcal{V}_{C}\) denote the bias-aligned (majority) and bias-conflicting (minority) groups, respectively, and bias severity is defined as \(\Delta_{loss}(\theta) = \mathbb{E}_{v \in \mathcal{V}_{C}}[\ell_v(\theta)] - \mathbb{E}_{u \in \mathcal{V}_{A}}[\ell_u(\theta)]\).

Assumption 2 (Weight Disparity via Amplified Gradients). Due to the bias amplification stage (Theorem 1), nodes in \(\mathcal{V}_{C}\) are predominantly misclassified and exhibit sharper gradient transitions, i.e., larger \(k_u\). Consequently, the assigned importance weights for the minority group are strictly larger in expectation than those for the majority group: \[\mathbb{E}_{v \in \mathcal{V}_{C}}[w_v] \gg \mathbb{E}_{u \in \mathcal{V}_{A}}[w_u].\]

Assumption 3 (Gradient Alignment via Upweighting). While Assumption 2 guarantees weight disparity, we further assume that the weighted global gradient flow aligns more closely with the descent direction of the heavily weighted minority group. Formally, we assume there exist constants \(\gamma_C > \gamma_A > 0\) such that the expected inner products between individual sample gradients and the overall upweighted gradient \(\nabla_{\theta} \mathcal{L}_{upweight}(\theta)\) satisfy: \[\small \mathbb{E}_{v \in \mathcal{V}_{C}}[\langle \nabla_{\theta} \ell_v(\theta), \nabla_{\theta} \mathcal{L}_{upweight}(\theta) \rangle] \ge \gamma_C \|\nabla_{\theta} \mathcal{L}_{upweight}(\theta)\|^2,\] \[\small \mathbb{E}_{u \in \mathcal{V}_{A}}[\langle \nabla_{\theta} \ell_u(\theta), \nabla_{\theta} \mathcal{L}_{upweight}(\theta) \rangle] \le \gamma_A \|\nabla_{\theta} \mathcal{L}_{upweight}(\theta)\|^2.\]

This assumption captures the typical optimization dynamics in upweighting strategies: upweighting a specific subset naturally forces the overall gradient update to be strongly correlated with the average gradient of that subset.

Theorem 2 (Bias Mitigation via Weighted Gradient Flow). Under Assumptions 2 and 3, given a sufficiently small learning rate \(\eta > 0\), and the optimization step \(\theta_{t+1} = \theta_t - \eta \nabla_{\theta} \mathcal{L}_{upweight}(\theta_t)\), optimizing the weighted objective strictly decreases the bias severity, i.e., \(\Delta_{loss}(\theta_{t+1}) < \Delta_{loss}(\theta_t)\).

Proof Sketch. The gradient of the upweighting objective is a weighted sum of individual gradients. Under Assumption 3, the optimization direction \(\nabla_{\theta} \mathcal{L}_{upweight}(\theta_t)\) is highly correlated with the descent direction of \(\mathcal{V}_{C}\) (\(\gamma_C > \gamma_A\)).

Assuming the loss function \(\ell\) is \(L\)-smooth, applying the Taylor expansion to an arbitrary node \(x\) yields \(\ell_x(\theta_{t+1}) = \ell_x(\theta_t) - \eta \langle \nabla_{\theta} \ell_x(\theta_t), \nabla_{\theta} \mathcal{L}_{upweight}(\theta_t) \rangle + R_x\), with the remainder uniformly bounded by \(|R_x| \le \frac{L}{2} \eta^2 \|\nabla_{\theta} \mathcal{L}_{upweight}(\theta_t)\|^2\).

Taking the expectation of the loss changes for both groups, we establish the upper bound for the minority group and the lower bound for the majority group based on the correlation bounds defined in Assumption 3: \[\begin{align} \begin{aligned} \mathbb{E}_{v \in \mathcal{V}_{C}}[\ell_v(\theta_{t+1}) - \ell_v(\theta_t)] \le &-\eta \gamma_C \|\nabla_{\theta} \mathcal{L}_{upweight}(\theta_t)\|^2 \\ &+ \frac{L}{2} \eta^2 \|\nabla_{\theta} \mathcal{L}_{upweight}(\theta_t)\|^2, \end{aligned} \end{align}\] \[\begin{align} \begin{aligned} \mathbb{E}_{u \in \mathcal{V}_{A}}[\ell_u(\theta_{t+1}) - \ell_u(\theta_t)] \ge &-\eta \gamma_A \|\nabla_{\theta} \mathcal{L}_{upweight}(\theta_t)\|^2 \\ &- \frac{L}{2} \eta^2 \|\nabla_{\theta} \mathcal{L}_{upweight}(\theta_t)\|^2. \end{aligned} \end{align}\]

Subtracting the expected change of the majority group from that of the minority group bounds the change in bias severity: \[\begin{align} \begin{aligned} \Delta_{loss}(\theta_{t+1}) - \Delta_{loss}(\theta_t) \le &-\eta (\gamma_C - \gamma_A) \|\nabla_{\theta} \mathcal{L}_{upweight}(\theta_t)\|^2 \\ &+ L \eta^2 \|\nabla_{\theta} \mathcal{L}_{upweight}(\theta_t)\|^2. \end{aligned} \end{align}\]

For a sufficiently small learning rate satisfying \(\eta < \frac{\gamma_C - \gamma_A}{L}\), the first-order negative term dominates, yielding: \[\Delta_{loss}(\theta_{t+1}) - \Delta_{loss}(\theta_t) < 0.\]

This process establishes that optimizing under the proposed upweighting strategy steadily reduces the expected loss disparity between the minority and majority groups, formally validating its effectiveness in mitigating the amplified bias. \(\hfill \blacksquare\)

5.3 Algorithm and Complexity Analysis↩︎

In this subsection, we summarize the training algorithm of our proposed method and then provide a theoretical analysis of its efficiency in terms of time and space complexity.

5.3.1 Algorithm↩︎

Algorithm 6 presents a detailed training process of Grad2Fair. Specifically, the training process consists of two stages: 1) Bias Amplification: an initial phase to amplify bias by optimizing over a high-confidence subset. 2) Upweighting via Gradient: a subsequent debiasing phase via a weighted loss function derived from the gradient information of the bias-amplified model.

5.3.2 Complexity Analysis↩︎

Let \(n = |\mathcal{V}|\), \(m = |\mathcal{E}|\), \(L\) be the number of GNN layers, and \(d\) be the hidden dimension. Here, we analyze the complexity of Grad2Fair.

Time Complexity: The time complexity of Grad2Fair is primarily determined by the GNN forward and backward passes, taking \(\mathcal{O}(L(md + nd^2))\) per epoch. Meanwhile, the bias amplification stage requires \(E_{amp}\) epochs, where the per-epoch sorting cost \(\mathcal{O}(n \log n)\) for subset selection is asymptotically dominated and negligible. The upweighting via gradient stage requires one additional forward and backward pass to compute input gradients for \(\mathcal{M}\), followed by \(E_{upweight}\) training epochs. The weight assignment has a complexity of \(\mathcal{O}(nd)\), which is negligible. Overall, the total time complexity is \(\mathcal{O}((E_{amp} + E_{upweight} + 1) \cdot L(md + nd^2))\). The single extra pass is a one-time cost. Thus, Grad2Fair introduces no asymptotic time overhead compared to standard GNN training.

Space Complexity: The baseline memory footprint includes the graph structure \(\mathcal{O}(m + nd)\) and model parameters \(\mathcal{O}(Ld^2)\). During the upweighting via gradient stage, calculating input gradients requires temporary memory, but we only persistently cache the derived scalar importance weights \(w_u\), reducing the extra overhead to just \(\mathcal{O}(n)\). Consequently, the overall space complexity remains \(\mathcal{O}(m + nd + Ld^2)\). Grad2Fair introduces only a marginal constant-factor memory increase, preserving the space complexity of the base architecture.

6 Experiments↩︎

In this section, we evaluate our method on the node classification task using four widely used real-world datasets and three synthetic datasets. We compare Grad2Fair with three state-of-the-art baselines for fair node classification, namely FairGKD [21], Fairwos [20], and FDKD [46], across two representative GNN backbones.

6.1 Experimental Setup↩︎

Datasets: We conduct experiments on four widely used real-world datasets and three synthetic datasets. Real-world datasets include Bail [47], Credit [48], Pokec-z [49], and Pokec-n [49], which cover diverse application scenarios. For all real-world datasets, we adopt a standard train/validation/test split ratio of 50%/25%/25% for node partitioning. For synthetic datasets, we generate SynFair following the setting of [41], while AttrBias and StruBias are constructed based on the protocols in [12]. We split these synthetic datasets into train/validation/test sets according to the ratio of 60%/20%/20%. Detailed descriptions of the real-world datasets are as follows:

• Bail: A judicial decision-making dataset containing records of defendants released on bail during the period 1990–2009. Nodes correspond to these defendants, and edges are built according to the similarity of defendants’ personal demographics and past criminal history records. The task is to classify whether defendants are on bail or not, with “race" as the sensitive attribute.

• Credit: A real-world dataset focusing on credit card user payment behavior, providing detailed information about users’ credit accounts and historical payment records. Nodes are credit card users, and edges are formed based on the similarity of users’ payment behavior and account information. The task is to predict future credit card payment defaults, with “age" as the sensitive attribute.

• Pokec-z/Pokec-n: Two subsets sampled from Pokec, the most popular social network in Slovakia, with anonymized user data collected in 2012. These two subsets are partitioned based on users’ geographic provinces. Nodes represent social network users, and edges are precomputed from the inherent social connections between platform users. The task is to infer users’ working fields, with “region" as the sensitive attribute.

Detailed descriptions of the synthetic datasets are as follows:

• SynFair: SynFair consists of seven subsets with different degrees of unfairness, referred to as “SynFair0/1/2/3/4/5/6”, varying from a low degree of unfairness to a high degree. We generate SynFair following the setting of “Syn-1” in [41]. For each subset, we set the number of nodes to 5,000. To generate subsets with different unfairness, we vary the probability \(p_{00}\) (where \(S=0\) and \(Y=0\)) from 0.25 to 0.07 with an interval of 0.03, where \(p_{11}=p_{00}\), \(p_{01}=p_{10}\), \(p_{11}+p_{00}+p_{01}+p_{10}=1\). The generated datasets correspond to “SynFair0/1/2/3/4/5/6”.

• AttrBias/StruBias: AttrBias and StruBias are synthetic datasets with different attribute bias and structural bias, respectively. We generate AttrBias and StruBias adopting the synthetic configurations for biased attributes and structures detailed in [12]. Specifically, both datasets consist of 1,000 nodes, with the binary sensitive attribute evenly distributed. The binary labels for the downstream task are derived from the sum of the third and fourth feature dimensions, combined with injected Gaussian noise. This formulation ensures that the ground-truth targets are theoretically independent of the sensitive attribute.

  • AttrBias: This dataset simulates a scenario with severe attribute bias but a completely fair graph structure. Each node is assigned a 10-dimensional feature vector. To inject attribute bias, the first two feature dimensions are drawn from distinct Gaussian distributions based on the sensitive group: \(\mathcal{N}(-\mu, 1^2)\) for \(S=0\) and \(\mathcal{N}(\mu, 1^2)\) for \(S=1\). To generate datasets with different bias levels, we vary \(\mu\) in the range of \(\{1,2,3,4,5,6,7\}\). The remaining eight dimensions are drawn from an unbiased uniform distribution \(\mathcal{U}(0, 1)\). The network structure is generated using an Erdős-Rényi random graph model with a uniform edge probability of \(p=0.002\), ensuring the topology remains agnostic to the demographic groups.

  • StruBias: This dataset simulates a scenario characterized by extreme structural homophily and group isolation, while maintaining perfectly unbiased node features. Each node is assigned a 10-dimensional feature vector. The first two feature dimensions are independently drawn from the same standard Gaussian, and the rest of the features are sampled from uniform distributions. To construct the biased topology, we rank nodes based on the sum of their first two feature dimensions. We can control the intra-community edge probability \(p_{intra}\) to generate StruBias. We vary the intra-community edge probability \(p_{intra}\) in the range of \(\{0.05,0.1,0.15,0.2,0.25,0.3,0.35\}\), while setting the inter-community edge probability \(p_{inter}\) and \(k\) to 0.0001 and 250, resulting in seven datasets with different bias levels.

Evaluation Metrics: We evaluate the performance of Grad2Fair from two complementary perspectives, i.e., utility and fairness. For utility evaluation, we leverage F1-score and ACC as evaluation metrics, where higher values indicate better utility performance. For fairness evaluation, we use two classic fairness metrics, i.e., \(\Delta_{\text{DP}}\) [39] and \(\Delta_{\text{EO}}\) [40], which can be computed as Eq. 1 . Smaller \(\Delta_{\text{DP}}\) and \(\Delta_{\text{EO}}\) values indicate better group fairness.

Baselines: We compare Grad2Fair with three state-of-the-art baseline methods for fair node classification, namely, FairGKD [21], Fairwos [20], and FDKD [46].

• FairGKD [21]: A demographic-agnostic method for learning fair GNNs without accessing sensitive attributes during training. Motivated by the observation that training on partial data (only node attributes or only graph topology) improves fairness, it constructs a synthetic teacher by combining fairness experts trained on partial data and uses knowledge distillation to guide the student GNN.

• Fairwos [20]: A counterfactual fairness framework for GNNs that operates in the absence of explicit sensitive attributes. It first generates pseudo-sensitive attributes via an encoder to capture the latent influence of sensitive information, then finds realistic graph counterfactuals from the dataset to serve as fairness constraints.

• FDKD [46]: A fairness method that leverages knowledge distillation and soft label reweighting without requiring demographic information. It trains an overfitted teacher model and uses its normalized logits as soft labels to guide a student model. Theoretically, this acts as an error-based reweighting mechanism to focus on challenging yet correctly classified samples. Although FDKD is not specifically designed for graph data, we adapt it to the graph setting by replacing its backbone with a GNN.

Implementation Details: We run all experiments five times and report the average results. For all methods, we utilize a 1-layer GCN or a 1-layer GIN as the backbone, followed by a linear layer as the classifier. The hidden dimensions for all backbones and the classifier are set to 16. We use the Adam optimizer with a weight decay of \(1\times10^{-5}\) across all methods. All experiments are conducted on an NVIDIA GeForce RTX 3090 GPU, and all models are implemented with PyTorch and PyTorch-Geometric. We perform a grid search to obtain the optimal hyperparameters for all methods. The learning rate is searched from {0.01, 0.001} for all methods. Detailed settings are provided as follows:

• Grad2Fair: We perform a grid search for bias amplification epochs \(E_{amp}\), upweighting epochs \(E_{upweight}\), and debiasing strength \(\lambda\) in a range of 100 to 700 with a step size of 50, {500, 600}, and 1 to 20 with a step size of 1, respectively. The selection ratio \(\tau\) is set to 0.5. To ensure accurate shortcut capture by the bias-amplified model, we train it for 50 or 100 standard epochs during the initial phase of bias amplification.

• FairGKD [21]: We conduct a grid search for the scalar temperature parameter \(\tau\) and the disadvantaged loss enhancement parameter \(\gamma\) in a range of {0.001, 0.01, 0.1, 0.5, 1}. The training epochs are set to 1000.

• Fairwos [20]: We conduct a grid search for \(\alpha\) and \(K\) in a range of {0.01, 0.05, 1, 2, 5} and {1, 2, 5, 10, 20}, respectively. The training epochs for the first and second processes are set to 1000 and 15, respectively.

• FDKD [46]: We perform a grid search for trade-off hyperparameter \(\alpha\) and temperature \(T\) in a range of {0.1, 0.3, 0.5, 0.7, 0.9} and {0.1, 0.3, 0.5, 0.7, 0.9}, respectively. The training epochs of the teacher and the student model are set to 1500 and 1000, respectively.

6.2 Overall Performance↩︎

In this subsection, we first verify the effectiveness of GradDist and then compare Grad2Fair with several baselines over two commonly used GNN backbones.

6.2.1 Effectiveness of GradDist↩︎

To verify GradDist, we conduct bias evaluation experiments on three synthetic datasets, including SynFair, AttrBias, and StruBias. Specifically, for each dataset, we evaluate its bias using GradDist, and then calculate correlations between evaluated results and bias-controlling parameters, e.g., \(|p_{00}-p_{01}|\) for SynFair, \(\mu\) for AttrBias, and \(p_{intra}\) for StruBias. As shown in Table 2, the evaluated results of GradDist present strong correlations with bias-controlling parameters. Specifically, across all three synthetic datasets, the Pearson correlation coefficients (\(r\)) consistently exceed \(0.87\), peaking at \(0.8983\) on the AttrBias dataset. This indicates a highly significant linear relationship, demonstrating that GradDist can proportionally capture the actual magnitude of the bias. Furthermore, the Spearman (\(\rho\)) and Kendall (\(\tau\)) coefficients, which measure rank correlation, also exhibit exceptional performance. Notably, on the AttrBias dataset, the Spearman and Kendall correlations reach \(0.9643\) and \(0.9048\), respectively. Even on the synthetically complex SynFair and StruBias datasets, the rank correlations remain robust (\(\rho = 0.8214\), \(\tau = 0.6190\)). These high monotonic correlation scores suggest that GradDist is not only capable of quantifying the absolute severity of bias but is also highly reliable for ranking models or datasets according to their bias levels. Overall, these empirical results strongly validate the sensitivity and effectiveness of GradDist as a robust metric for bias evaluation without demographics.

6.2.2 Comparison Study↩︎

To evaluate the effectiveness of Grad2Fair, we compare it against three state-of-the-art fairness methods using two standard GNN backbones. Tables 3 and 4 summarize the performance comparisons on the GCN and GIN backbones, respectively. In most cases, Grad2Fair achieves superior utility and fairness trade-offs compared to the baselines. This observation demonstrates the efficacy of Grad2Fair in improving graph fairness without relying on demographic information. Furthermore, the consistent performance across different GNN architectures highlights the model-agnostic nature of Grad2Fair.

It is worth noting that Grad2Fair experiences a significant drop in F1 score on the Bail dataset when using the GIN backbone. This can be attributed to the architectural properties of GIN and the underlying structure of the dataset. Specifically, while GIN is skilled at capturing local topological features compared to GCN, the edges in the Bail dataset are constructed based on node feature similarity via kNN and lack the rich structural complexity found in social networks, e.g., Pokec-z/n. Consequently, a potential explanation is that the bias amplification stage of Grad2Fair struggles to effectively amplify biases on the Bail dataset under the GIN backbone, as high-confidence and low-confidence samples share similar local topologies. We provide a more detailed analysis of the bias amplification stage in Section 6.3.

Furthermore, we observe that while FDKD successfully improves fairness and preserves utility on the GCN backbone, it struggles to achieve comparable effectiveness with GIN on the Bail dataset. As a fairness baseline not explicitly tailored for graph data, FDKD employs label smoothing to improve fairness, which acts as a reweighting strategy that assigns higher importance to correctly classified samples. Since this mechanism is conceptually similar to the bias amplification stage of Grad2Fair, we attribute this underperformance to the same underlying factor that limits Grad2Fair when using the GIN backbone on the Bail dataset.

6.3 Ablation Study↩︎

To evaluate the contributions of the core components in Grad2Fair, we conduct ablation studies on two GNN backbones. Specifically, we remove the bias amplification and upweighting via gradient stages, denoting these variants as “Grad2Fair w/o BA" and”Grad2Fair w/o UG", respectively. Additionally, we replace upweighting for the misclassified node in Eq. 3 with upweighting across all training nodes, denoted as “Grad2Fair w/o MNS".

Figures 7 and 8 present the ablation results on the GCN and GIN backbones, respectively. In most cases, removing the bias amplification (BA) stage improves fairness, validating its intended function of magnifying inherent biases. Notably, for datasets with severe inherent bias, such as Credit, removing the BA stage enhances both fairness and utility. Consequently, the performance of Grad2Fair on the Credit and Pokec-n datasets (Tables 3 and 4) is reported without the BA stage. Furthermore, on the Bail dataset, the removal of the BA stage yields contrasting results between the two backbones. We attribute this discrepancy to the simple topology of the Bail dataset and GIN’s superior ability to capture local structural patterns. As a result, during bias amplification, Grad2Fair equipped with GIN struggles to distinguish the local topological differences between high- and low-confidence samples, thereby rendering the BA stage ineffective.

Regarding the upweighting via gradient (UG) stage, removing it degrades the model’s fairness to a level comparable with the vanilla baseline. This demonstrates that the UG stage effectively mitigates model bias and enhances fairness. By jointly analyzing the results of “Grad2Fair w/o BA" and”Grad2Fair w/o UG", we find that the BA stage is less effective on artificially constructed graphs (e.g., Bail and Credit), largely due to their lack of complex local topological structures. Finally, the results of “Grad2Fair w/o MNS" demonstrate that applying gradient upweighting uniformly to all nodes fails to yield consistent fairness improvements and can even exacerbate bias. This finding validates the effectiveness and rationale of restricting gradient upweighting exclusively to misclassified samples, as formulated in Eq. 3 .

6.4 Hyperparameter Analysis↩︎

To analyze the impact of key hyperparameters, we investigate the performance sensitivity of Grad2Fair on the selection ratio \(\tau\) and debiasing strength \(\lambda\).

6.4.1 Sensitivity w.r.t. \(\tau\)↩︎

We vary \(\tau\) across the set \(\{0.01, 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 1.0\}\) while keeping all other parameters identical to those in Section 6.2.2. As shown in Figure 9, we observe that the utility performance of Grad2Fair improves as \(\tau\) increases, while the fairness performance remains stable. Since the BA stage only selects a subset to optimize the model, as \(\tau\) increases, the training of the BA stage increasingly approximates standard model training, thereby enhancing utility. Meanwhile, the stable fairness performance across a broad range of variations in \(\tau\) demonstrates the effectiveness of the UG stage on debiasing.

6.4.2 Sensitivity w.r.t. \(\lambda\)↩︎

We vary \(\lambda\) across the set \(\{0.1, 0.5, 1, 2, 5, 10, 15, 20\}\) while keeping all other parameters identical to those in Section 6.2.2. As shown in Figure 10, fairness improves at the expense of utility as \(\lambda\) increases. Despite this inherent trade-off, the overall performance of Grad2Fair remains robust to variations in \(\lambda\). Functionally, \(\lambda\) controls the extent to which the model learns from misclassified samples. While increasing \(\lambda\) forces the model to prioritize these challenging samples and enhances fairness, it inevitably compromises utility performance. Therefore, selecting an optimal \(\lambda\) requires carefully balancing the fairness-utility trade-off.

6.5 Further Probe↩︎

To obtain an in-depth understanding of Grad2Fair, we investigate the training efficiency, gradient visualization, and embedding visualization.

6.5.1 Training Efficiency↩︎

We compare the training time of Grad2Fair with that of several baselines. We maintain hyperparameter settings consistent with those in Section 6.2.2. As shown in Figure 11, we report the total training time averaged over five random seeds. The training time of Grad2Fair is markedly lower than that of the two fairness baselines (i.e., FairGKD and Fairwos), which demonstrates the high efficiency of Grad2Fair. Compared to these two baselines, Grad2Fair mitigates model bias through upweighting, which incurs no additional computational overhead and strictly matches the per-epoch cost of training vanilla models. Additionally, Grad2Fair exhibits higher efficiency than the vanilla models in most cases, which can be attributed to fewer required training epochs of Grad2Fair.

To ensure a fair comparison independent of the total number of epochs required for convergence, we further analyze the per-epoch training time. As shown in Tables 5 and 6, Grad2Fair achieves a lower per-epoch training time than both FairGKD and Fairwos. This indicates that the reduced total training time of Grad2Fair(shown in Figure 11) stems not only from requiring fewer epochs to converge but also from a lower computational cost per epoch. Furthermore, Grad2Fair maintains a per-epoch training time comparable to the vanilla baseline, demonstrating that our approach introduces negligible additional computational overhead. Overall, these empirical results confirm that Grad2Fair is a highly efficient fairness method.

6.5.2 Gradient Visualization↩︎

To further investigate the impact of the BA stage, we visualize the gradient distribution before and after the BA stage over two GNN backbones. Specifically, we present gradients of training nodes misclassified by the model after bias amplification. As shown in Figures 12 and 13, while bias amplification induces marginal changes in the overall gradient distributions across different groups, an analysis of the average gradients reveals a widening gap between these groups after bias amplification. This can be observed by the distance between the two dashed lines in Figures 12 and 13. The discrepancy in average gradients on the GCN backbone increases from \(2.42 \times 10^{-5}\) to \(2.85 \times 10^{-5}\). More notably, on the GIN backbone, this difference increases from \(6 \times 10^{-7}\) to \(7.9 \times 10^{-6}\), representing a full order-of-magnitude increase. Overall, this increasing distance transforms meaningless gradients into demographic information for debiasing.

6.5.3 Embedding Visualization↩︎

As shown in Figure 14, we visualize the node embeddings generated by Grad2Fair using t-SNE, with nodes color-coded according to their binary labels. To illustrate the spatial distribution of weights, normal nodes (those not in \(\mathcal{M}\)) are rendered as semi-transparent points, while high-weight nodes (those in \(\mathcal{M}\)) are emphasized as opaque markers with black contours, their sizes scaled proportionally to their weight magnitude. Although all nodes are naturally partitioned into two distinct clusters, the spatial distributions of normal and high-weight nodes are strikingly inverted relative to their labels. Specifically, while normal nodes seamlessly align with their true classes, the high-weight nodes of one class structurally overlap with the normal nodes of the opposing class. For instance, the normal nodes of class 0 and the high-weight nodes of class 1 are densely superimposed. Crucially, these high-weight nodes are conspicuously absent from the homophilous cores of their own ground-truth clusters. Instead, they are either densely concentrated along the inter-class decision boundary or scattered as isolated, topologically heterophilous instances deep within the opposing cluster. This observation demonstrates that Grad2Fair is capable of accurately locating the decision boundary, thereby precisely identifying the most vulnerable victim nodes without relying on demographic labels \(S\).

7 Conclusion↩︎

In this paper, we investigate the problem of graph fairness in the absence of demographic information. We first observe that the gradients of misclassified nodes encode latent demographic signals. Motivated by this observation, we introduce GradDist, a novel bias evaluation metric designed for demographics-free scenarios. GradDist quantifies bias by measuring the distance between local modes within the gradient distribution. Consequently, we propose Grad2Fair, a simple yet effective framework for demographics-free graph fairness. Grad2Fair adopts an amplify-then-debias paradigm, comprising two key stages: a bias amplification and an upweighting via gradient stage. The core intuition behind Grad2Fair is to exploit the underlying demographic information embedded within the gradients to mitigate bias. To validate the soundness of our approach, we provide a rigorous theoretical analysis of both stages. Extensive experiments on several datasets further demonstrate the empirical efficacy of GradDist and Grad2Fair.

Despite the strong empirical and theoretical results, our approach has certain limitations. First, GradDist is currently restricted to evaluating bias with respect to binary sensitive attributes, whereas many real-world applications involve multi-valued sensitive attributes, such as race or geographic region. Second, on datasets characterized by simplistic topological structures, the BA stage of Grad2Fair may exhibit reduced efficacy. Under such conditions, extracting demographic signals becomes challenging, which ultimately compromises the overall fairness improvements.

References↩︎

---

1. Manuscript received April 19, 2021; revised August 16, 2021.↩︎

2. The research is supported by the National Key R&D Program of China under grant No. 2022YFF0902500, the Guangdong Basic and Applied Basic Research Foundation, China (No. 2023A1515011050), Shenzhen Science and Technology Program (KJZD20231023094501003), GMCC-SYSU Joint Lab for Smart Applications, and Tencent AI Lab (RBFR2024004). (Corresponding author: Liang Chen.)↩︎

3. Liang Chen is with the School of Computer Science and Engineering, Sun Yat-Sen University, Guangzhou 510007, China. Email: chenliang6@mail.sysu.edu.cn↩︎

4. Zibin Zheng is with the School of Software Engineering, Sun Yat-sen University, Zhuhai 519082, China.↩︎

5. Jintang Li is with the Institute of Artificial Intelligence, Xiamen University, Xiamen 361005, China.↩︎

6. Yuchang Zhu, Zezhong Xie, Huizhe Zhang, and Huazhen Zhong are with the School of Computer Science and Engineering, Sun Yat-sen University, Guangzhou 510007, China.↩︎