GraphGini: Fostering Individual and Group Fairness in Graph Neural Networks
Authors: Anuj Kumar Sirohi
Anjali Gupta
Sandeep Kumar
Amitabha Bagchi
Sayan Ranu
Venue: Accepted by TMLR ()

Abstract: Graph Neural Networks (GNNs) have demonstrated impressive performance across various tasks, leading to their increased adoption in high-stakes decision-making systems. However, concerns have arisen about GNNs potentially generating unfair decisions for underprivileged groups or individuals when lacking fairness constraints. This work addresses this issue by introducing GraphGini, a novel approach that incorporates the Gini coefficient to enhance both individual and group fairness within the GNN framework. We rigorously establish that the Gini coefficient offers greater robustness and promotes equal opportunity among GNN outcomes, advantages not afforded by the prevailing Lipschitz constant methodology. Additionally, we employ the Nash social welfare program to ensure our solution yields a Pareto optimal distribution of group fairness. Extensive experimentation on real-world datasets demonstrates GraphGini's efficacy in significantly improving individual fairness compared to state-of-the-art methods while maintaining utility and group fairness.

Published in Transactions on Machine Learning Research (01/2026)
GraphGini: Fostering Individual and Group Fairness in Graph Neural Networks
Anuj Kumar Sirohi* Indian Institute of Technology Delhi
oiz218824 @vitd. oc.in
Anjali Gupta*
anjali@ese. itd.eeeee.ddd.... ac in
Indian Institute of Technology Delhi
Sandeep Kumar
ksandeep@iitte oc in
Indion Institute of Technology Delki
Amitabha Bagchi
bagchi@cse. itd. oc in
Indion Institute of Technology Delki
Sayan Ranu
sayanrumuQese.cco ac.
Indian Institute of Technology Delhi
Reviewed on OpenReview: https: // openreview. net/ forum? id= IEVGBI9N1L
Abstract
Graph Neural Networks (GNNs) have demonstrated impressive performance across varions lasks, leading to their increased adoption in high-stakes decision-making systems. However, concerns have arisen about GNNs potentially generating unfair decisions for underprivileged groups or individuals when lacking fairness constraints. This work addressos this issue by introducing GRAPHGINI, a novel approach that incorporates the Gini coefficient to enhance both individual and group fairness within the GNN framework. We rigorously establish that the Gini coefficient offers greater robustness and promotes equal opportunity among GNN outcomes, advantages not afforded by the prevailing Lipschitz constant methodology. Additionally, we employ the Nash social welfare program to ensure our solution yields a Pareto optimal distribution of group fairness. Extensive experimentation on real-world datasets demoustrates GRAPUGINI'S elficacy siguificantly improving individual fairness compared state-of- taae-offtheeart methods while maintaining utility and group fairness.
1 Introduction and Related Works
Graph Neural Networks (GNNs) are increasingly being adopted for various high-stakes applications, including medical diagnosis Ahmedt-Aristizal
credit scoring for loan issuance (Shumovskaia et al. 2020),
al.,
2021), molecular property prediction (Wieder et al.) 2020
Sirohi et al. 2025 Nishad et al.] 20200) and
recommendation engines and (Fan et al. 2019 Gong et al.
2020
Agrawal et al. 2024 Gupta et al. 2025 V
ct al. 2025 Chakraborty et al. 2023: Manchanda et al.
2020
However, recent studies have shown that
GNNs may explicitly or implicitly inherit existing societal biases in the training data and, in turn, generate decisions that are socially unfair (Dong et al.] 2023 Dai et al. 2022) It is, therefore, important to guard GNNs from being influenced by sensitive features such as gender, race, religion, etc.
There are two primary approaches to address the issue of algorithmic bias: individual fairness and group fairness (Mehrabi et al. 2021 Liu et al. 2022). Individual fairness involves masking the sensitive features and ensuring that individuals who are alike with respect to non-sensitive features receive similar treatment outcomes from system. The group fairness approach, on the other hand, looks within groups defined by sensitive features, e.g., female job applicants or male job applicants, and works to ensure that each such group has similar individual fairness characteristics to all other groups. For example, the variability in treatment between two highly qualified female candidates should be no more than the variability treatment between
*These authors contributed equally to this work.

---

Published in Transactions on Machine Learning Research (01/2026)
two highly qualified male candidates. In general, a fair system should ensure both individual fairness and group fairness since they ensure parity in two complementary dimensions.
1.1 Existing Works
For individual fairness, the key optimization parameter sought to be minimized is the Lápschila constand, i.e. the worst-case ratio of the distance between the GNN-generated embeddings of pairs of points and their distance based on some domain-specific criteria (e.g., number of common friends, similarity on initial attributes, etc.). The advantage of this metric, as observed in several works (c.f., e.g., (Kang et al., 2020 Lahoti et al. 2020; Dwork et al.) 2012: Song et al. 2022)), , is that it is differentiable. Intuitively, small Lipschitz constant implies that the distance in the embedding space is similar to the distance in the input space. Since the GNN prediction is a function of the embeddings, this implies that similar individuals are likely to get similar predictions (Kang et al. 2020).
Individual fairness:
Group fairness in GNNs has the objective of achieving accurate prediction while also being independent of protected attributes that define groups. RRahman al. (2019) propose the idea of "equality of representation", which expands upon the concept of statistical parity for the node2vec model.
Group fairness:
Bose & Hamilton 2011)), and Dai & Wang (2021) propose adversarial approaches to eliminate the influence of sensitive attributes. He et al. [2023 enables group fairness with respect to multiple non-binary sensitive
attributes. Among other works, the strategies include balance-aware sampling (Lin et al. 2023), attention to
mitigate group bias (Kose & Shen 2023 and bias-dampening normalization (Kose & Shen 2022
Lin et. al.
2024
Yang et al., 2024).
Both group and individual fairness: GUIDE Song et al. (0022 is the first and only state-of-the-art work to integrate group and individual fairness principles within GNN framework. Using Lipschitz constant. minimization to enforce individual fairness, GUIDE sought to achieve group fairness by trying to equalize the individual fairness achieved across groups. More recent works, such as Wang et al. (2024) and Yan el al. (2024); further explore this intersection by proposing alternative fairness formulations and optimization strategies to simultancously improve both fairness notions.
1.2 Contributions
The Lipschitz constant, because it is differentiable, has been the predominant metric for optimizing both individual and group fairness. However, this mathematical convenience comes at a cost. Specifically, the Lipschitz constant, being mar operator, fails to capture the distribution of outcomes, making it overly restrictive and sensitive to outliers. To address its restricted expressivity, we introduce GRAPHGINI, incorporating three key innovations:
Incorporating Gini and establishing its superior encapsulation of fairness: To capture fairness on the entire spectrum of outcomes, we propose the Gini coefficient, a well-established social welfare metric. We show that the Gini coelficient offers more robust and holistic fairness measure, naturally leading to equal opportunity Hardt al. (2016).
Differential approximation of the Gini coefficient: Fair ML models, including GNNs, typically enforce fairness constraints regularizers in the loss function. Unlike the Lipschitz constant, the Gini coelficient is non-differentiable, preventing direct optimization. We address this by proving an upper bound that is differentiable, allowing its seamless incorporation
loss regularizer.
Pareto Optimality: We establish a Pareto optimal distribution of group fairness through the use of the Nash Social Welfare Program (NSWP) (Charkhgard et al. 2022 which is an optimization technique that provides provably Pareto optimal solutions for multi-objective optimization problems.
With the incorporation of the proposed innovations, GRAPHGINI, outperforms 11 statc-of-tho-art fair GNN algorithms in both individual and group fairness, with minimal impact on utility, We demonstrate this using empirical framework that evaluates 3 GNN backbones across three real-world datasets.
2

---

Published in Transactions on Machine Learning Research (01/2026)
2 Background and Problem Formulation
We bold uppercase letters (e.g., A) to denote matrices and Aii,;) A[:J] and A[t.j] represent the i-th row, j-th column, and (i, entry of matrix A respectively. For notational brevity, we use 2; to represent the row vector of a matrix, L.e, 2; :[) As convention, use lowercase (e.g., n) and bold lowercase (e.g,, z) variable names to denote scalars and vectors, respectively. We use Tr(A) to denote the trace of
matrix A. The & and fg-norm of vector Rd are defined as ||2|/2 Ein | and ||z||2 = VE of respectively. All notations are summarized in Table in the Appendix.
Definition 1 (Graph). A graph G (V, has (i) n nodes (VI = (it) a set of edges & (iti) feature matrir X Raxd characterizing each node.
and
Definition 2 (Graph Neural Network (GNN) and Node Embeddings). A graph neural network consumes graph G (V,,, as input, and embeds every node into c-dimensional feature space. We denote Z Rx to be the set of embeddings, where denoles the embeddiin of node U; V.
Definition 3 (Sensitive attributes). Sensitive attributes are those attributes that should not be used by the GNN to influence the prediction (e.g. gender). As function of these allributes, v may be partitioned into disjoint groups.
For instance, gender may be classified as sensitive attribution, which partitions the node set into Vmate and Veemate such that V = Vmatt U Uemmatee-
Definition 4 (User similarity matrix S and Laplacian L). Based on domain knowledge happlg///pppplaaiinno the similarity matrix S denotes the similarity across any pair of nodes. The Laplacian L of S is defined as D where, D is a diagonal matriz, with Dii,
Without loss of generality, we assume the similarity value for a pair of nodes lies in the range [0, 1]. The distance between nodes is defined to be the inverse of similarity, i... for two nodes u, Uy E V, d., = s where is small positive constant to avoid division by zero. Furthermore, we assume that the distance/similarity is symmetric and is computed after masking the sensitive attributes.
2.1 Individual fairness
Individual fairness demands that any two similar individuals should receive similar algorithmic outcomes (Kang et al. 2020). In our setting, this implies that if two nodes (w: and Uz) are similar (i.e., S(us, 1y]] is high), their embeddings (z; and zz) should be similar as well.
As discussed $ the Lipschitz constant has been the predominant choice for enforcing individual fairness. In this section, we concretely establish limitations and show how the Gini coefficient offers a more expressive and robust mechanism for modeling individual fairness.
2.1.1 Limitations of the Lipschitz Constant
Definition The Lipschitz constant of GNN with node embeddings E Ruxe is defined as the smallest constant such that for all pairs of nodes Us By E V:
||z 1i|li di,f
||z, - 1-211 L. -dd = L LZ max
(1)
EV
Since the Lipschitz constant defined using a max operator, it only captures the worst-case discrepancy between input distances and GNN embeddings, ignoring the full distribution of variations across all node pairs. This results in incomplete and iallntially misleading quantification of inequality. We illustrate this
3

---

Published in Transactions on Machine Learning Research (01/2026)
with concrete example over population of 5 nodes, whose distance matrix is as follows.
A
B
C
D
E
A
1
2
2
2
2
B
2
2
2
C
2
2
D
1
2
E
1
We only show the upper triangle due to symmetry of the similarity function. The distance between pair of nodes i,j is defined as its inverse, i.e., di- STJ]] Thus, in our case, all pairs of distinct nodes have a distance of 2.
Corresponding to this cumilarity/dsslanne matrix, let us consider two GNNs that produce the embeddings in Table [ As can be seen, while GNN-1 preserves an identical distance of 2 in the output space among all
Table 1: Embeddings of GNNs.
Node
Embeddings from GNN-1
Embeddings from GNN-2
A
[10, 10, 10, 10)
[10, 10, 10, 10]
B
0,
0,,0,0,0
C
0, 0,0,0
0,
D
O, 0,0,1,00
0, 0,0
E
[0, 0,
0, 0,
nodes except those involving A, the inequality is higher in GNN-2. Despite this, the Lipschitz constants for both GNN-1 and GNN-2 are dominated by the (A, B) pair leading identical value of 19.5.
We address this limitation with the Gini coefficient.
2.1.2 Gini Coefficient
In economics theory, the Lorenz curve plots the cumulative share of total income held by the cumulative percentage of individuals ranked by their income, from the poorest to the richest (Gastwirth 1972 Sitthiyot & Holasut 2021 Dagum 1980p. The line at 45 degrecs thus represents perfect equality of incomes. The Gini
coefficient is the ratio of the area that lies between the line of equalily and the Lorenz curve over the total
area under the line of equality (Gastwirth 1972 Sitthiyot Holasut 2021 (See Fig. D in Appendix for an
example). Mathematically,
E L I Zg
Gini(x)
(2)
2n
where is the set of individuals, x; is the income of person and n | lower Gini indicates fairer distribution, with indicating perfect equality.
In context, rather than measuring income incquality, assess fairness in algorithmic outcomes by ensuring that similar individuals receive similar predictions (Kang al. 2020 The analogy to income distribution holds because, just as the Gini coefficient captures disparities across the entire population, our formulation captures disparities in algorithmic outcomes across all pairs of individuals. However, instead of treating all differences equally, we introduce a himilarity-wiigheee
extension.
Definition 6 (Gini Coefficient for Individual fairness). The individual fairness of the node set with embeddings Z and similarily matriz S is ils weighled Gini coefficient, which is defined follows,
Gini(V) Σn ΣØ= Sli (2: 2;
(3)
2n Σ
|z.|11
In this formulation, large disparities between dissimilar nodes have minimal impact on the Gini coefficient, while considerable disparities among similar nodes have stronger effect. The denominator normalizes
4

---

Published in Transactions on Machine Learning Research (01/2026)
disparities by the total weighted sum of outcomes. This prevents the metric from being arbitrarily sensitive to scale and ensures a consistent interpretation across different datasets and applications
Further, the Gini coefficient is superior to the Lipschitz constant because it is not limited to reflecting only the worst-case scenario. In the example presented in $ 2.1.1 for instance, Gini yields values of 0.377 and 0.74 for GNN-1 and GNN-2, respectively (c.f. Table D. accurately reflecting the higher inequality present GNN-2's outcomes. Also, it important highlight the Definition formalizes the multidimensional Gini index to vector-valued node embeddings, detailed derivation is presented in in Appendix [
2.2 Group Fairness
Optimizing individual fairness alone may cause group disparity (Kang al. 2020). Specifically, one group may have considerably higher level of individual fairness than other groups. We follow the same definition of group fairness proposed in GUIDE Song et al. (2022). with the only difference of replacing the Lipschitz constant with the Gini coefficient.
Definition (Group Fairness). Group Fairness is satisfied if the levels of individual fairness across all groups are equal. Mathematically, let (V,.... } be the partition of node set V induced by the sensitive attribute. Group fairness demands ji Gini(V;) = Gini(V)).
To convert group fairness satisfaction into an optimization problem, we introduce the notion of group dispority of individual fairness.
Definition 8 (Group Disparity). Given a pair of groups Vg, Vh, the dispority among these groups is quantified as:
GDIF(V, V.) = max Gini(Vy) (Vni(V,)
(4)
(i))(V)) Gini(V,)
GDIF(V,; Vn.) 2, with value of 1 indicating perfect satisfaction. Now, to generalize across groups, average group disparily measures the average disparity across all pairs.
A-GDIF((L,.". .mni) = m(m -
Σ
GDIF(V,V))
(5)
We now argue that minimizing the Gini Coofficient promotes equal opportunity. Definition (Equal Opportunity Hardt et al. (2016)). The GNN prediction for a node v, {v), satisfies *equal opportunity* if:
SE
for some small e, i.e., require that the rate of positive outcomes is similar among those who deserve positive outcomes.
Observation 1. Minimizing the Gini promotes equal opportunity.
The numerator of Gini (Eq. is EE Sli, Allz - 21l11 Since the denominator independent of the pair-wise distances between node embeddings, it implies:
aGini(V)
x S[i
(6)
0|l. 1y111
Therefore, minimizing Gini(V) will minimize ||z 2,llı when Sli.j] is large, which implies that similar nodes will have similar embeddings (small ||z, z, I11). Since GNN outcomes are functions of the embeddings, denoted by f(;;,, two nodes v and by are such that ||z; - 2, l| small, then by the Cauchy-Schwarz inequality,
(1(())) - [(z;)) R [2,) (z. - -2)1l < [ ||2, 2,111,
Here, the definition expressed using the fo-norm; alternative choices such fg-norm possible correspand different interpretations fairness.

---

Published in Transactions on Machine Learning Research (01/2026)
i.e, the GNN will yield similar outcomes for reasonably smooth f.
From our definition of group fairness (Def. 7 and the corresponding Group Disparity (GDIF) (Def. S minimization implies that the internal consistency of embeddings within each group becomes similar. Since similar embeddings yield similar outcomes, the predicted label will be similar for individuals with a true label of within a group. Let vn E V/ and 02 E V2 be two similar nodes such that Y(1)) (rs) = Then,
2z 22 Se (P(Y 1) 1)) s
for some small 6. For all such similar pairs in V and V2, we have
SE
which is the definition of Equal Opportunity.
2.3 Problem Formulation
We finally state our problem objective.
Problem 1 (Fair GNN). Given graph G = (V,E, symmetric similarity matriz S for nodes in V, and l disjoint groups differing in their sensitive attributes (i.e, V/), our goal is to learn node embeddings Z such that:
Overall individual fairness level is marimized (Eq. 30;
2. Cumulative group disparity is minimized (Eq. 50
3. The prediction quality the node embeddings is marimized.
3 GraphGini: Proposed Methodology
The key challenge in learning fair node embeddings Z is to design loss function that encapsulates all three objectives of Prob. | Designing this loss function requires us to navigate through three key challenges. (1) Gini is non-differentiable and hence cannot be integrated dircctly into the loss function. (2) Sccond, since group disparity a formulation over a max operator, it remains non-differentiable as well. (3) Finally, we need a mechanism to automatically balance the three optimization objectives of the GNN without resorting manual adjustments of weight parameters.
3.1 Optimizing Individual Fairness
The weighted Gini coefficient Gini(V) is not differentiable in general. In case ||z, 2 1 is 0, the derivatives from different directions may converge to different limits. To work around this problem, we present a differentiable (and convex) upper bound to this metric.
Proposition 1. Given node embeddings Z Raxe of graph G EV,EXX) with node similarity matriz S and corresponding Laplacian L (Recall Def. 4.
Gini(V) < Tr (Z LZ).
Proof. The normm, when multiplied by the square root of the dimension of the space, is an upper bound the 4-norm. Using this fact, we get:
Ski.i|lz 21112 S
S 1
2,112 S Vc
S 11 - 27112
(7)
j=1

---

Published in Transactions on Machine Learning Research (01/2026)
VI
56
Y6
Y2
X3
Y3
X5
Y5
Input Graph
Similarity Matrix (S)
Node labels (Y)
Vanilla GNN
P.C, + PaCs + PcCs
Initialise
D Utility
Grad Grad Norm
11
Attention Network
L2 Individual fairness
13
L Group fairness
15
14
Embedding (Z)
Figure 1: The figure illustrates the pipeline of GRAPHGINI The sequence of actions depicted in this figure is formally encapsulated in Alg. 1 (in Appendix) and discussed in $ 3.3
where e the dimension of the GNN embeddings. Now, substituting this inequality into the expression for Gini(V) (Eq. 3 we have:
ΣΣ Sli
2
Gini(V)
Sli 2 Tr Fz" (8)
2 2 =1
the denominator in Eq. is strictly positive and scales both sides of the inequality, thereby does not affect
the inequality.
The upper bound in Proposition | has appeared as a heuristic individual fairness regularizer in prior work Kang et al. 22200) Here, we present a new interpretation based on the Gini coefficient. Hereon, we use the notation Gini(V) Tr LZ) to denote the upper bound Gini with respect to node set V characterized by similarity matrix S and embeddings Z. An alternative solution to work around the cnn-differentiabille is to approximate it using smooth pooling-operatee surrogates such as softmax and top-k as aadividual-fairneee regularizers. In Appendix
K we demonstrate that these surrogates are empirically inferior to the proposed differentiable upper bound. Next, we discuss the effectiveness of minimizing this differentiable upper bound as surrogate for the true Gini coefficient. The following proposition outlines how optimisation over the relaxed objective remains aligned with reductions in the original fairness measure, i.e., the Gini coefficient.
Proposition The same value of Z minémizes both Gini(V) and differentiable upper bound Gini(V). Moreover, since Gini(V)= (
Tr(Z LZ) is conver in Z, we can efficiently find its global minimum. Consequently, solving for the minimizer of Gini(V) guarantees minémization of the true Gini coefficient as well.
Proof. The detailed proof is provided in App.
3.2 Optimizing Group Fairness through Nash Social Welfare Program
Group fairness optimization, defined in Eq. 5 is a function of the Gini coefficient. Hence, Eq. non- differentiable well. The natural relaxation to obtain differentiable proxy function is therefore to replace

---

Published in Transactions on Machine Learning Research (01/2026)
Gini(Vz) with (V) = Tr (Z Lgg)) in Eq. Here V/ V is a group of nodes, Z, {z: Z 02 E V/} are the node embeddings of Vg. and Lg is the Laplacian of the similarity matrix S, V/ x V. + R. Unfortunately, even with this modification, optimization of group fairness remains non-differentiable since a function of the form max by is differentiable everywhere except at a b To circumvent this non- differentiability, we employ Nash Social Welfare Program (NSWP) optimization CCharhhgard et al. 2022
The NSWP a technique in mathematical programming that combines multiple objectives into a single objective, leading to a Pareto-optimal solution. The core idea involves creating a product of the differences
Gáni(Va)) and Cini(V))
between Iwo minimization terms, both referenced to a common point. In our context, G)mi(V)) Gin(V)))
are the competing terms to be minimized. We choose 1 the common reference. Then, using the NSWP formulation, the resulting optimization leads to the following expression:
Gáni (Vg) -1) Gini(Vi))
Gini(Vh) - (Vn)lVy)
(9)
Intuitively, group fairness is maximized when for any pair of groups Gini(Vg) Gini(Vn). On the other hand, if Gini(Vy) >> Gini(Va) then Eq. approaches oc. We now establish that the solution obtained by minimizing Eq. 9 is Pareto optimal.
Proposition 3. Minimizing Eq. produces Parelo oplimal solutions for group fairness over all groups.
Proof. The detailed proof is provided in App.
3.3 Learning Framework
GRAPHGINI strives achieve balance among three distinct goals:
1. Utility Loss: We assume L1 denotes the loss term for the GNN prediction task.
Loss for individual fairness: To maximize the overall individual fairness level, Gini(V), we minimize:
C2 Tr (Z),
(10)
Loss for group fairness: To maximize group fairness across of disjoint node partitions (Vi.... Vm,, we minimize:
Gini(Vi)
-1)
Gini(V;) -1 Gini(V,) -1)
Σ
Ls = m(m 1)
Gini(V;)
W.jElL.ml ifj
Incorporating all of the above loss terms, we obtain:
L B + 32L2 + BaL3-
(11)
Here, 3, are tunable hyper-parametts parameters.
The overall framework of GRAPHGINI is presented in Fig. I
Alg. I in the Appendix presents the pseudocode. First, embeddings for nodes are learned on the input GNN using only the utility loss. These initial embeddings are now enhanced by injecting fairness through a Graph Attention Network (GAT) (Velickovic
et al. 2017 where the attention is reinforced in proportion to the similarity strength.
aij = exp(LeakyRel..(a" Whh (W/ E eep(eeaty/leelU((""
(12)
Here, W E Rddh is the weight matrix, he E TR the embedding for node in layer l, a E 2R2d is the attention vector. The symbol [.|l-] denotes concatenation of vectors and Nr represents the neighbourhood of node Using pairwise attention, the embeddings are aggregated as h h.*1 oEEjEN,O,, Wh)).
While ReLU is also operator, represents a special case handled pre-coded values. They transfer generic loss fonstions. See App. F.T for details.
8

---

Published in Transactions on Machine Learning Research (01/2026)
Table 2: Summary statistics of used datasets.
Name
# nodes
node attributes
# of edges # edges
Sensitive
in A in S
Attribute
Credit
30,000
13
304,754 100,483
687, 444 997, 641
age
Income 14,821
14
race age
Pokec-n
66,569
266
1,100,663
32, 837, 463
3.4 Balanced Optimization with GradNorm
The optimisation process requires a delicate calibration of weighing factors, i.c., coefficients 3,'s in our loss function (Eq. [ip. Manual tuning, the predominant approach among existing techniques, is challenging as these weights not only determine the relative importance of fairness objoctives compared to utility but also play a dual role in normalizing individual terms within the loss function. We perform gradient normalization automatically learn the weights (Chen et al., 2018
Let Oe be the parameters of the GAT at epoch t and Li(t), d E (1, denotes the value of the loss term Le in the 1-th epoch. We initiate the learning process with initialized weights (.)).. In later rounds (t > 0), we treat each (t( as adjustable parameters aimed at minimizing a modified loss function, which we will develop next.
First, corresponding to each (,((), we compute the l norm of the gradient.
(t) 1 3,t),,))))
(13)
The loss ratio in the f-th epoch is measured as (t) = (0
Z, which reveals the inverse training rate, i.e., the
lower the ratio, the higher is the training, Finally, instead of optimizing the original loss in & Eq. [1]. we
minimize the loss below that operates the gradient space of the individual loss terms. Specifically,
Σ (())).(()) G(t) R2(()
3
grradnorm (t)
(14)
R(t)
3
3
where, G(t)
Gt(t), R(t) = 3
Σ Rt(t)
3
Intuitively, Eq. strives to achieve similar training rates across all individual loss terms. Hence, it penalizes weighing factor (t) if the training rate is higher (t( than the average across all terms.
3.5 Convergence and Time Complexity
Convergence. Since our framework uses standard GNN architectures, the convergence analysis of gradient descent for GNNs from Awasthi et al. (2021) which assumes a smooth and bounded loss function, directly applics. Therefore, the optimization procedure for GRAPHGINI guarantced to converge under the same conditions. detailed discussion over convergence is provided in the Appendix G
Time complexity. The base Graph Neural Network (GNN) has time complexity of O(EE), where |&| represents the number of edges in the graph. Both GRAPUGINI and the primary baseline, GUIDE, require additional step of computing the Laplacian matrix. This computation is lincar with respect to the number of non-zero entries in the similarity matrix, which in the worst-case scenario is O(IV12, where |V] is the number of vertices in the graph. The overall time complexity of these fair GNN approaches can thus be expressed as O(1 + [V])), accounting for both the base GNN operations and the Laplacian computation. The runtime comparison is also empirically demonstrated in Appendix
4 Experiments
The objective in this section is to answer the following questions:

---

Published in Transactions on Machine Learning Research (01/2026)
Table 3: Performance comparison of benchmarked algorithms across datasets using the GCN backbone architecture. "Vanilla" indicates debiasing. Arrows: t higher is better, = lower is better. Best
performance per column is in bold. Individual fairness (IF) is reported in thousands.
Model
AUC (1)
IF (1)
GD
IF-Gini ()) GD-Gini (4)
Credit
Vanilla
0.68+0.10
40.01+2.16
1.34+0.05
0.30+0.01
1.72++0.02
FairGNN
0.68
23.35-11.399
1.3410.10
0.26+1.02
1.69:0001
NIFTY
0.69+40.01
30.85++1.45
1.25:10.05
0.26+10.2
1.67+0.001
PFR
0.64
36.37=7.90
1.46:1.02
0.30+1.00
1.72:0.01
InFoRM
0.68#
2.42=00.22
1.45=10.22
0.18#0.01
1.73+0.01
PostP
0.70=10.00
40.23+10.00
1.40
0.30
1.74
FairNMTF
0.69
40.62+1.34
1.38=0.02
0.29=0.02
1.71
GNN GEI
0.69:10.00
10.21#
1.35+0.05
0.28+0.01
1.70
TF-GNN
0.60
12.80=0.000
1.45+0.00
0.19=0001
1.71#00002
BeMAP
0.68+00.00
3.11+1.23
1.20++0.00
0.15+0.02
1.73+00.2
FairSIN
0.68
8.23-3.20
1.15+10.00
0.20
1.69:1001
GUIDE
0.68#0.02
1.94=0.10
1.00
0.14
1.41
GRAPHGINI
0.68
0.22=0.06
1.00=0.00
0.1210.01
1.10=0.01
Income
Vanilla
0.77+0001
370.8110.02
1.30+1001
0.32
1.56:0..2
FaiNGNN
0.76++0.00
250.22+85.32
1.16=00.03
0.30
1.55+0.001
NIFTY
0.73+0.00
44.32+5.67
1.39++0.03
0.25+0.01
1.60+0.001
PFR
0.75
245.95+0..50
1.3310.01
0.30+10.02
1.56+0.02
InFoRM
0.78-10.01
199.20110.04
1.35:10.04
0.26
1.54
PostProcess
0.77=0000
367.62+:0.00
1,28+0.00
0.31=0.01
1.55+10011
FairNMTF
0.77+00.00
358.20+0..2
1.28+10.01
0.30
1.57=+0.01
GNN GEI
0.77+00.00
357.23
1.47+0.01
0.30
1.56
TF-GNN
0.76+0000
25.65+00.0
1.85++0.00
0.24+0.01
1.60
BeMAP
0.73+0.00
211.66-22.34
1.33+00000
0.2610.01
1.57+0.01
FairSIN
0.73+0.00
287.22
1.42+0.00
0.27+0.01
1.61
GUIDE
0.73++0.01
33.20-11.144
1.00
0.20
1.10+4..1
GRAPHGINI
0.73
21.1215.22
1.00
0.1710.01
1.02+0.01
Pokec-n
Vanilla
0.77+0.01
950.284:39.11
6.93+1010
0.41+0.02
1.8040.01
FairGNN
0.69++0.3
363.73+78.58
6.29+11.22
0.35+00.1
1.76+00.02
NIFTY
0.7410.00
85.25+10.55
5.06-1.29
0.31+0.01
1.7240.02
PFR
0.53++0.00
98.25+9.44
15.8440.03
0.32+0.02
1.70
InFoRM
0.77+0000
230.45++6.33
6.62+0.11
0.34+0.01
1.69
PostProcoss
0.77+0.00
82..2
5.93+00.7
0.39+0.01
1.72+0.02
FaarNMTF
0.76
781.29-198.45
7.2310.11
0.39-10.01
1.7340.01
GNN GEI
0.77
875.1149.31
6.4318.31
0.37+0.01
1.74+0.02
TF-GNN
0.74
245.48
9.28++0.10
0.33+0.02
1.81
BeMAP
0.73
372.00+44875
2.29
0.31
1.41
FairSIN
0.73++0.00
482.00-439.20
2.88+10.03
0.31+0.02
1.41+00.33
GUIDE
0.73+00.02
55.05-30.87
1.11+:0.3
0.24+0.02
1.1940.01
GRAPHGINI
0.74+0.00
31.1015.22
1.00+0.00
0.21+0.01
1.14+0.01
RQ1: How well GRAPHGINI balances utility, individual fairness, and group fairness objectives compared to baselines?
10

---

Published in Transactions on Machine Learning Research (01/2026)
Table 4: Performance comparison of benchmarked algorithms across datasets using the GIN backbone architecture. "Vanilla" indicates debiasing. Arrows: t higher is better, lower is better. Bost
performance per column is in bold. Individual fairness (IF) is reported in thousands.
Model
AUC (f)
IF (L)
GD (4)
IF-Gini (1) GD-Gini (4)
Credit
Vanilla
0.71+0.00
118.02++1.22
1.80++0166
0.29 + 0.02
1.64 + 0.01
FairGNN
0.68
76.10:445.22
2.20::0.15
0.25 = 0.01
1.64 + 0.01
NIFTY
0.70+40.04
58.33-1-39.85
1.68+
0.25 + 0.01
1.64 + 0.01
PFR
0.71#0.03
160.55+100.20
2.44+1.20
0.30 = 0.01
1.66 1.66 0.01
InFoRM
0.69:+0.03
2.96:0.12
1.75+0.115
0.16 0.01
1.66
PostP
0.71+:.000
177.44-60.66
1.42::0.08
0.30 0.01
1.66
FairNMTF
0.71#0.01
107.72+9.04
1.440.23
0.28 0.02
GNN GEI
0.70+10.06
176.21#1.21
1.45 + 0.23
0.27 = 0.02
1
TF-GNN
0.71+0.01
18.42+0.422
1.29+0.11
0.21 = 0.01
1.70
BeMAP
0.68
12.25-43.25
1.39++001
0.17 + 0.00
FairSIN
0.68:0000
18.12 6.68
1.60+0.00
0.19 0.01
1.70
GUIDE
0.68+0.00
2.45
1.0010.00
0.12 0.01
1.30 + 0.01
GRAPHGINI
0.68
1.9240.09
1.0010.00
0.10 0.01
1.13 = 0.01
Income
Vanilla
0.80+0.02
2812.62+1061.04
1.87:00466
0.46 0.01
2.00 + 0.00
FairGNN
0.79+0.00
1359.93+880.222
3.32+t1.20
0.35 = 0.01
2.06 = 0.01
NIFTY
0.79+00001
617.11+320.15
1.16+0.30
0.29 + 0.02
1.65 + 0.01
PFR
0.7911000
2210.3511461.11
2.35
0.45 = 0.02
2.03 + 0.02
InFoRM
0.80+10.01
309.35:114.24
1.61
0.27 + 0.01
2.05 + 0.01
PostProcess
0.80
420.78+128
2.5+0.011
0.28 = 0.01
2.10 + 0.02
Fai
0.80+0.00
2574.38+
2.43+0.38
0.45 0.02
2.10 + 0.03
GNN GEI
0.7910000 2531.59::8..12
3.07+0.23
0.44 0.03
2.13 + 0.01
TF-GNN
0.80+0001
310.20+1.30
1.28+0.01
0.28 0.01
1.71 + 0.02
BeMAP
0.75
872.89475.11
1.3400.00
0.30 = 0.01
1.71 # 0.02
FaIrSIN
0.75+0.0
929.00 65.80
1.45+0.00
0.30 = 0.00
1.75 0.01
GUIDE
0.74+0.01
83.85-120.20
1.00+00.00
0.20 + 0.01
1.14 + 0.01
GRAPHGINI
0.74+0.00
55.731 9.12
1.00100000
0.16 0.01
1.09 + 0.01
Pokec-n
Vanilla
0.76+0.00
4450.00+1550.80
8.38++.30
0.45 = 0.02
1.81 + 0.02
FairGNN
0.69+0001
416.28+440.883
4.84+:2.94
0.36 0.01
1.52 + 0.02
NIFTY
0.7610.01
2777.361344.29
9.28
0.39 0.02
1.80 # 0.01
PFR
0.60+0.01
628.27485.89
6.20
0.36 0.02
1.56 = 0.01
InFoRM
0.75++0.01
271.65+300.63
6.83+1.33
0.33 + 0.01
1.55 + 0.02
PostProcess
0.75++0.0
9.76+0.25
0.44 + 0.01
1.80 + 0.01
0.75+10.00
1972.55-169.34
8.45+0.21
0.41 + 0.01
1.80+ 0.02
GNN GEI
0.75+00.01
4383. 261999
7.2940.87
0.44 = 0.02
1.75 0.02
TF-GNN
0.75++0.00
268.32++21.88
9.31+1.22
0.33 0.01
1.79 + 0.02
BeMAP
0.75+00.00
521.00+72.88
3.32+00.3
0.30 0.02
1.24 + 0.01
FairSIN
0.75++0.0
556.624: 102.38
3.42+0068
0.29 0.01
1.25 + 0.01
GUIDE
0.74+0.01
120.65+11.333
1.12:00.3
0.25 - 0.01
1.21 + 0.01
0.01
GRAPHGINI
0.74+0000
85.10=6.29
1.00= 0.00
0.22 = 0.02
1.15 + 0.01
RQ2: How robust is GRAPHGINI across GNN architectures?
RQ3: Is GRAPHGINI robust across similarity matrix variations?
11

---

Published in Transactions on Machine Learning Research (01/2026)
Table 5: Comparison of GRAPHGINI with and without Gradient Normalization (GRAPHGINI WGN).
Model
AUC(T)
[F))
GD(J)
AUC(1)
IF(U)
GD(L)
AUC())
IF() GD(U
GCN
GIN
JK
Credit
GraphGini WGN
0.6810.00 0.68#0.00
18820013
1.00
0.6810.00
2.1520.03
1.0010.00
0.68-0.00
2.01-0011
1.0010.00
GraphGini
0.22=0.06
1.00=0.00
0.68:2.00
1.92:0.09
1.00=0.00
0.68=0.00
1.88=0.02
1.00=0.00
Income
GraphGini WGN GraphGini
0.7310.00
21.12.1.:22
1.00
0.7410.00
55.73.1 9.12
1.00.10.00
0.75
31.23.1
3.22
1.00
0.73+0000
20.50#3.10
1.00=0.00
0.71+0000
19.03# 6.33
1.00=:0.00
0.75=0.00
29.17= 4.01
1.00:0.00
Pokec-n
GraphGini WGN
0.71+0.00
31.10=5.22
1.00= 0.00
0.74+00000
85.10=6.29
1.00: 0.00
0.78=0.10
41.5
1.00= 0.00
GraphGini
0.7410.00
27.6016.32
1.00=
0.7110.00
81.37=9.87
1.002 0.00
0.78=0.10
43.87+2.36
0.00
RQ4: Ablation study- What are the individual impacts of the various components on GRAPHGINI?
Our codebase is available at sttp:///gthuoocccm//tearritaaaad
4.1 Datasets
Table 2 presents summary of the real-world datasets used for benchmarking GRAPUGINI. Credit Dataset (Yeh & Lien, 2009): The graph contains 30,000 individuals, who are connected based on their payment activity. The class label whether an individual defaulted on loan.
Income Dataset (Song et al. 2022): This is a similarity graph over 14,821 individuals sampled from the Adult Data Set (Dua & Grail 2017). The class label indicates whether an individual's annual income exceeds
$50,000.
Pokec-n (Takac & Zabovsky
2012): Pokec-n social network where the class label indicates the
occupational domain of user.
4.2 Empirical Framework
Metrics: We use AUCROC and Fi-score to assess performance in node classification. To evaluate individual and group fairness, we use Gini as well as the metries used by GUIDE (Song et al. 2022): individual fairness (IF) LZ) and Group disparity (GD). For two groups g and h, GD = m (n/cg)) where Eg Tr L2 and én =Tr(Z'L,, Z). We also used Gini-based fairness metrics: IF-Gini Gini (Def. 6 and GD-Gini max[G,/Ga Gz/Ggg) for individual and group disparity, respectively, where Gy denotes the Gini for group f. We report the average GD across all pairs of groups. For group disparity, GD = 1 is the idcal case, with higher values indicating poorer performance. We also evaluate Equal Opportunity (EO), a classical measure of group fairness.
Backbones GNNs: We evaluate on three distinct GNN backbones: GCN KKipf & Welling 2016 GIN, Xu et al. 2018a). and Jumping Knowledge (JK) [u et al. 2018b
Baseline methods: We benchmark against eleven baselines, namely (1) GUIDE Song et al. 2022 (2)
FaiGGNN, (Dai & Wang 2021,, (3) NIFTY (Agarwal et al.) 2021), (4) PFR (Lahoti et al. 2020), (5) Inf FRFoRM
Kang et al. 2020). (6) Post Lohia et al.) 2019), (7) GEI (Speicher et al. 2018 (8) FaTr (Godsi
et al. 2024). ), (9) TF-GNN (Song et al.] 2023). (10) BeMap (Lin al. 2024), and (11) FairSTN (Yang et al.
2024j. GUIDE is the state of the art in this space. A more detailed summary of each of the bascline algorithms
is provided in App. D The reproducibility details for baselines, hyperparameter settings, and implementation
specifications given in the Appendix
We evaluate on two different scttings: (1) topological similarity, and (2) attribute similarily. To instantiate S for topological similarity, the (i.j)-th entry in S represents the cosine similarity between the i-th row and the j-th row of the adjacency matrix A. This is aligned with the similarity metric for evaluating fairness in existing works (Kng al. 2020). For the sctting of attribute similarity, the (i. ()th entry in S represents the cosine between the attributes of Us and vy after masking out the sensitive attributes.
Similarity matrix:
12

---

Published in Transactions on Machine Learning Research (01/2026)
Table 6: Impact of fairness regularizer, removing individual fairness constraint, i.e Bg
Model
GCN
GIN
JK
AUC(1) IF(4)
GD(L)
AUC(T)
IF())
GD(4)
AUC(()
IF(L) GD(L)
Credit
Guide GraphGini
0.68 0.68
16.52
1.00
0.68
17.46 13.35
1.00
0.68
9.38
1.00
13.77
1.00
0.68
1.00
0.68
9.28
1.00
Income
Guide 0.73
26.07
1.00
0.74
348.69
1.00
0.74
73.04
1.00
GraphGini
0.73
25.78
1.00
0.74
184.81
1.00
0.74
66.12
1.00
Pokec-n
Guide GraphGini 0.74
0.74
39.57
1.00
0.74
86.23
1.00
0.75
62.80
1.00
33.42
1.00
0.74
38.00
1.00
0.76
41.67
1.00
Table 7: Impact of fairness regularizer, removing group fairness constraint, i.e A3
Model
GCN
GIN
JK
AUC(t) IF(J) GD(L)
AUC(t)
IF(L)
GD(L)
AUC(1)
IF(I) GD(J)
Credit
Guide GraphGini
0.68
2.16
1.52
0.68
2.40
1.46
0.68
2.67
1.82
0.68
2.11
1.52
0.68
2.37
1.45
0.68
2.56
1.52
Income
Guide GraphGini
0.72
25.38
1.02
0.74
152.35
1.23
0.74
439.27
1.14
0.72
21.35
1.09
0.75
150.26
1.15
0.74
402.27
1.02
Pokec-n
Guide GraphGini
0.74
36.34
1.21
0.74
91.47 87.27
1.56
0.75
51.46
1.32
0.74
22.14
1.11
0.74
1.41
0.76
46.9
1.22
4.3
RQ1 and RQ2: Efficacy of GraphGini and Robustness to Architectures
Table 3 and present a comprehensive evaluation GRAPHGINI against state-of-the-art baselines encompass- ing all three datasets, established metrics in the literature and three distinct GNNN architectures (results for JK are presented Table M in the Appendix). In this experiment, the similarity matrix is based topological similarity. A clear trend emerges. While GRAPHGINI suffers minor decrease in AUCROC when compared to the vanilla backbone GNN, it comprehensively surpasses all baselines in individual and group fairness. Compared to GUIDE, which is the most recent and the only work to consider both individual and group fairness, GRAPHGINI outperforms it across all metrics and datasets. Specifically, GRAPHGINI never worse in AUCROC, while always ensuring higher level of individual and group fairness. In terms of numbers, for the Credit dataset, GRAPUGINI improves individual fairness by 88%, 11% and 14% as compared to GUIDE when embeddings are initialised by GCN, GIN and JK backbone architectures, respectively. Similarly, observe significant improvement in individual fairness for the Income dataset by 36%, 33%, & 26% and 43%, 29 %, & 46 % for the Pokec-n dataset without hurting utility and maintaining group fairness. In terms of Gini-based individual (IF-Gini) and group fairness (GD-Gini) metrics, GRAPHGINI outperforms across all GNN architectures and datasets. While this not surprising since we explicitly optimize for Gini, we note that this also leads superior performance the IF and GD measures when computed with the loss function used by GUIDE. This highlights that when the metric optimizes over the entire spectrum of outcomes, rather than just the worst-case scenario, GRAPHGINI produces fairer predictions. Beyond GUIDE,
13

---

Published in Transactions on Machine Learning Research (01/2026)
note that several of the baselines only optimize group fairness. Yet, GRAPHGINI outperforms all of them in this metric while also optimizing individual fairness.
Table 8: Equal Opportunily (EO) comparisons for GRAPHGINI and baselines on three datasets. & indicates the smaller the value is, the better. Best performances are in bold.
Model
Credit
Income
Pokec-n
Vanilla GCN
13.92 + 6.00
14.21 + 0.15
3.17+1.10
PRF
13.96 +0.79
12.15 = 0.03
1.82 + 0.18
FairGNN
13.77 +0.91
12.01 = 0.03
1.85 0.11
InFoRM
14.82 = 4.18
11.44 = 0.52
3.58 1.15
NIFTY
13.07 + 0.63
14.22 0.58
7.32 0.94
GUIDE
13.54 + 0.06
12.35 + 0.15
0.80 0.18
PostProcess
13.82 = 0.01
13.21 = 0.11
1.20 0.10
iFairNMFF
15.13 + 0.03
14.11 + 0.10
2.15 + 0.20
GNN GEI
15.20 0.12
14.20 = 0.25
4.60 + 0.42
TF-GNN
14.62 + 0.32
13.30 + 0.18
3.85 + 0.25
BeMAP
15.40 + 0.32
14.45 - 0.15
4.65 - 0.10
FairSIN
14.82 + 0.64
12.22
0.50
3.50 0.52
GraphGini
12.20 = 0.03
9.75 = 0.25
0.80 +0.08
4.4 Impact on Equal Opportunity (EO)
The results in Table g support Observation 1 showing that GRAPHGINI improves on the classical group fairness measure, Equal Opportunity (BO). We see that GRAPHGINI beats all baseline methods across the datasets on this measure. Overall, this experiment shows that our method able to connect the study of fairness in GNNs to the Economics litcrature by optimizing a metric that considered important in that discipline.
4.5
RQ3: Robustness to Similarity Matrix
In the next experiment, we use similarity matrix based on attribute similarity. In this case, the groups are created through k-means. The number of clusters selected based elbow plot (See Fig. E in the Appendix for details). The primary objectives in this experiment are threefold. Does GRAPUGINI continue to outperform GUIDE, the primary baseline, when similarity is on attributes? How well do these algorithms perform on the metric of Gini coefficient? How is the Gini coefficient distributed across groups (clusters)?
The findings are summarized in Table (in Appendix) on all three datasets for three GNN architectures mirroring the trends observed in Table 3 GRAPHGINI consistently exhibits the best. balance across all
three metrics and outperforms GUIDE across all datasets and architectures on average. Additionally, we delve into the Gini coefficient analysis for cach group (designated CIX). As evident from Table L (in A Appendix), GRAPHGIN achieves lower Gini coelficients across most clusters, underscoring the effectiveness of the regularizers.
4.6 Utility-Fairness Curves
We compare the full utility-fairness curves for GRAPHGINI and basclinc models across all three datasets in Figure 3 Here, utility is measured using AUC. For each baseline, we identified the point where its AUC matches that GrApHGInI and compared the corresponding Fairness values. For baselines that could not reach the AUC of GRAPHGINI, the was mcasured their best achievable performance. Across all datascts, GRAPHGINI consistently demonstrates higher fairness at comparable utility, confirming its effectiveness in achieving favourable trade-off between predietive performance and fairness.
14

---

Published in Transactions on Machine Learning Research (01/2026)
4.7 RQ4: Ablation Study
Impact of Gradient Normalization: Table presents the performance of GRAPHGINI with manual tuming (denoted as GRAPHGINI WGN) against automatic tuning through gradient normalization where all weights are initialized to 1. Gradient normalization imparts significant improvement in individual performance while achieving the same quality in group fairness and accuracy. Individual fairness (IF) benefits the most since the regularizer term corresponding to IF in our loss function of the smallest magnitude. Hence, when set. terms in the loss. With gradient normalization, this
equal weights, IF gets dominated by the other issue is circumvented. Finally, it is noteworthy that even without gradient normalization, GRAPHGINI- WGN outperforms GUIDE (refer to Table 3) across all datasets. This underscores that while gradient normalization contributes to improvement, it is not the sole reason for the superiority of GRAPHGInI over GUIDE. More detailed insights into the evolution of the automatically-tuuel weight parameters via gradient normalization are provided in App. J
Impact of attention: We conduct an ablation study comparing results with and without attention. Our findings show that attention primarily improves individual fairness. Fig. Dillustrates these results on individual fairness. This observation is expected since attention is weighted based on similarity to neighbors, promoting nodes to prioritize similar neighbors in their embeddings. Consequently, individual fairness, which advocates for similar individuals receiving similar outcomes, is reinforced.
Impact of regularizers: Next, we study the impact of the regularizers corresponding to individual and group fairness on the performance of GRAPUGINI as well as GUIDE. To turn off a particular regularizer, we fix its weight to 0. Table 0 and Table presents the results. Three key observations emerge. Firstly, as anticipated, both individual fairness and group fairness suffer when their respective regularizers the metrics of GRAPHGINI and GUIDE in Table 7 with Table 3). Second, while group fairness remains unaffected from turning off individual fairness, the reverse is not true. This phenomenon occurs since group fairness (Eq. ! is function over individual fairness. Thus, even when individual fairness is not directly optimized, it gets indirect assistance from optimizing group fairness. Finally, GRAPHGINI maintains its superiority over GUIDE, even with specific regularizers turned off. A more granular trade-off between utility, individual fairness, and group fairness for GRAPHGINI provided in Appendix M The results clearly show that significant improvements in fairness metrics can be achieved with minimal impact on accuracy. For example, by compromising 2% in accuracy, can achicve 90% increase in individual fairness and 30% increase in group fairness. We additionally evaluate the robustness of GRAPHGInI under variations in graph homophily heterophily, attribute noise levels, group imbalance ratios, and hidden embedding dimensions. A detailed ablation analysis covering these factors is provided in Appendices N O P and
deactivated (compare
4.8 Running Time
Table compares the running times of GRAPHGINI with GUIDE, both of which are similar. The vanilla model is faster since it does not account for the similarity matrix, which GRAPHGINI and GUIDE need to
Without Attention
With Attention
Individual Faimess
160
g
140
200
175
120
6
100
150
125
4.
80
100
60
75
2
40
50
20
25
0
GCN
GIN
JK
GCN GIN JK
GCN
GIN
JK
(a) Credit
(b) Income
(c) Pokec-n
Figure 2: Impact of attention on individual fairness.
15

---

Published in Transactions on Machine Learning Research (01/2026)
40
1.6
0.6
1.5
1.4
0.5
AUC
20
1.2
15
1.1
0.2
1.0
0.1
0.9
0.0
0.8
Vanilla
FairGNN
NIFTY
PFR
InFoRM
PostProcess
iFairNMTF
GNN GEL
TF- GN-
BeMAP
FairSIN
GUIDE
GraphGini
Vanilla
FairGNN
NIFTY
PFR
InFoRM
PostProcess
iFairNMTF
GNN GEL
TF-GNN
BeMAP
FairSIN
GUIDE
GraphGini
Vanilla
FairGNN
NIFTY
PFR
InFoRM
PostProcess
iFairNMTF
GNN GEL
TF-GNN
BeMAP
FairSIN
GUIDE
GraphGini
Credit
400
350
1.8
300
1.6
AUC
250
200
1.4
150
1.2
100
0.1
50
1.0
0.0
0.8
Vanilla
FairGNN
NIFTY
PFR
InFoRM
PostProcess
iFairNMTT
GNN GEI
TF- GNN
BeMAP
FairSIN
GraphGini
Vanilla
FairGNN
NIFTY
PFR
InFoRM
PostProcess
iFaiNMTTF
GNN GE!
TF-GNN
BeMAP
FairSIN
GUIDE
GraphGini
Vanilla
FairGNN
NIFTY
PFR
InFoRM
PostProcess
iFaINNMTE
GNN GEI
TF GNN
BeMAP
FairSIN
GUIDE
GraphGini
Income
1000
16
800
14
12
AUC
IF (1)
600
10
GD
0.3
0.2
200
0.1
0.0
Vanilla
FairGNN
NIFTY
PFR
InFoRM
PostProcess
|FainNMTT
GNN GEI
TF GNNN
BeMAP
FairSIN
GraphGini
Vanilla
FairGNN
NIFTY
PFR
InFoRM
PostProcess
FairNNTF
TF-GNN
BeMAP
FairSIN
GUIDE
GraphGini
Vanilla
FairGNN
NIFTY
PFR
InFoRM
PostProcess
|FairNMTF
TF-GNN
BeMAP
FairSIN
GUIDE
GraphGini
GNN
Pokec-n
Figure Fairnes Curve comparison of benchmarked algorithms across datasets using the GCN backbone architecture.
Table 9: Running time comparison for GCN on all three datasets, Time is reported in seconds for one iteration.
Datasets +
Credit
Income
Pokec-n
Model +
Vanila
0.014
0.046
0.082
GUIDE
0.041
0.051
0.094
GraphGini
0.042
0.050
0.096
incorporate to ensure individual and group fairness. Nonetheless, the running times remain small enough for practical workloads.
16

---

Published in Transactions on Machine Learning Research (01/2026)
5 Conclusion
In this work, we have shown how to combine the two key requirements of group fairness and individual fairness in a single GNN architecture GRAPHGINI. The GRAPHGINI achieves individual fairness by employing learnable attention scores that facilitate the aggregation of more information from similar nodes. Our major contribution is that we have used the well-accepted Gini coefficient to define fairness, overcoming the difficulty posed by its non-dfferentiaaiiitt This particular way of using the Gini coefficient may be of interest to future research, as it provides bridge between economic inequality measures and machine learning. Our approach to group fairness incorporates the concept of Nash Social Welfare. We also demonstrate that the gradient-normalization based technique (GradNorm) provides an effective way to balance utility, individual fairness, and group fairness objectives in graph learning, mitigating the need for exlensive manual tuning of objective weights. Empirical findings show GRAPHGINI significantly reduces individual unfairness while maintaining group disparity and utility performance after beating all statc-of-the-ar existing methods.
References
Chirag Agarwal, Himabindu Lakkaraju, and Marinka Zitnik. Towards unified framework for fair and stable graph representation learning. In Uncertainly in Arlificial Intelligence, pp. 2114 2124. PMLR, 2021.
Nimesh Agrawal, Anuj Kumar Sirohi, Sandeep Kumar, al. No prejudice! fair federated graph neural networks for personalized recommendation. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pp. 10775-10777 10783, 2024.
David Ahmedl-Arissizabbal Mohammad Ali Armin, Simon Denman, Clinton Fookes, and Lars Petersson. Graph-based deep learning for medical diagnosis and analysis: past, present and future. Sensors, 21(14): 4758, 2021.
Pranjal Awasthi, Abhimanyu Das, and Sreenivas Gollapudi. A convergence analysis of gradient descent graph neural networks. Advances in Newral Information Processing Systems, 01200385-20397 2021.
Avishek Bose and William Hamilton. Compositional fairness constraints for graph embeddings. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 715 724. PMLR, 2019.
Pritish Chakraborty, Sayan Ranu, Krishna Sri Ipsit Mantri, and Abir De. Learning and maximizing influence in social networks under capacity constraints. In Proceedings of the Sinteenth ACM International Conference 2023.
on Web Search and Dala Mining, pp.
Hadi Charkhgard, Kimia Keshanian, Rasul Esmacilbeigi, and Parisa Charkhgard. The magic of nash social welfare in optimization: Do not sum, just multiply! The ANZIAM Journal, 64(2):119-13)) 2022.
Zhao Chen, Vijay Badrinarayanan, Chen- Yu Lee, and Andrew Rabinovich. Gradnorm: Gradient normalization for adaptive loss balancing in deep multitask networks. In Internalional conference on machine learning, pp. 794 803. PMLR, 2018
Camilo Dagum. The generation and distribution of income, the lorenz curve and the gini ratio. Economie appliquée, 33(2):327-33) -37,7 1980.
Enyan Dai and Suhang Wang. Say no to the discrimination: Learning fair graph neural networks with limited sensitive attribute information. In Proceedings of the 14th ACM International Conference on Web Search and Data Mining, 2021.
Enyan Dai, Tianxiang Zhao, Huaisheng Zhu, Junjie Xu, Zhimeng Guo, Hui Liu, Jiliang Tang, and Suhang Wang. comprchensive survey on trustworthy graph neural networks: Privacy, robustness, fairness, and explainability. arXiv preprint orXiv:2204.080 085770, 2022.
Yushun Dong, Jian Kang, Hanghang Tong, and Jundong Li. Individual fairness for graph neural networks: A ranking based approach. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery 8 Data Mining, pp. 300-310, 330, 2021.
17

---

Published in Transactions on Machine Learning Research (01/2026)
Yushun Dong, Jing Ma, Song Wang, Chen Chen, and Jundong Li. Fairness in graph mining: A survey. IEEE Transactions on Knowledge and Dala Engineering, 2023.
Dheeru Dua and Casey Graff. Uci machine learning repository (2020). URL http://archive. ics. uct edu/ml, 2017.
Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel. Pairness through awareness. In Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, ITCS '12, pp. 214-226, New York, NY, USA, 2012. Association for Computing Machinery. ISBN 9781450311151.
Wenqi Fan, Yao Ma, Qing Li, Yuan He, Eric Zhao, Jiliang Tang, and Dawei Yin. Graph neural networks for social recommendation. In The world wide web conference, pp. 417 426, 2019.
Joseph L, Gastwirth. The estimation of the Lorenz curve and Gini index. The review of economics and
statistics, pp. 306-316, 1972.
Siamak Ghodsi, Seyed Amjad Seyedi, and Eirini Ntoutsi. Towards cabesson-fairness. harmony: Contrastive
regularization in individual fair graph clustering. CoRR, abs/ abs/a4/0 /t////222..0750 2024. doi: 10. 10.48550/ARXIT
2402.10756. URL https:///oi.nno wrw.oi...rgg//// 4/w5//////////////////////////// http//aaiiiv..... 10756
Lin Gong, Lu Lin, Weihao Song, and Hongning Wang. Jnet: Learning user representations via joint network embedding and topic embedding. In Proceedings of the 13th International Conference on Web Search and Data Mining, WSDM '20, pp. 205-213. Association for Computing Machinery, 2020.
Anjali Gupta, Prashant Kumar, Aniket Mishra, Abhishek Singh, Surender Kumar, Muthusamy Chelliah, Abhijnan Chakraborty, and Sayan Ranu. Persona identification in e-commerce with scarce labels and in-context graph learning. In Proceedings of the 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining V. 2, pp. 778-789, 2025.
Moritz Hardt, Eric Price, and Nati Srebro. Equality of opportunity in supervised learning. Advances in neural information processing systems, 29, 2016.
Yuntian He, Saket Gurukar, and Srinivasan Parthasarathy. Efficient fair graph representation learning using a multi-level framework. In Companion Proceedings of the ACM Web Conference 2023, pp. 298 301,000 2023.
Jian Kang, Jingrui He, Ross Macicjewski, and Hanghang Tong. Inform: Individual fairness graph mining. In Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery & data mining, 2020.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. CoRR, abs/1609.02907, 2016. URL http:///arsi..or//bbb///0000/ www./bs//////.././/////////////e 06907099077
O Deniz Kose and Yanning Shen. Fairgat: Fairness-aware graph attention networks. arXiv preprinl arX1v:2303.14511, 2023.
Oyku Deniz Kose and Yanning Shen. Fast&fair: Training acceleration and bias mitigation for gnns. Transac- tions Machine Learning Research, 2022.
Preethi Lahoti, Krishna P. Gummadi, and Gerhard Weikum. Operationalizing individual fairness with pairwise fair representations. Proc. VLDB Endow., 13(4):506-518 2020.
Xiao Lån, Jian Kang, Weilin Cong, and Hanghang Tong. Bemap: Balanced message passing for fair graph neural network. Xix preprint arXiv:2306. 04107, 2023.
Xiao Lin, Jian Kang, Weilin Cong, and Hanghang Tong. Bemap: Balanced message passing for fair graph neural network. In Solodad Villar and Benjamin Chamberlain (eds.), Proceedings of the Second Learning on Graphs Conference, volume 231 of Proceedings of Machine Learning Research, pp. 37:1 37:25, 2024.
Haochen Liu, Yiqi Wang, Wenqi Fan, Xiaorui Liu, Yaxin Li, Shaili Jain, Yunhao Liu, Anil Jain, and Jiliang Tang. Trustworthy ai: A computational perspective. ACM Transactions on Intelligent Systems and Technology, 14(1):1-50 2022.
18

---

Published in Transactions on Machine Learning Research (01/2026)
Pranay K Lohia, Karthikeyan Natesan Ramamurthy, Manish Bhide, Diptikalyan Saha, Kush R. Varshney, and Ruchir Puri. Bias miligation post-processing for individual and group fairness. In Teassp 2019-2019 ieee international conference on acoustics, speech and signal processing (icassp), pp. 2847 2851. IEEE, 2019.
Sahil Manchanda, Akash Mittal, Anuj Dhawan, Sourav Medya, Sayan Ranu, and Ambuj Singh. Geomb: Learning budget-constrained combinatorial algorithms over billion-sized graphs. Advances in Neural Information Processing Systems, 33:20000 20011,, 2020.
Ninareh Mehrabi, Fred Morstatter, Nripsuta Saxena, Kristina Lerman, and Aram Galstyan. A survey on bias and fairness in machine Iearning. ACM Computing Surveys, 54(6), 2021.
Sunil Nishad, Shubhangi Agarwal, Arnab Bhattacharya, and Sayan Ranu. Graphreach: Position-aware graph neural network using reachability estimations. arXiv preprint ar arvv:20008.0 09657, 2020.
Tahleen Rahman, Bartlomiej Surma, Michael Backes, and Yang Zhang. Fairwalk: Towards fair graph embedding. In Proceedings of the Twenty-Eighth International Joint Conference Artificial Intelligence, IJCAI-19. International Joint Conferences on Artificial Intelligence Organization, 2019.
Valentina Shumovskaia, Kirill Fedyanin, Tvan Sukharev, Dmitry Berestnev, and Maxim Panov. Linking bank clients using graph neural networks powered by rich transactional data: Extended abstract. In 2020 IEEE 7th International Conference on Dala Science and Advanced Analylics (DSAA), pp. 087-788, 2020.
Anuj Kumar Sirohi, Ajeet Kumar Yadav, and Pradipta Bandyopadhyay. Hydration-free energies for small molecules with physics- based descriptors: Graph neural network with cross-attention. Journal of Computa- tional Chemistry, (00277,,,, 2025.
Thitithep Sitthiyot and Kanyarat Holasut. A simple method for estimating the lorenz curve. Humanities and Social Sciences Communications, 8(1):1 9, 2021.
Weihao Song, Yushun Dong, Ninghao Liu, and Jundong Li. Guide: Group equality informed individual fairness in graph neural networks. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD '22, pp. 1625-1636 New York, NY, USA, 2022. Association for Computing Machinery. ISBN 9781450393850.
Zixing Song, Yuji Zhang, and Irwin King. Towards fair financial services for all: A temporal gnn approach for individual fairness on transaction networks. In Proceedings of the 32nd ACM International Conference on Information and Knowledge Monagement, pp. 2331-2341, 2023.
Till Speicher, Hoda Heidari, Nina Grgic-Hlaca Krishna P. Gummadi, Adish Singla, Adrian Weller, and Muhammad Bilal Zafar. A unified approach to quantifying algorithmic unfairness: Mcasuring individual and group unfairness via inequality indices. In SIGKDD, pp. 2239 2248, 2018. doi: 10.1145/3219819, 162202009999...2204666
Lubos Takac and Michal Zabovsky. Data analysis in public social networks. In International scientific conference and international workshop present day trends of innovations, 2012.
Ram Ganesh V, Ayush Singh, Aditi Rai, Harsh Pal, Deepanshu Bagotia, Akshay Sethi, Aakarsh Malhotra, and Sayan Ranu. TAG2M- A lask-agnostic knowledge distillation framework for distilling GNN to MLP. In Luiza Antonie, Jian Pei, Xiaohui Yu, Flavio Chierichetti, Hady W. Lauw, Yizhou Sun, and Srinivasan Parthasarathy (eds.), Proceedings of the 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining, V.2, KDD 2025, Toronto ON, Canada, August 3-7, 2025, pp. 2859 2870. ACM, 2025. doi: URL https://doi. org/10. /0/ 1111//111//1......1 3737145
10. 10.1145/337 1896.3737155.
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, Yoshua Bengio, et al. Graph attention networks. stat, 1050(20):10-485555 2017.
Zichong Wang, David Ulloa, Tongjia Yu, Raju Rangaswami, Roland Yap, and Wenbin Zhang. Individual fairness with group constraints in graph neural networks. E.ATT 2024, 2024.
19

---

Published in Transactions on Machine Learning Research (01/2026)
Oliver Wieder, Stefan Kohlbacher, Mélaine Kuenemann, Arthur Garon, Pierre Ducrot, Thomas Seidel, and Thierry Langer. A compact review of molecular property prediction with graph neural networks. Drug Discovery Today: Technologies, 37:1- 12, 2020.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks?
arXiv preprint
0080066 2018a.
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashii, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. In International conference on machine learning, pp. 5453 5462. PMLR, 2018b.
Kuan Yan, Dmytro Matsypura, and Junbin Gao. Big: A practical framework for balancing the conflict between group and individual fairness in graph neural networks. 2024 IEEE 23rd International Conference on Trust, Security and Privacy in Computing and Communications (TrustCom), pp. 2400-2400 2400- IEEE, 2024.
Cheng Yang, Jixi Liu, Yunhe Yan, and Chuan Shi. Fairsin: Achieving fairness in graph neural networks through sensitive information neutralization. Proceedings of the AAAI Conference on Artificial Intelligence, 38(8))924119222 2024.
I-Cheng Yeh and Che-hui Lien. The comparisons of data mining techniques for the predictive accuracy of probability of default of credit card clients. Expert systems with applications, 36(2):2473-244) 2009.
20

---

Published in Transactions on Machine Learning Research (01/2026)
A
Notations
To ensure clarity and consistency in the mathematical formulations used throughout this work, Table J summarizes the key notations employed.
Table J: Notations.
Notation
Description
G
input graph
V
sot of nodes in graph
set of edges in graph
number of nodes in graph features dimension
V
th group in graph adjacency matrix graph G node feature matrix of graph G output learning matrix of graph G with number of features pairwise similarity matrix of graph G Laplacian similarity malrix Gini of node set V
A E 10.1)am nxx
X Raxd
Z Raxe
R
LE Raxn
Gini(V)
B Lorenz curve
It is the plot of the proportion of the total income of the population (on the y-axis) cumulatively earned by the bottom x (on the x-axis) of the population. The line at 45 degrees thus represents perfect equality of incomes. The further away the Lorenz curve is from the line of perfect equality, the greater the incquality. The Gini coefficient is the area ratio between the line of equality and the Lorenz curve over the total area under the line of quality.
100
Gini Coefficient A/(A+B)
% of Cumulative Income (Y-Axis)
80
Line of Equality
60
40
Lorenz Curve
20
B
20
40
60
80
100
(X-Axis)
%
Population (from Poorest to Richest)
Figure D: Lorenz curve
21

---

Published in Transactions on Machine Learning Research (01/2026)
C Training Procedure of GraphGini
Algorithm 1 outlines the training process of the proposed GRAPHGINI model. Given an input graph comprising nodes, edges, and node features, along with & pairwise similarity matrix, the model aims to learn node embeddings that are both accurate and fair. The optimization involves three loss components-utiinee individual fairness, and group fairness combined using adaptive weights. The training proceeds iteratively through iitention-basee message passing over K layers, with GradNorm used to dynamically adjust the influence of each loss term. The model parameters, allention coefficients, and loss weights are updated until convergence.
Algorithm GraphGini Input: G G= (V,,, X) Output: Pair Embeddings Z
< Initialize GNN embeddings of V using utility loss L Initialize B1 1, f2 - A3 + 1 0
Compute Li, L2, and L Li + 32C2 BgLa
while not converged in epoch t do
5: for layer f = to K do
6: for each node E V do
h htt1 (Ejess an Wh₂) 8: end for
// message passing
end for
10: C Bi Li + 32L2 + 3zL3
11: Backpropagate using GradNorm loss corresponding to L (Eq. 14
12: Update W, oz.j 31, 32, $3, and Z
13:
1+1+1
14: end while
15: Return Z
D Baselines
Guide Song et al. 2022): This method is the state-of-the-art, which minimizes the average Lipschitz constant for individual fairness and proposes a new group disparity measure based on the ratios of individual fairness among the groups.
FairGNN Dai & Wang 2021 This model leverages adversarial learning to ensure that GNNs achieve fair node classifications. adhering to group fairness criteria.
NIFTY Agarwal al. (2021 :: Addressing counterfactual fairness along with stability problem, NIFTY perturbs attributes and employs Lipschitz constants normalize layer weights. Training incorporates contrastive learning techniques, and we adopt this model directly for various GNN backbone architectures.
PFR Lahoti al. (2020): PFR learns fair node embeddings a pre- pro-processing step, ensuring individual fairness in downstream tasks. The acquired embeddings serve as inputs for GNN backbones.
InFoRM Kang et al. (2020): This model formulates an individual fairness loss within a graph framework based on the Lipschitz condition. We integrate the proposed individual fairness loss into the training process of GNN backbones.
PostProces<Lohia et al. (2019): Lohia et al. 2019 proposes a post-processing based method to cuhance individual and group fairness. The method employs a bias detector assess disparity in outcomes, and when such biases are detected, it changes the model output different outcome. This algorithm is topology-ognostic.
22

---

Published in Transactions on Machine Learning Research (01/2026)
GEI Speicher et al. (2018): GEI considers diversity of outcomes within group, determined by sensitive attributes, measure of inequality. This implies the assumption that outcomes are independent of non-sensitive attributes within the group. In contrast, Gini allows weighting outcomes proportional to an input similarity mcasure (Eq. 2 leading to a more muanced calculation of inequality based on similarity non-sensitive altributes. To quantify this effect, we use GEI as the regularizer instead of Gini.
iFairNMTF Ghodsi et al. (2024): iFarNMTF is fair clustering model that uses individual Fairness Nonnegative Matrix Tri-Factorization technique with contrastive fairness regularization lo get balanced and cohesive clusters. We adapt iFairNMTF our setting by plugging their fairness regularizer term with our GNN loss.
TF-GNN Song et al. (2023): TF-GNN presents an individual fair Graph Neural Networks (GNNs) tailored for the analysis of temporal financial transaction network data. In our specific context, we integrate TF-GNN into our framework by incorporating their fairness regularizer term into our GNN loss function.
BeMap Lin et al. (2024): BeMap is a group fair Graph Neural Networks (GNNs) method based on fair message passing algorithm on the basis of 1-hop neighbours from different sensitive groups. We used this method our setting of different groups.
FairSIN Yang et al. (2024): FairSIN is also a group fairness enforcing framework for GNNs which proposes a neutralization-conten procedure, and using supplementary chirnoss-fcciitatiin Features (F3). These features are integrated into node representations prior to message passing. We also adopt this method to compare our method
E Tightness of upper bound in Eq. 8.
Proof of Proposition 2 Consider any such that each entry of is identical. In this case both Σ S(r,j] 2j|11 and Σ S j][ z 22 are 0
Let z = (Zi, ze) E R be a c-dimensional vector. We consider the relationship between its El and &
norms. When z has a single non-zero entry (e.g., (1,0...., 0)), the bound loose: ||z||| = ||z||| = 1, while
Vclz 2212222200 = Vc. When all entries of z are equal (e.g., (I,),...,1),, the bound is tight: ||z|| = c, ||z| l2 = ve, and v z
Since minimizing Gini(V) minimizes the fo-nom,, we have: min, (Gini(V)) = mina ||z|/2 While this does not directly minimize ||z//2, we can establish: min, |z||2 = min, /el|z||a 2 min, ||z|] This incquality shows that minimizing ||a|| provides an upper bound on the minimum of ||2||2- As ||z||a + during optimization, both ||z]| and /dlzil2 approach O.
Lemma 1. The upper bound of the Gini coefficient, defined as
Gini(V) = Tr
is a convex function in Z.
Proof. To prove convexity, we show that the Hessian of Gini(V) is positive semidefinite. The function is given by:
12 n
( (TZ'
S(ijill - 2,113
1=1 j=1
This is a quadratic form defined by the Laplacian L D S, where D the diagonal matrix.
Gradient Computation: Taking the gradient with respect uo Z:
v (Z) 2LZ
23

---

Published in Transactions on Machine Learning Research (01/2026)
Hessian Analysis: The Hessian of f(Z) is:
= 2L & ld.
where & denotes the Kronecker product, and La is the d x d identity matrix.
Positive Semidefiniteness of Hessian: The Laplacian L is known to be positive semidefinite, meaning for any vector V E R",
L 2
Since the Kronecker product of a positive semidefinite matrix with Ia preserves positive semidefinileness, we conclude that:
H = 2L X La - 0.
This proves that (Z) is convex function in Z.
E.1
The need for differentiability
For deep learning methods, if the loss function differentiable, then its gradient can be obtained using inbuilt packages such PyTorch to update the model's weights. In practice, these packages handle the non- differentiability of activation functions such ReLU by using hand-coded values at non-differentiable points. However, such values for generic loss functions are not available priori; therefore, differentiability of the loss function is essential. To elaborate, consider the Gini index. Ifx = (x1,..., ..)) and f'(x) = Ei= ΣØ= [. bور for a fixed j E [n]], let us define
mx(x) = Ki i < x,
In the case where n, # I2 for all i * j, clearly
0x(x) n 1
0z,
Let. & be the index such that Fa < Iy and there is no other coordinate value between them. Suppose we decrease I, until it reaches æg, then we reach a point of discontinuity, which we will call y. We note that the left partial derivative with respect to 2y is n 3- 3x)x-2m(xx), which is 2 less than its right partial derivative. Unlike the case of ReLU, there is straightforward way to decide which of these two values should be assumed at the point of non-differentiabiliy.. Furthermore, unlike ReLU, these two values cannot. be determined priori since they depend
F Pareto Optimality Proof
Proof of Proposition 3 Let the Gini upper bounds minimizing Eq. 9 be Gini(Vy) = eg and Gini(Vi) = eh- The solution is Pareto optimal if we cannot reduce EN without increasing Eg and vice-versa. We establish Pareto optimality through proof by contradiction. Suppose that there cxists assignment of node embeddings for which we get. (V,) = ey; Gini(V), (W)) = 66 and e > 6g. Since Eq. minimized at Eg and ej this means
that - ( - 1) c - 1) < [ c
- ( ce -1). which is contradiction.
G Convergence and Time Complexity
Convergence. As our framework considers only standard GNNs, the convergence analysis of gradient descent GNNs has been conducted in Awasthi et al. (2021) under the assumption of the smoothness of bounded loss function. Our overall loss is smooth, as the fairness regularizers for individual and group fairness are designed to ensure differentiabilityy Additionally, each term is bounded (loss L₁ CE loss, L2 S tr(x' and L3 < g [finite value of group disparity]); hence, the overall loss is smooth and bounded. Therefore, the analysis in Awasthi et al. 2021 directly applies to our framework.
Runtime. Table 9 presents the runtime for GRAPHGINI and the basclines. Empirical analysis shows that the inference time (i.e,, the time taken for forward pass) is comparable between GRAPHGINI, GradNorm,
24

---

Published in Transactions on Machine Learning Research (01/2026)
and GUIDE across all three datasets tested. Nonetheless, it's important to note that the absolute inference times for all methods are very small, suggesting that the computational overhead should not be significant. concern for the practical deployment of these fair GNN approaches.
Table K: Baseline hyper-parameters. indicates the parameter not used to train the model.
Datasets >
Credit
Income|
Pokec-n
Model
B2
B3
B2
83
B2
82
FairGNN
4
1000
4
10
100
NIFTY
PFR
PostProcess
iMTF
1e-7
le-7
1e-7
GNN GEI
1
1
TF-GNN
le-6
le-7
le-7
InFoRM
5c-6
lc-7
1e-7
GUIDE
5e-6
1
le-7
0.25
2.5e-7
0.05
Implementation details for Reproducibility
Each experiment is conducted five times, and the reported results consist of averages accompanied by standard deviations. Our experiments are performed on machine with Intel(R) Core(TM) CPU @ 2.30GHz with 16GB RAM, RTX A4000 GPU having 16GB memory on Microsoft. Windows 11 HSL.
For all three datasets, we employ a random node shuffling approach and designate 25% the labeled nodes for validation and an additional 25% for testing purposes. The training set sizes are set 6,000 labeled nodes (25%) for the Credit dataset, 3,000 labeled nodes (20%) for the Income dataset, and 4,398 labeled nodes (6%) for Pokec-n. For the Pokec-n dataset, friendship linkages serve edges, while for the remaining datasets, edges are not predefined, necossitating their construction based on feature similarity. More preciscly, we establish a connection for any given pair of nodes if the Euclidean distances between their features surpass a predetermined threshold. The fine-tuned hyper-parameters used to train baselines are given in Table K 31 is for all baselines. For GRAPHGINI, the backbone GNN architecture parameters are the same for all datasets, i.e. one hidden layer with hidden dimensions 16.
Number of clusters in datasets
To evaluate the Gini, we divide the test dataset into number of clusters based on the elbow graph (Figure. D Specifically, we employ K-means clustering to group samples based on their features, aiming to capture structural or distributional disparities that may exist in the data. The number of clusters for each dataset is determined using the elbow method, which evaluates the within-cluster sum of squares (WCSS) as a function of cluster count. As shown in Figure E the clbow point-where the marginal gain in reducing WCSS begins to diminish indicates the optimal number of clusters for the Credit, Income, and Pokec-n datasets.
Table L presents detailed comparison of the proposed GRAPHGINI model against baseline methods across three benchmark datascts. The results include performance metrics such as AUC and F1-score, alongside lairness indicators individual fairness (IF), group disparity (GD), and Gini coefficients computed for multiple subpopulations (clusters). The term Vanilla refers to a baseline model trained without any fairness enhancement. Across all architectures (GCN, GIN, JK), GRAPHGINI consistently achieves comparable or superior predictive performance while significantly reducing fairness violations, as reflected in both the IF and Gini values.
25

---

Published in Transactions on Machine Learning Research (01/2026)
Credit Dataset
Income Dataset
Pokec-n Dataset
3 1e4
1e4
le5
Distortion
Distortion
1.0
Distortion
2
5
4.
0.5
3
10 15 Number of Clusters
5
10
15
5
10
15
Number of Clusters
Number of Clusters
Figure E: The Elbow plots show the optimal number of clusters in each dataset K-means clustering.
J Impact of Gradient Normalization
In Fig. plot. the trajectory of the weights against training epochs. In the credit dataset, initially, utility loss is given higher weightage than group fairness loss, but after certain iterations, group fairness loss weightage overcomes utility loss weightage. Mcanwhile, the utility loss is always given the higher weightage in the other two datasets. These behaviors indicate the sensitivily of 8i. With the increase in the nunber of sterations/epocha initially, 3,s' are changing at different rates, but after a certain iteration, the values of 3,s" get stabilized, indicating similar training rates across all three losses.
Credit
Income
Pokec-n
Utility Loss(C;): B1
Utility Loss(C,): B1
Utility Loss(C;):
3
IF Loss(C2): B2
IF Loss(C2): B2
4
IF Loss(C2): B2
GD Loss(Cs): Ba
GD Loss(Cs): 83
GD Loss(Cy): B3
Weights
Weights
2
Weights
3
1
1
1
1000
2000
3000
4000
5000
6000
1000
2000
3000
4000
500
1000
1500
2000
Iterations
Iterations
Iterations
Credit
(b) Income
(c) Pokec-n
Figure F: Adaptive loss weights learned via GradNorm during training for the GRAPHGINI model with GCN backbone across three datasets.
K Multidimensional Gini and Comparison of its Differentiable Upper Bound with Smooth Pooling Operators
Let A(Z) E R.M. collect pairwise embedding disparities Aij == || - =zy1 for M (7) unordered pairs. Define
the (unnormalized) Gini fairness functional
Gini(Z) = M
Σ Aij
(15)
(1.)
i.c., the mean absolute pairwise disparity. By contrast, conventional pooling surrogates optimize
1B 2
(16)
26

---

Published in Transactions on Machine Learning Research (01/2026)
Table L: Gini coefficient for different clusters on Credit, Income, and Pokec-n datasets. The model indicates
the algorithm, and Vanilla represents that fairness mechanism has been used. Bost performances are in bold. Individual (un)fairness numbers reported in thousands.
Model Vanilla Guide
GraphGini
Vanilla
Guide
GraphGini
Vanilla
Guide
GraphGini
GCN
GIN
JK
Credit
AUC(1)
0.68
0.67
0.69
0.71
0.69
0.69
0.69
0.68
0.68
F1-score(1)
0.71
0.72
0.73
0.72
0.73
0.74
0.70
0.71
0.73
IF())
17.38
1.09
1.01
27.47
1.97
1.78
15.55
1.48
1.42
GD(L)
1.35
1.00
1.00
1.87
1.00
1.00
1.24
1.00
1.00
Gini C1 1 (L)
0.08
0.04
0.04
0.11
0.08
0.05
0.11
0.04
0.03
Gini C1 2 (L)
0.10
0.08
0.08
0.13
0.04
0.04
0.14
0.04
0.05
Gini C1 3 (4)
0.27
0.26
0.26
0.29
0.06
0.06
0.25
0.07
0.08
Gini (L)
0.20
0.19
0.19
0.17
0.13
0.10
0.19
0.08
Gini C1 5 (4)
0.09
0.07
0.07
0.11
0.04
0.05
0.13
0.04
0.04
Gini (L)
0.08
0.05
0.05
0.11
0.05
0.06
0.13
0.03
0.03
Income
AUC(1)
0.77
0.74
0.78
0.81
0.80
0.80
0.80
0.74
0.75
F1-score(1)
0.78
0.79
0.78
0.80
0.81
0.81
0.79
0.80
0.80
IF())
111.03
9.75
6.85
421.81
23.46
22.31
439.38
27.14
24.39
GD(L)
1.23
1.00
1.00
1.16
1.00
1.00
1.29
1.00
1.00
Gini C1 1 (1)
0.34
0.19
0.17
0.43
0.16
0.17
0.40
0.11
0.11
Gini CI 2 (L)
0.28
0.18
0.18
0.38
0.02
0.17
0.34
0.10
0.15
Gini C1 3 (1)
0.32
0.15
0.12
0.56
0.15
0.15
0.47
0.12
0.16
Gini (L)
0.21
0.08
0.21
0.15
0.15
0.24
0.12
0.11
Gini C1 5 (1)
0.37
0.13
0.13
0.60
0.25
0.24
0.49
0.39
0.32
Gini (L)
0.22
0.12
0.13
0.24
0.16
0.16
0.25
0.16
0.13
Pokec-n nn
AUC(1)
0.77
0.74
0.74
0.76
0.74
0.74
0.79
0.78
0.78
Fl-score(1)
0.75
0.77
0.79
0.76
0.77
0.79
0.76
0.78
0.78
IF))
859.67
16.60
26.16
1589.50
96.90
33.70
1450.98
59.42
44.51
GD(L)
2.55
1.00
1.00
3.50
1.00
1.00
3.07
1.00
1.00
Gini Cl 1
0.27
0.10
0.10
0.22
0.11
0.10
0.38
0.08
0.07
Gini Cl 2
0.17
0.09
0.08
0.13
0.13
0.14
0.34
0.09
0.08
Gini Cl 3
0.06
0.03
0.02
0.09
0.06
0.06
0.07
0.05
0.04
Gini
0.27
0.11
0.13
0.15
0.10
0.09
0.35
0.07
0.06
Gini CI 5
0.16
0.07
0.06
0.11
0.11
0.11
0.09
0.07
0.07
Gini
0.27
0.10
0.11
0.21
0.10
0.09
0.08
0.05
0.05
Gini Cl 7
0.28
0.12
0.10
0.24
0.10
0.10
0.33
0.10
0.11
Gini
0.27
0.16
0.12
0.29
0.12
0.09
0.33
0.10
for some However, for any 0, using Markov's inequality on the nonnegative random variable Aij sampled uniformly from pairs yields Pr[Ag 2 E[Ay]/E = G(Z)/s. Hence, we have,
Gini 2)
Σ T 20 S 1
(17)
M
Hence, minimizing Gini(Z) directly controls the fraction unfair pairs any scale e. Pooling substitutes (max, smooth-max. top-k, p-norm) do not provide such calibrated distributional guarantees, they may keep the maximum small while still allowing a large fraction of moderate violations. Further, let L be the graph Laplacian built from the same pairwise weights used in fairness evaluation. Then
GinilZ) S C Tr L.)
(18)
27

---

Published in Transactions on Machine Learning Research (01/2026)
Table M: Performance comparison of benchmarked algorithms across datasets using the JK backbone architecture. "Vanilla" indicates debiasing. Arrows: t higher is better, lower is better. Bost
performance per column is in bold. Individual fairness (IF) is reported in thousands.
Model
AUC (1) IF (L)
GD ())
IF-Gini (1)
GD-Gini (1)
Credit
Vanilla
0.64+0.10
31.50++3.25
1.35++0.05
0.28 + 0.03
1.71 + 0.01
FairGNN
0.66
2.65+1.85
1.5440.28
0.19 + 0.02
1.82 + 0.02
NIFTY
0.69-10.02
30.12442.25
1.26:40.02
0.27 + 0.01 0.01
1.73 + 0.00
PER
0.67+0.02
36.24+19.10
1.00:0.02
1.65 0.01
InFoRM
0.67=00.04
5.70+5.2
1.46#0.14
0.16
1.44 = 0.00
PostProcess
0.70
43.57+7.80
1.4400.01
0.28:000
1.69 + 0.01
FairNMTF
0.71#0.01
107.72+9.04
1.54+0.23
0.28 0.02
1.66 0.02
GNN GEI
0.68
43.16 + 4.15
1.4100.01
0.26 122600 0.00
1.53 = 0.02
TF-GNN
0.70#0.00
13.20+00.03
1.43+0001
0.20
1.49 + 0.02
BeMAP
0.600
11.36++2.07
1.45+H0.0
0
1.63 + 0.01
FairSIN
0.68
18.3948880
1.56:0.00
0.21
1.56 = 0.02
GUIDE
0.68
2.35
1.00=#000
0.12 0.02
1.30 0.01
GRAPHGINI
0.68
1.8810.02
1.00
0.10 0.01
1.08 0.01
Income
Vanilla
0.8010.01
190.70+165.33
1.18::015
0.38 + 0.02
1.80 + 0.00
FairGNN
0.77+0001
230.12+:40.85
1.32+0..14
0.35 = 0.01
0.01
1.81 = 0.01
NIFTY
0.73+0.01
47.40+12.200
1.40++0.05
0.20 0.02
1.83 + 0.01
PFR
0.73
130.40:150..5
1.13:0.21
0.36 0.02
1.72 = 0.01
InFoRM
0.79+10.00
195.61+11.78
1.36:10.14
0.33 0.01
1.81 + 0.02
PostProcess
0.7910.00
520.23+:20
1.27
0.40 = 0.02
1.54 = 0.01
FairNMTF
0.78+0001
604.80+-24.32
1.43
0.44 0.01
1.76 0.03
GNN GEI
0.79
197.29419.34
1.37+0.12
0.37 0.02
1.84 + 0.02
TF-GNN
0.78+0.01
205.08+
1.48+
0.34 0.01
1.90 + 0.01
BeMAP
0.75+10.0
297.25+441.5
1.39
0.35 - 0.01
1.83 = 0.02
FairSIN
0.75+0.00
282.45+49.55
1.46+0000
0.33 1 0.01
1.91 - 0.01
GUIDE
0.74+0.01
42.50
1.00
0.22 + 0.02
1.13 + 0.00
GRAPHGINI
0.75
29.47 4.01
1.00+0000
0.18 + 0.01
1.01 = 0.01
Pokec-n
Vanilla
0.7910.01
1639.30+:9574
8.48+0.51
0.42 0.01
1.77 = 0.01
FairGNN
0.70+0.00
807.79++81.22
11.68+22.89
0.35 0.01
1.79 + 0.02
NIFTY
0.7310001
477.31+165.68
8.20+1133
0.31 : 0.01
1.76 = 0.01
PFR
0.68+00.00
729.77474.62
15.66:5.47
0.35 - 0.02
1.80 0.03
InFoRM
0.78+0.01
315.27+-25.21
6.80+0054
0.30 + 0.01
1.74 + 0.01
PostProcess
0.78+0.00
8721.99433
10.22+00.33
0.42 + 0.03
1.80 + 0.01
iairNMTF
0.77 1602.52-192.73
9.37+10.10
0.41 + 0.01
1.79 + 0.03
GNN GEI
0.78+0.00
7788.65+56.88
9.21
0.43 = 0.01
1.80 = 0.01
TF-GNN
0.76++0.00
418.31454.26
10.20+1.45
0.30 0.02
1.81 0.02
BeMAP
0.76+10.00
126.95
5.56+00.45
0.30 0.01
1.53 - 0.01
FairSIN
0.76++0.00
282.45-1449.55
1.46++0.0
0.26 + 0.01
1.27 0.01
GUIDE
0.75+00.0
83.09+18.70
1.13+0.02
0.25 0.01
1.25 - 0.01
GRAPHGINI
0.78+0.10
43.87=2.36
1.00 0.00
0.23 - 0.01
1.18 - 0.01
for an explicit constant > 0 depending only on the weight normalization and feature bounds. By Jensen's Cauchy-Schwarz
inequality and the Cauchy Schwarz bound ||u|| < Vluul relate the mean absolute disparity to the mean
28

---

Published in Transactions on Machine Learning Research (01/2026)
squared disparity; the latter equals Laplacian quadratic form. upper bound in Tr(Z" I.Z).
Therefore Gini(Z) admits convex, smooth
To further validate our approach empirically, we compare GRAPHGINI with smooth pooling-operator surrogates. Specifically, we employ two commonly used surrogates, softmax and top-k as andividual-fainee regularizers in conjunction with the proposed Gini-based individual fairness. We conduct an ablation study on all three datasets using identical train validation test splits and GCN backbone. The results are presented in These results clearly indicate that modifying pooling surrogates alone is insufficient to achieve fair graph embeddings. It is also important to emphasize that group fairness plays crucial role in graph learning alongside individual fairness, as demonstrated in Table 6 of the manuscript.
Tables N O and [P]
Table N:
Performance comparison of pooling surrogates and GRAPHGINI on Credit dataset. Arrows: 1 higher better, + lower better.
Method
AUC (t)
IF (4)
GD (4)
IF-Gini (4)
GD-Gini (4)
Softmax
0.68#0.01
5.12+0.01
1.20=0.02
0.24+0.01
1.11#0.03
Top-k (5%)
0.68++0.01
19.26++0.01
1.344-0.01
0.25+
1.11+-0.01
GRAPHGINI
0.68:10.01
0.2210.01
1.01
0.1210.00
1.09:0.01
Table O:
Performance comparison of pooling surrogates and GRAPHGINI on Income dataset. Arrows: f
higher better, & lower better.
Method
AUC (f)
IF (1)
GD (L)
IF-Gini (1)
GD-Gini ())
Softmax
0.73+10.1
290.111..0
1.33:0001
0.21
1.19:00011
Top-k (5%)
0.73+0.01
213.448.04
1.25#0.01
0.22+1.01
1.17#0.01
GRAPHGINT
0.73++0.01
21.12+5.20
1.00
0.17+0000
1.03++0.01
Table P:
Performance comparison of pooling surrogates and GRAPHGINI on Pokec-n dataset.
Arrows: f
higher better, | lower better.
Method
AUC (1)
IF (J)
GD (L)
IF-Gini (1)
GD-Gini (L)
Softmax
0.74+0.01
345.8118.9
3.07+0.02
0.31
1.15#0.01
Top-k(5%)
0.74
276.57+11.0
5.09
0.29
1.18:00.01
GRAPHGINI
0.74+0.00
31.10#5.19
1.00
0.21
1.14::.01
L Comparison with Ranking- Based Approach
We also compared against REDRESS Dong et al. (2021) which ranking-based approach. As shown the Table Q GRAPHGINI consistently outperforms REDRESS by significant margin, demonstrating the effectiveness of our framework even beyond the Lipschitz setting.
M Hyperparameter Sensitivity Analysis
In the GRAPHGINI framework, the two key parameters, 82 and 83, must be fine-tuned to achieve optimal performance while balancing both fairness objectives. We evaluate their impact the performance of GRAPHGInI by varying these parameters simultancously and independently. Figure G illustrates the effect of GRAPHGINI regularizers on accuracy (AUC), individual fairness (IF), and group fairness (GD) on the Credit dataset using the GCN backbone. In Figures (a-c), the x-axis represents B2, the y-axis represents 8s, and the z-axis shows AUC, IF, and GD Figures (a), (b), and (c), respectively. The trends indicate that increasing both 82 and 3g results in decrease in AUC, while individual and group fairness improves. In all cases, Si is fixed at 1, and lower IF and GD values correspond to better individual and group fairness, respectively.
29

---

Published in Transactions on Machine Learning Research (01/2026)
Table Q: Performance comparison of REDRESS and GRAPHGINI across datasets using the GCN backbone
architecture. Arrows: f higher better, lower is better. Individual fairness (TF) is reported in
thousands.
Model
AUC (1)
IF (1)
GD (4)
IF-Gini (4) GD-Gini (4)
Credit
REDRESS
0.68+0.01
2.33:+0.01
1.52=#.01
0.17=0.01 0.12+0.01
1.77=0.01
GRAPHGINI
0.68
0.22+0.06
1.00++.000
1.10+0.01
Income
REDRESS
0.73+0.03
187.10=10.0
1.39:10.02
0.25+0.01
1.56.1..2
GRAPHGINI
0.73+0.09
21.12::.22
1.00=0.00
0.17#0.01
1.02:10.01
Pokec-n
REDRESS
0.74+0.00
350.22:19100
7.10:10.15
0.39
1.85=10022
GRAPHGINI
0.74+0.00
31.10=5.22
1.00=0.00
0.21#0.01
1.14=0.01
Figures (d-i) present when one fairness regularizer is varied while the other is fixed at 0. In Figures (d-f), As is set to O, showing that increasing 32 decreases accuracy but improves individual fairness. However, group fairness may fluctuate since optimization focuses solely on individual fairness. Tn Figures (g-i), B2 is set to O, demonstrating that increasing 33 reduces accuracy but enhances group fairness, with potential variations in individual fairness due to the focus on group fairness optimization.
N Sensitivity to Knmophilyy/Htterophhin
We evaluate the robustness of GRAPHGINI under varying levels of structural homophily on all three datasets: Credit, Income, and Pokec-n. The degree of homophily is controlled through degroe-preserving edge rewiring. For each value of E {0, 0.2, 0.4, 0.6, 0.8), fraction p| of edges is randomly selected, and one endpoint of each edge is replaced with a node having the same class label as the source. Increasing progressively raises the proportion of same-label connections, thereby producing graphs with higher homophily while maintaining the original degroe distribution. For every generated graph, we compute both topological and attribute-basod similarity matrices as defined in Sec. 2. We performed all experiments using the GCN backbone (the same trends hold for GIN and JK architectures) and report the results in Tables R and T It. evident that GRAPHGINI consistently maintains fairness and accuracy under diverse structural regimes. This validates GRAPHGINI 's robustness under varying graph structures.
Table R: Performance of GRAPHGINI compared GUIDE with varying homophily levels (p) on the Credit dataset using the GCN backbone. Arrows: t higher is better, J. lower is better.
Method
AUC (t)
IF (4)
GD (4)
IF-Gini (4)
GD-Gini (4)
GUIDE
0.68
1.98
1.08
0.16
1.41
0.0
GRAPHGINI
0.68
0.42
1.08
0.14
1.12
GUIDE
0.68
1.96
1.08
0.16
1.40
0.2
GRAPHGINI
0.68
0.31
1.06
0.13
1.11
GUIDE 0.68
1.94
1.05
0.14
1.33
0.4
GRAPUGINI
0.68
0.25
1.03
0.12
1.10
GUIDE
0.69
1.94
1.05
0.14
1.23
0.6
GRAPHGINI
0.69
0.22
1.01
0.12
1.09
GUIDE
0.69
1.94
1.01
0.14
1.20
0.8
GRAPHGINI
0.69
0.21
1.00
0.11
1.09
30

---

Published in Transactions on Machine Learning Research (01/2026)
0.7
2.2
2.0
0.6
18
16
0.5
18-9 18-8
10.8
10.9
1.2
189
le-7
le.3
le
le40
lef1
18+2
log
te
leg
1e4
le3
le+0
le+2
le:3
1e4
1e-3
16-2
leto
1et1
let2
16-4
(a) AUC
(b) IF
(c) GD
B==0
*
0==0
0.70
P==0
0.6
AUC
0.60
0.5
16.9
16.8
16.7
16.6
26.5
1c.9
1c-8
1e-7
1e-6
le.5
B2
B2
B2
(d) AUC (3z=0)
(e) IF (33=0)
(f) GD (3z=0)
0.7
h==
B==
2.2
8==0
2.0
0.6
10.0
AUC
7.5
5.0
1.4
2.5
1.2
0.0
1.0
1e-4
1e:3
1e-2
1e-1
1e+0
1e+1
1e+0
16/3
1e-2
1e-1
1e+0
le+1
B3
B3
B3
(g) AUC (32=0)
(h) TF (32=0)
(i) GD (B2=0)
Figure G: Porformance results GRAPHGINI for Crodit datasct on GCN-GNN with varying hyporparametors 32 for the overall individual unfairness (IF) objective and 33 for the group disparity (GD) objective. IF values are in thousands. Figures (a-c) are 3-D representations where the z-axis corresponds to AUC, individual fairness (IF), and group fairness (GD) in figures (a), (b), and (c), respectively. Figures (d-i) show 2-D reprosentations by varying fairness regularizer and fixing the other fairness regularizer to 0. Here, 31 is set to in all figures, and lower IF and GD correspond to better individual and group fairness, respectively.
O Sensitivity to Attribute Noise
To evaluate the resilience of GRAPHGINI to perturbations in node features, we perform a controlled attribute- noise sensitivity analysis. To investigate how fairness and performance respond to progressive corruption of input features, while keeping the graph topology fixed. We added Gaussian noise to original feature matrix X gaxd, follws:
x= X x ~~,0000)))
31

---

Published in Transactions on Machine Learning Research (01/2026)
Table S: Performance of GRAPHGINI compared to GUIDE with varying homophily levels (p) on the Income
datasct using the GCN backbone. Arrows: 1 higher is better, 4 lower better.
p
Method
AUC (1)
IF (4)
GD (4)
IF-Gini (4)
GD-Gini (4)
GUIDE
0.72
33.3
1.12
0.26
1.12
0.0
GRAPHGINI
0.72
25.4
1.10
0.18
1.10
GUIDE
0.73
33.1
1.12
0.26
1.11
0.2
GRAPHGINT
0.73
22.3
1.05
0.17
1.09
GUIDE
0.74
32.2
1.08
0.26
1.11
0.4
GRAPHGINT
0.74
20.8
1.03
0.16
1.06
GUIDE
0.74
32.7
1.02
0.25
1.10
0.6
GRAPHGINI
0.74
19.7
1.02
0.15
1.05
GUIDE
0.75
32.7
1.03
0.20
1.10
0.8
GRAPHGINI
0.75
19.4
1.00
0.15
1.05
Table T: Performance of GRAPHGINI compared to GUIDE with varying homophily levels (p) the Pokec-n
dataset using the GCN backbone. Arrows: f higher is better, J. lower is better.
Method
AUC (t)
IF (4)
GD (4)
TF-Gini (4)
GD-Gini (4)
GUIDE
0.72
85.2
1.20
0.27
1.19
0.0
GRAPHGINI
0.72
35.1
1.18
0.23
1.15
GUIDE
0.73
85.2
1.20
0.26
1.19
0.2
GRAPHGINI
0.74
33.5
1.13
0.22
1.14
GUIDE
0.74
76.4
1.19
0.25
1.19
0.4
GRAPHGINI
0.74
29.9
1.09
0.21
1.13
GUIDE
0.74
75.2
1.19
0.25
1.19
0.6
GRAPHGINI
0.74
28.2
1.06
0.21
1.12
GUIDE
0.75
75.2
1.19
0.25
1.19
0.8
GRAPHGINI
0.75
28.1
1.04
0.20
1.11
where a controls the noise magnitude. We vary E {0.0, 0.200.0..02,033300.. to increase the noise intensity of the feat ures. This approach preserves utructural information in the adjacency matrix A, ensuring that any observed variation arises solely from feature corruption. It is evident from Tables U V and [ that across all datasets, the performance of GRAPHGINI remains stable for moderate noise levels (a S 0.2), while the deterioration in fairness metrics under stronger noise.
P Sensitivity to Group Imbalance
Handling group imbalance is critical, real-world graph data often exhibits significant disparities in group representation. In our work, we have carefully selected datasets and corresponding train test splits to ensure that our method can effectively handle such imbalanced scenarios. Specifically, two of our datasets Credit and Income are highly imbalanced, whereas the Pokec-n dalaset is relatively balanced. For clarity, the approximate group ratios in these datasets are summarized Table X below. Our experimental results (Tables and 4) further demonstrate that GRAPHGINI remains robust and consistent even when the sensitive groups are highly imbalanced, highlighting its stability and birness-preserviis behavior across diverse data distributions.
32

---

Published in Transactions on Machine Learning Research (01/2026)
Table U: Performance of GRAPHGINI compared to GUIDE when noise (a) is added the features on the
Credit datasct. Arrows: higher is better, + lower is better.
Method
AUC (1)
IF (4)
GD (4)
IF-Gini (4)
GD-Gini (4)
GUIDE
0.69
1.94
1.01
0.15
1.41
0.0
GRAPHGINI
0.69
0.22
1.01
0.12
1.09
GUIDE
0.68
1.95
1.02
0.15
1.40
0.1
GRAPHGINT
0.68
0.24
1.02
0.13
1.10
GUIDE
0.67
2.01
1.04
0.17
1.40
0.2
GRAPHGINT
0.67
0.26
1.04
0.14
1.11
GUIDE
0.66
2.05
1.10
0.17
1.40
0.3
GRAPHGINI
0.66
0.28
1.07
0.15
1.12
GUIDE
0.64
2.21
1.10
0.17
1.42
0.4
GRAPHGINI
0.64
0.30
1.09
0.16
1.13
Table V: Performance of GRAPHGINI compared to GUIDE when noise (o) is added the features on the
Income dataset. Arrows: higher better, & lower is better.
Method
AUC (1)
IF (4)
GD (4)
IF-Gini (4)
GD-Gini (4)
GUIDE
0.74
39.1
1.00
0.21
1.02
0.0
GRAPHGINI
0.74
19.7
1.00
0.15
1.02
GUIDE
0.73
40.2
1.02
0.23
1.05
0.1
GRAPHGINI
0.73
20.8
1.02
0.16
1.04
GUIDE
0.72
45.5
1.04
0.23
1.08
0.2
GRAPHGINI
0.72
22.1
1.04
0.17
1.05
GUIDE
0.70
48.2
1.10
0.25
1.10
0.3
GRAPHGINI
0.70
23.5
1.07
0.18
1.10
GUIDE
0.68
49.4
1.10
0.27
1.12
0.4
GRAPHGGNI
0.68
25.0
1.09
0.19
1.11
Table W: Performance of GRAPHGINI compared GUIDE when noise (a) is added the features on the
Pokec-n dataset. Arrows: higher better, + lower is better.
Method
AUC (t)
IF (1)
GD (L)
IF-Gini (4)
GD-Gini (1)
GUIDE
0.74
65.1
1.10
0.24
1.18
0.0
GRAPHGINI
0.74
28.2
1.06
0.21
1.12
GUIDE
0.73
68.2
1.10
0.26
1.19
0.1
GRAPHGINI
0.73
29.6
1.07
0.21
1.13
GUIDE
0.72
74.3
1.15
0.28
1.21
0.2
GRAPUGINI
0.72
31.1
1.09
0.22
1.14
GUIDE
0.71
78.3
1.15
0.28
1.26
0.3
GRAPHGINI
0.71
32.8
1.11
0.23
1.15
GUIDE
0.69
80.2
1.16
0.29
1.26
0.4
GRAPHGINI
0.69
34.9
1.13
0.24
1.16
33

---

Published in Transactions on Machine Learning Research (01/2026)
Table X: Group Ratio across datasets. Ratios denote the proportion of the majority the minority groups.
Metric
Credit
Income
Pokec-n
Labels Group ratio (majority minority)
{0, 1}
{0, 1}
{0, 1}
78 22
78 22
51 49
Q Sensitivity to Embedding Dimension
To understand how the representation size affects the fairness utiiiiy trade-off by varying the hidden embedding dimension h E {8, 16, 32} of the GNN encoder used by GRAPUGINI All other components (losses, similarity S, optimization, and data splits) are kept fixed. For all datasets, we performed an ablation study by changing from small to moderate dimensions (h = 8 - 16/32), and reported the results Table Y below. We observe that for larger hidden dimensions, the performance of the GNN begins to diminish. All the results in the manuscript are presented with 1=16 al which fairness utility is best balanced.
Table Y: Effect of embedding dimension on the Credit, Income and Pokec-n datasets (GCN backbone). Arrows: t higher is better, & lower better.
h
AUC (1)
IF (4)
GD (4)
IF-Gini (4)
GD-Gini (J)
Credit
8
0.67
0.27
1.02
0.14
1.10
16
0.69
0.22
1.01
0.12
1.09
32
0.66
0.29
1.08
0.15
1.11
Income
8
0.72
22.8
1.03
0.17
1,10
16
0.74
19.7
1.02
0.15
1.08
32
0.71
23.2
1.08
0.18
1.10
Pokec-n
8
0.72
31.4
1.08
0.22
1.14
16
0.74
28.2
1.06
0.21
1.12
32
0.74
30.9
1.10
0.24
1.15
34


Reviews:
[{"review_id": "nxwAh4eRgx", "reviewer": "Reviewer_ycqx", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes GraphGini, which trains GNNs with fairness regularization by replacing Lipschitz-style individual fairness with a Gini-based dispersion of node embeddings (optimized via a Laplacian surrogate), and adding a group-fairness term balanced through a Nash Social Welfare–like product. The full objective combines task loss, individual fairness, and group fairness, with GradNorm auto-tuning their weights. On several node-classification benchmarks and backbones, it reports improved fairness metrics with minimal accuracy drop.", "claims_and_evidence_yn": "No", "claims_explanation": "1. The proposed loss $\\mathcal{L}_2$ is unmotivated by Gini and duplicates prior art. This training loss is the same structural surrogate that appears in Eq. 4 of InFoRM [1] for individual fairness on graphs. The proposed view with the Gini index does not bring in any fundamental breakthroughs.\n2. The paper argues that the baseline unfairness in Eq. 1 is flawed “because of the max.” But that invites a straightforward design change (e.g., softmax/LogSumExp, p-norm pooling, Huberized max, top-k averaging, or smooth-max) instead of introducing a new metric that, after relaxation, converges to the same Laplacian upper bound as before. Without an ablation showing that alternative pooling fails while the Gini route succeeds, the step to a new metric is unjustified.\n3. \"Gini is superior to Lipschitz” is only shown via a toy counterexample. The paper’s central conceptual claim rests on a hand-crafted example rather than a theorem (no conditions for equivalence/separation, no bounds that compare the two surrogates, no calibration/consistency result). In the absence of rigorous analysis or stress tests across regimes (dense/sparse graphs, noisy attributes, varying homophily), the superiority claim is not convincing.\n4. Furthermore, if we look at the standard definition of the Gini index (Eq. 2), then we can find that the canonical Gini is scalar; the authors generalize this definition in (3) for vector-valued inputs with 1-norm. This comes without sufficient justification. To be specific, any norm in one dimension is essentially of the absolute value form. Then we can directly define it as the 2-norm form, which avoids Proposition 1 and in this regard, past works like [1] are already optimizing the Gini-index objective, completely diminishing the contribution of the paper.\n5. The contribution claim of “auto-tuning of multi-objective loss” in 1.2 relies on existing techniques (e.g., GradNorm). It’s an implementation detail, not a new algorithmic contribution; the paper should avoid over-claiming.\n6. Final objective (Eq. 8) is a direct, routine combination of losses. The method aggregates standard terms without a new optimization principle or analysis demonstrating an edge over baselines; as presented, it’s too incremental to advance the field.\n\n[1] InFoRM: Individual Fairness on Graph Mining. KDD'20", "audience_yn": "Yes", "audience_explanation": "Graph fairness is an important problem that many researchers are interested in.", "requested_changes": "1. Justify (or revise) the multivariate Gini-index definition.\n2. Provide a formal result showing that the proposed Gini index is better than conventional metrics in some aspects, and why we need a foundational change rather than a pooling-operator change.\n3. Differentiate the main methodology from previous arts. \n4. Reposition the contribution section to avoid over-claims.\n5. Add some sensitivity studies. i.e. vary (a) homophily/heterophily levels (b) attribute noise (c) group imbalance ratio (d) embedding dimension (e) $\\beta$ initialization with or without GradNorm and then test the method.", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "ECuUYR1yxy", "reviewer": "Reviewer_ZP48", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies group and individual fairness for graph neural networks (GNNs) while maintaining task utility. It proposes the Gini coefficient as a unified optimization criterion for both individual and group fairness, as an alternative to the Lipschitz constant, and provides an upper bound via the trace of the Similarity Laplacian.\n\n**Strengths**\n- The paper is well-organized and clearly written.\n- The choice of the Gini coefficient is well motivated, and the theory is rigorous.\n- The trace-based upper bound is insightful and helps connect the fairness objective to established spectral tools.\n\n**Weaknesses**\n- Missing comparisons to non-Lipschitz approaches, especially trace- or Laplacian-regularization baselines that are closely related to the proposed bound.\n- The experimental comparisons in Tables 3–4 are hard to interpret because methods are evaluated at different points on the utility–fairness Pareto front. As presented, it is unclear whether improvements come from a different trade-off choice rather than a strictly better method.", "claims_and_evidence_yn": "Yes", "claims_explanation": "The claims are theoretically supported by convincing evidence in Observation 1 and Propositions 1 and 2. However, for real-world fairness applications, the empirical support using GNNs is insufficient and difficult to interpret, e.g., Tables 3–4 compare methods at different points on the utility–fairness Pareto front.", "audience_yn": "Yes", "audience_explanation": "The theoretical contributions are interesting and shed light on how Gini coefficients relate to the well-known equal opportunity metric in fairness, and the upper bound via the trace of the Similarity Laplacian provides a gradient-based optimization pathway. These points should interest readers working on fairness in GNNs and spectral regularization. Stronger, apples-to-apples empirical validation on standard benchmarks would further broaden the paper’s appeal and practical relevance.", "requested_changes": "Please use different values for the $\\beta$ coefficients in Eq. (11) to produce multiple points along the utility–fairness Pareto front.\n\n**Details to include:**\n- Sweep a sensible range of $\\beta$’s (e.g., per-term grids or log-spaced values) for each dataset.\n- Plot full utility–fairness curves for GraphGini and baselines; report matched comparisons at equal utility (or equal fairness) to ensure apples-to-apples evaluation.", "broader_impact_concerns": "This work can improve fairness in ML tasks involving GNNs, which is socially beneficial. At the same time, it could be misused (intentionally or inadvertently) to disadvantage vulnerable demographic groups (e.g., via proxy attributes or poorly chosen utility–fairness trade-offs), so its use should be approached with caution.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "6rAaEPf7nW", "reviewer": "Reviewer_Cesd", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposes GraphGini, a methodology to promote fairness in GNN outcomes. In contrast to traditional Lipschitz-based methodologies which overlook the whole distribution of outcomes, the Gini coefficient allows to enforce fairness  throughout the whole range of outcomes.\nThe authors highlight the different between the two clearly with a toy example.\nThe Gini coefficient for individual fairness is defined based on the node embeddings, while the group fairness depends on the individual fairness over the nodes in the groups defined by sensitive attributes.\nTo take into account the Gini coefficient in the loss function, a differentiable upper bound is derived.\nThe authors use the Nash social welfare to showcase that the fairness among groups is optimised in the GNN outcomes.\nFinally the training is viewed as as a multi-objective optimisation using gradient normalisation.\nThe experiments indicate that GraphGini outperforms 11 fair GNNs on three datasets in terms of fairness without sacrificing too much AUC.", "claims_and_evidence_yn": "Yes", "claims_explanation": "The authors clarify that the limitation Lipschitz- based methods stem from the fact that it is based on the maximum distance over all node pairs, instead of every node pair, and showcase with a toy example how this might mean that two different models can have the same constant.\nThe use of Gini coefficient and group fairness is clearly motivated in Observation 1, where starting from the penalty term we end up with the definition of equal opportunity in terms of outcomes.\nThe upper bound derivation seems correct, although I did not examine App E in all detail.\nThe Nash social welfare program makes sense in order to extend the individual fairness constraint to group fairness inside the loss function, and the gradient norm is required to optimise overall all regularisations.\nFinally the results overall support the advantage of GraphGini compared to the literature in terms of fairness metrics.", "audience_yn": "Yes", "audience_explanation": "Researchers working on fairness on graph learning should be interested in this.", "requested_changes": "Overall this is a well-written text, with clear motivation, solid methodology and promising results.\n\nMy only question pertains to the use of the similarity matrix based on the features.  To my understanding, groups are decided based on the sensitive feature when S is not topological (based on the first sentence in 4.5). \nI thus wanted to understand what are the limitations of GraphGini when S is based on the features and not the graph, because, to my understanding, this scenario might be more applicable to the real world. Since the the matrix becomes a dense V^2, I assume there are concerns at least pertaining to space requirements.\n  \nSome minor comments: \n\nThe code is not modular. In the majority it seems like it is derived by standalone notebooks which makes the code’s reusability and readability hard.\n\nThe proof of proposition 3 could be potentially omitted as it is trivial, or at least be put in the appendix. \n\nThe proof of proposition 4 is a direct reference to another paper, hence it could could also be omitted.\n\nIn the Proof of Proposition 2. App E, there a parentheses missing in “..,w have: min_z”.\n\nIn the Proof of Proposition 4 App F, there is a numeric reference while the references is not enumerated.", "broader_impact_concerns": "There is no clear ethical concern about this work.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)