JOURNAL OF LATEX CLASS FILES, VOL. 14, NO. 8, AUGUST 2021
1
Grad2Fair: A Gradient-driven Approach for Graph Fairness without Demographics
arXiv:2607.14705v1 [cs.LG] 16 Jul 2026
Yuchang Zhu, Zezhong Xie, Huizhe Zhang, Huazhen Zhong, Jintang Li, Liang Chen, and Zibin Zheng, Fellow, IEEE,
Abstract—Graph neural networks (GNNs) frequently encounter group fairness issues, often yielding biased predictions against specific demographic groups defined by sensitive attributes such as gender or race. While this challenge has motivated extensive research, most existing solutions rely on the strong assumption that demographics are fully available. To bypass this strict requirement, a few recent studies have attempted to use predicted demographics as proxies to enforce fairness constraints. However, predicted demographics may be inaccurate, resulting in the failure to improve fairness. In this work, we investigate the problem of graph fairness without demographic information and avoid the utilization of predicted demographics. Motivated by our observation that the gradient distributions of misclassified nodes implicitly encode demographic information, we first propose GradDist, a gradientbased metric that quantifies bias by measuring the distance between local modes within these distributions. To mitigate this bias, we propose Gradient-to-Fairness (Grad2Fair), a gradientguided approach for group fairness without demographics. Due to the potential demographics in gradients, Grad2Fair directly leverages gradients to debias and eliminates demographic prediction, thereby enabling stable fairness performance. Experiments on several real-world datasets demonstrate the effectiveness of Grad2Fair, as evidenced by superior performance over baselines in most cases. Our code is available at https://github.com/ZzoomD/Grad2Fair. Index Terms—Graph Neural Networks, Group Fairness, Demographics, Upweight, Gradient.
I. Introduction RAPH-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) [13]–[15] have emerged as a powerful approach for
G
Manuscript received April 19, 2021; revised August 16, 2021. 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.) Liang Chen is with the School of Computer Science and Engineering, Sun Yat-Sen University, Guangzhou 510007, China. Email: [email protected] Zibin Zheng is with the School of Software Engineering, Sun Yatsen University, Zhuhai 519082, China. Jintang Li is with the Institute of Artificial Intelligence, Xiamen University, Xiamen 361005, China. 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.
modeling such data, recent studies [5], [6], [16] 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 [6], [17], [18], 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 [4], disentanglement [19], re-balancing [20], neutralization [21], and alignment [22]. In summary, the core idea behind these methods is to eliminate sensitive attribute information from model outcomes through welldesigned 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) [23] 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 [9], [10] 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 [8], follows a predict-thenconstrain 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 [7] and our proposed method, seeks to mitigate bias without explicit demographic inference. While FairGKD [7] explores the relationship between biases and
0000–0000/00$00.00 © 2021 IEEE
w/ Demo. w/o8, Demo. JOURNAL OF LATEX CLASS FILES, VOL. 14, NO. AUGUST 2021
Fairness-aware Training 𝒢!
GNNs
Representative methods
GNNs w/o Predicted Demo.
𝑆
EDITS [4]
Fairness-aware Training
NIFTY [5] …
GNNs
w/ Predicted Demo.
Fairness-aware Training 𝑆$
( 𝒢! = (𝒱, ℰ, 𝑋)
Grad2Fair (ours)
GNNs Representative methods
Fairness-aware Training
FairGNN [6] …
Predict 𝑆$ 𝒢!
Representative methods
FairGKD [7]
𝒢!
Representative methods Fairwos [8]
𝑆$
fairGNN-WOD [9]
Predict 𝑆$
Themis [10]
𝒢!
𝑆
𝑆 = fully available demo.
𝑆 = partially available demo.
𝑆$ = predicted demo.
Fig. 1. A taxonomy of representative graph fairness methods, categorized by demographic availability and the utilization of inferred demographics. “Demo.” is an abbreviation for demographics. “w/” and “w/o” denote “with” and “without”, respectively. The pink region indicates areas outside the scope of this paper.
S=0
S=1
Avg_S=0
Avg_S=1
Correctly Classified
Incorrectly Classified
0 1 2 Gradient (×10 3 )
0
Density (×103 )
1 0.5 0
2
1 2 Gradient (×10 3 )
Fig. 2. Kernel Density Estimation (KDE) of gradient distributions for correctly and incorrectly classified samples. While gradients for correctly classified instances overlap, those within the misclassified subset exhibit pronounced distributional divergence across different demographic groups.
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 [24] 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 IV. 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 highperformance 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 intermodal 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 II provides a brief overview of related literature. Section III introduces the necessary notations and formalizes the problem definition. Section IV presents an empirical investigation and introduces a bias evaluation metric for fairness without demographics. Section V introduces details of our proposed approach Grad2Fair, followed by the complexity analysis. Section VI presents experimental results to verify the effectiveness of Grad2Fair. Finally, Section VII summarizes this paper and highlights its limitations. II. Related Work In this section, we provide a brief overview of related literature, including group fairness in graph learning and fairness without demographic information. A. 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 [25], the emergence of GNNs [14],
JOURNAL OF LATEX CLASS FILES, VOL. 14, NO. 8, AUGUST 2021
3
[52] 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 [16] utilizes a biased edge dropout algorithm to reduce homophily with respect to the sensitive attribute. EDITS [4] minimizes the Wasserstein distance between groups to debias node attributes and topology. Similarly, Graphair [18] employs adversarial learning to guide data debiasing, and FairAGG [26] reweights edges based on their fairness contributions via Shapley values. In contrast, in-processing methods integrate fairness constraints directly into the training process. FairGNN [6] and FairVGNN [17] leverage adversarial learning to learn representations that are independent of sensitive attributes. NIFTY [5] incorporates counterfactual contrastive learning to ensure model invariance, while FairGB [20] employs counterfactual node mixup and contribution alignment loss to rebalance groups during training. FairINV [27] reframes group fairness as invariant learning and employs an invariant objective. To address the potential utility degradation caused by fairness-aware training, FairSAD [19], FUGNN [28], and FairSIN [21] investigate the trade-off between utility and fairness. Beyond these core areas, research has also expanded into fairness under distribution shifts [29], fair graph transformers [30], [31], fair federated graph learning [51], and fairness considering false positives [32]. Despite significant progress, most existing preprocessing 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.
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 [8], fairGNN-WOD [9], and Themis [10], 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 [7] leverages a knowledge distillation framework, guiding a student model via a fair teacher trained on partial data. Nevertheless, FairGKD [7] 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.
B. Fairness without Demographics Driven by strict privacy regulations, fairness without demographics [53] 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 [38], minimize the correlation between non-sensitive features and final predictions to achieve fairness. Meanwhile, another line of studies focuses on Rawlsian Max-Min fairness [36] without demographics, which maximizes the performance of the worst-off groups. For example, distributionally robust optimization (DRO) [33] employs a robust optimization framework to enhance performance for high-loss subpopulations. To address the susceptibility of DRO to noise, adversarial reweighted learning (ARL) [34] identifies and improves computationally identifiable groups via adversarial training. Additionally, recent advancements [35] have further integrated paradigms like invariant representation
III. Preliminaries A. 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 ∈ {0, 1}n as the node label vector. Let G = (V, E, X) denote an undirected attributed graph, where V is a set of |V| = n nodes and E is a set of |E| = m edges. X ∈ Rn×d represents the node feature matrix with d dimensions. The adjacency matrix A ∈ {0, 1}n×n describes the graph topology, where Auv = 1 if an edge euv ∈ E connects node u and v, and Auv = 0 otherwise. S ∈ {0, 1}n represents the binary sensitive attribute, where Su = Sv indicates that nodes u and v belong to the same demographic group. X̃ ∈ Rn×(d−1) is the node feature matrix without S. B. 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 G = (V, E, X), a GNN classifier f (·) takes G as input and predicts node labels Ŷ ∈ {0, 1}n . The group fairness can be evaluated using demographic parity (DP) [44] and equal opportunity (EO) [45]. Specifically, demographic parity requires predictions to be independent of the sensitive attribute S, and equal opportunity ensures the same true
JOURNAL OF LATEX CLASS FILES, VOL. 14, NO. 8, AUGUST 2021
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: ∆DP = |P (Ŷv = 1 | Sv = 0) − P (Ŷv = 1 | Sv = 1)|, ∆EO = |P (Ŷv = 1 | Yv = 1, Sv = 0) − P (Ŷv = 1 | Yv = 1, Sv = 1)|,
(1)
4
TABLE I Correlations between misclassified node gradients and bias levels.
∆|p00 −p01 | − ∆grad ∆DP − ∆grad
Pearson (r)
Spearman (ρ)
Kendall (τ )
0.9014 0.9301
0.8571 0.9286
0.7143 0.8095
where small ∆DP and ∆EO indicate fairer GNN models. C. 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 G̃ = (V, E, X̃) without the sensitive attribute S, along with the node label ground truth Y , our goal is to learn a fair GNN classifier f (·) on G̃. Thus, the optimization problem for group fairness without demographics can be defined as follows: Ŷ = fθ (G̃), θ∗ = arg min Lcls Ŷ , Y θ
s.t. Cfair Ŷ ; G̃ ≤ ϵ,
(2)
where θ is the trainable parameter of the model f (·) and θ∗ is the optimal parameter. Lcls (·, ·) represents the loss function for the node classification task, and Cfair (·; ·) represents a fairness constraint function. ϵ represents a fairness tolerance threshold, indicating the maximum tolerable fairness disparity. IV. 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. A. Empirical Investigation A recent study [24] 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 [46] to generate synthetic datasets with different bias levels. Specifically, these synthetic datasets have binary sensitive attributes and node labels. We set the probability p00 of S = 0, Y = 0 to vary from 0.25 to 0.07 with an interval of 0.03, where p11 = p00 , p01 = p10 , p11 + p00 + p01 + p10 = 1. Meanwhile, we fix other parameters to align the settings of Syn-1 in [46]. For clarity, the seven generated synthetic datasets are referred to as “SynFair0” to “SynFair6”. According to Syn2 in [46], the larger unbalanced group ratio, i.e., larger |p00 − p01 |, 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 2layer graph convolution network (GCN) classifier and then calculate differences ∆grad of average gradient between two demographic groups within misclassified nodes on the training set. As shown in Table I, we report three types of correlation results: the correlation between the unbalanced group ratio ∆|p00 −p01 | and ∆grad , and the correlation between the fairness performance ∆DP and ∆grad . According to the definition in [47]–[49], the experimental results demonstrate that ∆grad exhibits strong positive correlations with ∆|p00 −p01 | and ∆DP , respectively. ∆|p00 −p01 | and ∆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. Fur-
JOURNAL OF LATEX CLASS FILES, VOL. 14, NO. 8, AUGUST 2021
1.00
6 4 2 0
1
0 1 2 Gradient (×10 4 )
3
Avg_S=0
0.75 0.50 0.25 0.00
1
0 1 2 Gradient (×10 4 )
3
Avg_S=1
SynFair-4
8 Density (×103 )
Density (×104 )
Density (×103 )
8
S=1
SynFair-2
6 4 2 0
1
0 1 2 Gradient (×10 4 )
SynFair-6
1.00 Density (×104 )
S=0
SynFair-0
5
3
0.75 0.50 0.25 0.00
1
0 1 2 Gradient (×10 4 )
3
Fig. 3. Gradient visualization of misclassified nodes on synthetic datasets with different bias levels. The gradient average between demographic groups exhibits a larger margin on a more biased dataset, e.g., SynFair-6.
S=0
S=1
Avg_S=0
1.5 1.0 0.5 0.0
Pokec-z Density (×103 )
Density (×103 )
German
0 2 Gradient (×10 3 )
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 fˆ(g) is defined as:
Avg_S=1
4 3 2 1 0
0.0
0.5 Gradient (×10 3 )
1.0
Fig. 4. Gradient visualization of misclassified nodes on real-world datasets. The difference in average gradients between demographic groups varies significantly across datasets.
thermore, the gradient distribution of misclassified nodes within the training set includes potential demographic information, paving the way to achieve fairness without demographic information. B. Bias Evaluation Metric Inspired by our observation on the correlation between ∆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 ∆grad between two demographic groups. However, calculating ∆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 Qg = {g1 , g2 , . . . , gM } extracted from a specific layer or
M g − gi 1 X ˆ K , f (g) = M h i=1 h
(3)
where M represents the number of nodes in the observed discrete gradient set. K(·) denotes the standard 1 2 Gaussian kernel K(u) = √12π e− 2 u 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 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 calculusbased criteria: d ˆ =0 f (g) dg g=g ∗
and
d2 ˆ < 0. f (g) dg 2 g=g ∗
(4)
The first-order condition (stationarity) ensures that the PM pointg−gisi a critical point, where the summation i=1 K( h ) · (g − gi ) 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 P = {gj∗ }. To capture the most significant bias-induced divergence between opposing
JOURNAL OF LATEX CLASS FILES, VOL. 14, NO. 8, AUGUST 2021
6
subgroups, we extract the two most dominant peaks based on their density magnitudes: TopPeaks = {g1∗ , g2∗ } ∈ arg top-2g∗ ∈P fˆ(g ∗ ) , (5)
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 [50], 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 highconfidence samples to optimize the trained model during the initial training phase, thereby reinforcing the model’s reliance on these shortcuts. Let fθamp denote a GNN classifier with trainable parameters θamp . Given an undirected attributed graph G̃ = (V, E, X̃), for each node u ∈ Vtr , the prediction confidence is defined as cu = max(fθamp (G̃)u ). After a specific number of warm-up epochs, we select a subset of samples Vsub consisting of those with the highest confidence scores:
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: GradDist =
|g1∗ − g2∗ | , max(Qg ) − min(Qg )
(6)
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. V. 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. A. Bias Amplification As revealed by our empirical investigation in Section IV-A, the gradient distribution disparity (∆grad ) of misclassified nodes exhibits a strong positive correlation with both the dataset’s inherent bias levels and the resulting fairness metrics, e.g., ∆DP . However, as illustrated in Fig. 4, certain real-world graph datasets, e.g., Pokecz, 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.
Vsub = {u ∈ Vtr | cu > percentile(c, 1 − τ )},
(7)
where τ is a hyperparameter representing the selection ratio, e.g., 0.25. The optimization objective for this stage is defined as: X Lamp = ℓ(fθamp (G̃)u , Yu ), (8) u∈Vsub
where ℓ(·) denotes the cross-entropy loss. By iteratively optimizing Lamp , 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 Lamp on the high-confidence subset Vsub 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 VA and the bias-conflicting (minority) group VC . 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 ∈ VA | cu > τ ) ≫ P (u ∈ VC | cu > τ ).
(9)
This implies that the selected subset Vsub is overwhelmingly dominated by VA , such that |Vsub ∩ VA | ≈ |Vsub | and |Vsub ∩VC | ≈ 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,
JOURNAL OF LATEX CLASS FILES, VOL. 14, NO. 8, AUGUST 2021
7
Bias Amplification
Upweighting via Gradient Save Best ∗ 𝜃,-.
GNN (𝜃!"# )
Standard Epochs
1 Input graph 𝒢,
Loss on subset ' ℓ(𝑓))*+ 𝒢, %∈𝒱&'(
%
𝑤%
𝒱$%&
… Confidence
Input graph 𝒢,
1+λ $ 𝑘% %
Gradient
GNN ∗ (𝜃,-. )
Weighted Loss GNN
, 𝑌% )
𝒱!"# : High-confidence Subset
' 𝑤% ℓ(𝑓) 𝒢, % , 𝑌% )
%∈𝒱$%
: Incorrectly Classified
: Correctly Classified
Fig. 5. Framework overview of Grad2Fair.
denoted as ∆loss (θ) = Ev∈VC [ℓv (θ)] − Eu∈VA [ℓu (θ)]. The amplification of bias is equivalent to the strict increase of ∆loss (θ) during the optimization of Lamp . Theorem 1 (Bias Amplification via Skewed Gradient Flow). Given a sufficiently small learning rate η > 0 and the optimization step θt+1 = θt −η∇θ Lamp (θt ), optimizing the model on the high-confidence subset Vsub strictly increases the bias severity, i.e., ∆loss (θt+1 ) > ∆loss (θt ). Proof Sketch. Following Assumption 1, the gradient of the average amplification loss Lamp is dominated by the bias-aligned samples: ∇θ Lamp (θt ) ≈
1 |Vsub |
X
∇θ ℓu (θt ).
(10)
u∈Vsub ∩VA
Assuming the loss function ℓ is L-smooth, applying the Taylor expansion to the loss of an arbitrary node x at step t + 1 gives: ℓx (θt+1 ) = ℓx (θt ) − η⟨∇θ ℓx (θt ), ∇θ Lamp (θt )⟩ + Rx , (11) where the remainder Rx is uniformly bounded by |Rx | ≤ L 2 2 2 η ∥∇θ Lamp (θt )∥ . Because the optimization direction is dominated by VA , we assume there exist constants α > 0 and β ≥ 0 with α > β such that the expected gradient correlations satisfy: Eu∈VA [⟨∇θ ℓu (θt ), ∇θ Lamp (θt )⟩] ≥ α∥∇θ Lamp (θt )∥2 , (12) 2 Ev∈VC [⟨∇θ ℓv (θt ), ∇θ Lamp (θt )⟩] ≤ β∥∇θ Lamp (θt )∥ . (13) Taking the expectation of the loss difference for both demographic groups, we obtain: Eu∈VA [ℓu (θt+1 ) − ℓu (θt )] ≤ − ηα∥∇θ Lamp (θt )∥2 (14) L + η 2 ∥∇θ Lamp (θt )∥2 , 2 Ev∈VC [ℓv (θt+1 ) − ℓv (θt )] ≥ − ηβ∥∇θ Lamp (θt )∥2 (15) L − η 2 ∥∇θ Lamp (θt )∥2 . 2
Subtracting the expected change of the bias-aligned group from that of the bias-conflicting group yields the change in bias severity: ∆loss (θt+1 ) − ∆loss (θt ) ≥η(α − β)∥∇θ Lamp (θt )∥2 − Lη 2 ∥∇θ Lamp (θt )∥2 .
(16)
For a sufficiently small learning rate satisfying η < α−β L , the first-order inner product terms strictly dominate the remainder bounds. Consequently, we obtain: ∆loss (θt+1 ) − ∆loss (θt ) > 0
(17)
which directly implies ∆loss (θt+1 ) > ∆loss (θt ). In summary, the theoretical analysis above proves the effectiveness of our bias amplification strategy, which provides a foundation for the subsequent debiasing. ■ B. Upweighting via Gradient The bias amplification strategy described in Section V-A successfully bridges the gap between latent demographic groups and observable gradient signals. Specifically, under the bias-amplified model fθ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 G̃ = (V, E, X̃), the bias-amplified model fθamp quantifies the fitting difficulty and feature sensitivity of each node. To derive a nodespecific importance score, we compute the gradient of the loss function with respect to the input features X̃ for each node u ∈ Vtr : gu = ∇X̃u ℓ(fθamp (G̃)u , Yu ),
ku = ∥gu ∥2 .
(18)
We adopt the gradient norm relative to input features rather than model parameters because the former directly
JOURNAL OF LATEX CLASS FILES, VOL. 14, NO. 8, AUGUST 2021
8
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 ku values. To balance the contributions across groups while maintaining the model’s overall utility, we focus on the set of misclassified nodes M = {u ∈ Vtr | argmax(fθamp (G̃)u ) ̸= Yu }, as these nodes are most likely to be victims of model bias. We apply min-max normalization to the gradient norms within M to ensure stability across different datasets: ku − minv∈M (kv ) k̃u = , (19) maxv∈M (kv ) − minv∈M (kv ) + ϵ
Eu∈VA [⟨∇θ ℓu (θ), ∇θ Lupweight (θ)⟩] ≤ γA ∥∇θ Lupweight (θ)∥2 . (24)
where ϵ is a small constant for numerical stability. We then assign an importance weight wu to each node u: ( 1 + λ · k̃u , if u ∈ M, wu = (20) 1, otherwise, where λ > 0 is a hyperparameter controlling the strength of the debiasing. Finally, the model is trained by minimizing the weighted objective function: X Lupweight = wu · ℓ(fθ (G̃)u , Yu ). (21) u∈Vtr
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 V-A to formally demonstrate how minimizing Lupweight mitigates the bias amplified in the previous stage. Recall that VA and VC denote the bias-aligned (majority) and bias-conflicting (minority) groups, respectively, and bias severity is defined as ∆loss (θ) = Ev∈VC [ℓv (θ)] − Eu∈VA [ℓu (θ)]. Assumption 2 (Weight Disparity via Amplified Gradients). Due to the bias amplification stage (Theorem 1), nodes in VC are predominantly misclassified and exhibit sharper gradient transitions, i.e., larger ku . Consequently, the assigned importance weights for the minority group are strictly larger in expectation than those for the majority group: Ev∈VC [wv ] ≫ Eu∈VA [wu ]. (22) 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 γC > γA > 0 such that the expected inner products between individual sample gradients and the overall upweighted gradient ∇θ Lupweight (θ) satisfy: Ev∈VC [⟨∇θ ℓv (θ), ∇θ Lupweight (θ)⟩] ≥ γC ∥∇θ Lupweight (θ)∥2 , (23)
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 η > 0, and the optimization step θt+1 = θt − η∇θ Lupweight (θt ), optimizing the weighted objective strictly decreases the bias severity, i.e., ∆loss (θt+1 ) < ∆loss (θt ). Proof Sketch. The gradient of the upweighting objective is a weighted sum of individual gradients. Under Assumption 3, the optimization direction ∇θ Lupweight (θt ) is highly correlated with the descent direction of VC (γC > γA ). Assuming the loss function ℓ is L-smooth, applying the Taylor expansion to an arbitrary node x yields ℓx (θt+1 ) = ℓx (θt ) − η⟨∇θ ℓx (θt ), ∇θ Lupweight (θt )⟩ + Rx , with the remainder uniformly bounded by |Rx | ≤ L 2 2 2 η ∥∇θ Lupweight (θt )∥ . 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: Ev∈VC [ℓv (θt+1 ) − ℓv (θt )] ≤ − ηγC ∥∇θ Lupweight (θt )∥2 L + η 2 ∥∇θ Lupweight (θt )∥2 , 2 (25) Eu∈VA [ℓu (θt+1 ) − ℓu (θt )] ≥ − ηγA ∥∇θ Lupweight (θt )∥2 L − η 2 ∥∇θ Lupweight (θt )∥2 . 2 (26) Subtracting the expected change of the majority group from that of the minority group bounds the change in bias severity: ∆loss (θt+1 ) − ∆loss (θt ) ≤ − η(γC − γA )∥∇θ Lupweight (θt )∥2 + Lη 2 ∥∇θ Lupweight (θt )∥2 . (27) For a sufficiently small learning rate satisfying η <
γC −γA , the first-order negative term dominates, yielding: L
∆loss (θt+1 ) − ∆loss (θt ) < 0.
(28)
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. ■ C. 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.
JOURNAL OF LATEX CLASS FILES, VOL. 14, NO. 8, AUGUST 2021
Algorithm 1 Training Algorithm of Grad2Fair 1: Input: Undirected attributed graph G̃ = (V, E, X̃), la-
bels Y , hyperparameters τ (selection ratio), λ (debiasing strength), ϵ (stability constant), bias amplification epochs Eamp , upweighting epochs Eupweight . 2: Output: Fairness-enhanced model parameters θ ∗ . 3: 4: // Stage 1: Bias Amplification 5: Initialize
parameters θamp for the bias-amplified model. 6: for epoch = 1 to Eamp do 7: Compute prediction confidence cu = max(fθamp (G̃)u ) for all u ∈ Vtr . 8: Identify high-confidence subset: Vsub = {u ∈ Vtr | cu > percentile(c, 1 − τ )}. 9: Update θamp by minimizing Lamp = P ℓ(f ( G̃) , Y ). θ u u amp u∈Vsub 10: end for ∗ 11: Save the best amplified model parameters θamp . 12: 13: // Stage 2: Upweighting via Gradient ∗ 14: Load θamp and identify the misclassified set M = {u ∈ ∗ Vtr | argmax(fθamp (G̃)u ) ̸= Yu }.
9
complexity of O(nd), which is negligible. Overall, the total time complexity is O((Eamp +Eupweight +1)·L(md+nd2 )). 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 O(m + nd) and model parameters O(Ld2 ). During the upweighting via gradient stage, calculating input gradients requires temporary memory, but we only persistently cache the derived scalar importance weights wu , reducing the extra overhead to just O(n). Consequently, the overall space complexity remains O(m + nd + Ld2 ). Grad2Fair introduces only a marginal constant-factor memory increase, preserving the space complexity of the base architecture. VI. 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 [7], Fairwos [8], and FDKD [37], across two representative GNN backbones.
∗ 15: Compute input gradients gu = ∇X̃ ℓ(fθamp (G̃)u , Yu ) u
for u ∈ M. 16: Calculate gradient norms ku = ∥gu ∥2 and apply minmax normalization to obtain k̃u using ϵ. 17: Generate importance weights W = {wu }u∈Vtr where wu = 1 + λ · k̃u if u ∈ M, and wu = 1 otherwise. 18: Initialize parameters θ for the final fairness-enhanced model. 19: for epoch = 1 to Eupweight do 20: Update θ by P minimizing the weighted objective Lupweight = u∈Vtr wu · ℓ(fθ (G̃)u , Yu ). 21: end for 22: return Optimized parameters θ ∗ = θ.
1) Algorithm: Algorithm 1 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. 2) Complexity Analysis: Let n = |V|, m = |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 O(L(md + nd2 )) per epoch. Meanwhile, the bias amplification stage requires Eamp epochs, where the per-epoch sorting cost 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 M, followed by Eupweight training epochs. The weight assignment has a
A. Experimental Setup Datasets: We conduct experiments on four widely used real-world datasets and three synthetic datasets. Realworld datasets include Bail [40], Credit [41], Pokecz [43], and Pokec-n [43], 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 [46], while AttrBias and StruBias are constructed based on the protocols in [4]. 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
JOURNAL OF LATEX CLASS FILES, VOL. 14, NO. 8, AUGUST 2021
10
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.
vary the intra-community edge probability pintra 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 pinter 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 F1score and ACC as evaluation metrics, where higher values indicate better utility performance. For fairness evaluation, we use two classic fairness metrics, i.e., ∆DP [44] and ∆EO [45], which can be computed as Eq. (1). Smaller ∆DP and ∆EO values indicate better group fairness. Baselines: We compare Grad2Fair with three stateof-the-art baseline methods for fair node classification, namely, FairGKD [7], Fairwos [8], and FDKD [37].
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 [46]. For each subset, we set the number of nodes to 5,000. To generate subsets with different unfairness, we vary the probability p00 (where S = 0 and Y = 0) from 0.25 to 0.07 with an interval of 0.03, where p11 = p00 , p01 = p10 , p11 + p00 + p01 + p10 = 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 [4]. 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: N (−µ, 12 ) for S = 0 and N (µ, 12 ) for S = 1. To generate datasets with different bias levels, we vary µ in the range of {1, 2, 3, 4, 5, 6, 7}. The remaining eight dimensions are drawn from an unbiased uniform distribution U (0, 1). The network structure is generated using an ErdősRé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 10dimensional 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 pintra to generate StruBias. We
FairGKD [7]: 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 [8]: 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 [37]: 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 × 10−5 across all methods. All experiments are conducted on an NVIDIA GeForce RTX 3090 GPU, and all models are implemented with PyTorch and PyTorchGeometric. 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 Eamp , upweighting epochs Eupweight , and debiasing strength λ in a range of 100 to 700 with
JOURNAL OF LATEX CLASS FILES, VOL. 14, NO. 8, AUGUST 2021
TABLE II Correlations between results of GradDist and bias-controlling parameters.
SynFair AttrBias StruBias
Pearson (r)
Spearman (ρ)
Kendall (τ )
0.8722 0.8983 0.8917
0.8214 0.9643 0.8214
0.6190 0.9048 0.6190
a step size of 50, {500, 600}, and 1 to 20 with a step size of 1, respectively. The selection ratio τ is set to 0.5. To ensure accurate shortcut capture by the biasamplified model, we train it for 50 or 100 standard epochs during the initial phase of bias amplification. • FairGKD [7]: We conduct a grid search for the scalar temperature parameter τ and the disadvantaged loss enhancement parameter γ in a range of {0.001, 0.01, 0.1, 0.5, 1}. The training epochs are set to 1000. • Fairwos [8]: We conduct a grid search for α 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 [37]: We perform a grid search for trade-off hyperparameter α 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. B. 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. 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., |p00 − p01 | for SynFair, µ for AttrBias, and pintra for StruBias. As shown in Table II, 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 (ρ) and Kendall (τ ) 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 (ρ = 0.8214, τ = 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
11
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. 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 III and IV 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 highconfidence and low-confidence samples share similar local topologies. We provide a more detailed analysis of the bias amplification stage in Section VI-C. 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. C. 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. (20) with upweighting across all training nodes, denoted as “Grad2Fair w/o MNS”. Figures 6 and 7 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.
JOURNAL OF LATEX CLASS FILES, VOL. 14, NO. 8, AUGUST 2021
12
TABLE III Comparison of Grad2Fair using the GCN backbone with baseline methods on four datasets. In each row, the best result is marked in bold, while the runner-up result is marked with an underline. Datasets
Metrics
Vanilla GCN
FairGKD
Fairwos
FDKD
Grad2Fair
Bail
F1 (↑) ACC (↑) ∆DP (↓) ∆EO (↓)
78.27 ± 0.89 84.09 ± 0.73 5.39 ± 0.28 3.21 ± 0.70
81.96 ± 1.05 87.33 ± 0.78 5.47 ± 0.27 3.72 ± 0.41
77.59 ± 0.78 83.35 ± 0.71 5.98 ± 1.52 3.48 ± 1.72
79.50 ± 0.29 85.17 ± 0.24 5.45 ± 0.24 3.57 ± 0.50
78.89 ± 0.67 83.97 ± 1.17 4.35 ± 0.55 2.18 ± 1.08
Credit
F1 (↑) ACC (↑) ∆DP (↓) ∆EO (↓)
82.13 ± 0.63 73.81 ± 0.65 11.93 ± 0.40 9.36 ± 0.24
81.95 ± 0.11 73.71 ± 0.13 11.75 ± 0.11 9.49 ± 0.09
82.87 ± 0.83 74.54 ± 0.70 10.47 ± 3.85 8.30 ± 3.34
81.90 ± 0.04 73.63 ± 0.05 11.56 ± 0.06 9.27 ± 0.08
84.15 ± 2.23 75.03 ± 2.65 4.73 ± 4.63 3.64 ± 3.97
Pokec-z
F1 (↑) ACC (↑) ∆DP (↓) ∆EO (↓)
70.23 ± 0.27 69.74 ± 0.25 8.22 ± 0.48 6.47 ± 0.56
69.79 ± 0.48 69.53 ± 0.19 7.19 ± 0.81 6.02 ± 0.80
69.88 ± 1.38 69.09 ± 1.84 8.69 ± 2.49 8.51 ± 1.94
70.53 ± 0.17 69.94 ± 0.30 8.07 ± 0.39 5.90 ± 0.61
70.70 ± 0.41 68.85 ± 0.68 6.71 ± 0.45 4.62 ± 0.49
Pokec-n
F1 (↑) ACC (↑) ∆DP (↓) ∆EO (↓)
65.04 ± 0.33 68.56 ± 0.36 2.81 ± 0.79 4.06 ± 0.92
64.88 ± 0.54 68.31 ± 0.63 2.73 ± 0.72 4.18 ± 0.80
65.90 ± 1.85 69.54 ± 1.13 2.45 ± 0.80 2.30 ± 1.84
65.42 ± 0.30 69.14 ± 0.19 1.41 ± 0.60 2.32 ± 0.79
65.46 ± 1.64 67.20 ± 0.60 0.86 ± 0.44 2.22 ± 0.93
TABLE IV Comparison of Grad2Fair using the GIN backbone with baseline methods on four datasets. In each row, the best result is marked in bold, while the runner-up result is marked with an underline. Metrics
Vanilla GIN
FairGKD
Fairwos
FDKD
Grad2Fair
Bail
F1 (↑) ACC (↑) ∆DP (↓) ∆EO (↓)
72.04 ± 2.18 77.20 ± 2.51 7.79 ± 0.80 6.55 ± 0.87
75.29 ± 3.47 81.10 ± 3.78 4.73 ± 1.42 3.39 ± 1.93
75.50 ± 0.57 80.80 ± 1.62 6.29 ± 0.75 3.62 ± 0.47
68.06 ± 2.86 72.66 ± 2.87 5.77 ± 1.05 4.30 ± 1.81
68.99 ± 5.92 77.40 ± 4.52 4.87 ± 2.38 3.18 ± 1.76
Credit
F1 (↑) ACC (↑) ∆DP (↓) ∆EO (↓)
82.82 ± 0.46 74.61 ± 0.51 11.31 ± 1.06 8.77 ± 1.20
83.01 ± 0.61 74.85 ± 0.71 10.62 ± 1.92 8.32 ± 1.61
80.94 ± 2.07 72.45 ± 2.40 10.98 ± 2.43 8.30 ± 2.88
82.24 ± 0.41 73.98 ± 0.47 12.05 ± 1.23 9.46 ± 1.03
83.25 ± 1.14 74.84 ± 1.30 4.85 ± 3.30 2.47 ± 2.49
Pokec-z
F1 (↑) ACC (↑) ∆DP (↓) ∆EO (↓)
67.64 ± 0.91 68.30 ± 0.98 3.57 ± 0.95 4.75 ± 0.85
68.84 ± 1.17 67.97 ± 1.06 1.79 ± 0.68 1.81 ± 1.15
67.14 ± 2.06 68.87 ± 0.75 6.46 ± 4.36 6.09 ± 3.68
68.82 ± 0.86 68.99 ± 0.68 3.68 ± 1.03 3.90 ± 0.76
67.33 ± 1.54 66.66 ± 2.28 1.64 ± 1.20 1.72 ± 1.48
Pokec-n
F1 (↑) ACC (↑) ∆DP (↓) ∆EO (↓)
62.67 ± 1.01 67.87 ± 0.91 0.78 ± 0.78 3.37 ± 1.24
63.27 ± 0.94 67.40 ± 0.65 2.33 ± 1.39 3.77 ± 1.74
64.50 ± 1.59 69.79 ± 1.00 2.98 ± 1.37 5.85 ± 1.46
61.75 ± 0.98 68.76 ± 0.50 0.80 ± 0.60 3.18 ± 1.17
63.27 ± 0.81 68.10 ± 0.83 0.63 ± 0.32 2.47 ± 0.86