# FairSample: Training Fair and Accurate Graph Convolutional Neural Networks
Efficiently

Zicun Cong, Baoxu Shi, Shan Li, Jaewon Yang, Qi He, , Jian Pei  Zicun Cong was
with School of Computing Science, Simon Fraser University. E-mail:
<EMAIL_ADDRESS>
Baoxu Shi was with LinkedIn Corporation, Sunnnyvale, USA. E-mail:
<EMAIL_ADDRESS>
Shan Li was with LinkedIn Corporation, Sunnnyvale, USA. E-mail:
<EMAIL_ADDRESS>
Jaewon Yang was with LinkedIn Corporation, Sunnnyvale, USA. E-mail:
<EMAIL_ADDRESS>
Qi He was with LinkedIn Corporation, Sunnnyvale, USA. E-mail<EMAIL_ADDRESS>
Jian Pei is with School of Computing Science, Simon Fraser University. E-mail:
<EMAIL_ADDRESS>

###### Abstract

Fairness in Graph Convolutional Neural Networks (GCNs) becomes a more and more
important concern as GCNs are adopted in many crucial applications. Societal
biases against sensitive groups may exist in many real world graphs. GCNs
trained on those graphs may be vulnerable to being affected by such biases. In
this paper, we adopt the well-known fairness notion of demographic parity and
tackle the challenge of training fair and accurate GCNs efficiently. We
present an in-depth analysis on how graph structure bias, node attribute bias,
and model parameters may affect the demographic parity of GCNs. Our insights
lead to FairSample, a framework that jointly mitigates the three types of
biases. We employ two intuitive strategies to rectify graph structures. First,
we inject edges across nodes that are in different sensitive groups but
similar in node features. Second, to enhance model fairness and retain model
quality, we develop a learnable neighbor sampling policy using reinforcement
learning. To address the bias in node features and model parameters,
FairSample is complemented by a regularization objective to optimize fairness.

###### Index Terms:

Graph neural network, Sampling, Fairness

##  1 Introduction

Graph Convolutional Neural Networks (GCNs) are deep neural networks learning
latent representations for a given graph [1, 2]. GCNs learn latent
representations of nodes (node embeddings) from the graph topology and then
use the embeddings for prediction tasks. Due to the superior prediction
performance, GCNs enjoy many real world applications, such as talent
recruitment [3], healthcare [4], and recommender system [5]. At the same time,
fairness in GCNs becomes a serious concern. GCNs can inherit the bias in the
underlying graphs and make discriminatory decisions correlated with sensitive
attributes, such as age, gender, and nationality [6, 7, 8]. In order to use
GCNs for many real world applications, such as job recommendation, it is
critical for GCNs to make fair predictions for people with different sensitive
values [9].

Demographic parity [6, 10] is a well adopted notion of fairness, which aims
for similar predictions for different demographic groups (see Section 3.2 for
a brief review). Being closely related to the legal doctrine of disparate
impact [11, 12], demographic parity has drawn tremendous attention. There are
many challenges in improving the demographic parity fairness of GCNs. First,
GCNs leverage node features to generate embeddings, but node features are
often correlated with sensitive attributes [6]. For example, it has been shown
that a user’s postal code may manifest the user’s nationality [13]. Second, a
graph structure can also inherit societal bias – nodes with the same sensitive
values are more likely to be connected due to homophily. For example, it has
been observed in social networks that people with the same religions are more
likely to become friends [14]. GCNs learn node embeddings by aggregating and
transforming node feature vectors over graph topology. In a biased graph, a
node mainly receives information from neighbors in the same sensitive group.
Therefore, the embeddings learned on the graph tend to be correlated with
sensitive attributes and lead to discriminatory predictions [8, 15]. Last,
there is a well-known tradeoff between accuracy and demographic parity
fairness of machine learning models [16, 17, 18]. A fair GCN should achieve
the desirable fairness level with less sacrifice in utility [8].

There are some pioneering methods tackling demographic parity fairness in
GCNs. For example, FairGNN [6] learns a demographic parity fair GCN classifier
by adding one or more fairness penalty terms in the loss function of the
classifier, which rectifies the model parameters. However, FairGNN ignores the
important feature aggregation mechanisms of GCNs and fails to explore their
effects on improving model fairness. As a result, the fairness and accuracy
performance achieved by FairGNN is limited.

A few unsupervised fairness enhancing methods [8, 15] optimize the graph
adjacency matrix by dropping edges so that the learned node embeddings are
independent of sensitive attributes. As they adjust the adjacency matrix by
assigning a learnable parameter to each edge of the input graph, they cannot
scale up to large real world networks. Moreover, as the node embeddings in
those methods are not optimized for specific graph mining tasks, the learned
embeddings may not perform well in accuracy and fairness on a user’s target
task, such as node classification. Last, dropping edges may not be enough to
adjust the biased neighborhood composition if all neighbors of a node have the
same sensitive value.

In this paper, we tackle the challenges of training demographic parity fair
and accurate GCN models efficiently and make several contributions. First, we
systematically analyze how graph structure bias, node attribute bias, and
model parameters may affect the demographic parity of GCNs. Second, based on
the analysis and insights, we propose FairSample, a novel framework to improve
the demographic parity of GCNs with a minimal tradeoff in accuracy and
efficiency. FairSample has three major components to address the challenges in
building fair and accurate GCNs efficiently. To address the societal bias in
an input graph, FairSample has a novel edge injector and an original
computation graph sampler to rectify the feature aggregation process of GCNs.
The edge injector adds edges across nodes with different sensitive values and
ensures that each node has enough neighbors with different sensitive values
from which GCNs can learn unbiased embeddings. Computation graph sampler
selects neighbors that help GCNs make both accurate and fair predictions. We
employ reinforcement learning to train the sampler with a small number of
parameters such that it enhances the demographic parity of GCNs and retains
good accuracy and scalability. To address the bias in node features and model
parameters, FairSample is complemented by a regularization objective to
optimize fairness following the state-of-the-art approach [6]. Last, we
conduct extensive experiments on a series of real world datasets to
demonstrate that FairSample has superior capability in training fair and
accurate GCNs. Our results show that FairSample outperforms the state-of-the-
art fair GCN methods in terms of both fairness and accuracy. Compared to the
GCN methods without fairness constraints, FairSample achieves up to $65.5\%$
improvement in fairness at the cost of only at most $5.0\%$ accuracy decrease.
Furthermore, FairSample incurs only a small extra computational overhead,
making it more computationally efficient than the majority of the baseline
methods.

The rest of the paper is organized as follows. In Section 2, we review the
related work. The essentials of graph convolutional neural networks and
demographic parity are reviewed in Section 3. In Section 4, we explore the
intuitions and formulate the problem. We develop FairSample in Section 5 and
report the experimental results in Section 6. In Section 7, we conclude the
paper.

##  2 Related Work

In this section, we briefly review the related work on fair GCNs [19, 6, 8]
and sampling strategies for efficient GCN training [20, 21, 22].

###  2.1 Fair Graph Convolutional Neural Networks

Most existing fair machine learning methods are developed for independently
and identically distributed (i.i.d) data [8]. They can be categorized into
three groups. The pre-processing methods enhance model fairness by repairing
biased training datasets, such as revising data labels [23, 24, 25] and
perturbing data attributes [26, 27, 28]. The post-processing methods enhance
the fairness of a model by calibrating the prediction scores of the model [17,
29, 30]. The in-processing methods revise the training process of specific
machine learning models to enhance model fairness. Typically, fairness notion
related regularizers are added into model objective functions [31, 32, 10].
Please see [9] for a survey of fair machine learning models.

In general, graph data is non-IID. It has been discovered that both node
attributes and graph structure can contain societal bias [15, 6]. Due to the
feature aggregation mechanisms of GCNs, the predictions of GCNs may inherit
both types of biases [6]. However, the existing fairness methods on i.i.d data
are not suitable to be directly applied to GCNs, as they cannot handle the
graph structure bias [8]. Very recently, there are exciting advances in
enforcing fairness in GCNs. Most studies adopt demographic parity as the
fairness measure. FCGE [19], FairGNN [6], and DFGNN [33] apply adversarial
learning to improve the fairness in node embeddings. The embeddings are
optimized to prevent a discriminator from accurately predicting the
corresponding sensitive attribute values. These methods do not explicitly
rectify biases in graph structures and have suboptimal fairness performance.

A few pre-processing methods are proposed to remedy graph structure biases and
improve demographic parity. FairWalk [11] extends the node2vec graph embedding
method [34] using sensitive attribute-aware stratified sampling to create a
diversified node context. Li et al. [8] and Laclau et al. [7] propose to
adjust the adjacency matrix of an input graph such that nodes from different
sensitive groups have similar embeddings. EDITS [15] produces a fair version
of the input graph by altering its adjacency matrix and node attributes. Kose
and Shen [35] propose a fairness-aware data augmentation framework on node
attributes and graph structures for graph contrastive learning. As these
methods do not optimize their utility on specific tasks, they may lose
considerable accuracy on a user’s target task.

Some studies explore other fairness notions in GCNs. For example, Agarwal et
al. [16] and Ma et al. [36] adopt contrastive learning to train GCN
classifiers under the constraint of counterfactual fairness [37]. In favor of
individual fairness, Dong et al. [38] propose a ranking-based regularizer on
GCNs. Some studies [39, 40, 41] investigate and mitigate the accuracy
disparity between sensitive groups. These methods, however, may not improve
demographic parity in GCNs [9].

Our approach FairSample is an in-processing fairness enhancing method, which
revises the training process of GCNs to enhance their demographic parity.
Different from the existing fairness enhancing methods, FairSample rectifies
the feature aggregation process and models parameters of GCNs at the same time
to explicitly optimize GCNs towards good accuracy and fairness.

###  2.2 Sampling Strategies for Efficient GCN Training

Most GCN models [2, 6] use the whole $K$-hop neighborhood of each node to
train node embeddings and result in high computation and memory costs. Thus,
those methods cannot scale up to large graphs [20, 22]. To scale up GCN
models, sampling strategies have been proposed to limit the neighborhood size
for each given node and reduce the cost of feature aggregation. The sampling
strategies can be a heuristic probability distribution [20, 21, 42, 43] or a
learned parameterized model [44, 45, 22].

Our method also employs a sampling strategy for training GCNs. Different from
the existing methods, our sampling strategy is designed to sample balanced and
informative sets of neighbors to enhance model fairness with minimal tradeoff
in model utility.

##  3 Preliminaries

In this section, we review the essentials of graph convolutional neural
networks (GCNs) and how to train fair GCNs. Table I shows the commonly used
notations in the paper.

TABLE I: Frequently used notations. Symbol | Definition
---|---
$\mathcal{G}=(\mathcal{V},\mathcal{E},\mathbf{X})$ |  An attributed graph with nodes $\mathcal{V}$, edges $\mathcal{E}$, and node feature vectors $\mathbf{X}$
$\mathcal{A}=\\{a_{1},\ldots,a_{\zeta}\\}$ | Domain of the categorical sensitive attribute
$\mathcal{V}_{a_{i}}$ | The sets of nodes taking the sensitive value $a_{i}$
$\mathbf{x}_{i}$ | Feature vector of node $v_{i}$
$s_{i}\in\mathcal{A}$ | Sensitive attribute value of $v_{i}$
$\Gamma_{v}$ | The set of 1-hop neighbors of node $v$
$f_{G}$ | A $K$-layer GCN node classifier
$\mathbf{h}_{i}^{l}\ (1\leq l\leq K)$ | Embedding of $v_{i}$ in the $l$-th layer of a GCN
$\mathbf{W}_{l}\ (1\leq l\leq K)$ | Parameters in the $l$-th layer of a GCN
$\mathcal{T}_{v_{i}}$ | Computation graph of $v_{i}$
$\mathcal{L}_{\text{dp}}$ | Demographic parity regularizer
$p(v)$ | A sample of child nodes of $v$
$\text{P}(v_{j}|v_{i})$ | Probability of sampling a child node $v_{j}$ of $v_{i}$

###  3.1 Graph Convolutional Neural Networks

Denote by $\mathcal{G}=(\mathcal{V},\mathcal{E},\mathbf{X})$ an _attributed
graph_ , where $\mathcal{V}=\\{v_{1},\ldots,v_{n}\\}$ is a set of $n$ nodes,
$\mathcal{E}\subseteq\mathcal{V}\times\mathcal{V}$ is a set of edges,
$\mathbf{X}\in\mathbb{R}^{n\times d}$ is a matrix of node features, and
$\mathbf{x}_{i}\in\mathbb{R}^{d}$ is the feature vector of node $v_{i}$
$(1\leq i\leq n)$. Denote by $\Gamma_{v}$ the set of 1-hop neighbors of node
$v$. To investigate the fairness in GNNs, we assume that all nodes have a
categorical _sensitive attribute_ $\mathcal{A}$, such as age, gender, and
disability. Each node $v_{i}$ is associated with a _sensitive value_
$s_{i}\in\mathcal{A}$, where $\mathcal{A}=\\{a_{1},\ldots,a_{\zeta}\\}$ is the
domain of the sensitive attribute. Denote by
$\mathcal{V}_{a_{i}}=\\{v_{j}|v_{j}\in\mathcal{V},s_{j}=a_{i}\\}$ and
$\mathcal{V}_{\neq a_{i}}=\mathcal{V}\setminus\mathcal{V}_{a_{i}}$ $(1\leq
i\leq\zeta)$ the sets of nodes taking and not taking the sensitive value
$a_{i}$, respectively.

We focus on the semi-supervised node classification problem, which has wide
practical applications [6, 2]. Our proposed method can also be applied to
other graph learning tasks, like link prediction problem. Denote by
$\mathcal{V}_{L}=\\{v_{1},\ldots,v_{m}\\}\subseteq\mathcal{V}$ a set of
labeled nodes and by $Y_{L}=\\{y_{1},\ldots,y_{m}\\}$ the corresponding class
labels. We follow the common setting in fair machine learning [6, 32] and
assume that the class labels $y_{i}\in\\{0,1\\}$ $(1\leq i\leq m)$ are binary.
Our proposed method can also be applied to multi-class classification
problems.

A $K$-layer GCN [20, 46] uses graph structures and node attributes to predict
node labels. In the $l$-th layer $(1\leq l\leq K)$, the GCN updates the
embedding $\mathbf{h}^{l}_{v}$ of node $v$ by aggregating the $(l-1)$-th layer
embeddings of the neighbors of $v$. A simple and general formulation of GCNs
[21, 22] is

$\mathbf{h}_{v}^{l}=\rho(\frac{1}{|\Gamma_{v}|+1}\sum_{v_{i}\in\Gamma_{v}\cup\\{v\\}}\mathbf{h}_{v_{i}}^{l-1}\mathbf{W}_{l}),$
(1)

where $\rho(\cdot)$ is a non-linear activation function,
$\mathbf{W}_{l}\in\mathbb{R}^{d_{l-1}\times d_{l}}$ is a learnable
transformation matrix in the $l$-th layer of a GCN, $d_{l}$ is the
dimensionality of the $l$-th layer node embeddings, and
$\mathbf{h}_{v}^{0}=\mathbf{x}_{v}$. The GCN predicts the label of $v$ as
$\hat{y}_{v}=\sigma(\mathbf{h}^{K}_{v}\mathbf{W}_{c})$, where $\mathbf{W}_{c}$
is the classifier parameters and $\sigma(\cdot)$ is the softmax function. The
GCN is trained by optimizing the cross entropy loss
$\mathcal{L}_{\text{accuracy}}$.

Given a very large graph, the limited GPU memory is often not enough to store
the whole graph. To leverage GPU for fast computation, GCNs are trained using
stochastic gradient descent, that is, only mini-batches of nodes and their
corresponding computation graphs are loaded into GPU. Computation graph
describes how features are aggregated and transformed in each GCN layer to
compute node embeddings [46]. For each node $v\in\mathcal{V}$, the computation
graph $\mathcal{T}_{v}$ of $v$ uses a tree structure defining how to compute
embedding $\mathbf{h}_{v}^{l}$ by aggregating the previous layer embeddings of
the neighbors of $v$ [46]. Given $\mathcal{T}_{v}$, the embedding
$\mathbf{h}_{v}^{K}$ can be computed by iteratively aggregating embeddings
along the edges in $\mathcal{T}_{v}$ in a bottom-up manner.

######  Example 1 (GCN Classifier and Computation Graph).

Given a simple example input graph shown in Figure 1(a), a 2-layer GCN $f_{G}$
aims to predict the label of node $v_{1}$. Figure 1(b) shows the computation
graph $\mathcal{T}_{v_{1}}$ of $v_{1}$ in the 2-layer GCN. In the first layer
of $f_{G}$, it computes the embeddings $\mathbf{h}_{v_{1}}^{1}$,
$\mathbf{h}_{v_{2}}^{1}$, $\mathbf{h}_{v_{3}}^{1}$, and
$\mathbf{h}_{v_{4}}^{1}$ of $v_{1}$, $v_{2}$, $v_{3}$, and $v_{4}$,
respectively. By Equation 1,
$\mathbf{h}_{v_{1}}^{1}=\rho(\frac{1}{4}\sum_{1\leq i\leq
4}\mathbf{x}_{v_{i}}\mathbf{W}_{1})$,
$\mathbf{h}_{v_{2}}^{1}=\rho(\frac{1}{2}(\mathbf{x}_{1}+\mathbf{x}_{2})\mathbf{W}_{1})$,
$\mathbf{h}_{v_{3}}^{1}=\rho(\frac{1}{2}(\mathbf{x}_{1}+\mathbf{x}_{3})\mathbf{W}_{1})$,
and
$\mathbf{h}_{v_{4}}^{1}=\rho(\frac{1}{3}(\mathbf{x}_{1}+\mathbf{x}_{2}+\mathbf{x}_{4})\mathbf{W}_{1})$.
In the second layer of $f_{G}$, it computes the embedding
$\mathbf{h}_{v_{1}}^{2}=\rho(\frac{1}{4}\sum_{1\leq i\leq
4}\mathbf{h}_{v_{i}}^{1}\mathbf{W}_{2})$ of $v_{1}$. Finally, $f_{G}$ predicts
the label of node $v_{1}$ as
$\hat{y}_{v_{1}}=\sigma(\mathbf{h}^{2}_{v_{1}}\mathbf{W}_{c})$.

Given a graph with an average node degree $d$, a $K$-layer GCN needs to
aggregate information from $d^{K}$ neighbors for each node on average, which
incurs high computation cost for large $d$ [1, 44]. Moreover, to compute the
gradients of the loss function, for each $K$-hop neighbor $u$ of $v$, we need
to store its all $K$ embeddings $\mathbf{h}_{u}^{l}\ (1\leq l\leq K)$ in
memory, which results in hefty memory footprints [47]. To tackle the
challenge, a sampling strategy can be used to train GCNs [20, 22, 45] such
that in each layer of a GCN, a node only aggregates embeddings from a small
number of randomly sampled neighbors. Specifically, the sampling methods down-
sample the computation graph $\mathcal{T}_{v}$ in a top-down manner such that
each node in $\mathcal{T}_{v}$ contains at most $k$ child nodes. Then, the
embedding $\mathbf{h}_{v}^{l}$ is computed by following the new computation
graph. That is, $\mathbf{h}_{v}^{l}=\rho(\frac{1}{k+1}\sum_{v_{i}\in
p(v)\cup\\{v\\}}\mathbf{h}_{v_{i}}^{l-1}\mathbf{W}_{l-1}),$ where $p(v)$ is a
sample of $k$ child nodes of $v$ according to a sampling policy. By
regularizing the size of the computation graph in a GCN, the sampling methods
can train the GCN in less cost. Figure 1(c) shows an example of down-sampled
computation graph. Up to $1$ child node per node in $\mathcal{T}_{v_{1}}$ is
sampled.

Figure 1: (a) An input graph to a 2-layer GCN. (b) The original computation
graph of node $v_{1}$ in the 2-layer GCN. (c) The down-sampled computation
graph of node $v_{1}$ in the 2-layer GCN. The embedding of a node in a layer
is plotted on the left of the node. The arrows indicate the directions of
embedding aggregation.

###  3.2 Fairness Notion of Demographic Parity

Many notions of algorithmic fairness have been proposed in literature, such as
demographic parity [10], counterfactual fairness [36], and individual fairness
[48]. Due to its societal importance [11, 12], demographic parity has been
widely adopted in fair machine learning algorithms [6, 8, 32, 10].

######  Definition 1 (Demographic Parity [10]).

Given random samples $(\mathbf{x},s)$ drawn from a joint distribution over a
feature space $\mathcal{X}$ and a sensitive attribute $\mathcal{A}$, a
classifier $f(\cdot):\mathbb{R}^{d}\rightarrow\\{0,1\\}$ is said to satisfy
demographic parity if the prediction $f(\mathbf{x})$ is independent of the
sensitive attribute value $s$, that is, $\forall a\in\mathcal{A}$,
$\mathbb{E}[f(\mathbf{x})|s=a]=\mathbb{E}[f(\mathbf{x})]$.

To train a fair classifier, in-processing fairness methods add one or more
demographic parity penalty terms $\mathcal{L}_{\text{dp}}$ in the loss
function of the classifier to penalize discriminatory behaviors. In
particular, the traditional regularization methods [6, 10, 32] train a fair
GCN classifier by optimizing the _loss of fairness and utility_ , defined by

$\mathcal{L}=\mathcal{L}_{\text{accuracy}}+\alpha\mathcal{L}_{\text{dp}},$ (2)

where $\alpha$ is the weight of the fairness penalty.

There is a well recognized tradeoff between model accuracy and demographic
parity [12, 16, 17, 18]. GCNs use feature aggregation mechanisms over graph
topology to learn node representations. Due to this unique property, applying
Equation 2 to regularize the model parameters alone may not be sufficient to
train GCNs with good accuracy and fairness. In this paper, we study how to
rectify the feature aggregation process of GCNs by modifying their computation
graphs so that fairness can be improved with minor tradeoff in utility.

##  4 Intuition and Problem Formulation

Since GCNs perform node classification by aggregating and transforming node
feature vectors over graph structures [46], biased graph connections may lead
to poor demographic parity [6]. To fix the issue and strengthen demographic
parity in node classification, one idea is to modify connections in input
graphs [8, 7].

To elaborate the insight of modifying input graph structures to improve
demographic parity, for the sake of simplicity, let us analyze the fairness of
_simple GCNs_ [49], which are a type of GCNs without the non-linear activation
function in Equation 1. Simple GCNs are widely adopted in recommender systems,
thanks to its good scalability and comparable or even improving performance to
general GCNs with nonlinear activation functions [5, 50, 51, 52]. We leave the
theoretical analysis on general GCNs to future work.

Denote by $\tilde{\mathbf{A}}\in\mathbb{R}^{n\times n}$ a _random walk
probability matrix_ , where each element $\tilde{\mathbf{A}}{[i,j]}$ $(1\leq
i\leq n,1\leq j\leq n)$ is the probability of a $K$-step random walk starting
at $v_{i}$ and terminating at $v_{j}$. Let $\beta{[\neq
a,a]}=\frac{1}{|\mathcal{V}_{\neq a}|}\sum_{v_{i}\in\mathcal{V}_{\neq
a},v_{j}\in\mathcal{V}_{a}}\tilde{\mathbf{A}}{[i,j]}$ be the average
probability for a $K$-step random walk starting at a node with sensitive value
not equal to $a$ and terminating at a node with sensitive value $a$.
Similarly, denote by $\beta{[a,a]}$ the average probability for a $K$-step
random walk starting at a node with sensitive value $a$ and terminating at a
node with the same sensitive value.

Following the idea in logit matching [53], an empirical counterpart of the
regularization term $\mathcal{L}_{\text{dp}}$ in Equation 2 is
$\hat{\mathcal{L}}_{\text{dp}}=\sum_{a\in\mathcal{A}}\left\lVert\frac{\sum_{v_{i}\in\mathcal{V}_{a}}\mathbf{p}_{v_{i}}}{|\mathcal{V}_{a}|}-\frac{\sum_{v_{j}\in\mathcal{V}_{\neq
a}}\mathbf{p}_{v_{j}}}{|\mathcal{V}_{\neq a}|}\right\rVert_{2},$ where a logit
$\mathbf{p}_{v}=\mathbf{h}_{v}^{K}\mathbf{W}$ is the input vector to the
softmax function of a graph neural network. $\hat{\mathcal{L}}_{\text{dp}}$
measures the disparity between the prediction logits of sensitive groups.

Next, we show that we can reduce the upper bound of the demographic parity
regularizer $\hat{\mathcal{L}}_{\text{dp}}$ on GCNs by modifying the
connections in the input graph. Thus, we may train GCNs with better
demographic parity on the modified graph.

######  Theorem 1.

Denote by
$\mathbf{\mu}_{a}=\frac{1}{|\mathcal{V}_{a}|}\sum_{v\in\mathcal{V}_{a}}\mathbf{x}_{v}$
the mean of the node feature vectors in a group $\mathcal{V}_{a}$ and by
$dev(\mathcal{V}_{a})=\max_{v\in\mathcal{V}_{a}}\\{\|v-\mu_{a}\|_{\infty}\\}$
the deviation. Let
$\delta_{a}=\max\\{dev(\mathcal{V}_{a}),dev(\mathcal{V}_{\neq a})\\}$. For any
SGCN with parameters $\mathbf{W}$, an upper bound of the regularization term
$\hat{\mathcal{L}}_{\text{dp}}$ is

$\hat{\mathcal{L}}_{\text{dp}}\leq\sum_{a\in\mathcal{A}}\lVert\mathbf{W}\rVert_{2}(|\beta{[a,a]}-\beta{[\neq
a,a]}|\cdot\lVert\mu_{a}-\mu_{\neq
a}\rVert_{2}+2\sqrt{d}\sum_{a\in\mathcal{A}}\delta_{a}).$ (3)

###### Proof.

$\hat{\mathcal{L}}_{\text{dp}}=\sum_{a\in\mathcal{A}}\left\lVert\frac{\sum_{v_{i}\in\mathcal{V}_{a}}\mathbf{p}_{v_{i}}}{|\mathcal{V}_{a}|}-\frac{\sum_{v_{j}\in\mathcal{V}_{\neq
a}}\mathbf{p}_{v_{j}}}{|\mathcal{V}_{\neq a}|}\right\rVert_{2}$ by definition.
Wu et al. [49] show that the prediction of a $K$-layer SGCN on a node $v$ is
$\hat{y}_{v}=\sigma(\mathbf{h}_{v}\mathbf{W})$, where
$\mathbf{h}_{v}=\sum_{u\in\mathcal{V}}\tilde{\mathbf{A}}[v,u]\mathbf{x}_{u}$.
Plugging in the definition of $p_{i}=\mathbf{h}_{v_{i}}\mathbf{W}$, the term
$\hat{\mathcal{L}}_{\text{dp}}^{a}=\lVert\frac{\sum_{v_{i}\in\mathcal{V}_{a}}p_{i}}{|\mathcal{V}_{a}|}-\frac{\sum_{v_{j}\in\mathcal{V}_{\neq
a}}p_{j}}{|\mathcal{V}_{\neq a}|}\rVert_{2}$ in
$\hat{\mathcal{L}}_{\text{dp}}$ can be rewritten as
$\hat{\mathcal{L}}_{\text{dp}}^{a}=\lVert\frac{\sum_{v_{i}\in\mathcal{V}_{a}}\mathbf{h}_{v_{i}}\mathbf{W}}{|\mathcal{V}_{a}|}-\frac{\sum_{v_{j}\in\mathcal{V}_{\neq
a}}\mathbf{h}_{v_{j}}\mathbf{W}}{|\mathcal{V}_{\neq a}|}\rVert_{2}$. As the
Lipschitz constant for a linear function $g(\mathbf{x})=\mathbf{x}\mathbf{W}$
is the spectral normal of $\mathbf{W}$ [54], we have

$\hat{\mathcal{L}}_{\text{dp}}^{a}\leq\lVert\mathbf{W}\rVert_{2}\left\lVert\frac{\sum_{v_{i}\in\mathcal{V}_{a}}\mathbf{h}_{v_{i}}}{|\mathcal{V}_{a}|}-\frac{\sum_{v_{j}\in\mathcal{V}_{\neq
a}}\mathbf{h}_{v_{j}}}{|\mathcal{V}_{\neq a}|}\right\rVert_{2}.$ (4)

For simplicity, we use the bracket notation to represent the range of a
vector111Consider three vectors $\mathbf{x}_{1}$, $\mathbf{x}_{2}$, and
$\mathbf{x}_{3}$ with the same dimensionality $d$. If $\mathbf{x}_{1}$
satisfies that, for $i\in[1,d]$,
$\mathbf{x}_{2}[i]-\mathbf{x}_{3}[i]\leq\mathbf{x}_{1}[i]\leq\mathbf{x}_{2}[i]+\mathbf{x}_{3}[i]$,
we write $\mathbf{x}_{1}\in[\mathbf{x}_{2}\pm\mathbf{x}_{3}]$. . By the
definition of $\delta_{a}$, for a node $v\in\mathcal{V}_{a}$, we have
$\mathbf{x}_{v}\in[\mathbf{\mu}_{a}\pm\delta_{a}*\mathbbm{1}]$, where
$\mathbbm{1}\in\mathbb{R}^{d}$ is an all one vector. By the definition of
$\mathbf{h}_{v}$, we have
$\mathbf{h}_{v_{i}}\in[\sum_{v_{j}\in\mathcal{V}_{a}}\tilde{\mathbf{A}}[i,j]\mathbf{\mu}_{a}+\sum_{v_{j}\in\mathcal{V}_{\neq
a}}\tilde{\mathbf{A}}[i,j]\mathbf{\mu}_{\neq a}\pm\delta_{a}*\mathbbm{1}]$.
Thus, the mean node embedding
$\frac{\sum_{v_{i}\in\mathcal{V}_{a}}\mathbf{h}_{v_{i}}}{|\mathcal{V}_{a}|}\in[\beta{[a,a]}\mu_{a}+\beta{[a,\neq
a]}\mu_{\neq a}\pm\delta_{a}*\mathbbm{1}]$. Similarly, we have the mean node
embedding $\frac{\sum_{v_{i}\in\mathcal{V}_{\neq
a}}\mathbf{h}_{v_{i}}}{|\mathcal{V}_{\neq a}|}\in[\beta[\neq
a,a]\mu_{a}+\beta[\neq a,\neq a]\mu_{\neq a}\pm\delta_{a}*\mathbbm{1}]$.
Therefore, we have
$\frac{\sum_{v_{i}\in\mathcal{V}_{a}}\mathbf{h}_{i}^{K}}{|\mathcal{V}_{a}|}-\frac{\sum_{v_{i}\in\mathcal{V}_{\neq
a}}\mathbf{h}_{i}^{K}}{|\mathcal{V}_{\neq a}|}\in[(\beta[a,a]-\beta[\neq
a,a])\mu_{a}+(\beta[a,\neq a]-\beta[\neq a,\neq a])\mu_{\neq a}\pm
2\delta_{a}*\mathbbm{1}]$. Since $\beta[a,\neq a]=1-\beta[a,a]$ and
$\beta[\neq a,\neq a]=1-\beta[\neq a,a]$, the vector range can be written as
$\frac{\sum_{v_{i}\in\mathcal{V}_{a}}\mathbf{h}_{i}^{K}}{|\mathcal{V}_{a}|}-\frac{\sum_{v_{i}\in\mathcal{V}_{\neq
a}}\mathbf{h}_{i}^{K}}{|\mathcal{V}_{\neq a}|}\in[(\beta[a,a]-\beta[\neq
a,a])(\mu_{a}-\mu_{\neq a})\pm 2\delta_{a}*\mathbbm{1}]$. Thus,
$\lVert\frac{\sum_{v_{i}\in\mathcal{V}_{a}}\mathbf{h}_{i}^{K}}{|\mathcal{V}_{a}|}-\frac{\sum_{v_{i}\in\mathcal{V}_{\neq
a}}\mathbf{h}_{i}^{K}}{|\mathcal{V}_{\neq
a}|}\rVert_{2}\leq|\beta[a,a]-\beta[\neq a,a]|*\lVert\mu_{a}-\mu_{\neq
a}\rVert_{2}+2\sqrt{d}\delta_{a}$. Plugging the above inequality into Equation
4, we have
$\hat{\mathcal{L}}_{\text{dp}}^{a}\leq\lVert\mathbf{W}\rVert_{2}*(|\beta[a,a]-\beta[\neq
a,a]|*\lVert\mu_{a}-\mu_{\neq a}\rVert_{2}+2\sqrt{d}\delta_{a})$.

Plugging in the upper bound of each term in $\hat{\mathcal{L}}_{\text{dp}}$,
we have Equation 3. ∎

Equation 3 indicates three sources of poor demographic parity of GCNs, namely,
node attribute bias $\lVert\mu_{a}-\mu_{\neq a}\rVert_{2}$, graph structure
bias $|\beta[a,a]-\beta[\neq a,a]|$, and model parameters $\mathbf{W}$. In the
literature, some techniques have been developed to reduce node attribute bias
and model parameter bias [24, 55, 32, 6]. In addition to debiasing node
features and GCN parameters, Equation 3 suggests that we can further improve
the demographic parity of a GCN by mitigating the graph structure bias. In
particular, we can regulate the graph structure such that
$\beta{[a,a]}=\beta{[\neq a,a]}$.

A solution that eliminates graph structure biases is to process the graph
structures by adding and removing edges so that each node $v$ has a balanced
neighborhood, that is, $\Gamma_{v}$ has the same number of nodes from each
sensitive group. Formally, $\forall a_{i},a_{j}\in\mathcal{A}$, we want
$|\Gamma_{v}\cap\mathcal{V}_{a_{i}}|=|\Gamma_{v}\cap\mathcal{V}_{a_{j}}|$.

(a)

(b)

(c)

Figure 2: An example showing the intuition of the FairSample approach. (a) An
input graph to FairSample. (b) The augmented graph after injecting an inter-
group edge. (c) Jointly train the sampling policy $f_{S}$ and the 2-layer GCN
node classifier $f_{G}$ with the computation graph of a node $v_{1}$.

A remaining question is which edges should be changed. A straightforward
strategy is to pre-process the input graph $\mathcal{G}$ by randomly adding
and removing edges so that each node has a balanced neighborhood. This method,
however, may not work well, as $\mathcal{G}$ is modified without considering
the utility for training GCNs. As a result, too many noisy edges may be
introduced into $\mathcal{G}$ and the GCNs trained on the changed graph may
not be useful [56, 57]. Thus, an ideal method for graph structure bias
reduction should alter the edges in a way that minimizes
$|\beta[a,a]-\beta[\neq a,a]|$ and maintains the prediction power of GCNs
built on the modified graph. This is our major insight driving the development
of our method in this paper.

Based on the above intuition, we define the problem of _learning a demographic
parity fairness-aware sampling strategy for GCNs_. Given a graph
$\mathcal{G}=(\mathcal{V},\mathcal{E},\mathbf{X})$, where there is a sensitive
attribute $\mathcal{A}\in\mathcal{X}$ and the sensitive values of the nodes
are $\mathbf{S}=\\{s_{1},\ldots,s_{n}\\}$, and a set of labeled node
$\mathcal{V}_{L}\subseteq\mathcal{V}$ with corresponding binary labels
$Y_{L}$, we aim to design a sampling strategy that can mitigate graph
structure bias and learn a fair graph convolutional neural network
$f(\mathcal{G},\mathbf{S},\mathcal{V}_{L},Y_{L})\rightarrow\hat{Y}_{U},$ where
$\hat{Y}_{U}$ is the set of predicted labels of unlabeled nodes
$U=\mathcal{V}\setminus\mathcal{V}_{L}$. The learned GCN should have high
accuracy and good demographic parity.

##  5 FairSample: Sampling for Fair GCNs

In this section, motivated by the analysis in Section 4, we develop
FairSample, a two-phase framework for training demographic parity fair GCNs
and retaining scalability and accuracy.

###  5.1 The Framework of FairSample

A graph is _homophilic_ with respect to the sensitive values if the nodes with
the same sensitive value are more likely to be connected. In this paper, we
assume homophilic input graphs, which are widely observed in real world social
networks [6, 7, 11]. Our method can be easily adapted to heterophilic graphs
as discussed at the end of this subsection, where the nodes with the same
sensitive value are less likely to be connected.

Our analysis in Section 4 suggests that we can strengthen demographic parity
in node classification by learning node embeddings with balanced
neighborhoods. Dai et al. [56] suggest that the accuracy in node
classification can be improved by aggregating embeddings from informative
neighbors. A neighbor node $u$ of a node $v$ is _informative_ with respect to
$v$, if $u$ and $v$ have similar node feature vectors [56, 22]. Based on the
two intuitions, our framework trains a fair and accurate GCN by modifying the
computation graphs in training a GCN so that each node aggregates embeddings
from a set of balanced and informative neighbors.

There are two major challenges. First, we have to handle nodes with dominating
intra-group connections, which may lead to bias in graph structure. Intra-
group connections are edges between the nodes with the same sensitive values.
Inter-group connections are edges between the nodes with different sensitive
values. If all neighbors of a node $v$ have the same sensitive values, there
is no way for $v$ to aggregate embeddings from diverse sensitive groups.
Second, we need to sample the edges for embedding aggregation in GCN training
so that we can learn GCNs with good accuracy, demographic parity, and
scalability. An edge sampling method not carefully designed may not help with
either model accuracy [56, 57] or model demographic parity [8, 7].

FairSample tackles the two challenges in a two-phase framework. In phase 1,
FairSample uses an edge injector $f_{E}$ to augment the input graph
$\mathcal{G}$ by adding inter-group edges to improve the inter-group
connectivity of the graph. As the injected edges may introduce noise into the
data, the accuracy of the GCN classifier $f_{G}$ built on the modified graph
may be hurt [56]. To alleviate the problem, we only connect similar nodes with
the same class labels. As justified by Dai et al. [56], adding such
connections can benefit the accuracy of GCNs. Phase 1 improves the
heterophilic neighborhood for nodes with dominated intra-group connections.

######  Example 2 (Phase 1).

Consider the input graph in Figure 2a, where each node has a binary sensitive
value (represented by the colors of the nodes) and a binary class label
(represented by the shapes of the nodes). Node $v_{5}$ and node $v_{1}$ are
similar nodes with the same class label, since the distance between the two
nodes in the graph is short, only $2$. At the same time, they have different
sensitive values. Thus, in Phase 1, FairSample may connect the two nodes and
obtain the graph shown in Figure 2b.

In phase 2, FairSample uses reinforcement learning to learn a computation
graph sampling policy $f_{S}$. The policy samples the edges in the computation
graphs for training $f_{G}$ such that the loss of fairness and utility
(Equation 2) of $f_{G}$ can be minimized. FairSamlpe jointly learns $f_{G}$
and $f_{S}$ on the graph augmented by $f_{E}$.

######  Example 3 (Phase 2).

Figure 2c shows the training process of $f_{S}$ and a 2-layer GCN $f_{G}$
using the augmented input graph in Figure 2b, where the left part shows the
sampling operations on the computation graph $\mathcal{T}$ of $v_{1}$ and the
right part shows the computation of the loss function $\mathcal{L}$ of $f_{G}$
following the sampled computation graph. The policy $f_{S}$ samples
$\mathcal{T}$ in a top-down breadth-first manner. Up to 2 child nodes per node
in $\mathcal{T}$ are sampled. First, the child nodes $v_{2}$ and $v_{5}$ of
the root node $v_{1}$ are sampled. Then, $f_{S}$ iteratively samples the child
nodes of $v_{2}$ and $v_{5}$ to obtain the sampled computation graph
$\mathcal{T}^{\prime}$. The classifier $f_{G}$ computes the loss function
$\mathcal{L}$ following $\mathcal{T}^{\prime}$ and optimizes its parameters
using the backpropagation. FairSample uses the value of $\mathcal{L}$ as the
reinforcement signal to train the policy $f_{S}$ to minimize $\mathcal{L}$.

Through this reinforcement learning process, $f_{S}$ helps each node in
$\mathcal{T}^{\prime}$ to aggregate embeddings from a set of neighbors that
can improve the demographic parity and accuracy of $f_{G}$.

To adapt FairSample to heterophilic input graphs, we can use the edge injector
$f_{E}$ to add intra-group edges and enhance the graph’s intra-group
connectivity.

###  5.2 Edge Injector

Theorem 3 suggests that injecting inter-group edges into the input graph may
improve the demographic parity of the GCN built on the modified graph. To
improve the demographic parity and retain the prediction quality of the GCN
being trained, we pre-process the input graph by adding inter-group edges
connecting similar nodes with the same class labels. A challenge in
implementing the strategy is that we only know the labels of
$\mathcal{V}_{L}$, which usually only contains a very small number of nodes.
As a result, we can only inject edges between a small number of nodes and the
benefits from our edge injection strategy may be severely limited. To tackle
the challenge of label sparsity, we can add accurate pseudo labels to some of
the unlabeled nodes [56, 58]. Let
$\mathcal{V}^{\prime}_{L}=\mathcal{V}_{L}\cup\mathcal{V}_{P}$ be the augmented
set of labeled nodes, where $\mathcal{V}_{P}$ is the set of nodes with pseudo
labels. With more labeled and pseudo-labeled nodes, our edge injection
strategy can create more inter-group edges to better mitigate graph structure
bias.

We use a GCN as the pseudo label predictor, which utilizes both node features
and graph structures to make accurate label predictions. To obtain accurate
pseudo labels, we follow the existing work [56, 58] and only keep the pseudo
labels with confidence scores larger than a threshold $\tau$. Our framework
can take any GNN models as the pseudo label predictor.

Next, we introduce our edge injection strategy. As two nodes with a small
shortest-path distance in the graph are more similar [59], we limit that two
nodes $v_{i},v_{j}\in\mathcal{V}^{\prime}_{L}$ are connected by $f_{E}$ only
if their shortest-path distance is smaller than or equal to $h$. Specifically,
our edge injector proceeds as follows.

Let $C_{v}$ be the set of nodes in the $h$-hop neighborhood of $v$ that have
the same class labels as $v$ but different sensitive values from $v$. For each
node $v\in\mathcal{V}^{\prime}_{L}$, $f_{E}$ uniformly randomly picks at most
$\min\\{m,|C_{v}|\\}$ nodes in $C_{v}$ and connects them with $v$. We set $h$
to 2 in this work to reduce the computational cost for searching $C_{v}$ and
avoid the over-smooth issue [60, 61] that may significantly degrade the
accuracy of GCNs. As $f_{E}$ injects inter-group edges in a heuristic manner,
it may introduce noisy edges into the data and negatively affect the utility
of the GCNs being trained. However, as we apply the computation graph sampler
$f_{S}$ to pick informative neighbors for GCN training, the noisy edges may
not be used and thus their negative effect on the accuracy of the GCN may be
reduced. This is because the sampler is trained to optimize the loss of
demographic parity and utility of the target GCN classifier. If an edge
significantly degrades the utility of the target GCN classifier, that edge may
not be selected by the sampler. Our empirical study in Section 6.5 shows that
the edge injection strategy can improve the fairness of the trained GCN
classifiers without sacrificing accuracy in most cases.

###  5.3 Computation Graph Sampler

Now, we introduce our computation graph sampler $f_{S}$ for training a fair,
accurate, and scalable GCN $f_{G}$. The sampler $f_{S}$ is learned by
reinforcement learning to optimize the loss $\mathcal{L}$ of fairness and
utility of $f_{G}$.

An ideal computation graph sampling method should improve the demographic
parity of the target GCN classifier $f_{G}$ and maintain the utility of
$f_{G}$. Stratified node sampling with respect to the sensitive values can
select a balanced set of nodes for feature aggregation, which benefits the
demographic parity of $f_{G}$ according to Theorem 3. This method, however,
may not train an accurate $f_{G}$, as it does not consider the informativeness
of the nodes. Node similarity sampling for feature aggregation, on the one
hand, can benefit the accuracy of $f_{G}$ [57, 22] and, on the other hand,
cannot improve the demographic parity of $f_{G}$, as it cannot reduce the
structure bias of the input graph.

To train GCNs with good demographic parity and high accuracy, we propose a
computation graph sampler $f_{S}$, which leverages reinforcement learning to
combine the sampling results from the stratified sampling method and the
similarity sampling method. Our key idea in $f_{S}$ is to sample the
computation graphs $\mathcal{T}$ in the GCN $f_{G}$ such that each node in the
sampled computation graph aggregates embeddings from a balanced and
informative set of child nodes. Specifically, $f_{S}$ down-samples
$\mathcal{T}$ in a top-down breadth-first manner. The sampler $f_{S}$ starts
from the root node $v$ of $\mathcal{T}$. Following the sampling framework by
Yoon et al. [22], $f_{S}$ samples $k$ child nodes of $v$ with replacement and
discards the duplicate sampled nodes to get a set of up to $k$ sampled child
nodes $p(v)$. A child node $v_{i}$ of $v$ is sampled following the probability
$\text{P}(v_{i}|v)$, which is a parameterized function taking the feature
vectors of $v_{i}$ and $v$ as input. Then, for each $v_{i}\in p(v)$, $f_{S}$
samples a set of child nodes $p(v_{i})$ by repeating the above steps. The
sampler $f_{S}$ iteratively operates on each sampled node in $\mathcal{T}$
until reaching the leaves of $\mathcal{T}$. We use sampling with replacement
here to ensure independence among samples.

After getting the sampled computation graphs $\mathcal{T}^{\prime}$, we apply
the classifier $f_{G}$ to compute node predictions following
$\mathcal{T}^{\prime}$ and calculate the loss function $\mathcal{L}$
correspondingly. Then, we update the parameters of $f_{S}$ and $f_{G}$ to
minimize $\mathcal{L}$. We update the parameters of $f_{G}$ using
backpropagation. Since the sampling operation is non-differentiable [1], we
cannot directly train the parameters of $f_{S}$ using the gradients of
$\mathcal{L}$. To address this challenge, FairSample uses the log derivative
technique in reinforcement learning [62] to train sampling policies.

The probability $\text{P}(v_{j}|v_{i})$ of sampling a child node $v_{j}$ of
$v_{i}$ is computed based on two components, node similarity sampling
$q_{\text{sim}}(v_{j}|v_{i})$ and stratified sampling
$q_{\text{fair}}(v_{j}|v_{i})$. The component
$q_{\text{sim}}(v_{j}|v_{i})=(\mathbf{x}_{i}\mathbf{W}_{s})\cdot(\mathbf{x}_{j}\mathbf{W}_{s})$
is designed to improve model accuracy, where
$\mathbf{W}_{s}\in\mathbb{R}^{d\times d_{s}}$ is a feature transformation
matrix and $d_{s}$ is the dimensionality of the transformed features. It
assigns higher probabilities to the child nodes that have similar features as
$v_{i}$, and thus helps to sample informative child nodes that can benefit the
accuracy of GCNs [57]. The component
$q_{\text{fair}}(v_{j}|v_{i})=\frac{1}{|\Gamma_{v_{i}}\cap\mathcal{V}_{s_{j}}|}$
is designed to improve model fairness. It assigns higher probabilities to the
minority sensitive groups in the child nodes $\Gamma_{v_{i}}$ of $v_{i}$, and
thus helps to sample a set of child nodes with balanced sensitive values. An
attention mechanism is applied to perform a tradeoff between the two
components. Specifically, we define
$\text{P}(v_{j}|v_{i})=\frac{q(v_{j}|v_{i})}{\sum_{v\in\Gamma_{v_{i}}}q(v|v_{i})}$,
where $q(v_{j}|v_{i})=\mathbf{a}\cdot\langle
q_{\text{sim}}(v_{j}|v_{i}),q_{\text{fair}}(v_{j}|v_{i})\rangle$ and
$\mathbf{a}\in\mathbb{R}^{2}$ is an attention vector. The attention vector
$\mathbf{a}$ learns which component is more effective on optimizing the loss
$\mathcal{L}$ of $f_{G}$. Both $\mathbf{W}_{s}$ and $\mathbf{a}$ are learnable
parameters of our sampling policy and are shared by all nodes in
$\mathcal{V}$.

FairSample borrows the training mechanism by Yoon et al. [22] to learn the
parameters $\theta=(\mathbf{W}_{s},\mathbf{a})$ of $f_{S}$. The gradient of
$\mathcal{L}$ with respect to $\theta$ is estimated as
$\nabla_{\theta}\mathcal{L}\approx\frac{d}{d\theta}(\frac{1}{|\mathcal{T}_{1}^{\prime}|}\sum_{v_{i}\in\mathcal{T}^{\prime}_{1}}\frac{d\mathcal{L}}{d\mathbf{h}^{1}_{v_{i}}}\mathbb{E}_{v_{j}\in
p(v_{i})}[\log\text{P}(v_{j}|v_{i})\mathbf{x}_{j}]),$ where
$\mathcal{T}^{\prime}_{1}$ is the set of nodes in the first layer of the
sampled computation graph $\mathcal{T}^{\prime}$, $\mathbf{h}^{1}_{v_{i}}$ is
the embedding of $v_{i}$ following $\mathcal{T}^{\prime}$, and $p(v_{i})$ is
the set of child nodes of $v_{i}$ in $\mathcal{T}^{\prime}$.

######  Example 4.

Continue the training process of $f_{S}$ in Figure 2c, which is discussed in
Example 3. Among the child nodes of the root node $v_{1}$, $v_{5}$ has the
largest sampling probability, as $v_{5}$ not only has features similar to
those of $v_{1}$ (large $q_{sim}(v_{5}|v_{1})$) but also belongs to the
minority sensitive group in $\Gamma_{v_{1}}$ (large
$q_{\text{fair}}(v_{5}|v_{1})$).

The optimization framework [22] utilized by FairSample is principled and
general. It can readily accommodate various definitions of $\mathcal{L}_{dp}$
as long as $\mathcal{L}_{dp}$ is differentiable, such as the many proposed in
literature [6, 8, 32, 19]. In literature, some definitions of
$\mathcal{L}_{dp}$ are based on the adversarial learning framework [6, 19] and
are prone to be unstable during training [63]. In our experiments, we choose
the well-adopted definition [32], that is,

$\mathcal{L}_{dp}=\sum_{a\in\mathcal{A}}\left|\frac{\sum_{v_{i}\in\mathcal{V}_{a}}f(v_{i})}{|\mathcal{V}_{a}|}-\frac{\sum_{v_{j}\in\mathcal{V}_{\neq
a}}f(v_{j})}{|\mathcal{V}_{\neq a}|}\right|,$

where $f(v_{i})$ is the predicted probability of the positive label, and
$\mathcal{V}_{a_{i}}$ and $\mathcal{V}_{\neq a_{i}}$ are the sets of nodes
taking and not taking the sensitive value $a_{i}$, respectively. The adopted
$\mathcal{L}_{dp}$ is stable during training, efficient to compute, and
empirically well-performed.

##  6 Empirical Study

In this section, we evaluate the performance of our FairSample framework for
training demographic parity fair GCN classifiers and compare with the state-
of-the-art baselines.

###  6.1 Datasets and Experiment Settings

####  6.1.1 Dataset

We conducted experiments using a LinkedIn production dataset and five public
fair GCN benchmark datasets [6]. Table II shows some statistics of the
datasets.

TABLE II: Some statistics of the datasets. “Intra. ratio”, “Sens.”, and “Nation.” are short for “Intra-group edge ratio”, “Sensitive attribute”, and “Nationality”, respectively. Dataset | NBA | PNL | PZL | PNG | PZG | LNKD
---|---|---|---|---|---|---
Nodes | 403 | 66,569 | 67,797 | 66,569 | 67,797 | 40,000
Edges | 16,570 | 729,129 | 882,765 | 729,129 | 882,765 | 6,002,612
Intra. ratio | 73% | 95% | 96% | 47% | 46% | 73%
Sens. | Nation. |  Living region |  Living region | Gender | Gender |  Level
Task |  Income level | Job | Job | Job | Job | Industry

The Pokec-n and Pokec-z datasets are subnetworks of a social network Pokec
[64] in Slovakia, where the nodes are users and the edges are their
connections. Pokec-n and Pokec-z are created by sampling the users from two
provinces, Nitriansky and Zilinsky, respectively. Each dataset consists of the
users from the two major living regions of the corresponding province. The
feature vector of a node is generated based on the corresponding user’s
profile, including living region, gender, spoken language, age, etc. We use
living region and gender as the sensitive attributes and conduct separate
experiments for each. Both living region and gender are binary variables. The
living region represents one of the two major living regions within each
corresponding province. Denote by PNL and PZL the Pokec-n and Pokec-z datasets
with living region as the sensitive attribute, respectively. Similarly, we
denote the Pokec-n and Pokec-z datasets with gender as the sensitive attribute
as PNG and PZG, respectively. As shown in Table II, PNL and PZL datasets are
homophilic, as there are more intra-group edges than inter-group edges in the
graphs. Similarly, PNG and PZG datasets are heterophilic. The classification
task is to predict whether a user is a student.

The NBA dataset consists of 403 NBA players as the nodes and their
relationships on Twitter as the edges. The binary sensitive attribute of a
player is whether a player is a U.S. or oversea player. The classification
task is to predict whether the salary of a player is over the median. The
feature vector of a node is generated based on the corresponding player’s
profile, including performance statistics, height, age, etc. The input graph
is homophilic.

The LNKD dataset is a subset of the LinkedIn social networks where the nodes
are alumni from a US university, and the edges are the connections between
them. The binary sensitive attribute of a user is the user’s seniority level,
high or low. The classification task is to predict whether a user is suitable
for working in the “Hospital & Health Care” industry. The feature vector of a
node is generated based on the corresponding user’s profile. The dataset is
homophilic.

For the five large datasets, we follow the same setting used by Dai et al.
[6], where we randomly sample 500 labeled nodes as the training set, 25% of
the labeled nodes as the validation set, and 25% of the labeled nodes as the
test set. On the NBA dataset where the total number of nodes is less than 500,
we randomly sample 50% of the labeled nodes as the training set instead. The
training, validation, and test sets have no overlaps. We generate $5$ sets of
training, validation, and test datasets with different random seeds for each
dataset.

####  6.1.2 Baselines

We compare the performance of FairSample (FS for short in the tables and
figures) with 12 representative baselines belonging to three categories,
namely, graph neural networks (GNNs) without fairness constraints, pre-
processing fairness methods, and in-processing fairness methods.

GAT [65], DGI [66], and GCA [67] are famous GNNs without fairness constraints,
which only aim to optimize model utility. GAT learns node classifiers in an
end-to-end fashion. DGI and GCA employ contrastive objective functions to
learn node embeddings in an unsupervised manner. We train a logistic
regression on top of the embeddings learned by DGI and GCA, respectively, to
predict node labels.

We include three pre-processing fairness enhancing methods for GNNs. FairAdj
[8] modifies the adjacency matrix of the input graph to enforce fairness
constraints. A GNN is used to learn node embeddings on the modified adjacency
matrix. FCGE [19] is an adversarial framework to enforce fairness constraints
on node embeddings. The embeddings are optimized to confuse a discriminator,
which is jointly trained to predict the sensitive attribute value of a node
from its embedding. FairAj and FCGE perform node classifications in the same
way as DGI. EDITS [15] mitigates the unfairness in GNNs by producing unbiased
training data. EDITS debiases the input graph by altering its adjacency matrix
and node attributes. We train a classic two-layer GCN [2] on top of the
debiased graph to predict node labels.

Last, we include six in-processing fairness enhancing methods. GraphSage [20]
and PASS [22] are celebrated sampling frameworks to efficiently train GCN
classifiers. Stratified-GraphSage is an extension of GraphSage by performing
stratified sampling within sensitive groups to sample nodes for embedding
aggregation. It performs embedding aggregation using a more balanced
neighborhood than GraphSage. The probability of sampling a neighbor $v_{j}$ of
a node $v_{i}$ is set to
$\text{P}(v_{j}|v_{i})=\frac{1}{|\mathcal{A}|\cdot|\Gamma_{v_{i}}\cap\mathcal{V}_{s_{j}}|}$.
To enforce fairness in GCN classifiers, the three methods train GCNs by
adopting the same demographic parity regularizer as FairSample does. GSR,
PASSR, and SGSR are short for GraphSage, PASS, and Stratified-GraphSage with
the demographic parity regularizer, respectively. FairGNN [6] is a state-of-
the-art method for fair node classification tasks under the constraint of
demographic parity. FairGNN adopts an adversarial framework [19] to rectify
the final layer representations in the target GNN classifier. We test a
2-layer GCN and a 2-layer GAT as the backbones of FairGNN, denoted by FGCN and
FGAT, respectively. NIFTY [16] leverages contrastive learning to train GNNs
under the constraint of counterfactual fairness. The method generates
augmented counterfactual views of the input graph by flipping the node
sensitive values. A 2-layer multi-layer perceptron (MLP) [68] predicts the
node labels using only the node feature vectors. MLP adopts the same
demographic parity regularizer as FairSample to enforce fairness.

####  6.1.3 Implementation Details and Parameter Settings

All GCN methods in our experiments train 2-layer GCNs with non-linear
activation functions. FairSample adopts a celebrated 2-layer GCN [2] as the
pseudo label predictor. To be consistent, the dimensionalities of the node
embeddings in all methods are set to 64.

TABLE III: The comparison between FairSample and the baselines. OOM is short for “out of memory”. For the LNKD dataset, $x$ and $y$ are the anonymized mean accuracy and $\Delta DP$ of FairSample, respectively. Performance of the baselines on the LNKD dataset are presented in the difference with respect to FairSample. FairSample outperforms all baselines up to 65.5% in fairness improvement only at the cost of at most 5.0% classification accuracy drop. The best records are in bold. Method | NBA | PNL | PZL | PNG | PZG | LNKD
---|---|---|---|---|---|---
ACC (%) |  $\triangle$DP (%) | ACC (%) |  $\triangle$DP (%) | ACC (%) |  $\triangle$DP (%) | ACC (%) |  $\triangle$DP (%) | ACC (%) |  $\triangle$DP (%) | ACC (%) |  $\triangle$DP (%)
GAT | 71.4$\pm$5.1 |  11.9$\pm$8.9 |  65.4$\pm$5.0 |  3.8$\pm$1.4 |  66.8$\pm$4.7 |  7.6$\pm$4.3 | 68.0$\pm$1.0 |  10.4$\pm$1.6 |  65.1$\pm$4.9 |  5.3$\pm$2.4 |  (x-1.9)$\pm$0.7 |  (y+6.8)$\pm$5.5
DGI |  70.4$\pm$3.3 |  14.7$\pm$1.2 |  67.1$\pm$2.1 |  2.4$\pm$1.3 |  67.7$\pm$0.4 |  5.8$\pm$2.0 |  65.6$\pm$1.8 |  11.4$\pm$3.2 |  66.3$\pm$1.2 |  2.3$\pm$0.8 |  (x-5.8)$\pm$0.8 |  (y+3.1)$\pm$1.7
GCA |  68.1$\pm$4.7 |  14.2$\pm$6.1 |  65.3$\pm$1.5 |  2.7$\pm$2.1 |  67.0$\pm$1.0 |  4.7$\pm$2.0 |  66.8$\pm$1.0 |  9.6$\pm$2.4 |  67.0$\pm$1.1 |  3.5$\pm$0.5 | OOM | OOM
EDITS |  60.0$\pm$5.9 |  17.4$\pm$10.0 | OOM | OOM | OOM | OOM | OOM | OOM | OOM | OOM | OOM | OOM
FairAdj |  70.4$\pm$7.5 |  10.4$\pm$5.6 | OOM | OOM | OOM | OOM | OOM | OOM | OOM | OOM | OOM | OOM
FCGE |  67.8$\pm$7.5 |  8.6$\pm$7.1 |  64.3$\pm$2.5 |  7.1$\pm$1.5 |  67.3$\pm$0.6 |  2.4$\pm$1.5 |  67.2$\pm$1.3 |  10.0$\pm$2.6 |  66.9$\pm$0.7 |  2.6$\pm$1.3 |  (x-10.1)$\pm$2.7 |  (y+7.2)$\pm$5.7
MLP |  66.8$\pm$3.1 |  13.4$\pm$10.7 |  64.3$\pm$1.4 |  2.0$\pm$1.6 |  66.6$\pm$0.6 |  3.0$\pm$1.9 |  63.8$\pm$1.0 |  4.9$\pm$2.4 |  65.4$\pm$1.6 |  2.9$\pm$1.6 |  (x-0.4) $\pm$ 0.8 |  (y+3.6)$\pm$3.3
GSR |  62.0$\pm$4.6 |  7.7$\pm$5.6 | 67.7$\pm$1.1 |  1.1$\pm$0.5 | 68.0$\pm$0.5 |  2.1$\pm$0.9 |  67.0$\pm$1.0 |  7.5$\pm$3.0 |  66.5$\pm$0.7 |  1.7$\pm$1.0 |  (x-7.2)$\pm$2.5 |  (y+4.9)$\pm$2.6
SGSR |  56.2$\pm$2.8 |  8.6$\pm$9.3 |  66.3$\pm$1.3 |  1.4$\pm$0.7 |  67.5$\pm$0.5 |  2.3$\pm$1.5 |  65.5$\pm$0.9 |  11.0$\pm$1.4 |  65.7$\pm$0.8 |  3.0$\pm$1.3 |  (x-7.1)$\pm$2.6 |  (y+1.9)$\pm$1.8
PASSR |  66.1$\pm$2.2 |  6.5$\pm$6.6 |  67.3$\pm$1.1 |  1.1$\pm$0.6 |  67.6$\pm$0.3 |  1.5$\pm$0.9 |  67.0$\pm$0.4 |  10.7$\pm$1.8 | 67.1$\pm$0.7 |  2.2$\pm$1.3 |  (x-0.2)$\pm$1.9 |  (y+2.0)$\pm$1.9
FGCN |  67.8$\pm$4.7 |  11.7$\pm$2.2 |  66.2$\pm$1.3 |  2.5$\pm$1.1 |  66.3$\pm$1.3 |  2.7$\pm$1.2 |  66.6$\pm$0.7 |  5.3$\pm$2.3 |  66.5$\pm$0.8 |  2.9$\pm$1.1 |  (x-2.2)$\pm$5.1 |  (y+3.8)$\pm$2.8
FGAT |  66.1$\pm$5.6 |  16.8$\pm$11.3 |  67.1$\pm$1.5 |  2.4$\pm$0.8 |  65.3$\pm$1.8 |  3.1$\pm$1.8 |  66.9$\pm$0.7 |  6.2$\pm$4.2 |  66.7$\pm$2.0 |  2.6$\pm$1.6 |  (x-5.5)$\pm$2.9 |  (y+7.6)$\pm$4.7
NIFTY |  59.0$\pm$9.9 |  7.8$\pm$8.8 |  64.7$\pm$2.1 |  6.5$\pm$1.0 |  66.3$\pm$1.1 |  5.4$\pm$1.5 |  65.5$\pm$1.6 |  13.3$\pm$0.8 |  63.9$\pm$2.6 |  1.7$\pm$0.6 |  (x-8.9)$\pm$1.3 |  (y+11.1)$\pm$5.3
FS |  67.8$\pm$4.3 | 6.2$\pm$6.9 |  67.4$\pm$0.6 | 0.9$\pm$0.5 |  67.7$\pm$0.7 |  1.1$\pm$0.9 |  67.2$\pm$0.6 | 4.7$\pm$2.1 | 67.1$\pm$0.5 | 1.4$\pm$1.3 |  x$\pm$0.6 | y$\pm$0.9
FS(noise) |  67.3$\pm$3.4 |  10.1$\pm$2.6 |  67.3$\pm$0.7 |  1.0$\pm$0.7 |  67.5$\pm$1.1 | 0.9$\pm$0.7 |  66.8$\pm$0.6 |  5.2$\pm$2.0 |  67.0$\pm$0.6 |  2.3$\pm$1.4 | (x+0.2)$\pm$1.5 |  (y+1.4)$\pm$2.1

For the NBA dataset, we sample $k=10$ neighbors per node in the four sampling-
based methods, FairSample, GSR, SGSR, and PASSR. This is because, empirically,
we observe that the accuracies of the learned node classifiers are saturated
when $k=10$. For the same reason, we set $k=6$ for the LinkedIn dataset and
$k=20$ for the remaining four large datasets. All the other baselines are
allowed to use the full neighborhood to train GNNs. We test a wide range of
the demographic parity regularizer weight $\alpha\in\\{0,1,2,5,10\\}$ in the
loss functions of the sampling-based methods. We vary the hyperparameters of
the other fairness enhancing methods within the ranges suggested by their
authors to maximize their performance. We train the sampling-based methods for
300 epochs with an early stopping rule on validation loss. For the other
baselines, we use the suggested number of training epochs and early stopping
rules in the released source codes. In FairSample, we tune the number of
injected edges per node $m\in\\{0,4,\ldots,20\\}$ and fix the confidence
threshold of the pseudo label predictor $\tau=0.8$. FairGNN assumes that the
sensitive values of some nodes may be missing and employs an estimator to
predict the missing values. In our experiments, we observe that the worst
accuracy of the sensitive value estimator of FairGNN across all datasets is
78%. To fairly compare with FairGNN, we test a variant FairSample (Noise) of
FairSample. We uniformly randomly flip 22% of the sensitive values in each
dataset when FairSample (Noise) is run.

We use the published Python codes of GAT [69], DGI [70], GCA [71], FairAdj
[72], FCGE [73], FairGNN [69], EDITS [74], and NIFTY [75]. The remaining
algorithms are implemented in Python. All experiments are conducted on a
server with 8 Tesla P100 GPUs, and 672G main memory.

TABLE IV: The $p$-values of the hypothesis tests. The $p$-values that are less than the significance level $1\%$ are in bold. Method | GAT | DGI | GCA | MLP | EDITS | FairAdj | FCGE | GSR | SGSR | PASSR | FGCN | FGAT | NIFTY
---|---|---|---|---|---|---|---|---|---|---|---|---|---
ACC $p$-value | 0.64 | 0.98 | 0.94 | 0.99 | 0.90 | 0.98 | 0.99 | 0.99 | 0.99 | 0.91 | 0.99 | 0.99 | 0.99
$\Delta$DP $p$-value | $\mathbf{8e^{-6}}$ | $\mathbf{6e^{-7}}$ | $\mathbf{5e^{-6}}$ | $\mathbf{7e^{-4}}$ | 0.156 | $\mathbf{1e^{-3}}$ | $\mathbf{3e^{-7}}$ | $\mathbf{7e^{-4}}$ | $\mathbf{3e^{-4}}$ | $\mathbf{4e^{-4}}$ | $\mathbf{2e^{-4}}$ | $\mathbf{4e^{-4}}$ | $\mathbf{1e^{-5}}$

###  6.2 Can FairSample Learn Fair and Accurate GCNs?

We evaluate the performance, in demographic parity and accuracy, of FairSample
in learning GCNs. We use accuracy (ACC) to evaluate the utility of a learned
node classifier. Following the best practice in literature [10, 6], the
violation of demographic parity can be measured by $\Delta
DP=\text{max}_{a_{i_{1}},a_{i_{2}}\in\mathcal{A}}(|\mathbb{E}[f(\mathbf{x})|s=a_{i_{1}}]-\mathbb{E}[f(\mathbf{x})|s=a_{i_{2}}]|)$.
A classifier with a smaller $\Delta DP$ is more fair.

Following Donini et al. [31], we apply a two-step mechanism to choose the best
hyperparameter setting for each method. In the first step, we run each method
with each hyperparameter setting 5 times. The highest mean validation accuracy
$\text{Acc}_{best}$ across all the methods and hyperparameter settings is
identified. A validation accuracy threshold is set to
$\text{Acc}_{t}=\text{Acc}_{best}*0.95$. In the second step, for each method,
among the hyperparameter settings with mean validation accuracies higher than
$\text{Acc}_{t}$, we select the hyperparameter setting with the smallest mean
validation $\Delta DP$. If a method cannot learn a model with a mean
validation accuracy passing $\text{Acc}_{t}$, we pick the hyperparameter
setting with the best mean validation accuracy.

The performance of all methods is reported in Table III. GAT, DGI, and GCA
have poor fairness performance, as they only aim to optimize the accuracy of
GNNs. They do not achieve the best accuracy on all datasets. This is because
the fairness constraints on some baselines may act as regularizers, which
potentially reduce overfitting, and thus empirically improve generalization
performance [76, 77]. GCA does not scale up well as it uses the whole $K$-hop
neighborhoods of each node to train node embeddings, and hence suffers from
high memory footprints. FairSample uses a computation graph sampler with a
small number of parameters to down-sample the input graph. Thus, it enjoys
better scalability than GCA.

The pre-processing methods, EDITS, FairAdj, and FCGE do not have good
performance in either accuracy or fairness. As they learn node embeddings in
an unsupervised manner, they may not achieve a good performance in our node
classification tasks. FairAdj and EDITS cannot handle large datasets. As they
adjust the adjacency matrix by assigning a learnable parameter to each edge of
the input graph, these methods have a large memory consumption. FairSample has
better performance than the pre-processing methods, as it can explicitly
optimize the utility and fairness in training the node classifiers.

MLP has worse accuracy and fairness than FairSample, since the graph structure
information can help improve the accuracy in node classification [6].
Moreover, FairSample is more fair than MLP, as FairSample intelligently
aggregates feature vectors from nodes in different sensitive groups to
mitigate unfairness in predictions.

NIFTY has the worst fairness performance among the in-processing baselines, as
the method aims to optimize GNNs under the counterfactual fairness rather than
the demographic parity fairness. Despite using a sampled neighborhood,
FairSample achieves better accuracy than FairGNN. FairGNN also does not have
good fairness performance, as FairGNN only tries to improve fairness by
rectifying the parameters of GNNs and does not mitigate the bias in graph
structures. To the contrary, by rectifying both the model parameters and the
graph structures, FairSample achieves an outstanding performance of training
fair GCNs with good accuracies. The performance of FairSample (Noise) is
better than FairGNN, which indicates that FairSample is robust under sensitive
value noise. FairSample constantly outperforms PASSR and SGSR in both accuracy
and fairness. This is because their sampling strategies do not take both
utility and fairness into consideration.

FairSample constantly outperforms GSR in fairness with just a slight accuracy
loss on the PNL and PZL datasets. The reason is that our hyperparameter
selection method [31] favors fairness. Among all the hyperparameter settings
with accuracy above a certain threshold, we choose the one with the best
fairness performance. To conduct a more comprehensive comparison between
FairSample and GSR, we vary the hyperparameter settings of each method, and
find the Pareto frontier [78] between accuracy and $\Delta DP$. The Pareto
frontier of a method characterizes its optimal tradeoff between accuracy and
fairness [12]. A model has a better fairness-utility tradeoff if the model
achieves the same fairness level with better utility, and vice versa [8].
Figure 3 shows the mean and the standard deviation of $1-\Delta DP$ and the
accuracy of each hyperparameter setting in the Pareto frontier of each method
on the PNL and PZL datasets. Each point in the figure represents the
performance of a method with a specific hyperparameter setting. We observe
that FairSample is closer to the top right corner than GSR, indicating that
FairSample achieves a better fairness-utility tradeoff. For the same level of
fairness, FairSample can learn more accurate GCNs than GSR.

To study the statistical significance, for each baseline, we conduct the one
sided Wilcoxon signed-rank test [79] between FairSample and the baseline to
test if FairSample is more fair. The null hypothesis is that the $\Delta DP$
of FairSample is greater than or equal to that of the baseline method.
Similarly, we also conduct one sided Wilcoxon signed-rank tests to test if
FairSample is less accurate than the baselines. The $p$-values of the
hypothesis tests are reported in Table IV. It shows that FairSample is more
fair than all but one baselines with statistical significance. Although the
hypothesis test between the $\Delta DP$ of FairSample and EDITS is not
statistically significant, as shown in Table III, FairSample has substantially
better scalability than EDITS. Table IV also shows that there is no
statistical significance showing that FairSample is less accurate than any
baselines.

(a) PNL

(b) PZL

Figure 3: The demographic parity and accuracy tradeoff of the models trained
by FairSample and GSR. A point closer to the top-right corner is better.

The results clearly demonstrate that FairSample can learn fair and accurate
GCNs and outperform the baselines.

###  6.3 Can FairSample Mitigate Graph Structure Bias and Improve Fairness?

As explained in Section 4, mitigating the structure bias of an input graph may
improve the demographic parity of the GCNs built on graphs. To verify our
analysis, we evaluate the capability of FairSample in training fair GCNs by
reducing graph structure bias alone.

TABLE V: The comparison of FairSample with the baselines in training fair GCNs
without demographic parity regularizers in the loss functions. The results of
all methods on the LNKD dataset are reported in the same way as in Table III.
The best records are in bold.

Dataset Metrics GSR SGSR PASSR FSnr NBA ACC (%) 61.5$\pm$2.6 56.2$\pm$2.8
66.1$\pm$2.2 66.3$\pm$4.1 $\triangle$DP (%) 5.3$\pm$4.5 8.6$\pm$9.3
6.5$\pm$6.6 5.1$\pm$3.3 PNL ACC (%) 67.9$\pm$0.7 67.9$\pm$0.8 68.0$\pm$0.6
68.0$\pm$1.1 $\triangle$DP (%) 1.9$\pm$0.9 1.5$\pm$0.9 2.0$\pm$1.4 1.0$\pm$0.8
PZL ACC (%) 67.8$\pm$0.5 68.5$\pm$0.6 68.5$\pm$0.3 68.1$\pm$0.3 $\triangle$DP
(%) 6.6$\pm$2.1 6.6$\pm$2.2 6.2$\pm$1.4 5.7$\pm$1.1 PNG ACC (%) 66.5$\pm$0.7
65.5$\pm$0.9 67.0$\pm$0.4 67.5$\pm$0.8 $\triangle$DP (%) 11.1$\pm$2.3
11.0$\pm$1.4 10.7$\pm$1.8 10.0$\pm$2.3 PZG ACC (%) 66.4$\pm$0.9 65.5$\pm$1.5
67.2$\pm$1.0 67.6$\pm$0.6 $\triangle$DP (%) 2.4$\pm$2.1 2.8$\pm$1.2
1.8$\pm$1.6 1.6$\pm$1.0 LNKD ACC (%) (x-7.8)$\pm$1.0 (x-9.1)$\pm$1.1
(x-0.6)$\pm$1.9 x$\pm$1.0 $\triangle$DP (%) (y+5.7)$\pm$3.3 (y+6.5)$\pm$6.5
(y+1.0)$\pm$1.9 y$\pm$1.2

To demonstrate the effectiveness of our graph structure bias reduction
strategy, we disable the demographic parity regularizer in FairSample and
train GCNs with the cross-entropy loss function. Denote by FairSamplenr this
variant of FairSample. We compare FairSample with three sampling baselines.
The weight of the fairness regularizer for each of the three sampling
baselines, GSR, SGSR, and PASSR, is set to $0$. The mean and standard
deviation of the performance of all methods are reported in Table V.

GS performs poorly because it uniformly samples neighbors without fairness
consideration and results in discrimination between different sensitive groups
due to inheriting the graph structure bias. SGS sacrifices considerable model
accuracy in order to achieve fairness. PASS achieves the best accuracy but not
fairness score among the baselines, as its sampling policy is optimized for
model utility but not fairness. FairSamplenr employs a graph enrichment
strategy and a fairness-aware computation graph sampling strategy to reduce
graph structure bias and improve fairness. Therefore, it achieves superior
performance in training fair and accurate GCNs.

The experimental results strongly confirm that FairSample can mitigate graph
structure bias and improve fairness.

###  6.4 Convergence and Computational Cost

(a) The accuracy convergence curves of FairSample, FGAT, and NIFTY

(b) The $\Delta DP$ convergence curves of FairSample, FGAT, and NIFTY

(c) The accuracy convergence curves of FairSample, GSR, and PASSR

(d) The $\Delta DP$ convergence curves of FairSample, GSR, and PASSR

Figure 4: The accuracy and $\Delta DP$ convergence curves of FairSample, FGAT,
NIFTY, GSR, and PASSR across training epochs. For the sake of display clarity,
we report the results of PASSR and GSR separately from the other baselines in
Figures 4c and 4d.

We analyze the convergence and computational cost of FairSample and the
baselines in training fair GCNs.

Figure 4 shows the convergence curves of FairSample, PASSR, GSR, FGAT, and
NIFTY in accuracy and $\Delta DP$ on the PZL dataset. Similar observations are
obtained on the other datasets. We train each method 5 times and report the
mean accuracy and mean $\Delta DP$ on the test datasets across the training
epochs. FairSample, GSR, and PASSR converge and stop after around 100 training
epochs. FGAT and NIFTY require more epochs to converge, we report their
convergence curves across the first 500 training epochs.

FGAT has poor convergence performance in both accuracy and $\Delta DP$, as it
employs adversarial learning to train fair GNNs, which is known to be unstable
during training [63, 6]. NIFTY generates counterfactual graph views by
uniformly removing edges and node attributes, as well as flipping sensitive
values. However, removing some influential edges and node attributes may
deteriorate the utility of GCN classifiers [35]. Figure 4b shows that NIFTY
has the worst $\Delta DP$. This is because NIFTY is not explicitly designed to
optimize the demographic parity of GCNs.

Figures 4c and 4d show that FairSample converges very quickly with only around
50 training epochs. FairSample outperforms PASSR and GSR in training fair GCNs
with a clear margin. This is because FairSample modifies the computation
graphs of GCNs to rectify graph structure bias.

Figures 5a and 5b show the average training time and the average GPU memory
usage of FairSample and the other GNN baselines, respectively. It is worth
noting that the two baselines, EDITS and FairAdj, exhibit high GPU memory
consumption, which leads to the “out of memory” issue. Therefore, these two
methods are not included in the figure. Limited by space, we only report the
results on the PZG dataset. Similar observations are obtained on the other
datasets.

Clearly, FairSample is more efficient and consumes less GPU memory than the
non-sampling baselines, as FairSample leverages sampling strategies to reduce
the sizes of computation graphs. FairSample requires longer training time and
GPU memory than SGSR and GSR. The training time of SGSR, GSR, and FairSample
is 21.09, 21.56, and 32.27 seconds, respectively. The GPU memory costs of
SGSR, GSR, and FairSample are 1371, 1371, and 1413 MB, respectively. The two
baseline methods employ heuristic strategies for computation graph down-
sampling, while FairSample uses a learnable smart sampling strategy.
Therefore, FairSample has higher computational cost.

The experimental results confirm that FairSample brings only a small
computation overhead to train fair GCNs.

(a) Training time

(b) GPU Memeory Usage

Figure 5: The training time (in second) and GPU memory usage (in MB) of
FairSample and the baselines on the PZG dataset. The bars in the figures are
sorted in ascending order from left to right based on their values. The y-axis
is in logarithmic scale.

###  6.5 Ablation Study

TABLE VI: Comparison between FairSample and variants. The results of all
methods on the LNKD dataset are reported in the same way as in Table III. The
best records are in bold.

Dataset Metrics FSne FSns FSnr FS NBA ACC (%) 66.8$\pm$2.2 65.6$\pm$6.2
65.6$\pm$6.2 67.8$\pm$4.3 $\triangle$DP (%) 5.1$\pm$5.7 8.3$\pm$3.8
5.7$\pm$5.3 6.2$\pm$6.9 PNL ACC (%) 67.4$\pm$0.7 67.7$\pm$1.1 68.0$\pm$1.1
67.4$\pm$0.7 $\triangle$DP (%) 0.9$\pm$0.5 1.1$\pm$0.5 1.0$\pm$0.8 0.9$\pm$0.5
PZL ACC (%) 67.5$\pm$0.5 68.0$\pm$0.5 68.1$\pm$0.3 67.7$\pm$0.7 $\triangle$DP
(%) 1.5$\pm$0.7 2.1$\pm$0.9 5.5$\pm$1.1 1.1$\pm$0.9 PNG ACC (%) 67.2$\pm$0.6
67.0$\pm$1.0 67.5$\pm$0.8 67.2$\pm$0.6 $\triangle$DP (%) 4.7$\pm$2.1
7.5$\pm$3.0 10.0$\pm$2.3 4.7$\pm$2.1 PZG ACC (%) 66.9$\pm$1.0 66.4$\pm$0.9
67.6$\pm$0.6 67.1$\pm$0.5 $\triangle$DP (%) 1.7$\pm$1.4 2.4$\pm$2.1
1.6$\pm$1.0 1.4$\pm$1.0 LNKD ACC (%) (x-0.3)$\pm$1.5 (x-7.2)$\pm$2.5
(x-0.1)$\pm$1.5 x$\pm$0.6 $\triangle$DP (%) (y+0.2)$\pm$0.8 (y+4.9)$\pm$2.6
(y+0.9)$\pm$1.3 y$\pm$0.9

We conduct an ablation study to understand the effectiveness of the edge
injector $f_{E}$, the computation graph sampler $f_{S}$, and the demographic
parity regularizer in FairSample.

We implement an ablation for each of the components. Denote by FairSamplene
the ablation for our edge injector, which trains GCN classifiers on the
original input graph. Denote by FairSamplenr the ablation for the demographic
parity regularizer in the loss function, which trains GCNs by optimizing the
cross-entropy loss function. Denote by FairSamplens the ablation for our
computation graph sampler, which trains GCNs by performing uniform random node
sampling.

Table VI shows the ablation performance. On all the datasets except the
smallest one (NBA), the fairness of FairSample is better than or equal to that
of FairSamplene. This result aligns well with our analysis that adding inter-
group (intra-group) edges to connect similar nodes from the same class
benefits the fairness of the GCNs on homophilic (heterophilic) graphs. On the
NBA datasets, FairSample underperforms slightly in fairness compared to
FairSamplene. We select the hyperparameters for each method based on the
fairness of the validation dataset. Given FairSample’s higher model
complexity, it may not generalize as well as FairSamplene on the NBA test
datasets.

Similar to FairSamplene, the baseline method PASSR also uses reinforcement
learning to train its sampling policy. Different from PASSR, FairSamplene
adopts the idea of stratified sampling to train fair GCN classifiers. The
performance of PASSR shown in Tables III and the performance of FairSamplene
shown in Table VI indicate that FairSamplene outperforms PASSR in fairness on
all cases.

FairSample consistently outperforms FairSamplens with respect to both
fairness. FairSamplens uniformly samples the neighbors of each node to train
GCNs. Thus, it is less effective in picking a set of informative and balanced
neighbors for GCN training.

Comparing the performance of FairSamplenr and FairSample, we can see that
adding a demographic parity regularizer in the loss functions can improve
model fairness. Due to the high model complexity and high nonlinearity of
GCNs, the fairness regularizer may regularize the GCNs to improve their
testing accuracies [77].

###  6.6 Parameter Sensitivity

(a) # Injected edges per node $m$

(b) Fairness regularizer weight $\alpha$

(c) Depth of GCN $K$

(d) # Sampled child node per node $k$

Figure 6: The effect of the hyperparameters $m$, $\alpha$, $K$, and $k$ on the
demographic parity and accuracy of FairSample.

We study how the number of injected edges per node $m$, the weight of the
demographic parity regularizer $\alpha$, the depth of GCNs $K$, and the number
of sampled child nodes per node $k$ affect the demographic parity and accuracy
of FairSample.

To study the effect of a particular hyperparameter on GCNs trained by
FairSample, we fix the other hyperparameters and vary the hyperparameter we
are interested in. For each hyperparameter setting, we conduct the experiments
5 times, and report the mean accuracy and $\Delta DP$. Limited by space, we
only report the results on the PZL dataset in Figure 6. Similar observations
are obtained on the other datasets.

Figure 6a indicates that injecting inter-group edges can reduce $\Delta DP$.
This is because injecting inter-group edges can help our computation graph
sampler in sampling a balanced neighborhood for training fair GCNs. As shown
in Figure 6a, the accuracies of the GCNs change within a small range as $m$
increases, which suggests that the injected edges can improve model fairness
and retain a good model accuracy. Figure 6b shows that a larger $\alpha$ leads
to a more fair model, but incurs a higher accuracy cost. Figure 6c shows the
effect of the depth of GCNs $K$ on model accuracy and fairness. When $K=0$,
the GCNs degenerate to logistic regression models. On the one hand, the
accuracies of the GCNs increase as $K$ increases from $0$ to $2$, as the graph
structure information is used to learn better representations. On the other
hand, a large $K$ may cause the over-smooth issue [60, 61], and hence does not
help with model accuracy. The figure also indicates that a large $K$ can
benefit mode fairness. This is because deeper GCNs are capable of learning
more sophisticated decision boundaries to satisfy the demographic parity
constraint. Since GCNs use the $K$-hop neighbors to train node embeddings, the
computational cost increases with $K$. The effect of $k$ is reported in Figure
6d. Sampling more neighbors for GCN training can learn GCNs with better
utility. However, it also leads to higher computation cost. When $k=1$, the
GCNs make approximately random predictions. Therefore, they have small $\Delta
DP$. When the GCN classifiers have reasonable accuracies, the $\Delta DP$ of
GCNs decrease as $k$ increases. This is because each node is capable of
aggregating information from more diversified neighbors.

##  7 Conclusions

In this paper, we tackle the challenging problem of building demographic
parity fair and accurate GCNs efficiently for semi-supervised node
classification tasks. We systematically analyze how graph structure bias, node
attribute bias, and model parameters may affect the demographic parity of
GCNs. Based on the theoretical analysis, we develop a novel framework
FairSample for GCN training, which employs a graph enrichment strategy and a
computation graph sampling strategy. We report extensive experiments
demonstrating the superior capability of FairSample in training GCN
classifiers with good demographic parity and high accuracy. In five public
benchmark datasets and one LinkedIn production dataset, we observe an
improvement up to 65.5% in fairness at the cost of only at most 5%
classification accuracy drop.

FairSample is the first step into the frontier of designing sampling
strategies for fair and accurate GCNs. There are a few interesting ideas for
future work. First, it is valuable to extend FairSample to improve the other
fairness notions in GCNs, such as individual fairness [48]. Second, an in-
depth theoretical understanding of the potential and boundaries of sampling
strategies for fair GCNs in more general settings remains an interesting
challenge.

## References

  * [1] W. Huang, T. Zhang, Y. Rong, and J. Huang, “Adaptive Sampling Towards Fast Graph Representation Learning,” in _NeurIPS_ , 2018.
  * [2] T. N. Kipf and M. Welling, “Semi-supervised classification with graph convolutional networks,” in _ICLR_ , 2017.
  * [3] L. Liu, W. Zhang, J. Liu, W. Shi, and Y. Huang, “Learning multi-graph neural network for data-driven job skill prediction,” in _IJCNN_ , 2021.
  * [4] L. Cui, H. Seo, M. Tabar, F. Ma, S. Wang, and D. Lee, “DETERRENT: knowledge guided graph attention network for detecting healthcare misinformation,” in _KDD_ , 2020.
  * [5] X. He, K. Deng, X. Wang, Y. Li, Y. Zhang, and M. Wang, “Lightgcn: Simplifying and powering graph convolution network for recommendation,” in _SIGIR_ , 2020.
  * [6] E. Dai and S. Wang, “Say no to the discrimination: Learning fair graph neural networks with limited sensitive attribute information,” in _WSDM_ , 2021\.
  * [7] C. Laclau, I. Redko, M. Choudhary, and C. Largeron, “All of the fairness for edge prediction with optimal transport,” in _AISTATS_ , 2021.
  * [8] P. Li, Y. Wang, H. Zhao, P. Hong, and H. Liu, “On dyadic fairness: Exploring and mitigating bias in graph connections,” in _ICLR_ , 2021.
  * [9] N. Mehrabi, F. Morstatter, N. Saxena, K. Lerman, and A. Galstyan, “A survey on bias and fairness in machine learning,” _ACM Comput. Surv._ , vol. 54, no. 6, pp. 115:1–115:35, 2021.
  * [10] A. Agarwal, A. Beygelzimer, M. Dudík, J. Langford, and H. M. Wallach, “A reductions approach to fair classification,” in _ICML_ , 2018.
  * [11] T. A. Rahman, B. Surma, M. Backes, and Y. Zhang, “Fairwalk: Towards fair graph embedding,” in _IJCAI_ , 2019.
  * [12] S. Xu and T. Strohmer, “Fair data representation for machine learning at the pareto frontier,” _CoRR_ , vol. abs/2201.00292, 2022.
  * [13] S. Barocas, M. Hardt, and A. Narayanan, _Fairness and Machine Learning_. fairmlbook.org, 2019, http://www.fairmlbook.org.
  * [14] M. Thelwall, “Homophily in myspace,” _Journal of the American Society for Information Science and Technology_ , vol. 60, no. 2, pp. 219–231, 2009.
  * [15] Y. Dong, N. Liu, B. Jalaian, and J. Li, “EDITS: modeling and mitigating data bias for graph neural networks,” in _WWW_ , 2022.
  * [16] C. Agarwal, H. Lakkaraju, and M. Zitnik, “Towards a unified framework for fair and stable graph representation learning,” in _UAI_ , 2021.
  * [17] A. K. Menon and R. C. Williamson, “The cost of fairness in binary classification,” in _FAT_ , 2018.
  * [18] H. Zhao and G. J. Gordon, “Inherent tradeoffs in learning fair representations,” _J. Mach. Learn. Res._ , vol. 23, pp. 57:1–57:26, 2022\.
  * [19] A. J. Bose and W. L. Hamilton, “Compositional fairness constraints for graph embeddings,” in _ICML_ , 2019.
  * [20] W. L. Hamilton, Z. Ying, and J. Leskovec, “Inductive representation learning on large graphs,” in _NeurIPS_ , 2017.
  * [21] J. Chen, T. Ma, and C. Xiao, “Fastgcn: Fast learning with graph convolutional networks via importance sampling,” _arXiv preprint arXiv:1801.10247_ , 2018\.
  * [22] M. Yoon, T. Gervet, B. Shi, S. Niu, Q. He, and J. Yang, “Performance-adaptive sampling strategy towards fast and accurate graph neural networks,” in _KDD_ , 2021.
  * [23] F. Kamiran, T. Calders, and M. Pechenizkiy, “Discrimination aware decision tree learning,” in _ICDM_ , 2010.
  * [24] F. Kamiran and T. Calders, “Data preprocessing techniques for classification without discrimination,” _Knowl. Inf. Syst._ , vol. 33, no. 1, pp. 1–33, 2011.
  * [25] B. L. Thanh, S. Ruggieri, and F. Turini, “k-nn as an implementation of situation testing for discrimination discovery and prevention,” in _KDD_ , 2011.
  * [26] S. Hajian and J. Domingo-Ferrer, “A methodology for direct and indirect discrimination prevention in data mining,” _IEEE Trans. Knowl. Data Eng._ , vol. 25, no. 7, pp. 1445–1459, 2013.
  * [27] N. Kilbertus, M. G. Rodriguez, B. Schölkopf, K. Muandet, and I. Valera, “Fair decisions despite imperfect predictions,” in _AISTATS_ , 2020.
  * [28] M. Feldman, S. A. Friedler, J. Moeller, C. Scheidegger, and S. Venkatasubramanian, “Certifying and removing disparate impact,” in _KDD_ , 2015.
  * [29] F. Kamiran, A. Karim, and X. Zhang, “Decision theory for discrimination-aware classification,” in _ICDM_ , 2012.
  * [30] I. Valera, A. Singla, and M. G. Rodriguez, “Enhancing the accuracy and fairness of human decision making,” in _NeurIPS 2018_ , 2018.
  * [31] M. Donini, L. Oneto, S. Ben-David, J. Shawe-Taylor, and M. Pontil, “Empirical risk minimization under fairness constraints,” in _NeurIPS_ , 2018.
  * [32] P. Manisha and S. Gujar, “FNNC: achieving fairness through neural networks,” in _IJCAI_ , 2020.
  * [33] L. Oneto, N. Navarin, and M. Donini, “Learning deep fair graph neural networks,” in _ESANN_ , 2020, pp. 31–36.
  * [34] A. Grover and J. Leskovec, “node2vec: Scalable feature learning for networks,” in _KDD_ , 2016.
  * [35] Ö. D. Kose and Y. Shen, “Fair node representation learning via adaptive data augmentation,” _CoRR_ , 2022.
  * [36] J. Ma, R. Guo, M. Wan, L. Yang, A. Zhang, and J. Li, “Learning fair node representations with graph counterfactual fairness,” in _WSDM_. ACM, 2022.
  * [37] M. J. Kusner, J. R. Loftus, C. Russell, and R. Silva, “Counterfactual fairness,” in _NeurIPS_ , 2017.
  * [38] Y. Dong, J. Kang, H. Tong, and J. Li, “Individual fairness for graph neural networks: A ranking based approach,” in _KDD_ , 2021.
  * [39] J. Ma, J. Deng, and Q. Mei, “Subgroup generalization and fairness of graph neural networks,” in _NeurIPS_ , 2021.
  * [40] X. Tang, H. Yao, Y. Sun, Y. Wang, J. Tang, C. Aggarwal, P. Mitra, and S. Wang, “Investigating and mitigating degree-related biases in graph convoltuional networks,” in _CIKM_ , 2020.
  * [41] J. Kang, Y. Zhu, Y. Xia, J. Luo, and H. Tong, “Rawlsgcn: Towards rawlsian difference principle on graph convolutional network,” in _WWW_ , 2022.
  * [42] X. Huang, Q. Song, Y. Li, and X. Hu, “Graph Recurrent Networks With Attributed Random Walks,” in _KDD_ , 2019.
  * [43] A. Bojchevski, J. Klicpera, B. Perozzi, A. Kapoor, M. Blais, B. Rózemberczki, M. Lukasik, and S. Günnemann, “Scaling Graph Neural Networks with Approximate PageRank,” in _KDD_ , 2020.
  * [44] Z. Liu, Z. Wu, Z. Zhang, J. Zhou, S. Yang, L. Song, and Y. Qi, “Bandit Samplers for Training Graph Neural Networks,” _arXiv:2006.05806 [cs, stat]_ , Jun. 2020.
  * [45] W. Cong, R. Forsati, M. Kandemir, and M. Mahdavi, “Minimal Variance Sampling with Provable Guarantees for Fast Training of Graph Neural Networks,” in _KDD_ , 2020.
  * [46] Z. Jia, S. Lin, R. Ying, J. You, J. Leskovec, and A. Aiken, “Redundancy-free computation for graph neural networks,” in _KDD_ , 2020.
  * [47] Z. Liu, K. Zhou, F. Yang, L. Li, R. Chen, and X. Hu, “EXACT: scalable graph neural networks training via extreme activation compression,” in _ICLR_ , 2022.
  * [48] C. Dwork, M. Hardt, T. Pitassi, O. Reingold, and R. S. Zemel, “Fairness through awareness,” in _Innovations in Theoretical Computer Science 2012, Cambridge, MA, USA, January 8-10, 2012_ , 2012.
  * [49] F. Wu, A. H. S. Jr., T. Zhang, C. Fifty, T. Yu, and K. Q. Weinberger, “Simplifying graph convolutional networks,” in _ICML_ , 2019.
  * [50] L. Chen, L. Wu, R. Hong, K. Zhang, and M. Wang, “Revisiting graph based collaborative filtering: A linear residual graph convolutional network approach,” in _AAAI_ , 2020.
  * [51] X. Wang, H. Jin, A. Zhang, X. He, T. Xu, and T. Chua, “Disentangled graph collaborative filtering,” in _SIGIR_ , 2020.
  * [52] S. Wu, W. Zhang, F. Sun, and B. Cui, “Graph neural networks in recommender systems: A survey,” _CoRR_ , vol. abs/2011.02260, 2020.
  * [53] B. Shin, H. Yang, and J. D. Choi, “The pupil has become the master: Teacher-student model-based word embedding distillation with ensemble learning,” in _IJCAI_ , 2019.
  * [54] T. Miyato, T. Kataoka, M. Koyama, and Y. Yoshida, “Spectral normalization for generative adversarial networks,” in _ICLR_ , 2018.
  * [55] F. du Pin Calmon, D. Wei, B. Vinzamuri, K. N. Ramamurthy, and K. R. Varshney, “Optimized pre-processing for discrimination prevention,” in _NeurIPS_ , 2017.
  * [56] E. Dai, C. Aggarwal, and S. Wang, “NRGNN: learning a label noise resistant graph neural network on sparsely and noisily labeled graphs,” in _KDD_ , 2021\.
  * [57] T. Zhao, Y. Liu, L. Neves, O. J. Woodford, M. Jiang, and N. Shah, “Data augmentation for graph neural networks,” in _EAAI_ , 2021.
  * [58] A. Iscen, G. Tolias, Y. Avrithis, and O. Chum, “Label propagation for deep semi-supervised learning,” in _CVPR_ , 2019.
  * [59] L. Yen, M. Saerens, A. Mantrach, and M. Shimbo, “A family of dissimilarity measures between nodes generalizing both the shortest-path and the commute-time distances,” in _KDD_ , 2008.
  * [60] M. Chen, Z. Wei, Z. Huang, B. Ding, and Y. Li, “Simple and deep graph convolutional networks,” in _ICML_ , 2020.
  * [61] M. Liu, H. Gao, and S. Ji, “Towards deeper graph neural networks,” in _KDD_ , 2020.
  * [62] V. François-Lavet, P. Henderson, R. Islam, M. G. Bellemare, and J. Pineau, “An introduction to deep reinforcement learning,” _Found. Trends Mach. Learn._ , vol. 11, no. 3-4, pp. 219–354, 2018.
  * [63] A. Beutel, J. Chen, T. Doshi, H. Qian, A. Woodruff, C. Luu, P. Kreitmann, J. Bischof, and E. H. Chi, “Putting fairness principles into practice: Challenges, metrics, and improvements,” in _AIES_ , 2019.
  * [64] L. Takac and M. Zabovsky, “Data analysis in public social networks,” in _International scientific conference and international workshop present day trends of innovations_ , vol. 1, no. 6, 2012.
  * [65] P. Velickovic, G. Cucurull, A. Casanova, A. Romero, P. Liò, and Y. Bengio, “Graph attention networks,” in _ICLR_ , 2018.
  * [66] P. Velickovic, W. Fedus, W. L. Hamilton, P. Liò, Y. Bengio, and R. D. Hjelm, “Deep graph infomax,” in _ICLR_ , 2019.
  * [67] Y. Zhu, Y. Xu, F. Yu, Q. Liu, S. Wu, and L. Wang, “Graph contrastive learning with adaptive augmentation,” in _WWW_ , J. Leskovec, M. Grobelnik, M. Najork, J. Tang, and L. Zia, Eds. ACM / IW3C2, 2021.
  * [68] I. Goodfellow, Y. Bengio, and A. Courville, _Deep learning_. MIT press, 2016.
  * [69] “Fairgnn,” https://github.com/EnyanDai/FairGNN, 2022, accessed: 2022-11-22.
  * [70] “Dgi,” https://github.com/PetarV-/DGI, 2022, accessed: 2022-11-22.
  * [71] “Gca,” https://github.com/CRIPAC-DIG/GCA, 2022, accessed: 2022-11-22.
  * [72] “Fairadj,” https://github.com/brandeis-machine-learning/FairAdj, 2022, accessed: 2022-11-22.
  * [73] “Fcge,” https://github.com/brandeis-machine-learning/FairAdj/blob/main/src/adv.py, 2022, accessed: 2022-11-22.
  * [74] “Edits,” https://github.com/yushundong/EDITS, 2022, accessed: 2022-11-22.
  * [75] “Nifty,” https://github.com/chirag126/nifty, 2022, accessed: 2022-11-22.
  * [76] R. Islam, S. Pan, and J. R. Foulds, “Can we obtain fairness for free?” in _AIES_. ACM, 2021.
  * [77] L. Chu, L. Wang, Y. Dong, J. Pei, Z. Zhou, and Y. Zhang, “Fedfair: Training fair models in cross-silo federated learning,” _arXiv preprint arXiv:2109.05662_ , 2021.
  * [78] P. Ngatchou, A. Zarei, and A. El-Sharkawi, “Pareto multi objective optimization,” in _Proceedings of the 13th International Conference on, Intelligent Systems Application to Power Systems_. IEEE, 2006.
  * [79] R. F. Woolson, “Wilcoxon signed-rank test,” _Wiley encyclopedia of clinical trials_ , pp. 1–3, 2007.