# Bridging the Fairness Divide: Achieving Group and Individual Fairness in
Graph Neural Networks

Duna Zhan  University of Georgia  Dongliang Guo  University of Virginia
Pengsheng Ji  University of Georgia  Sheng Li  University of Virginia

###### Abstract

Graph neural networks (GNNs) have emerged as a powerful tool for analyzing and
learning from complex data structured as graphs, demonstrating remarkable
effectiveness in various applications, such as social network analysis,
recommendation systems, and drug discovery. However, despite their impressive
performance, the fairness problem has increasingly gained attention as a
crucial aspect to consider. Existing research in graph learning focuses on
either group fairness or individual fairness. However, since each concept
provides unique insights into fairness from distinct perspectives, integrating
them into a fair graph neural network system is crucial. To the best of our
knowledge, no study has yet to comprehensively tackle both individual and
group fairness simultaneously. In this paper, we propose a new concept of
individual fairness within groups and a novel framework named Fairness for
Group and Individual (FairGI), which considers both group fairness and
individual fairness within groups in the context of graph learning. FairGI
employs the similarity matrix of individuals to achieve individual fairness
within groups, while leveraging adversarial learning to address group fairness
in terms of both Equal Opportunity and Statistical Parity. The experimental
results demonstrate that our approach not only outperforms other state-of-the-
art models in terms of group fairness and individual fairness within groups,
but also exhibits excellent performance in population-level individual
fairness, while maintaining comparable prediction accuracy.

##  1 Introduction

Graph-based data provides a natural way to present complex relationships and
structures in the real world and has wide applications in various domains,
such as social networks and recommendations. Graph Neural Networks (GNNs) have
emerged as powerful tools for graph-structured data, including Graph
Convolutional Networks (GCNs) (Kipf & Welling, 2016), Graph Attention Neural
Networks (GAT) (Wang et al., 2019), and Graphsage (Hamilton et al., 2017).
Despite the impressive performance of these models, a notable limitation is
that GNNs can potentially be biased and exhibit unfair prediction when the
training graph is biased or contains sensitive information.

Existing work on fair graph learning mainly focuses on group, individual, and
counterfactual fairness. Models emphasizing group fairness concentrate on
mitigating bias at the demographic group level and guaranteeing fairness for
protected groups such as FairGNN (Dai & Wang, 2021). Models prioritizing
individual fairness aim to ensure fairness at the individual level, such as
InFoRM (Kang et al., 2020). Graph learning with counterfactual fairness
assesses fairness by assuring the fairness of predictions for each individual
compared to counterfactual scenarios, like GEAR (Ma et al., 2022).

When focusing on a single type of fairness, like individual or group fairness,
the existing fair graph learning models demonstrate effectiveness in
mitigating bias while achieving comparable accuracy. However, group and
individual fairness possess inherent limitations, and integrating them is not
a trivial task. Group fairness measurements such as Statistical Parity (SP)
(Dwork et al., 2012) and Equal Opportunity (EO) (Hardt et al., 2016) only
consider fairness at the demographic level, neglecting individual-level
fairness. Conversely, individual fairness prioritizes equity on a personal
scale but falls short of ensuring fairness across broader demographic groups.

For instance, Fig. 1 presents an example of an admissions model where gender
is identified as the sensitive attribute: females are represented by red, and
males by blue. In Fig. 1(a), the machine learning model ensures group
fairness, signifying that it upholds fairness at the demographic level, but
overlooks individual fairness within these groups. In contrast, the model
illustrated in Fig. 1(b) maintains fairness at both the demographic and
individual levels. It adheres to the principle that similar inputs should
yield similar outputs, a criterion essential for individual fairness, which is
achieved through the Lipschitz condition. Consequently, this machine learning
model not only ensures fairness across groups but also assures that candidates
with analogous attributes, like grades and experience, receive comparable
outcomes. Such consistency is crucial for preserving equity throughout the
admissions process. To the best of our knowledge, this paper is the first
study that simultaneously achieves both group and individual fairness within
groups. Our work addresses and mitigates unfairness at both the group and
individual levels, as exemplified in Fig. 1(b).

(a) Machine learning model with group fairness (b) Machine learning model with
group fairness and individual fairness

Figure 1: A toy example for student admission model with gender as the
sensitive attribute. The red color represents female students, which is also
the protected group. The blue color denotes male students. Fig. 1 (a) shows
the machine learning model can only guarantee the group fairness. Fig. 1 (b)
shows the machine learning model can guarantee both group and individual
fairness.

To address the abovementioned problems, we design an innovative definition to
quantify individual fairness within groups. Further, we develop a novel
framework named Fairness for Group and Individual (FairGI), designed to
address concerns related to group and individual fairness. Our goal is to
address two major challenges: (1) how to resolve the conflicts between group
fairness and individual fairness and (2) how to ensure both group fairness and
individual fairness within groups in graph learning. For the first challenge,
we define a new definition of individual fairness within groups. This has been
designed to prevent discrepancies between group fairness and individual
fairness across different groups. For the second challenge, we develop a
framework FairGI to simultaneously achieve group fairness and individual
fairness within groups and maintain comparable accuracy for the model
prediction.

The primary contributions of this paper can be summarized as follows: (1) We
introduce a novel problem concerning the achievement of both group fairness
and individual fairness within groups in graph learning. To the best of our
understanding, this is the first study of this unique issue; (2) We propose a
new metric to measure individual fairness within groups for graphs; (3) We
propose an innovative framework FairGI, to ensure group fairness and
individual fairness within groups in graph learning and maintaining comparable
model prediction performance; (4) Comprehensive experiments on various real-
world datasets demonstrate the effectiveness of our framework in eliminating
both group and individual fairness and maintaining comparable prediction
performance. Moreover, the experiments show that even though we only constrain
individual fairness within groups, our model achieves the best population
individual fairness compared to state-of-the-art models.

##  2 Related Work

###  2.1 Fairness in Machine Learning

With the advances in machine learning, the applications of machine learning
models are widely used in our daily life, including financial services (Leo et
al., 2019), hiring decisions (Chalfin et al., 2016), precision medicine
(MacEachern & Forkert, 2021), and so on. Machine learning models can also be
applied in sensitive situations and make crucial decisions for different
people. However, recent research shows that the current machine learning
models may suffer from discrimination (Dressel & Farid, 2018). Thus,
considering fairness in machine learning models is becoming an important topic
when we apply the models to make decisions in our daily life.

The algorithms for fairness in machine learning can be divided into three
groups: pre-processing, in-processing, and after-processing. The pre-
processing methods mainly focus on adjusting the input data to reduce the
unfairness before training the model. The data preprocessing techniques
include: re-weighting the sensitive groups to avoid discrimination (Kamiran &
Calders, 2012) and re-sampling the data distribution (Calmon et al., 2017).
The in-processing methods integrate fairness constraints directly into the
learning algorithm during the training process, such as adversarial debiasing
(Zhang et al., 2018) and fairness-aware classifier (Zafar et al., 2017). Post-
processing techniques adjust the output of the machine learning model after
training to satisfy fairness constraints, including rejecting option-based
classification (Kamiran et al., 2012) and equalized odds post-processing
(Hardt et al., 2016).

###  2.2 Fairness in Graph Learning

GNNs are successfully applied in many areas. However, they have fairness
issues because of built-in biases like homophily, uneven distributions,
unbalanced labels, and old biases like gender bias. These biases can make
disparities worse through unfair predictions. Therefore, ensuring fairness in
GNNs is essential for achieving unbiased decision-making and equitable
outcomes. Many methods have been suggested to address fairness in learning
from graphs, mainly focusing on three types: group fairness, individual
fairness, and counterfactual fairness.

Group fairness approaches, such as FairGNN (Dai & Wang, 2021) and FairAC (Guo
et al., 2023a), focus on achieving fairness across different groups, ensuring
balanced outcomes at the group level. Recent advancements in this category
include FairSample (Cong et al., 2023), FairVGNN (Wang et al., 2022), FatraGNN
(Li et al., 2024), G-Fame (Liu et al., 2023) and NT-FairGNN (Dai & Wang,
2022), which all dedicated to maintaining fairness among groups within graph
neural networks.

Individual fairness methods, such as InForm (Kang et al., 2020), PFR (Lahoti
et al., 2019), and IFGNN (Xu et al., 2023), focus on fairness at the
individual level. These approaches ensure that similar entities within the
graph are treated equivalently, prioritizing the notion that fairness must be
maintained on a person-by-person basis. However, they often overlook the
aspects of group fairness. Guide (Song et al., 2022) equalizes the individual
fairness level among different groups, but it still focuses on individual
fairness and does not consider group fairness.

Counterfactual fairness methods explore hypothetical scenarios where certain
attributes or connections are altered to understand their causal impact on
fairness. Methods such as GEAR (Ma et al., 2022), Nifty(Agarwal et al., 2021),
and CAF (Guo et al., 2023b) aim to achieve model fairness from a causal
perspective, ensuring that individual predictions remain fair by contrasting
them with both their original scenarios and counterfactual alternatives.

To underline the prevalent limitations of current methods, it is noteworthy
that existing approaches tend to focus on a single dimension of fairness,
either group fairness, individual fairness, or counterfactual fairness, which
restricts their ability to produce truly fair outcomes for both groups and
individuals. Dwork et al. (2012) emphasize the inherent conflicts between
group fairness and individual fairness, illustrating that combining these two
concepts of fairness into one model presents significant challenges.

To address the inherent conflicts between group and individual fairness, we
propose a novel metric, "individual fairness within groups," which
specifically aims to improve fairness at the individual level within each
group. Additionally, we develop a framework named FairGI that optimizes
individual fairness within groups by utilizing a node similarity matrix.
FairGI also incorporates adversarial learning to achieve group fairness with
respect to EO and SP. This innovative framework represents a more refined and
comprehensive method for achieving both group and individual fairness in graph
learning, encompassing a broader spectrum of fairness considerations.

##  3 Preliminary

###  3.1 Preliminaries for fairness learning in graphs

####  3.1.1 Individual fairness

Individual fairness emphasizes fairness at the individual level, ensuring that
individuals with similar inputs are treated consistently and fairly. We
present the definition of individual fairness in graph learning based on the
Lipschitz continuity below (Kang et al., 2020).

######  Definition 1.

(Individual Fairness.) Let $\mathcal{G}=(\mathcal{V},\mathcal{E})$ be a graph
with node set $\mathcal{V}$ and edge set $\mathcal{E}$. $f_{G}$ is the graph
learning model. $Z\in R^{n\times n_{z}}$ is the output matrix of $f_{G}$,
where $n_{z}$ is the embedding dimension for nodes, and $n=|V|$. $M\in
R^{n\times n}$ is the similarity matrix of nodes. The model $f_{G}$ is
individual fair if its output matrix $Z$ satisfies

$L_{If}(Z)=\frac{\sum_{v_{i}\in\mathcal{V}}\sum_{v_{j}\in\mathcal{V}}\Arrowvert\mathbf{z}_{i}-\mathbf{z}_{j}\Arrowvert_{F}^{2}M[i,j]}{2}=Tr(Z^{T}LZ)\leq
m\epsilon,$ (1)

where $L\in R^{n\times n}$ is the Laplacian matrix of $M$, $\epsilon\in R^{+}$
is a constant and $m$ is the number of nonzero values in $M$. $\mathbf{z}_{i}$
is the $i$th row of matrix $Z$ and $M[i,j]$ is the element in the $i$th row
and $j$th column of matrix $M$. $L_{If}$ can be viewed as the population
individual bias of model $f_{G}$.

####  3.1.2 Group fairness

In this paper, we consider two key definitions of group fairness, which are
Statistical Parity (SP) (Dwork et al., 2012) and Equal Opportunity (EO) (Hardt
et al., 2016).

######  Definition 2.

(Statistical Parity.)

$\Delta SP=P(\hat{y}=1|s=0)-P(\hat{y}=1|s=1),$ (2)

where $\hat{y}$ is the predicted label, $y$ is the ground truth of the label,
and $s$ is the sensitive attribute.

######  Definition 3.

(Equal Opportunity.)

$\Delta EO=P(\hat{y}=1|y=1,s=0)-P(\hat{y}=1|y=1,s=1),$ (3)

where $\hat{y}$ is the predicted label, $y$ is the ground truth of the label,
and $s$ is the sensitive attribute.

###  3.2 Problem formulation and notations

####  3.2.1 Notations

Let $\mathcal{G}=(\mathcal{V},\mathcal{E},\mathcal{X})$ be an undirected
graph, where $\mathcal{V}$ is the set of nodes and $\mathcal{E}$ is the set of
edges. We have $|\mathcal{V}|=n$. Let $X\in R^{n\times d}$ be the input matrix
of node features with $d$ dimensions. In this paper, we assume the dataset
contains a single sensitive feature characterized by binary values. Let
$s_{i}$ be the sensitive attribute of the $i$th node in $\mathcal{G}$ and
$\mathcal{S}=\\{s_{1},s_{2},...,s_{n}\\}$. Let $y_{i}$ be the target label of
the $i$th node in $\mathcal{G}$. The sensitive attribute divides the nodes
into two groups. Without loss of generation, we name the group with
$s=1,s\in\mathcal{S}$ as protected group and $s=0,s\in\mathcal{S}$ as
unprotected group. Still, our methods can be easily extended to sensitive
attributes with multiple values.

In this work, we address the unfairness issues in the node classification task
on graphs. Our method ensures both group fairness and individual fairness
within groups while preserving comparable accuracy performance. The fair graph
learning problem is defined below.

####  3.2.2 Problem

Let $\mathcal{G}=(\mathcal{V},\mathcal{E},\mathcal{X})$ be an undirected graph
with sensitive attribute $s\in\mathcal{S}$. Denote $X\in R^{n\times d}$ as the
matrix of node features. Let $\mathcal{P}$ be the set of groups of nodes in
$\mathcal{G}$ divided by $\mathcal{S}$, i.e.
$\mathcal{V}=\mathcal{V}_{p_{2}}\bigcup\mathcal{V}_{p_{2}}$, where
$\mathcal{V}_{p_{i}}=\\{v_{i}|v_{i}\in\mathcal{V},s_{i}=0,s_{i}\in\mathcal{S}\\}$
and $\mathcal{V}_{p_{2}}=\\{v_{i}|v_{i}\in V,s_{i}=1,s_{i}\in\mathcal{S}\\}$.
A function $f_{G}:G\to R^{n\times d_{h}}$ learns the node embeddings of $G$,
i.e.,

$f_{G}(\mathcal{G},\mathcal{S})=H,$ (4)

where $H\in R^{n\times d_{h}}$ is the node embedding matrix, $|V|=n$ and
$d_{h}$ is the dimension of node embeddings. $f$ satisfies group fairness and
individual fairness within groups if and only if $H$ does not contain
sensitive information and for $\forall p_{k}\in\mathcal{P}$,

$\Arrowvert\mathbf{h}_{i}-\mathbf{h}_{j}\Arrowvert_{2}\leq
c_{k}\Arrowvert\mathbf{x}_{i}-\mathbf{x}_{j}\Arrowvert_{2},\leavevmode\nobreak\
\forall i,j\in\mathcal{V}_{p_{k}},$ (5)

where $\mathbf{h}_{i}$ is $i$th node embedding learned from $f$,
$\mathbf{x}_{i}$ is the $i$th node feature from $X$ and $c_{k}\in R^{+}$ is
the Lipschitz constant for group $p_{k}$.

##  4 Methodology

###  4.1 Framework

We propose a novel framework that balances group fairness and individual
fairness in the groups to address the problem shown in figure 1 and provide a
more precise measurement for group fairness. Both group fairness and
individual fairness have limitations in real-world application. While group
fairness focuses on fairness at the group level, it ignores individual
fairness within these groups. Current individual fairness approaches measure
individual fairness by Lipchitz Continous (Kang et al., 2020). However,
strictly adhering to individual fairness may lead to conflicts with group
fairness (Dwork et al., 2012). Our method provides a novel framework to
address the above challenges by proposing a novel definition of individual
fairness within groups. Combining this new definition with group fairness, we
develop a more precise and reliable approach to guarantee fairness in graph
learning.

The detailed algorithm of FairGI is shown in Algorithm 1. Since our method
allows for model training even when sensitive labels are partly missing, we
initially train a sensitive attribute estimator utilized GCN (Kipf & Welling,
2016) to predict the unlabeled sensitive attributes. For the node
classification task, we employ GAT (Wang et al., 2019) to generalize node
embedding and predict target labels. We design a novel loss function to
achieve individual fairness within groups in our framework. To guarantee group
fairness, we employ an adversarial learning layer that hinders adversaries
from precisely predicting sensitive attributes, thereby reducing the bias from
sensitive information. Unlike FairGNN (Dai & Wang, 2021), which solely
optimizes SP, we theoretically demonstrate that our adversarial loss function
can enhance group fairness in terms of both EO and SP. In addition, we devise
a conditional covariance constraint loss function to increase the stability of
the adversarial learning process and prove that optimizing the loss function
leads to the minimum value of EO.

Figure 2: Overview of FairGI. Our method comprises three main parts, i.e., an
individual fairness module, an group fairness module and a GNN classifier for
node prediction.

Fig. 2 shows the framework of FairGI. In this framework, we employ a GNN
classifier for the node classification task. To ensure individual fairness
within groups, we propose a loss function $L_{Ifg}$ to minimize bias among
individuals within the same group. To mitigate group bias, we incorporate
adversarial learning and develop covariance loss functions to optimize EO and
SP. Additionally, we enhance the adversarial learning process by integrating a
sensitive attribute classifier $f_{S}$.

The comprehensive loss function of our approach is:

$L=L_{C}+L_{G}+\alpha L_{Ifg},$ (6)

where $L_{C}$ is the loss for node label prediction, $L_{G}$ represents the
loss for debiasing group unfairness, and $L_{Ifg}$ represents the loss for
mitigating individual unfairness within groups.

Algorithm 1 Algorithm of our framework

1:Input: $\mathcal{G}(\mathcal{V},\mathcal{E}),X,\mathcal{S}$

2:Output: Sensitive attribute classifier $f_{S}$, node classifier $f_{C}$,
node label prediction $\hat{y}$

3:Train sensitive attribute classifier $f_{S}$ by given sensitive attribute
labels using loss function $L_{Sens}$ in Eq.(11).

4:repeat

5: Obtain estimated sensitive attribute
$\hat{s},\hat{s}\in\mathcal{\tilde{S}}$ by $f_{S}$.

6: Optimize $f_{G}$ to predict the node label by loss function $L_{C}$ in
Eq.(19)

7: Optimize $f_{G}$ to debias group unfairness by loss function $L_{G}$ in
Eq.(18)

8: Optimize $f_{G}$ to debias individual unfairness within groups by loss
function $L_{Ifg}$ in Eq.(10)

9: Optimize adversary $f_{A}$ by $L_{A}$ in Eq.(23)

10:until Converge

11:return $f_{S}$, $f_{G}$ and $\hat{y}$

###  4.2 Optimization of Individual Fairness within Groups

####  4.2.1 Challenges of balancing individual fairness and group fairness

We can observe that the definitions of group fairness, especially SP and EO,
may contradict individual fairness in specific circumstances. As noted by
(Dwork et al., 2012), potential discrepancies can arise between group and
individual fairness when the distance between groups is significant. Assume
$\Gamma$ represents the protected group and $\Gamma^{\prime}$ denotes the
unprotected group. If there is a considerable distance between individuals in
$\Gamma$ and those in $\Gamma^{\prime}$, strictly adhering to individual
fairness may not guarantee similar outcomes for both groups. Thus, this can
lead to a conflict with the goal of group fairness, which seeks to maintain
equal treatment and opportunity for all groups. Inspired by (Dwork et al.,
2012), we alleviate the conflicts between SP and individual fairness by
loosening the Lipschitz restriction between different groups.

####  4.2.2 Loss function for individual fairness within groups

To balance group and individual fairness and address the limitation of group
fairness, we introduce a novel definition of individual fairness within
groups. Based on the proposed definition, we design a loss function that
ensures individual fairness within the known groups. Note that our approach is
also applicable to groups that are not mutually exclusive.

######  Definition 4.

(Individual Fairness within Groups.) The measurement of individual fairness
within group $p$ is:

$L_{p}(Z)=\frac{\sum_{v_{i}\in\mathcal{V}_{p}}\sum_{v_{j}\in\mathcal{V}_{p}}\Arrowvert\mathbf{z}_{i}-\mathbf{z}_{j}\Arrowvert_{2}^{2}M[i,j]}{n_{p}},$
(7)

where $\mathcal{V}_{p}$ represents the set of nodes in group $p$ and $Z$
denotes the node embedding matrix. $\mathbf{z}_{i}$ is the $i$th row of $Z$.
$M$ is the similarity matrix of nodes. $L$ is the laplacian matrix of $M$ and
$n_{p}$ is the number of pairwise nodes in group $p$ with nonzero similarities
in $M$.

Our objective focuses on optimizing individual fairness within each group,
guaranteeing equitable treatment for individuals in the same groups. To
achieve this, our loss function is designed to minimize the maximum individual
unfairness over all groups in our loss function.

Firstly, we consider the loss function that minimizes the maximum unfairness
over all the groups as follows:

$f^{*}=\textrm{argmin}_{f\in\mathcal{H}}\\{max_{p\in\mathcal{P}}L_{p}(Z)\\},$
(8)

where $Z=f(\cdot)$, $\mathcal{H}$ is a class of graph learning models,
$\mathcal{P}$ is the set of groups and $L_{p}$ is the individual loss for
group $p$. Motivated by the concept of guaranteeing the optimal situation for
the most disadvantaged group, as presented in (Diana et al., 2021), we employ
the minimax loss function from Eq. (8). This approach prioritizes minimizing
the maximum unfairness across groups, rather than simply aggregating
individual fairness within each group to ensure a more equitable outcome.

The optimal solution in Eq.(8) is hard to obtain, thus we can relax the loss
function as expressed in Eq. (9). Given an error bound $\gamma$ for each
group, the extension of the minimax problem can be formulated as follows:

$\displaystyle\textrm{minmize}_{f\in\mathcal{H}}\sum_{p\in\mathcal{P}}L_{p}(Z),\leavevmode\nobreak\
$ $\displaystyle\textrm{subject to }L_{p}(f)\leq\gamma,p\in\mathcal{P}.$ (9)

In our framework, we not only focus on the loss of individual fairness within
groups in Eq.(9), but also consider the loss of label prediction and group
fairness. Thus, we further convert Eq.(9) into the unconstrained loss function
shown in Eq.(10) by introducing Lagrange multiplier $\lambda_{p}$ to the loss
function. We can achieve individual fairness within groups by minimizing the
loss function below:

$L_{Ifg}=\sum_{p\in\mathcal{P}}L_{p}(Z)+\sum_{p\in\mathcal{P}}\lambda_{p}(L_{p}(Z)-\gamma),$
(10)

where $\lambda_{p}$ and $\gamma$ are hyperparameters in our model.

###  4.3 Enhancing Group Fairness Through Ensuring Equal Opportunity and
Statistical Parity

In this section, we enhance group fairness by introducing a novel loss
function tailored to optimize EO. This approach marks a significant difference
from the covariance constraint proposed by FairGNN (Dai & Wang, 2021), which
only optimizes SP. Additionally, our methodology integrates the loss functions
for EO and SP, enabling the simultaneous optimization of both EO and SP, thus
presenting a comprehensive framework for enhancing group fairness in model
predictions.

####  4.3.1 Adverserial learning

As we address the circumstance where certain sensitive labels are absent, we
utilized GCN (Kipf & Welling, 2016) to train the sensitive estimator $f_{S}$,
and the loss function for the sensitive label prediction is:

$L_{Sens}=-\frac{1}{|\mathcal{V}|}\sum_{i\in\mathcal{V}}((s_{i})\textrm{log}(\hat{s}_{i})+(1-s_{i})\textrm{log}(1-\hat{s}_{i})),$
(11)

where $s_{i}$ is the sensitive attribute for the $i$th node, $\hat{s}_{i}$ is
the predicted senstive labels.

To optimize SP, the min-max loss function of adversarial learning is (Dai &
Wang, 2021):

$\min\limits_{\Theta_{C}}\max\limits_{\Theta_{A}}L_{A_{1}}=\mathbb{E}_{h\sim
p(h|\hat{s}=1)}[\textrm{log}(f_{A}(h))]+\mathbb{E}_{h\sim
p(h|\hat{s}=0)}[\textrm{log}(1-f_{A}(h))],$ (12)

where $\Theta_{C}$ is the parameters for graph classifier $f_{C}$,
$\Theta_{A}$ is the parameters for adversary $f_{A}$ and $h$ is the node
presentation of the last layer of GNN classifier $f_{C}$. $h\in
p(h|\hat{s}=1)$ denotes sampling nodes from the protected group within the
graph $\mathcal{G}$.

While FairGNN demonstrates that optimizing Eq. (12) can achieve the minimum SP
(Dai & Wang, 2021) in the GNN classifier, it does not guarantee the attainment
of the minimum EO. Both EO and SP are significant metrics for group fairness.
Optimizing solely for SP can adversely affect the performance of EO, leading
to model bias. To address the shortage of Eq. (12), we propose a novel min-max
loss function designed for adversarial learning to achieve the minimum EO in
Eq. (13).

$\min\limits_{\Theta_{C}}\max\limits_{\Theta_{A}}L_{A_{2}}=\mathbb{E}_{h\sim
p(h|\hat{s}=1,y=1)}[\textrm{log}(f_{A}(h))]+\mathbb{E}_{h\sim
p(h|\hat{s}=0,y=1)}[\textrm{log}(1-f_{A}(h))].$ (13)

The Theorem 6 in the Appendix demonstrates that the optimal solution of Eq.
(13) ensures the GNN classifier satisfies $\Delta EO=0$, given two easily
attainable assumptions. In addition, we can also mitigate sensitive
information by letting $f_{A}$ predict the sensitive attribute closer to a
uniform distribution, as inspired by Gong et al. (2020).

To simultaneously optimize EO and SP, we combining Eq.(12) and Eq.(13) to
obtain the loss function for adversarial learning as:

$L_{A}=L_{A_{1}}+L_{A_{2}}.$ (14)

####  4.3.2 Covariance constraint

The limitation of adversarial debiasing is instability. Similar to adversarial
learning, FairGNN focuses on optimizing Statistical Parity (SP) through the
covariance constraint loss as described by (Dai & Wang, 2021) but ignores the
EO. Eq. (15) shows the

$L_{R_{1}}=\lvert
Cov(\hat{s},\hat{y})\lvert=\lvert\mathbb{E}[(\hat{s}-\mathbb{E}[\hat{s}](\hat{y}-\mathbb{E}[\hat{y}])]\lvert,$
(15)

Note that $\Delta EO=0$ is not the prerequisite of $L_{R_{1}}=0$. Eq. (15)
does not enhance the model fairness in terms of EO.

Thus, we propose a covariance constraint loss function to optimize EO as
follows:

$L_{R_{2}}=|Cov(\hat{s},\hat{y}|y=1)|=|\mathbb{E}[(\hat{s}-\mathbb{E}[\hat{s}|y=1](\hat{y}-\mathbb{E}[\hat{y})|y=1]|y=1]|.$
(16)

Theorem 7 in the Appendix shows that under the mild assumption, $L_{R2}=0$ is
the prerequisite of $\Delta EO=0$. Consequently, Eq. (16) effectively
optimizes EO. We can further enhance group fairness in our model by optimizing
EO and SP using Eq. (17).

$L_{Cov}=L_{R1}+L_{R2}.$ (17)

In conclusion, the loss function that we utilize to mitigate group fairness
is:

$L_{G}=\beta L_{A}+\gamma L_{Cov},$ (18)

where $\beta$ and $\gamma$ are hyperparameters.

###  4.4 Node Prediction

For the node prediction task, we employ GAT (Wang et al., 2019) to predict
node labels. The loss function for GNN classifier $f_{C}$ is:

$L_{C}=-\frac{1}{|\mathcal{V}|}\sum_{i\in\mathcal{V}}((y_{i})\textrm{log}(\hat{y_{i}})+(1-y_{i})\textrm{log}(1-\hat{y_{i}})).$
(19)

In the conclusion, we highlight the distinct contributions of our work in
comparison to existing methodologies. Our research introduces a novel problem
statement that aims to address both group fairness and individual fairness.
This dual focus sets our work apart from others like FairGNN, which only
considers group fairness. Moreover, when considering group fairness, our
approach not only optimizes for SP but also for EO, providing a more
comprehensive group fairness optimization. In contrast, FairGNN’s loss
functions are solely directed at SP. This broader and more comprehensive
fairness optimization strategy underscores the innovative contributions of our
framework.

##  5 Experiments

Table 1: Comparisons of our method and baselines on three datasets. $\uparrow$
denotes the larger value is the better and $\downarrow$ indicates the smaller
value is the better. Best performances are in bold.

Dataset | Method | Acc $\uparrow$ | AUC $\uparrow$ |  $\Delta SP$ $\downarrow$ |  $\Delta EO$ $\downarrow$ | MaxIG $\downarrow$ | IF $\downarrow$
---|---|---|---|---|---|---|---
| GCN | 68.82$\pm$0.17 | 73.98$\pm$0.07 | 2.21$\pm$0.61 | 3.17$\pm$1.10 | 5.69$\pm$0.08 | 899.54$\pm$13.10
| GAT | 69.14$\pm$0.68 | 74.24$\pm$0.90 | 1.40$\pm$0.64 | 2.86$\pm$0.49 | 6.10$\pm$0.62 | 880.89$\pm$89.97
| PRF | 55.39$\pm$0.08 | 53.83$\pm$0.02 | 1.08$\pm$0.09 | 1.82$\pm$0.18 | 0.64$\pm$0.01 | 101.26$\pm$1.27
| InFoRM | 68.77$\pm$0.39 | 73.69$\pm$0.10 | 1.84$\pm$0.69 | 3.58$\pm$1.15 | 1.52$\pm$0.05 | 238.41$\pm$7.97
Pokec-n | NIFTY | 65.97$\pm$0.57 | 69.87$\pm$0.64 | 4.62$\pm$0.52 | 7.32$\pm$0.94 | 1.87$\pm$0.15 | 310.84$\pm$26.25
| GUIDE | 69.46$\pm$0.04 | 74.67$\pm$0.01 | 2.95$\pm$0.11 | 0.80$\pm$0.18 | 0.61$\pm$0.00 | 101.77$\pm$0.28
| FairGNN | 69.86$\pm$0.30 | 75.58$\pm$0.52 | 0.87$\pm$0.38 | 2.00$\pm$1.08 | 1.26$\pm$0.96 | 192.29$\pm$142.06
| Ours | 68.86$\pm$0.58 | 75.07$\pm$0.1 | 0.63$\pm$0.37 | 0.75$\pm$0.30 | 0.47$\pm$0.09 | 67.41$\pm$13.68
| GCN | 69.08$\pm$2.02 | 74.20$\pm$1.69 | 17.12$\pm$7.10 | 10.03$\pm$4.92 | 25.99$\pm$2.12 | 17.87$\pm$1.74
| GAT | 70.80$\pm$3.70 | 72.48$\pm$4.32 | 11.90$\pm$8.94 | 16.70$\pm$10.57 | 21.14$\pm$10.86 | 20.79$\pm$9.95
| PRF | 55.58$\pm$0.93 | 58.26$\pm$4.45 | 1.99$\pm$0.99 | 2.22$\pm$1.65 | 4.47$\pm$2.25 | 3.06$\pm$1.55
| InFoRM | 68.71$\pm$2.78 | 74.19$\pm$1.85 | 16.64$\pm$5.64 | 12.75$\pm$6.80 | 26.52$\pm$8.25 | 18.82$\pm$5.17
NBA | NIFTY | 70.55$\pm$2.30 | 76.18$\pm$0.83 | 11.82$\pm$4.28 | 5.69$\pm$3.48 | 17.14$\pm$5.01 | 11.93$\pm$3.43
| GUIDE | 63.31$\pm$2.86 | 67.46$\pm$3.44 | 13.89$\pm$5.11 | 10.50$\pm$4.76 | 29.54$\pm$16.34 | 19.84$\pm$10.75
| FairGNN | 72.95$\pm$2.10 | 77.37$\pm$1.11 | 1.19$\pm$0.43 | 0.62$\pm$0.43 | 10.91$\pm$12.59 | 18.51$\pm$23.72
| Ours | 73.13$\pm$1.75 | 79.28$\pm$0.46 | 0.43$\pm$0.28 | 0.62$\pm$0.32 | 0.12$\pm$0.11 | 0.08$\pm$0.07
| GCN | 70.35$\pm$0.99 | 65.18$\pm$6.58 | 14.55$\pm$6.13 | 13.92$\pm$6.00 | 5.18$\pm$1.34 | 39.11$\pm$6.69
| GAT | 70.89$\pm$1.84 | 71.30$\pm$1.64 | 15.95$\pm$2.40 | 15.96$\pm$2.77 | 5.88$\pm$3.34 | 35.28$\pm$15.41
| PRF | 69.87$\pm$0.09 | 69.90$\pm$0.04 | 14.63$\pm$0.78 | 13.96$\pm$0.79 | 5.80$\pm$0.08 | 39.79$\pm$0.63
| InFoRM | 69.91$\pm$3.70 | 65.55$\pm$5.6 | 14.80$\pm$3.84 | 14.82$\pm$4.18 | 4.09$\pm$1.68 | 33.62$\pm$13.86
Credit | NIFTY | 68.74$\pm$2.34 | 68.84$\pm$0.41 | 9.91$\pm$0.30 | 9.07$\pm$0.63 | 2.92$\pm$1.18 | 24.73$\pm$9.75
| GUIDE | 62.01$\pm$0.01 | 67.44$\pm$0.01 | 13.88$\pm$0.10 | 13.54$\pm$0.06 | 0.22$\pm$0.01 | 1.90$\pm$0.01
| FairGNN | 73.40$\pm$0.15 | 70.18$\pm$0.03 | 3.91$\pm$0.11 | 3.49$\pm$0.25 | 1.88$\pm$0.09 | 13.84$\pm$0.70
| Ours | 74.09$\pm$0.13 | 68.81$\pm$0.11 | 3.84$\pm$0.22 | 2.60$\pm$0.20 | 0.22$\pm$0.01 | 1.84$\pm$0.10

In this section, we conduct a comprehensive comparison between our proposed
method and other cutting-edge models, evaluating their performance on real-
world datasets to demonstrate the effectiveness of our approach.

###  5.1 Datasets and Baselines

In this experiment, we utilize three public datasets, Pokec_n Dai & Wang
(2021) , NBA Dai & Wang (2021), and Credit Yeh & Lien (2009).

We compare our method with other state-of-art fairness models for graph
learning. In our comparison, we include basic GNNs like GCN (Kipf & Welling,
2016) and GAT (Velickovic et al., 2017), which don’t fix bias. We also include
GNNs like PFR (Lahoti et al., 2019) and InFoRM (Kang et al., 2020), aiming at
individual fairness. To compare group fairness methods, we include FairGNN
(Dai & Wang, 2021). Additionally, we include NIFTY (Agarwal et al., 2021), a
method based on causal inference for fairness, as a baseline in our study.
Further descriptions of datasets and baselines can be found in the Appendix.

####  5.1.1 Evaluation metrics

In this experiment, we primarily focus on analyzing and comparing individual
fairness within groups as well as group fairness. Furthermore, we assess the
performance of the prediction task by employing metrics such as Area Under the
Curve (AUC) and Accuracy (ACC). We include MaxIG, IF, SP, and EO in the
experiments for the fairness evaluation metrics. MaxIG is defined as:

${\rm MaxIG}=\max(L_{p}(Z)),\leavevmode\nobreak\ p\in\mathcal{P},$ (20)

where $L_{p}(\cdot)$ can be computed in Eq. (7) and $Z$ is the output of GNN
Classifier.

###  5.2 Results and Analysis

####  5.2.1 Individual unfairness and group unfairness in graph neural
networks

Based on the experimental results presented in Table 1, several key findings
emerge regarding the performance and biases of various GNNs.

Traditional GNNs, such as GCN and GAT, exhibit both individual and group
biases. This suggests that while these models may have good performance, they
do not adequately handle fairness issues. Models that address group fairness,
such as FairGNN, demonstrate good performance in group fairness metrics like
SP and EO, but struggle with individual fairness metrics, such as IF and
MaxIG. This underscores the challenge of simultaneously optimizing for both
group and individual fairness.

On the contrary, models like PRF, InFoRM, NIFTY, and GUIDE, which primarily
target individual fairness, perform well in mitigating individual biases.
However, they have poor performance in group fairness. This dichotomy
indicates a potential trade-off regarding group-level fairness while promoting
individual fairness. These findings emphasize the need for more comprehensive
solutions that simultaneously address individual and group biases.

####  5.2.2 Effectiveness of FairGI in mitigating both individual fairness and
group fairness

The results in Table 1 highlight the efficacy of our approach, leading to two
primary observations: (1) Our method outperforms competing methods by ensuring
superior group fairness and intra-group individual fairness while retaining
comparable prediction accuracy and AUC of the ROC curve; (2) While our
technique is constrained only to fairness within groups, it remarkably
achieves superior population individual fairness compared to baselines. This
suggests that we can attain the pinnacle of population individual fairness by
concentrating solely on intra-group individual fairness and overlooking inter-
group individual fairness. This outcome is intuitively reasonable given the
potential substantial variances among individuals from different groups.

Figure 3: Comparison of our method, our method without loss function of
individual fairness within groups, our method without the optimization for EO.

###  5.3 Ablation Studies

In the ablation study, we examine the impact of two modules, individual
fairness within groups and optimization of equal opportunity, on the
performance of our method. We conduct a comparison between our method and two
of its variants using the Credit dataset. The first variant, "ours w/o Ifg,"
omits the individual fairness within groups loss $L_{Ifg}$ from our method.
The second variant, "ours w/o EO," eliminates the optimizations for equal
opportunity, specifically the loss functions $L_{A_{2}}$ and $L_{R2}$, from
our method.

Figure 3 illustrates the comparative results. We can observe that upon the
removal of $L_{Ifg}$, there is a noticeable increase in MaxIG, EO, and SP,
with MaxIG experiencing the most significant rise. This strongly attests to
the efficacy of the loss function $L_{Ifg}$ in enhancing individual fairness.
When we disregard the optimizations for EO, MaxIG remains relatively unchanged
while both EO and SP increase. This highlights the crucial role of $L_{A2}$
and $L_{Cov2}$ in optimizing group fairness.

##  6 Conclusion

In this paper, we present an innovative problem that considers both group
fairness and individual fairness within groups. In this particular context, we
propose a novel definition named MaxIG for individual fairness within groups.
Furthermore, we propose a novel framework named FairGI to achieve both group
fairness and individual fairness within groups in graph learning. FairGI
leverages the similarity matrix to mitigate individual unfairness within
groups. Additionally, it exploits the principles of adversarial learning to
mitigate group unfairness. Extensive experiments demonstrate that FairGI
achieves the best results in fairness and maintains comparable prediction
performance.

## References

  * Agarwal et al. (2021) Chirag Agarwal, Himabindu Lakkaraju, and Marinka Zitnik.  Towards a unified framework for fair and stable graph representation learning.  In _Uncertainty in Artificial Intelligence_ , pp. 2114–2124. PMLR, 2021.
  * Calmon et al. (2017) Flavio Calmon, Dennis Wei, Bhanukiran Vinzamuri, Karthikeyan Natesan Ramamurthy, and Kush R Varshney.  Optimized pre-processing for discrimination prevention.  _Advances in neural information processing systems_ , 30, 2017.
  * Chalfin et al. (2016) Aaron Chalfin, Oren Danieli, Andrew Hillis, Zubin Jelveh, Michael Luca, Jens Ludwig, and Sendhil Mullainathan.  Productivity and selection of human capital with machine learning.  _American Economic Review_ , 106(5):124–127, 2016.
  * Cong et al. (2023) Zicun Cong, Baoxu Shi, Shan Li, Jaewon Yang, Qi He, and Jian Pei.  Fairsample: Training fair and accurate graph convolutional neural networks efficiently.  _IEEE Transactions on Knowledge and Data Engineering_ , 2023.
  * Dai & Wang (2021) 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_ , pp. 680–688, 2021.
  * Dai & Wang (2022) Enyan Dai and Suhang Wang.  Learning fair graph neural networks with limited and private sensitive attribute information.  _IEEE Transactions on Knowledge and Data Engineering_ , 2022.
  * Diana et al. (2021) Emily Diana, Wesley Gill, Michael Kearns, Krishnaram Kenthapadi, and Aaron Roth.  Minimax group fairness: Algorithms and experiments.  In _Proceedings of the 2021 AAAI/ACM Conference on AI, Ethics, and Society_ , pp. 66–76, 2021.
  * Dressel & Farid (2018) Julia Dressel and Hany Farid.  The accuracy, fairness, and limits of predicting recidivism.  _Science advances_ , 4(1):eaao5580, 2018.
  * Dwork et al. (2012) Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel.  Fairness through awareness.  In _Proceedings of the 3rd innovations in theoretical computer science conference_ , pp. 214–226, 2012.
  * Gong et al. (2020) Sixue Gong, Xiaoming Liu, and Anil K Jain.  Jointly de-biasing face recognition and demographic attribute estimation.  In _Computer Vision–ECCV 2020: 16th European Conference, Glasgow, UK, August 23–28, 2020, Proceedings, Part XXIX 16_ , pp. 330–347. Springer, 2020.
  * Guo et al. (2023a) Dongliang Guo, Zhixuan Chu, and Sheng Li.  Fair attribute completion on graph with missing attributes.  _arXiv preprint arXiv:2302.12977_ , 2023a.
  * Guo et al. (2023b) Zhimeng Guo, Jialiang Li, Teng Xiao, Yao Ma, and Suhang Wang.  Towards fair graph neural networks via graph counterfactual.  In _Proceedings of the 32nd ACM International Conference on Information and Knowledge Management_ , pp. 669–678, 2023b.
  * Hamilton et al. (2017) Will Hamilton, Zhitao Ying, and Jure Leskovec.  Inductive representation learning on large graphs.  _Advances in neural information processing systems_ , 30, 2017.
  * Hardt et al. (2016) Moritz Hardt, Eric Price, and Nati Srebro.  Equality of opportunity in supervised learning.  _Advances in neural information processing systems_ , 29, 2016.
  * Kamiran & Calders (2012) Faisal Kamiran and Toon Calders.  Data preprocessing techniques for classification without discrimination.  _Knowledge and information systems_ , 33(1):1–33, 2012.
  * Kamiran et al. (2012) Faisal Kamiran, Asim Karim, and Xiangliang Zhang.  Decision theory for discrimination-aware classification.  In _2012 IEEE 12th international conference on data mining_ , pp. 924–929. IEEE, 2012.
  * Kang et al. (2020) Jian Kang, Jingrui He, Ross Maciejewski, and Hanghang Tong.  Inform: Individual fairness on graph mining.  In _Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery & data mining_, pp. 379–389, 2020.
  * Kipf & Welling (2016) Thomas N Kipf and Max Welling.  Semi-supervised classification with graph convolutional networks.  _arXiv preprint arXiv:1609.02907_ , 2016.
  * Lahoti et al. (2019) Preethi Lahoti, Krishna P Gummadi, and Gerhard Weikum.  Operationalizing individual fairness with pairwise fair representations.  _arXiv preprint arXiv:1907.01439_ , 2019.
  * Leo et al. (2019) Martin Leo, Suneel Sharma, and Koilakuntla Maddulety.  Machine learning in banking risk management: A literature review.  _Risks_ , 7(1):29, 2019.
  * Li et al. (2024) Yibo Li, Xiao Wang, Yujie Xing, Shaohua Fan, Ruijia Wang, Yaoqi Liu, and Chuan Shi.  Graph fairness learning under distribution shifts.  _arXiv preprint arXiv:2401.16784_ , 2024.
  * Liu et al. (2023) Zheyuan Liu, Chunhui Zhang, Yijun Tian, Erchi Zhang, Chao Huang, Yanfang Ye, and Chuxu Zhang.  Fair graph representation learning via diverse mixture-of-experts.  In _Proceedings of the ACM Web Conference 2023_ , pp. 28–38, 2023.
  * Ma et al. (2022) Jing Ma, Ruocheng Guo, Mengting Wan, Longqi Yang, Aidong Zhang, and Jundong Li.  Learning fair node representations with graph counterfactual fairness.  In _Proceedings of the Fifteenth ACM International Conference on Web Search and Data Mining_ , pp. 695–703, 2022.
  * MacEachern & Forkert (2021) Sarah J MacEachern and Nils D Forkert.  Machine learning for precision medicine.  _Genome_ , 64(4):416–425, 2021.
  * Song et al. (2022) 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_ , pp. 1625–1634, 2022.
  * Takac & Zabovsky (2012) Lubos Takac and Michal Zabovsky.  Data analysis in public social networks.  In _International scientific conference and international workshop present day trends of innovations_ , volume 1. Present Day Trends of Innovations Lamza Poland, 2012.
  * Velickovic et al. (2017) Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, Yoshua Bengio, et al.  Graph attention networks.  _stat_ , 1050(20):10–48550, 2017.
  * Wang et al. (2019) Xiang Wang, Xiangnan He, Yixin Cao, Meng Liu, and Tat-Seng Chua.  Kgat: Knowledge graph attention network for recommendation.  In _Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_, pp. 950–958, 2019.
  * Wang et al. (2022) Yu Wang, Yuying Zhao, Yushun Dong, Huiyuan Chen, Jundong Li, and Tyler Derr.  Improving fairness in graph neural networks via mitigating sensitive attribute leakage.  In _Proceedings of the 28th ACM SIGKDD conference on knowledge discovery and data mining_ , pp. 1938–1948, 2022.
  * Xu et al. (2023) Kejia Xu, Zeming Fei, Jianke Yu, Yu Kong, Xiaoyang Wang, and Wenjie Zhang.  Ifgnn: An individual fairness awareness model for missing sensitive information graphs.  In _Australasian Database Conference_ , pp. 287–300. Springer, 2023.
  * Yeh & Lien (2009) 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–2480, 2009.
  * Zafar et al. (2017) Muhammad Bilal Zafar, Isabel Valera, Manuel Gomez Rogriguez, and Krishna P Gummadi.  Fairness constraints: Mechanisms for fair classification.  In _Artificial intelligence and statistics_ , pp. 962–970. PMLR, 2017.
  * Zhang et al. (2018) Brian Hu Zhang, Blake Lemoine, and Margaret Mitchell.  Mitigating unwanted biases with adversarial learning.  In _Proceedings of the 2018 AAAI/ACM Conference on AI, Ethics, and Society_ , pp. 335–340, 2018.

##  Appendix A Appendix

###  A.1 Proof of Theorems

######  Proposition 5.

Let Eq.(13) be the loss function of adversary learning. The optimal solution
of Eq.(13) is achieved if and only if $p(h|\hat{s}=0,y=1)=p(h|\hat{s}=1,y=1)$.

###### Proof.

By Proposition 1. in (Dai & Wang, 2021), the optimal value of adversary is in
Eq.(21)

$f_{A_{2}}^{*}(h)=\frac{p(h|\hat{s}=1,y=1)}{p(h|\hat{s}=1,y=1)+p(h|\hat{s}=0,y=1)}.$
(21)

We denote $B=p(h|\hat{s}=1,y=1)$ and $C=p(h|\hat{s}=0,y=1)$. Thus, the min-max
loss function in Eq.(13) can be written as the following with the optimal
solution of adversary:

$\displaystyle L_{A_{2}}$ $\displaystyle=\mathbb{E}_{h\in
B}[log\frac{B}{B+C}]+\mathbb{E}_{h\in C}[log\frac{C}{B+C}]$ (22)
$\displaystyle=\mathbb{E}_{h\in
B}[log\frac{B}{\frac{1}{2}(B+C)}]+\mathbb{E}_{h\in
C}[log\frac{C}{\frac{1}{2}(B+C)}]-2log2$
$\displaystyle=D_{KL}(B||B+C)+D_{KL}(C||B+C)-2log2$
$\displaystyle=2JSD(B||C)-2log2,$

where $D_{KL}(\cdot)$ is the Kullback–Leibler divergence and $JSD(\cdot)$ is
the Jensen–Shannon divergence.

We know that $JSD(B||C)$ is non-negative and equals to 0 if and only if
distributions $B$ and $C$ are equal. Thus, the loss function $L_{A_{2}}$
achieves the minimum value if and only if
$p(h|\hat{s}=0,y=1)=p(h|\hat{s}=1,y=1)$. The proof is adapted to Proposition
4.1 in Dai & Wang (2021).

∎

######  Theorem 6.

Let $\hat{y}$ be the prediction label of GNN classifier $f_{G}$, $h$ be the
node presentation generated by GNN classifier $f_{G}$. We assume:

  1. 1.

The prediction of sensitive attribute $\hat{s}$ and $h$ are conditionally
independent, i.e., $p(\hat{s},h|s,y=1)=p(\hat{s}|s,y=1)p(h|s,y=1)$.

  2. 2.

$p(s=1|\hat{s}=1,y=1)\neq p(s=1|\hat{s}=0,y=1)$.

If Eq.(13) achieves the global optimum, the prediction of GNN classifier
$f_{G}$ will satisfy equal opportunity, i.e.
$p(\hat{y}|s=0,y=1)=p(\hat{y}|s=1,y=1)$.

Combining Eq.(12) and Eq.(13), we have the loss function of adversarial
learning as:

$L_{A}=L_{A_{1}}+L_{A_{2}}.$ (23)

###### Proof.

By proposition 7.1, we have $p(h|\hat{s}=0,y=1)=p(h|\hat{s}=1,y=1)$ when we
obtain the optimum solution for the loss function 13. Thus, we have

$\sum_{s\in S}p(h,s|\hat{s}=1,y=1)=\sum_{s\in S}p(h,s|\hat{s}=0,y=1).$ (24)

Under the conditionally independent assumption in assumption 1, we have

$\displaystyle\sum_{s\in S}p(h|\hat{s}=1,y=1)p(s|\hat{s}=1,y=1)=$ (25)
$\displaystyle\sum_{s\in S}p(h|\hat{s}=0,y=1)p(s|\hat{s}=0,y=1).$

Reformulating the Eq.(25) and by the assumption 2, we obtain

$\displaystyle\frac{p(h\lvert s=1,y=1)}{p(h\lvert s=0,y=1)}$
$\displaystyle=\frac{p(s=0\lvert\hat{s}=0,y=1)-p(s=0\lvert\hat{s}=1,y=1)}{p(s=1\lvert\hat{s}=1,y=1)-p(s=1\lvert\hat{s}=0,y=1)}$
(26)
$\displaystyle=\frac{1-p(s=1\lvert\hat{s}=0,y=1)-1+p(s=1\lvert\hat{s}=1,y=1)}{p(s=1\lvert\hat{s}=1,y=1)-p(s=1\lvert\hat{s}=0,y=1)}$
$\displaystyle=1$

Thus, we have $p(h|s=1,y=1)=p(h|s=0,y=1)$, which leads to
$p(\hat{y}|s=1,y=1)=p(\hat{y}|s=0,y=1)$. The equal opportunity is satisfied
when we achieve the global minimum in Eq.(13). The proof is adapted to Theorem
4.2 in Dai & Wang (2021).

∎

######  Theorem 7.

Suppose $p(\hat{s},h\lvert s,y=1)=p(\hat{s}\lvert s,y=1)p(h\lvert s,y=1)$,
when $f_{G}$ satisfy equal opportunity, i.e. $p(\hat{y},s\lvert
y=1)=p(\hat{y}\lvert y=1)p(s\lvert y=1)$, we have $L_{R_{2}}=0$.

###### Proof.

Since $p(\hat{s},h\lvert y=1)=p(\hat{s}\lvert y=1)p(h\lvert y=1)$, we have the
following equation:

$\displaystyle p(h\lvert s,\hat{s},y=1)$
$\displaystyle=\frac{p(h,s,\hat{s}\lvert y=1)}{p(s,\hat{s}\lvert y=1)}$ (27)
$\displaystyle=\frac{p(\hat{s},h\lvert s,y=1)}{p(\hat{s}\lvert s,y=1)}$
$\displaystyle=p(h\lvert s,y=1),$

thus, we have $p(\hat{y}\lvert s,\hat{s},y=1)=p(\hat{y}\lvert s,y=1)$.

If $p(\hat{y},s\lvert y=1)=p(\hat{y}\lvert y=1)p(s\lvert y=1)$,
$p(\hat{y},\hat{s}|y=1)$ can be written as:

$\displaystyle p(\hat{y},\hat{s}|y=1)$ $\displaystyle=\sum\limits_{s\in
S}p(\hat{y}\lvert s,y=1)p(\hat{s},s\lvert y=1)$ (28)
$\displaystyle=p(\hat{y}\lvert y=1)p(\hat{s}\lvert y=1).$

Thus, we have $L_{R_{2}}=\lvert Cov(\hat{s},\hat{y}\lvert y=1)\rvert=0$, which
proof the theorem. The proof is adapted by the proof of Theorem 4.3 in Dai &
Wang (2021). ∎

###  A.2 Datasets and Baselines

Datasets. In the experiments, we utilize three datasets. Table 2 shows the
summary of the datasets. Our datasets demonstrate comprehensive coverage of
diverse data categories and varied sample sizes. The detailed descriptions of
the datasets are presented below:

  * •

The PockeC dataset, presented by Takac & Zabovsky (2012), serves as a
benchmark dataset derived from Slovakian social networks, facilitating the
evaluation and development of various algorithms and models in this context.
This comprehensive dataset encompasses various features for each individual
within the network, such as gender, age, educational background, geographical
region, recreational activities, working areas, etc. (Dai & Wang, 2021)
partitioned the dataset into two distinct subsets, Pokec_n and Pokec_z, based
on the provinces of the individuals. Each of the two datasets contains two
predominant regions within the relevant provinces. In this experiment, we
utilize the Pokec_n dataset and regard the geographical region as the
sensitive attribute. In the node classification task, we use working areas as
the target variable for node prediction.

  * •

The NBA dataset, introduced by Dai & Wang (2021), consists of data from 403
professional basketball players in the National Basketball Association (NBA).
The dataset includes features such as age, nationality, salary, and other
relevant player attributes. In our experiments, nationality is considered a
sensitive attribute, while the target label focuses on determining whether a
player’s salary is above or below the median.

  * •

The Credit dataset is introduced by Yeh & Lien (2009), which offers valuable
insights into various aspects of consumer behavior. The dataset includes
features such as spending habits and credit history, which are essential for
understanding the financial patterns of these individuals. The primary
objective of this dataset is to facilitate the prediction of credit card
default, with age being identified as the sensitive attribute.

Count | Pokec-n | Credit | NBA
---|---|---|---
Number of Nodes | 66,569 | 30,000 | 403
Number of node attributes | 59 | 13 | 39
Number of Edges | 729,129 | 304,754 | 16,570
Senstive attibute | region | age | nationality
Table 2: Basic statistics of datasets.

Baselines.We compare our methods with other state-of-art models in the node
classification task.

  * •

FairGNN: FairGNN is a graph neural network (GNN) model introduced by Dai &
Wang (2021) employs adversarial learning address the challenges of group
fairness in graph representation learning.

  * •

GUIDE: GUIDE was proposed by Song et al. (2022) to ensure group equality
informed individual fairness in graph representation learning.

  * •

PRF: Pairwise Fair Representation (PFR) is a graph learning method introduced
by Lahoti et al. (2019) to achieve individual fairness in graph representation
learning.

  * •

InFoRM: Individual Fairness on Graph Mining (InFoRM) (Kang et al., 2020)
achieves individual fairness in graph representation learning by employing
Lipschitz continuity.

  * •

NIFTY: Agarwal et al. (2021) propose NIFTY (unifying fairness and stability)
that applies the Lipschitz condition to achieve counterfactual fairness in
graph learning.

###  A.3 Experiment Settings

In this experiment, we compare our method to the state of art models for
fairness in graph learning. Here we use Graph Convolutional Network (GCN)
(Kipf & Welling, 2016) and Graph Attention Network (GAT) (Wang et al., 2019)
as the vanilla comparison models since they do not apply fairness skills. We
also include graph learning models with group fairness like FairGNN (Dai &
Wang, 2021). Graph learning models with individual fairness include GUIDE Song
et al. (2022), PRF (Lahoti et al., 2019) and InFoRM (Kang et al., 2020). Graph
learning models with counterfactual fairness such as NIFTY (Agarwal et al.,
2021). The parameters of our method are shown in Table 3. We apply four
datasets in the experiments. For each dataset we randomly divide them into
training set, test set, and validation set with ratios of 50%, 25% and 25%.

Count | Pokec-n | Credit | NBA
---|---|---|---
$\alpha$, coefficient of $L_{Ifg}$ | 1e-9 | 0.5 | 1e-9
$\beta$, coefficient of $L_{A}$ | 0.02 | 0.8 | 0.01
$\gamma$ | 0.004 | 0.004 | 0.004
$\lambda_{1}$ | 0.5 | 0.5 | 0.5
$\lambda_{2}$ | 1.25 | 1.25 | 1
$\eta$, coefficient of $L_{Cov}$ | 3 | 6 | 16
number of sensitive labels | 200 | 500 | 50
learning rate | 0.0005 | 0.001 | 0.001
weight decay | 1e-5 | 1e-5 | 1e-5
Table 3: Hyper parameter setting for datasets.

Figure 4: Comparison of our method, our method without loss function of
individual fairness within groups, our method without the optimization for EO.

###  A.4 Additional Analysis on Ablation Studies

Figure 4 presents performance comparisons based on AUC, ACC, and IF. We note
that eliminating individual fairness losses within groups results in a
marginal increase in ACC compared to our approach. When we exclude EO
optimization losses, both ACC and AUC exhibit a non-significant increase,
demonstrating that our method can maintain comparable accuracy.

Furthermore, We can observe that if we remove the loss of individual fairness
within groups, the performance of IF becomes worse. This observation
demonstrates the effectiveness of the loss function of individual fairness
within groups, i.e., $L_{Ifg}$.