# Fairness-aware Message Passing for
Graph Neural Networks

Huaisheng Zhu1, Guoji Fu2, Zhimeng Guo1, Zhiwei Zhang1, Teng Xiao1, Suhang
Wang1
1The Pennsylvania State University, 2National University of Singapore
{hvz5312, zhimeng, zbz5349, tengxiao<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Graph Neural Networks (GNNs) have shown great power in various domains.
However, their predictions may inherit societal biases on sensitive
attributes, limiting their adoption in real-world applications. Although many
efforts have been taken for fair GNNs, most existing works just adopt widely
used fairness techniques in machine learning to graph domains and ignore or
don’t have a thorough understanding of the message passing mechanism with
fairness constraints, which is a distinctive feature of GNNs. To fill the gap,
we propose a novel fairness-aware message passing framework GMMD, which is
derived from an optimization problem that considers both graph smoothness and
representation fairness. GMMD can be intuitively interpreted as encouraging a
node to aggregate representations of other nodes from different sensitive
groups while subtracting representations of other nodes from the same
sensitive group, resulting in fair representations. We also provide a
theoretical analysis to justify that GMMD can guarantee fairness, which leads
to a simpler and theory-guided variant GMMD-S. Extensive experiments on graph
benchmarks show that our proposed framework can significantly improve the
fairness of various backbone GNN models while maintaining high accuracy.

##  1 Introduction

In recent years, Graph Neural Networks (GNNs) have emerged as a powerful
approach for node representation learning on graphs, facilitating various
domains such as recommendation system [1, 2], social network mining [3, 4] and
knowledge graph [5, 6]. The success of GNNs relies on message passing
mechanisms, which allows them to aggregate information from neighboring nodes
and preserve both topological and node feature information [4, 7, 8]. Despite
the significant progress of GNNs, GNNs may inherit societal biases on
sensitive attributes in data such as ages, genders, and races [9, 10, 11],
resulting in biased predictions. Moreover, nodes with the same sensitive
attributes are likely to be connected. The message passing process smooths
representations of connected nodes, further segregating the representations of
nodes in different sensitive groups, causing over-association of their
predictions with sensitive attributes. The biased predictions largely limit
the adoption of GNNs in many real-world applications, e.g., healthcare [12],
credit scoring [13] and job hunting [14].

Recently, many efforts have been taken to learn fair GNNs [9, 10, 11, 15, 16,
17]. Most of these methods propose to adapt the power of regularization [16],
adversarial debiasing [9, 11], or contrastive learning techniques [15, 17]
from traditional fairness models of Euclidean data to graph structured data.
Additionally, some methods aim to directly remove bias from node features and
graph topology [10]. While these methods can alleviate bias issues, it is
still difficult to understand their effect in conjunction with the message
passing process, which is a distinctive feature for GNN models. Training fair
models in machine learning is a complex task as it involves utility and
fairness performance. In the case of GNNs, the message passing process is a
critical component: (i) it can greatly influence the utility performance of
GNN models [18]; and (ii) it might magnify the bias in graph [9]. To control
the trade-off between the utility and fairness of models, it is important to
design a fairness-ware message passing with a deep understanding of its
mechanism about how to achieve fair prediction results. Hence, the above
problems pose an important and challenging research question: How to design a
new message passing process that has high accuracy, is fairness-aware, and
also provides a thorough understanding of how it can debias GNN models?

Generally, message passing can be treated as solving an optimization problem
with smoothness regularization [19, 20, 21, 22, 23, 24]. Specifically, message
passing schemes are derived by the one step gradient of smoothness
regularization, and they typically entail the aggregation of node features
from neighboring nodes, which shows great utility performance. However, such
optimization problem with smoothness regularization only considers utility
without fairness. Therefore, we propose a new optimization formulation that
considers both utility and fairness. By solving the new optimization problem,
we obtain a novel fairness-aware message passing framework, GMMD, with utility
performance ensured by the smoothness regularization, and fairness performance
ensured by the fairness regularization. It can easily trade-off utility and
fairness by adjusting the weight of each regularization term. Intuitively, the
message passing of GMMD can be interpreted as encouraging each node $v_{i}$ to
weightedly aggregate representations of other nodes with different sensitive
attributes of $v_{i}$, and weightedly subtract representations of other nodes
with the same sensitive attribute, which can alleviate over-association of the
learned representation with sensitive attributes, resulting in fair
representations with good utility ensured by smoothness. We also theoretically
show that GMMD can minimize the upper bound of the metric for group fairness,
resulting in fair predictions. Based on our theoretical analysis, we further
propose a more efficient and simpler variant called GMMD-S.

Our main contributions are: (i) We propose a novel fairness-aware message
passing framework GMMD to mitigate biased predictions on graph data, which
guarantees graph smoothness and enhances fairness; (ii) We theoretically show
that the proposed message passing can achieve better downstream performance
with regard to fairness metrics; and (iii) Experimental results on real-world
datasets show that GMMD exhibits a superior trade-off between prediction
performance and fairness.

##  2 Related Works

Graph Neural Networks. Graph Neural Networks have shown great ability in
representation learning on graphs [18, 25]. Existing GNNs can be roughly
divided into spectral-based and spatial-based GNNs. Spectral-based approaches
are defined according to graph theory [4, 26, 27, 28, 29, 30, 31]. The
convolution operation is firstly proposed to graph data from spectral domain
[26]. Then, a first-order approximation is utilized to simplify the graph
convolution via GCN [4]. Spatial-based GNN models learn node representation by
aggregating the information of the neighbor nodes such as GraphSage [3], APPNP
[7] and GAT [32]. Despite their differences, most GNN variants can be
summarized as the message-passing framework composed of pattern extraction and
interaction modeling within each layer. Recent works also show that the
message passing scheme in each layer can be treated as one step gradient of
solving a graph signal denoising problem [19, 20, 21, 22, 23, 24].

Fairness in Graph Learning. Despite their great success, most existing GNNs
just focus on the utility performance while ignoring the fairness issue, which
can lead to discriminatory decisions [33]. Therefore, many efforts have been
taken for fair GNNs [9, 10, 11, 15, 16, 17, 34, 35, 36, 37, 38]. For example,
adversarial debiasing is adopted to train fair GNNs by preventing an adversary
from predicting sensitive attributes from learned fair node representations
[9, 16]. Fairwalk use a fair random walk method to learn fair network
embedding [34]. Some recent works also study contrastive learning methods with
fairness concern [15, 39]. FMP [40] proposes a fair message passing with
transparency. Even though message passing of FMP can implicitly optimize
fairness constraints, it still lacks a direct and theoretical understanding of
how its message passing process can mitigate biases in GNNs based on fairness
metrics. Therefore, the aforementioned works ignore a fairness-aware message
passing component or don’t provide a thorough understanding of how fairness-
aware message passing can debias predictions in GNNs. In this work, we develop
a novel fairness-ware message passing approach with a theoretical
understanding of how it can give fair prediction results.

##  3 Notations and Problem Definition

Notations. Let ${\mathcal{G}}=({\mathcal{V}},{\mathcal{E}},\mathbf{X})$ be an
undirected attributed graph, where
${\mathcal{V}}=\\{v_{1},v_{2},\ldots,v_{N}\\}$ is the set of $N$ nodes,
${\mathcal{E}}\subseteq{\mathcal{V}}\times{\mathcal{V}}$ is the set of edges,
and $\mathbf{X}$ is the node feature matrix with the $i$-th row of
${\mathbf{X}}$, i.e., ${\mathbf{X}}_{i,:}$ as node feature of $v_{i}$. The
graph structure can be denoted as the adjacency matrix
${\mathbf{A}}\in\mathbb{R}^{N\times N}$. ${A}_{ij}=1$ if
$(v_{i},v_{j})\in{\mathcal{E}}$; ${A}_{ij}=0$ otherwise. The symmetrically
normalized graph Laplacian matrix is defined as
$\tilde{{\mathbf{L}}}={\mathbf{I}}-\tilde{{\mathbf{A}}}$, where
$\tilde{{\mathbf{A}}}=\hat{{\mathbf{D}}}^{-\frac{1}{2}}\hat{{\mathbf{A}}}\hat{{\mathbf{D}}}^{-\frac{1}{2}}$
is a normalized self-loop adjacency matrix with
$\hat{{\mathbf{A}}}={\mathbf{A}}+{\mathbf{I}}$ and $\tilde{{\mathbf{D}}}$ is
the degree matrix of $\tilde{{\mathbf{A}}}$.
${\mathcal{N}}_{i}=\\{v_{j}:{(v_{i},v_{j})\in{\mathcal{E}}}\\}$ denotes the
set of $v_{i}$ neighbors. We use $\mathbf{s}\in\\{0,1\\}^{N}$ to denote
sensitive attributes of all nodes, where the $i$-th element of $\mathbf{s}$,
i.e., $s_{i}\in\\{0,1\\}$, is the binary sensitive attribute of $v_{i}$. The
set of nodes from group 0 ($s_{i}=0$) is denoted as
${\mathcal{S}}_{0}=\\{v_{i}:{v_{i}\in{\mathcal{V}}\land s_{i}=0}\\}$. The set
of nodes from group 1 ($s_{i}=1$) is denoted as
${\mathcal{S}}_{1}=\\{v_{i}:{v_{i}\in{\mathcal{V}}\land s_{i}=1}\\}$. $N_{1}$
and $N_{2}$ are the number of nodes in ${\mathcal{S}}_{0}$ and
$\mathcal{S}_{1}$.

Graph Signal Denoising. Recently, it is shown that many popular GNNs can be
uniformly understood as solving graph signal denoising problems with various
diffusion properties [19, 20, 21, 22, 23, 24]. For instance, the message
passing in GCN [4], GAT [32] and APPNP [7] can be considered as one gradient
descent iteration for minimizing
$\lambda_{s}\cdot\operatorname{tr}\big{(}{\mathbf{F}}^{T}\tilde{{\mathbf{L}}}{\mathbf{F}}\big{)}+\left\|{\mathbf{F}}-{\mathbf{X}}_{\text{in}}\right\|_{F}^{2}$
with the initialization ${\mathbf{F}}^{(0)}={\mathbf{X}}_{\text{in}}$ and
weight $\lambda_{s}$, where ${\mathbf{X}}_{\text{in}}$ can be the original
feature ${\mathbf{X}}$ or hidden features after feature transformation on
${\mathbf{X}}$. These hidden features can be obtained by passing
${\mathbf{X}}$ through several layers of MLPs. These GNN models optimize
smoothness regularization over graph structure implicitly, but they may also
inherit biased representations from the graph structure [10, 41].

Problem Formulation. For fair semi-supervised node classification, part of
nodes $v_{i}\in{\mathcal{V}}_{L}$ are provided with labels
$y_{i}\in{\mathcal{Y}}_{L}$, where $\mathcal{V}_{L}\subseteq\mathcal{V}$ is
the set of labeled nodes, and ${\mathcal{Y}}_{L}$ is the corresponding label
set. Given ${\mathcal{G}},{\mathcal{V}}_{L}$ and $\mathbf{s}$, the goal of
GNNs for fair semi-supervised node classification is to learn a function
$f\left({\mathcal{G}}\right)\rightarrow{\mathcal{Y}}_{L}$ and predict the
labels of unlabeled nodes, where the predicted labels should maintain high
accuracy whilst satisfying the fairness criteria about sensitive attributes
$\mathbf{s}$.

##  4 Graph Neural Network with Fairness-aware Message Passing

In this section, we introduce the proposed fairness-aware message passing
framework GMMD, which aims to give fair prediction and maintain high accuracy.
Unlike traditional message passing methods that optimize smoothness
regularization over graphs while ignoring fairness constraints, GMMD
formulates a new optimization problem that simultaneously considers smoothness
and fairness. Then, by performing one-step gradient descent on this
optimization function, we obtain a fairness-aware message passing approach
that can learn fair and smooth representations that preserve utility and
fairness performance. We also provide theoretical analysis to that GMMD can
guarantee the fairness performance. Based on our theoretical analysis, a
simpler and theory-guided fairness-aware message passing method (GMMD-S) is
introduced with the fairness guarantee.

###  4.1 Fairness-aware Message Passing - GMMD

Traditional message passing methods in GNN models learn smooth representation
over graphs while ignoring fairness issues, which hinders their adoption in
many real-world applications [9, 33]. This motivates us to design a fairness-
aware message passing method. Inspired by previous works [19, 20, 21] that
treat message passing as the on step gradient of an optimization problem based
on smoothness assumption of graph representations, we propose a new
optimization problem with fairness considerations. Specifically, to guarantee
both smoothness and fairness, a fairness-aware message passing method should
be the solution of the following optimization function:

$\small\min_{\mathbf{F}}h({\mathbf{F}})=h_{s}({\mathbf{F}})+\lambda_{f}h_{f}({\mathbf{F}})=\frac{\lambda_{s}}{2}\operatorname{tr}\big{(}{\mathbf{F}}^{T}\tilde{{\mathbf{L}}}{\mathbf{F}}\big{)}+\frac{1}{2}\left\|{\mathbf{F}}-{\mathbf{X}}_{\text{in}}\right\|_{F}^{2}+\lambda_{f}h_{f}({\mathbf{F}}),$
(1)

where
$h_{s}({\mathbf{F}})=\frac{\lambda_{s}}{2}\operatorname{tr}\big{(}{\mathbf{F}}^{T}\tilde{{\mathbf{L}}}{\mathbf{F}}\big{)}+\frac{1}{2}\left\|{\mathbf{F}}-{\mathbf{X}}_{\text{in}}\right\|_{F}^{2}$
is smoothness regularization to recover a clean node representation matrix
${\mathbf{F}}\in\mathbb{R}^{N\times d}$ and guide the smoothness of
$\mathbf{F}$ over the graph. $h_{f}({\mathbf{F}})$ is a regularization to
control the fairness of ${\mathbf{F}}$. In this paper, we adopt Maximum Mean
Discrepancy (MMD) [42] as fairness regularization $h_{f}({\mathbf{F}})$ as it
enables us to gain a better understanding of the resulting message passing
approach from both an intuitive and a theoretical standpoint. We leave the
other choices as future work. MMD is a popular estimator for measuring the
distribution discrepancy of two groups. For two groups $\mathcal{S}_{0}$ and
$\mathcal{S}_{1}$, MMD measures the distribution discrepancy as:

$\small\ell_{\text{MMD}}\left({\mathbf{F}}\right)=\frac{1}{N_{0}^{2}}\sum_{v_{i}\in{\mathcal{S}}_{0}}\sum_{v_{j}\in{\mathcal{S}}_{0}}k\left({\mathbf{F}}_{i},{\mathbf{F}}_{j}\right)+\frac{1}{N_{1}^{2}}\sum_{v_{i}\in{\mathcal{S}}_{1}}\sum_{v_{j}\in{\mathcal{S}}_{1}}k\left({\mathbf{F}}_{i},{\mathbf{F}}_{j}\right)-\frac{2}{N_{0}N_{1}}\sum_{v_{i}\in{\mathcal{S}}_{0}}\sum_{v_{j}\in{\mathcal{S}}_{1}}k\left({\mathbf{F}}_{i},{\mathbf{F}}_{j}\right),$
(2)

where $\mathbf{F}_{i}$ is the node representation of $v_{i}$ and
$k({\mathbf{F}}_{i},{\mathbf{F}}_{j})$ denotes the kernel similarity between
${\mathbf{F}}_{i}$ and ${\mathbf{F}}_{j}$. As our fairness constraint involves
exactly matching the considered distributions using MMD, $k(\cdot,\cdot)$
should be characteristic kernels. As shown in [43], RBF and Laplace are
popular stationary characteristic kernels. Thus, in this paper, we set
$k({\mathbf{F}}_{i},{\mathbf{F}}_{j})$ to be the RBF kernel, i.e.,
$k({\mathbf{F}}_{i},{\mathbf{F}}_{j})=\exp\left(-\alpha\|{\mathbf{F}}_{i}-{\mathbf{F}}_{j}\|^{2}\right)$,
where $\alpha$ determines the rate at which the similarity between two data
points decreases as the distance between them increases. Several works [44,
45, 46] have shown the benefits of directly using MMD as a regularizer to
train fair models., e.g., we can directly adopt MMD to regularize the node
representations of GNNs. However, such direct adoption doesn’t consider the
message passing process, which makes it challenging to comprehend the actual
impact of using MMD regularization in conjunction with GNNs’ message passing.
In addition, we also empirically show that simple adoption can’t perform well
in Section 5. Hence, instead of simply using it as a regularizer, based on
this new optimization problem, we adopt one-step gradient for
$h({\mathbf{F}})$ and propose the fairness-aware message passing based on MMD,
which can be written as:

$\displaystyle{\mathbf{F}}^{(k)}={\mathbf{F}}^{(k-1)}-\gamma\nabla
h\big{(}{\mathbf{F}}^{(k-1)}\big{)}$
$\displaystyle={\mathbf{F}}^{(k-1)}-\gamma(\lambda_{s}\tilde{{\mathbf{L}}}{\mathbf{F}}^{(k-1)}+{\mathbf{F}}^{(k-1)}-{\mathbf{X}}_{\text{in}})+4\gamma\lambda_{f}\alpha{\mathbf{P}}{\mathbf{F}}^{(k-1)}$
(3)
$\displaystyle=\big{(}(1-\gamma){\mathbf{I}}-\gamma\lambda_{s}\tilde{{\mathbf{L}}}+4\gamma\lambda_{f}\alpha{\mathbf{P}}\big{)}{\mathbf{F}}^{(k-1)}+\gamma{\mathbf{X}}_{\text{in}},$

where for $i\neq j$, if $v_{i}$ and $v_{j}$ are in the same sensitive group
${\mathcal{S}}_{t}$,
$P_{ij}=-k({\mathbf{F}}^{(k-1)}_{i},{\mathbf{F}}^{(k-1)}_{j})/N_{t}^{2}$,
$t\in\\{0,1\\}$. If $v_{i}$ and $v_{j}$ are in different sensitive groups,
${P}_{ij}=k({\mathbf{F}}^{(k-1)}_{i},{\mathbf{F}}^{(k-1)}_{j})/N_{0}N_{1}$.
And ${P}_{ii}=-\sum_{k=1,m\neq i}^{N}{P}_{im}$. The detailed derivation for
Eq.(3) is in Appendix A.1. Following [19], we set the learning rate
$\gamma=\frac{1}{1+\lambda_{s}}$. Then the final message passing of GMMD can
be written as:

${\mathbf{F}}^{(k)}={\mathbf{F}}^{(k-1)}-\gamma\nabla
h\big{(}{\mathbf{F}}^{(k-1)}\big{)}=\big{(}(1-\gamma)({\mathbf{I}}-\tilde{{\mathbf{L}}})+4\gamma\lambda_{f}\alpha{\mathbf{P}}\big{)}{\mathbf{F}}^{(k-1)}+\gamma{\mathbf{X}}_{\text{in}}.$
(4)

The proposed message passing method can implicitly optimize both fairness and
smoothness regularization in Eq.(1) to learn fair and smooth representation.
To better understand this message passing mechanism in Eq.(4), we interpret it
as modeling inter-sensitive-group and intra-sensitive-group relations to learn
fair representation. Specifically, for two nodes $v_{i}$ and $v_{j}$ from
different sensitive groups, we have $P_{ij}>0$, meaning that $v_{i}$ will
aggregate information from $v_{j}$ with the aggregation as kernel similarity
$P_{ij}$; on contrary, if $v_{i}$ and $v_{j}$ are from the same sensitive
group, then $P_{ij}<0$, meaning that $v_{i}$ will subtract the information
from $v_{i}$. Hence the proposed approach can mitigate bias in GNNs by
aggregating representations of nodes with different sensitive attributes to
bring nodes from different sensitive groups closer in the embedding space, and
subtracting representations of nodes with the same sensitive attributes to
prevent representations overly correlated with sensitive attributes.
Therefore, our proposed message passing mechanism can mitigate the issue of
biased label assignment in GNNs by modifying the way node representations are
updated during message passing, promoting fairer and more accurate
predictions. In order to gain a deeper comprehension of GMMD, we will also
provide a theoretical understanding of our model for fairness performance.

###  4.2 Theoretical Analysis

Next, we provide theoretical understandings of proposed GMMD. We show that
GMMD can minimize the upper bound of the metric for group fairness. All
detailed proofs can be found in Appendix F.

One of the most widely used fairness metrics for group fairness is demographic
parity [14], which ensures an equal positive rate for two groups. The
difference in demographic parity, denoted as
$\Delta_{\text{DP}}=|\mathbb{E}(\hat{y}|S=0)-\mathbb{E}(\hat{y}|S=1)|$,
measures the fairness of the model, where $\hat{y}$ is the predicted
probability for nodes being positive and $S$ is the sensitive attribute of
nodes. Note that following [10, 9, 40] we only consider binary sensitive
attributes, but our analysis can be easily extended to multivariate or
continuous sensitive attributes. The details of $\Delta_{\text{DP}}$ are in
Appendix E.

With the definition of $\Delta_{\text{DP}}$, we will theoretically analyze how
our proposed message passing could affect the difference in demographic
parity. We consider a K-layer GMMD with each layer performing fairness aware
message passing as Eq.(4) and the input to the model is
${\mathbf{F}}^{(0)}={\mathbf{X}}$. Then, we can obtain the representation
${\mathbf{F}}^{(K)}$ with a $K$-layer model, with both fairness and smoothness
constraints Finally, a linear model is applied to ${\mathbf{F}}^{(K)}$ with a
Softmax function to predict the probability of labels as
$\hat{{\mathbf{Y}}}=\text{softmax}({\mathbf{F}}^{(K)}{\mathbf{W}})$, where
${\mathbf{W}}\in\mathbb{R}^{d\times c}$ is the learnable weight matrix.
$\hat{{\mathbf{Y}}}\in\mathbb{R}^{N\times c}$ is a matrix, where $i$-th row
means the predicted label of node $v_{i}$. $d$ is the dimension of the input
feature ${\mathbf{X}}$ and $c$ is the number of classes. We use
$\mu\in\mathbb{R}^{d}$ to denote the sample mean of the original features of
all nodes, i.e., $\mu=\sum_{v_{i}\in{\mathcal{V}}}{\mathbf{X}}_{i}/N$.
Furthermore, $\mu^{(s)}\in\mathbb{R}^{d}$ represents the sample mean of
original feature for the sensitive group $s$, $s\in\\{0,1\\}$. We first
demonstrate $\Delta_{\text{DP}}^{\text{Rep}}({\mathbf{F}}^{(K)})$ at the
representation level is the upper bound of $\Delta_{\text{DP}}$ through the
following theorem:

######  Theorem 4.1.

Minimizing representation discrepancy between two sensitive groups
$\Delta_{\text{DP}}^{\text{Rep}}({\mathbf{F}}^{(K)})=\|\mathbb{E}({\mathbf{F}}^{(K)}\mid
S=0)-\mathbb{E}(\mathbf{F}^{(K)}\mid S=1)\|$ is equivalent to minimizing
$\Delta_{\text{DP}}$ of the model prediction for a binary classification
problem, and ${\mathbf{F}}^{(K)}$ is the final output of a $K$ layer model
before the softmax function. When $K$ is set as 2, we have:

$\displaystyle\Delta_{\text{DP}}\leq\frac{L}{2}\left\|{\mathbf{W}}\right\|\left(\Delta_{\text{DP}}^{\text{Rep}}({\mathbf{F}}^{(K)})+C_{1}\left\|\bm{\Delta}\right\|\right),$
(5)

where
$C_{1}=(2+\frac{4}{N_{0}}+\frac{4}{N_{1}})^{2}+6+\frac{8}{N_{0}}+\frac{8}{N_{1}}$
and $\bm{\Delta}$ is the maximal deviation of ${\mathbf{X}}$ from $\mu$ i.e.,
$\bm{\Delta}_{m}=\max_{i}|\mu_{m}-{\mathbf{X}}_{i,m}|$. $L<1$ is the Lipschitz
constant for the Softmax function.

The proof is in Appendix F.1. Theorem 4.1 shows that minimizing
$\Delta_{\text{DP}}^{\text{Rep}}$ at the representation level will minimize
the fairness metric $\Delta_{\text{DP}}$. With this theorem, we can analyze
the influence of our GMMD on $\Delta_{\text{DP}}^{\text{Rep}}$ to evaluate
whether it promotes fairness in the classification task by reducing
discrimination.

Next, we theoretically show that performing our proposed message passing to
learn node representation can minimize the fairness metric at the
representation level $\Delta_{\text{DP}}^{\text{Rep}}$.

######  Theorem 4.2.

For an arbitrary graph, after $K$-layer fairness-aware message passing with
Eq.(4) on the original feature ${\mathbf{X}}$ to obtain ${\mathbf{F}}^{(K)}$,
when $K=2$, the consequent representation discrepancy on ${\mathbf{F}}^{(K)}$
between two sensitive groups is up bounded as:

$\small\Delta_{\text{DP}}^{\text{Rep}}({\mathbf{F}}^{(K)})\leq\big{(}3-(\frac{1}{N_{0}N^{2}_{1}}+\frac{1}{N^{2}_{0}N_{1}})\sum_{i\in
S_{0}}\sum_{j\in
S_{1}}k({\mathbf{F}}^{(K-1)}_{i},{\mathbf{F}}^{(K-1)}_{j})\big{)}C_{3}+C_{2},$
(6)

where
$C_{2}=\|\mu^{(0)}-\mu^{(1)}\|+8(1+\frac{1}{N_{0}}+\frac{1}{N_{1}})^{2}\|\bm{\Delta}\|+2\|\bm{\Delta}\|$.
Also, the constant value $C_{3}$ is
$C_{3}=(3-\frac{1}{N_{0}}-\frac{1}{N_{1}})\|(\mu^{(0)}-\mu^{(1)})\|+(4+\frac{2}{N_{0}}+\frac{2}{N_{1}})\|\bm{\Delta}\|$.

The proof is in Appendix F.2. Theorem 4.2 shows that
$\Delta_{\text{DP}}^{\text{Rep}}({\mathbf{F}}^{(K)})$ is upper bounded by the
third term of the MMD loss in Eq.(2) and constant values $C_{2}$ and $C_{3}$.
Therefore, combining theorem 4.2 and theorem 4.1, optimizing the third term of
MMD regularization can minimize
$\Delta_{\text{DP}}^{\text{Rep}}({\mathbf{F}}^{(K)})$, which minimizes the
upper bound of the fairness metric $\Delta_{\text{DP}}$. The proposed GMMD can
implicitly optimize the MMD regularization and can be flexibly incorporated to
various GNN backbones such as GAT [32] and GIN [47] (see Appendix C). These
findings highlight the efficacy of GMMD in mitigating fairness issues and
facilitating various backbone GNNs.

###  4.3 Simple Fairness-aware Message Passing - GMMD-S

From the theoretical analysis in Section 4.2, we find that directly optimizing
the third term of MMD regularization can also effectively minimize the upper
bound of the fairness metric. This motivate us to further simplify GMMD to
obtain a theory-guided method for mitigating bias for GNNs. Specifically, we
simplify the fairness regularization function in Eq.(1) as
$h_{f}({\mathbf{F}})=-\frac{1}{N_{0}N_{1}}\sum_{v_{i}\in{\mathcal{S}}_{0}}\sum_{v_{j}\in{\mathcal{S}}_{1}}k\left({\mathbf{F}}_{i},{\mathbf{F}}_{j}\right)$
and obtain simplified fairness-aware message passing as follows:

${\mathbf{F}}^{(k)}={\mathbf{F}}^{(k-1)}-\gamma\nabla
h\big{(}{\mathbf{F}}^{(k-1)}\big{)}=\big{(}(1-\gamma)({\mathbf{I}}-\tilde{{\mathbf{L}}})+4\gamma\lambda_{f}\alpha\widetilde{{\mathbf{P}}}\big{)}{\mathbf{F}}^{(k-1)}+\gamma{\mathbf{X}}_{\text{in}},$
(7)

where for $i\neq j$, if $v_{i}$ and $v_{j}$ are in the same sensitive group,
$\widetilde{P}_{ij}=0$. If $v_{i}$ and $v_{j}$ are in the different sensitive
groups, $\widetilde{P}_{ij}=-k({\mathbf{F}}_{i},{\mathbf{F}}_{j})/N_{0}N_{1}$.
And $\widetilde{P}_{ii}=-\sum_{k=1,m\neq i}^{N}\widetilde{P}_{im}$,
$\gamma=\frac{1}{1+\lambda_{s}}$. The details can be found in Appendix A.2.
Compared to GMMD, this simplified version doesn’t need to calculate the
similarity between node pairs from the same sensitive group and can greatly
improve the efficiency of the algorithm. Using this message passing can
immediately optimize the third term of the MMD regularization, which can
provably minimize $\Delta_{\text{DP}}$ in Theorem 4.2 and Theorem 4.1. We call
this simplified version as GMMD-S.

###  4.4 Model Framework and Training Method

Model Framework. To increase the expressive power of GMMD, we perform
transformations on the original features, resulting in
${\mathbf{X}}_{\text{in}}=\text{MLP}_{\theta}({\mathbf{X}})$, where
${\mathbf{X}}_{\text{in}}\in\mathbb{R}^{N\times c}$ and
$\text{MLP}_{\theta}(\cdot)$ denotes $M$ layer MLP parameterized by $\theta$.
Note that $c$ can be replaced with any values for hidden dimensions, but
setting it as $c$ yields better empirical results in our experiment. Following
[19], we treat ${\mathbf{F}}^{(0)}={\mathbf{X}}_{\text{in}}$. After
transformations, we operate fairness-aware message passing in Eq.(7) or Eq.(4)
for $K$ layers, obtaining
$\mathbf{F}^{(K)}=\text{GMMD}(\mathbf{A},\mathbf{X}_{\text{in}},\mathbf{s})$.
We add Softmax function to ${\mathbf{F}}^{(K)}$ to get predictions. Finally,
cross-entropy loss is used to train the model. Our full algorithm is given in
Appendix B.

Incorporate Different Backbones. Moreover, our models is flexible to
facilitate various GNN backbones. For the fairness-aware message passing in
Eq.(4) and Eq.(7), the first term of these equations is the message passing
method of GCN, $\mathbf{I}-\tilde{\mathbf{L}}$. Therefore, we can simply
replace this message passing style with different GNN models. We also conduct
the experiments of GAT and GIN backbones to show the flexibility of our
proposed method in Section 5.4. We discuss the details of how to incorporate
our model with different backbones in Appendix C.

Efficient Training. Calculating ${\mathbf{P}}$ or $\widetilde{{\mathbf{P}}}$
is time-consuming, where the time complexity are ${\mathcal{O}}(N^{2}c)$ and
${\mathcal{O}}(N_{0}N_{1}c)$. To efficiently train our algorithm, we randomly
sample an equal number of nodes from ${\mathcal{S}}_{0}$ and
${\mathcal{S}}_{1}$ in each training epoch to update the sampled nodes’
representation by Eq.(4) or Eq.(7). Let the sampled sensitive group set be
${\mathcal{S}}^{\prime}_{0}$ and ${\mathcal{S}}^{\prime}_{1}$, where
$|{\mathcal{S}}^{\prime}_{0}|$ and $|{\mathcal{S}}^{\prime}_{1}|$ are both
equal to $N_{s}$. We can get the sampled fairness-aware message passing as
follows:

$\small{\mathbf{F}}^{(k)}_{i}={\mathbf{F}}^{(k)}_{i}+4\gamma\lambda_{f}\alpha{\sum}_{j\in{\mathcal{S}}^{\prime}_{0}\cup{\mathcal{S}}^{\prime}_{1}}P_{ij}{\mathbf{F}}^{(k-1)}_{j},~{}{\mathbf{F}}^{(k)}=\big{(}(1-\gamma)({\mathbf{I}}-\tilde{{\mathbf{L}}})+\gamma{\mathbf{X}}_{\text{in}}\big{)}{\mathbf{F}}^{(k-1)},~{}i\in{\mathcal{S}}^{\prime}_{0}\cup{\mathcal{S}}^{\prime}_{1},$
(8)

where we can also replace ${\mathbf{P}}$ with $\widetilde{{\mathbf{P}}}$ for
our simplified fairness-aware message passing in Eq.(7). We give time
complexity of our proposed method in Appendix D. A detailed training time
comparison with state-of-the-art methods is given in Appendix H.4.

##  5 Experiment

In this section, we empirically evaluate the effectiveness of the proposed
fairness-aware message passing GMMD on real-world graphs and analyze its
behavior on graphs to gain further insights.

###  5.1 Experimental Setup

Datasets. We perform experiments on three widely-used datasets for fairness
aware node classification, i.e., German, Credit and Bail [39]. We provide the
detailed descriptions, statistics, and sensitive attribute homophily measures
of datasets in Appendix G.1.

Baselines. In the following part, we denote the proposed message passing
method in Eq.(4) as GMMD and Eq.(7) as GMMD-S. To evaluate the effectiveness
of GMMD and GMMD-S, we consider the following representative and state-of-the-
art baselines for group fairness in graph domains, including NIFTY [39], EDITS
[10], FairGNN [9], FMP [40]. We also adopt a baseline named MMD, which
directly adds MMD regularization at the output layer of the GNN. For all
baselines and our model, GCN [4] is used as the backbone. For fair
comparisons, we set the number of layers for GCN in all methods as $2$. The
details of baselines and implementations are given in Appendix G.3.

Evaluation Protocol. We use the default data splitting following NIFTY [39]
and EDITS [10]. We adopt AUC, F1-score and Accuracy to evaluate node
classification performance. As for fairness metric, we adopt two quantitative
group fairness metrics to measure the prediction bias, i.e., demographic
parity $\Delta_{\text{DP}}$ and equal opportunity $\Delta_{\text{EO}}$ [48],
where the smaller values represent better performance. A detailed description
of these two fairness metrics is shown in Appendix E.

Setup. We run each experiment 5 times and report the average performance. For
a fair comparison, we select the best configuration of hyperparameters based
on performance on the validation set for all methods. For all baselines, we
use the same hyperparameter search space used in [11]. The detailed setup and
hyper-parameter settings are given in Appendix G.3.

Table 1: Model utility and bias of node classification. The best and runner-up
results are colored in red and blue. $\uparrow$ represents the larger, the
better; while $\downarrow$ represents the opposite.

Dataset | Metric | GCN | NIFTY | EDITS | FairGNN | FairVGNN | FMP | MMD | GMMD | GMMD-S
---|---|---|---|---|---|---|---|---|---|---
German |  AUC ($\uparrow$) | 74.11$\pm$0.37 |  68.78$\pm$2.69 |  69.41$\pm$2.33 |  67.35$\pm$2.13 |  72.41$\pm$2.10 |  68.20$\pm$4.63 |  72.41$\pm$3.10 | 74.03$\pm$2.28 |  73.10$\pm$1.46
F1 ($\uparrow$) |  82.46$\pm$0.89 |  82.78$\pm$0.50 |  81.55$\pm$0.59 |  82.01$\pm$0.26 | 83.25$\pm$0.50 |  81.38$\pm$1.30 |  81.70$\pm$0.67 | 83.13$\pm$0.64 |  82.54$\pm$0.92
ACC ($\uparrow$) | 73.44$\pm$1.09 |  69.92$\pm$1.14 |  71.60$\pm$0.89 |  69.68$\pm$0.30 |  72.27$\pm$1.32 |  72.53$\pm$2.22 |  69.99$\pm$0.56 | 72.28$\pm$1.64 |  71.87$\pm$1.24
$\Delta_{\text{DP}}$ ($\downarrow$) |  35.17$\pm$7.27 |  13.56$\pm$5.32 |  4.05$\pm$4.48 |  3.49$\pm$2.15 | 1.71$\pm$1.68 |  6.48$\pm$4.40 |  7.56$\pm$7.49 |  2.09$\pm$1.60 | 0.90$\pm$0.44
$\Delta_{\text{EO}}$ ($\downarrow$) |  25.17$\pm$5.89 |  5.08$\pm$4.29 |  3.89 $\pm$ 4.23 |  3.40 $\pm$ 2.15 | 0.88 $\pm$ 0.58 |  5.81$\pm$4.03 |  5.34$\pm$5.31 | 0.76 $\pm$ 0.52 |  0.99 $\pm$ 0.33
Credit |  AUC ($\uparrow$) | 73.87$\pm$0.02 |  74.36$\pm$0.21 | 73.01$\pm$0.11 |  71.95$\pm$1.43 |  71.95$\pm$1.43 |  69.42$\pm$4.25 |  69.84$\pm$0.85 |  71.62$\pm$0.07 |  71.78$\pm$0.30
F1 ($\uparrow$) |  81.92$\pm$0.02 |  81.72$\pm$0.05 |  81.81$\pm$0.28 |  81.84$\pm$1.19 | 87.08$\pm$0.74 |  84.99$\pm$2.78 |  85.87$\pm$0.37 | 87.57$\pm$0.01 |  86.96$\pm$0.58
ACC ($\uparrow$) |  73.67$\pm$0.03 |  73.45$\pm$0.06 |  73.51$\pm$0.30 |  73.41$\pm$1.24 |  78.04$\pm$0.33 |  75.81$\pm$2.35 |  76.13$\pm$0.35 | 78.11$\pm$0.30 | 78.08$\pm$0.36
$\Delta_{\text{DP}}$ ($\downarrow$) |  12.86$\pm$0.09 |  11.68$\pm$0.07 |  10.90$\pm$1.22 |  12.64$\pm$2.11 |  5.02$\pm$5.22 |  5.20$\pm$5.42 |  2.28$\pm$1.33 | 1.55$\pm$1.99 | 2.27$\pm$1.75
$\Delta_{\text{EO}}$ ($\downarrow$) |  10.63$\pm$0.13 |  9.39$\pm$0.07 |  8.75$\pm$1.21 |  10.41$\pm$2.03 |  3.60$\pm$4.31 |  4.60$\pm$4.49 |  2.24$\pm$1.06 | 1.08$\pm$1.53 | 1.95$\pm$1.43
Bail |  AUC ($\uparrow$) |  87.08$\pm$0.35 |  78.20$\pm$2.78 |  86.44$\pm$2.17 |  87.36$\pm$0.90 |  85.68$\pm$0.37 |  87.02$\pm$0.13 |  86.68$\pm$0.25 | 88.18$\pm$2.04 | 89.12$\pm$0.66
F1 ($\uparrow$) | 79.02$\pm$0.74 |  76.49$\pm$0.57 |  75.58$\pm$3.77 |  77.50$\pm$1.69 | 79.11$\pm$0.33 |  77.46$\pm$0.40 |  77.51$\pm$0.67 |  77.92$\pm$1.99 |  78.72$\pm$0.49
ACC ($\uparrow$) |  84.56$\pm$0.68 |  74.19$\pm$2.57 |  84.49$\pm$2.27 |  82.94$\pm$1.67 |  84.73$\pm$0.46 |  83.69$\pm$0.26 |  84.41$\pm$0.40 | 84.95$\pm$1.63 | 85.62$\pm$0.45
$\Delta_{\text{DP}}$ ($\downarrow$) |  7.35$\pm$0.72 | 2.44$\pm$1.29 |  6.64$\pm$0.39 |  6.90$\pm$0.17 |  6.53$\pm$0.67 |  6.85$\pm$0.19 |  7.33$\pm$1.05 |  2.83$\pm$1.99 | 1.68$\pm$1.34
$\Delta_{\text{EO}}$ ($\downarrow$) |  4.96$\pm$0.62 | 1.72$\pm$1.08 |  7.51$\pm$1.20 |  4.65$\pm$0.14 |  4.95$\pm$1.22 |  4.24$\pm$0.72 |  6.48$\pm$0.75 |  3.89 $\pm$ 0.96 | 3.80$\pm$0.77
| Avg.(Rank) | 5.53 | 6.20 | 6.33 | 6.53 | 3.53 | 6.07 | 5.80 | 2.40 | 2.60

###  5.2 Overall Performance Comparison

In this subsection, we conduct experiments on real-world graphs to evaluate
the utility and fairness of GMMD. Table 1 reports the average AUC, F1-score
and Accuracy with standard deviation on node classification after five runs.
We also report average $\Delta_{\text{EO}}$ and $\Delta_{\text{DP}}$ with
standard deviation as the fairness metric. From the table, we make the
following observations: (i) Generally, our GMMD and GMMD-S achieve the best
performance in terms of the average rank for all datasets and across all
evaluation metrics, which indicates the superiority of our model in achieving
a better trade-off between model utility and fairness. The average rank of
GMMD and GMMD-S are 2.4 and 2.6 with regard to all metrics. (ii) When compared
with FairGNN, FairVGNN, EDITS, NIFTY and FMP, GMMD can consistently outperform
them. This improvement is mainly because our model combines fairness
regularization with the original message passing process of GNNs. It can
effectively learn a fair representation and achieves better model utility with
smoothness regularization simultaneously. (iii) Our simplified model GMMD-S,
which just minimizes the third term of the MMD regularization inspired from
Theorem 4.2, achieves comparable or even better results compared with GMMD,
which verifies our motivation to design a simpler fairness-aware message
passing mechanism with less time cost to mitigate the fairness issue on GNNs
by minimizing the inter-group kernel similarity.

###  5.3 Parameter Analysis and Empirical Analysis on Theory

Figure 1: Hyper-parameter Analysis on Bail and German. A deeper color denotes
a larger value.

Hyper-parameters Analysis. Here we investigate the hyper-parameters most
essential to our framework, i.e., $\lambda_{f}$ and $\lambda_{s}$ ($\gamma$ is
set as $1/(1+\lambda_{s}$)) to control smoothness and fairness regularization,
respectively. The results are shown in Figure 1. To better understand the
influence of hyperparameters, we use homophily ratio and sensitive homophily
ratio of the graphs to explain the observations, which are discussed in
Appendix G.1. From the figure, we can make the following observation: (i) For
the German dataset, excessively high or low weights assigned to the smoothness
regularization term $\lambda_{s}$ lead to lower accuracy values caused by a
lower homophily ratio of it, meaning that neighboring nodes may not
necessarily have similar labels. For this case, it’s challenging to increase
the performance by simply increasing the weights of the smoothness
regularization. In contrast, for the Bail dataset with a higher homophily
ratio, the accuracy increases and remains stable with the increasing value of
$\lambda_{s}$. (ii) Also, $\Delta_{\text{DP}}$ will drop with the increase of
$\lambda_{s}$ for the Bail dataset with a lower sensitive homophily ratio but
will enhance the bias issue for the German dataset with a higher sensitive
homophily ratio. This is because encouraging nodes with edges to have similar
label prediction results with smoothness regularization can also help to
result in consistent prediction results for different groups on the Bail
dataset with lower sensitive homophily ratio, where connected nodes have a
higher probability of sharing different sensitive attributes. Thus, consistent
prediction results for different groups can lead to drop on
$\Delta_{\text{DP}}$. However, for the German dataset with a higher sensitive
homophily ratio, such regularization can exacerbate the bias issue by giving
similar prediction results for nodes in the same sensitive group. Therefore,
it’s important to select $\lambda_{s}$ and $\lambda_{f}$ by considering
homophily ratio and sensitive homophily ratio. (iii) Generally, from our
experimental results, we can observe that $\lambda_{s}$ is better to be
selected from 0.5 to 1.0 to have both utility and fairness performance
guarantee. A too small (e.g., 0.1) value of $\lambda_{s}$ may degenerate the
accuracy performance in all three datasets. Meanwhile, it’s better to select
$\lambda_{f}$ from 1 to 5 to have lower $\Delta_{\text{DP}}$. The
hyperparameter sensitivity analysis on $\alpha$ and the number of MLP layers
$M$ are not included here as they are not directly relevant to our key
motivation. Therefore, we include sensitivity results of them in Appendix H.2.

Effect of Layers $K$. We then explore the effect of layers $K$ on the utility
(AUC, F1, Acc) and fairness ($\Delta_{\text{DP}}$ and $\Delta_{\text{EO}}$).
Figure 2 shows the corresponding results. We can find that (i) the utility
performance first increases and then decreases with the increase of $K$. This
is because a larger $K$ leads to over-smoothing issues, which will degenerate
the model’s performance; and (ii) $\Delta_{DP}$ and $\Delta_{EO}$ consistently
drop as $K$ increases. This is because more GMMD layers can effectively
minimize the MMD loss and lead to a fairer model. To learn a fair and accurate
model, the number of layers $K$ can be selected from 2 to 4 based on our
experimental results.

Figure 2: Different $K$ layers analysis on Bail and Credit datasets.

Empirical Analysis for Theorem 4.2. We can understand the empirical
implications of our Theorem 4.2 combining with Theorem 4.1 on GMMD and GMMD-S
as follows: by maximizing the inter-group kernel similarity term, which is
defined as $1/N_{0}N_{1}\sum_{i\in S_{0}}\sum_{j\in
S_{1}}k({\mathbf{F}}^{(K-1)}_{i},{\mathbf{F}}^{(K-1)}_{j})$, we can
simultaneously minimize the fairness metric. The corresponding results are
shown in Figure 3, where Sim denotes the inter-group kernel similarity
multiplied by 100. We can observe that $\Delta_{\text{DP}}$ will decrease with
the increase of the inter-group kernel similarity. Furthermore, at the initial
stages of training, the smoothness regularization will dominate the model,
which will increase the accuracy performance and lead to unfair predictions.
This is because the message passing of GNNs from smoothness regularization may
introduce or exacerbate bias [10]. Then, our proposed GMMD can minimize the
inter-group similarity and help GNN models to mitigate the biased prediction
results.

Figure 3: Empirical Analysis for the theorem on Bail and Credit datasets.

###  5.4 Ablation Study and Different Backbones

Table 2: Ablation Study on German dataset. Method | German
---|---
AUC ($\uparrow$) |  F1 ($\uparrow$) |  ACC ($\uparrow$) |  $\Delta_{\text{DP}}$ ($\downarrow$) |  $\Delta_{\text{eo}}$ ($\downarrow$)
w/o smooth |  67.08$\pm$0.43 |  82.46$\pm$0.38 |  70.80$\pm$0.33 | 0.78$\pm$0.42 | 1.01$\pm$0.37
w/o fair | 73.75$\pm$1.93 | 83.64$\pm$0.59 | 74.40$\pm$0.86 |  6.09$\pm$1.56 |  2.50$\pm$0.91
w/o both |  69.01$\pm$6.22 |  83.06$\pm$0.86 |  73.20$\pm$1.13 |  2.92$\pm$1.50 |  3.04$\pm$1.29
w/o sample |  73.68$\pm$2.18 | 83.15$\pm$0.17 | 73.37$\pm$1.00 | 1.37$\pm$0.79 |  2.21$\pm$1.51
GMMD | 74.03$\pm$2.28 |  83.13$\pm$0.64 |  72.28$\pm$1.64 |  2.09$\pm$1.60 | 0.76$\pm$0.52

Ablation Study. We conduct ablation studies to gain insights into the effect
of message passing without smoothness and fairness regularization, which are
denoted as “w/o smooth” and “w/o fair” in Table 5.4. We also conduct the
experiment without the sampling methods, “w/o sample”. First, smoothness
regularization alone can achieve great performance on AUC, F1 and Acc but
introduces bias and doesn’t perform well on the fairness metric. Fairness
regularization as an optimization target alone for GMMD produces better
results on the fairness metric. The full model (last row) achieves the best
performance, which illustrates that we can greatly control the trade-off
between fairness and utility performance with the message passing from two
regularization terms. Moreover, the average rank for “w/o sample” and the full
model are 2.4 and 2.4, which shows that our model with the sampling method can
achieve comparable performance with the model training with all samples. It
verifies the effectiveness of our sampling method to train GMMD.

Different Backbones Analysis. To further show the effectiveness of our model,
we adopt various backbones of our model. Specifically, we replace the message
passing method (${\mathbf{I}}-\tilde{{\mathbf{L}}}$) in Eq.(4) and Eq.(7) with
the message passing method employed in GAT and GIN. The detailed discussion of
GMMD with different backbones is put into the Appendix H.1. The corresponding
results on Bail dataset are given in Table 3 and results of other datasets are
in Table 5 in Appendix G.3. As shown in Table 3, our GMMD and GMMD-S
outperform the state-of-the-art method FairVGNN about both utility and
fairness in most cases, which once again proves the effectiveness of our
proposed method, and also shows that our framework is flexible to facilitate
various GNN backbones.

Table 3: Node classification performance with GIN and GAT as backbones. The
best and runner-up results of different backbones are colored in red and blue.

Dataset | Metric | GIN | GAT
---|---|---|---
Vanilla | FariVGNN | GMMD | GMMD-S | Vanilla | FariVGNN | GMMD | GMMD-S
Bail |  AUC ($\uparrow$) |  86.14$\pm$0.25 |  83.22$\pm$1.60 | 86.53$\pm$1.54 | 86.50$\pm$1.61 |  88.10$\pm$3.52 |  87.46$\pm$0.69 | 90.58$\pm$0.74 | 89.77$\pm$0.74
F1 ($\uparrow$) |  76.49$\pm$0.57 |  76.36$\pm$2.20 | 76.62$\pm$1.88 | 76.64$\pm$1.71 |  76.80$\pm$5.54 |  76.12$\pm$0.92 | 78.45$\pm$3.21 | 77.34$\pm$0.47
ACC ($\uparrow$) |  81.70$\pm$0.67 |  83.86$\pm$1.57 | 84.08$\pm$1.35 | 84.04$\pm$1.26 | 83.71$\pm$4.55 |  81.56$\pm$0.94 |  83.39$\pm$4.50 | 83.44$\pm$2.13
$\Delta_{\text{DP}}$ ($\downarrow$) |  8.55$\pm$1.61 |  5.67$\pm$0.76 | 3.57$\pm$1.11 | 3.61$\pm$1.42 |  5.66$\pm$1.78 |  5.41$\pm$3.25 | 1.24$\pm$0.28 | 3.27$\pm$1.79
$\Delta_{\text{EO}}$ ($\downarrow$) |  6.99$\pm$1.51 |  5.77$\pm$1.26 | 4.69$\pm$0.69 | 4.71$\pm$0.66 |  4.34$\pm$1.35 | 2.25$\pm$1.61 | 1.18$\pm$0.34 |  2.52$\pm$2.22

###  5.5 Visualization and Case Study

Generally, GMMD encourages a node $v_{i}$ to aggregate nodes $v_{j}$ from a
different sensitive group to mitigate fairness issues, using weights based on
kernel similarity $k({\mathbf{F}}^{(K-1)}_{i},{\mathbf{F}}^{(K-1)}_{j})$.
Next, we provide visualization and case study to understand how GMMD can
preserve utility performance when learning fair representation. More results
can be found in Appendix H.3. Specifically, in Figure 4 (a) and (b), we
calculate the pair-wise kernel similarity of randomly sampled nodes from
different sensitive groups. We visualize the distribution of similarity for
these node pairs with the same labels and different labels, respectively. We
can observe that node pairs having the same labels exhibit larger kernel
similarity, whereas nodes with distinct labels show a lower similarity. The
above observation suggests that our model assigns higher weights to nodes with
the same label, thereby encouraging nodes to aggregate relevant label semantic
information and preserving the utility performance. In Figure 4 (c) and (d),
we randomly sample the one-hop sub-graph of a central node and calculate the
kernel similarity based on learned representations between the central node
and neighbor nodes. We can observe that our model can successfully assign
higher weights to inter sensitive group edges which connect two nodes from the
same label. This observation also demonstrates that our proposed message
passing can keep utility performance by assigning higher weights to nodes with
the same label from different sensitive groups.

Figure 4: Visualization and Case Study. For case study in (c) and (d), node
color denotes the class label of nodes and node shape denotes sensitive group
of nodes. Blue lines denote inter sensitive group edges and their line width
is proportional to kernel similarity between the connected nodes.

##  6 Conclusion

In this paper, we propose a novel fairness-aware message passing framework
GMMD to mitigate fair issues on graph data. The key idea is to derive a new
message passing method for GNNs from an optimization problem with smoothness
and fairness constraints. Interestingly, the derived message passing can be
intuitively interpreted as encouraging a node to aggregate representations of
other nodes from different sensitive groups while subtracting representation
of other nodes from the same sensitive groups. By mixing node representations
from various sensitive groups, GMMD can alleviate the issue of learning
representations that have high correlation with sensitive attributes.
Moreover, we theoretically show that GMMD enjoys good downstream performance
on the fairness metric. We empirically validate our theoretical findings and
our extensive experiments on several graph benchmarks validate the superiority
of GMMD on both utility and fairness performance.

## References

  * [1] Wenqi Fan, Yao Ma, Qing Li, Yuan He, Eric Zhao, Jiliang Tang, and Dawei Yin.  Graph neural networks for social recommendation.  In The world wide web conference, pages 417–426, 2019.
  * [2] Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L Hamilton, and Jure Leskovec.  Graph convolutional neural networks for web-scale recommender systems.  In Proceedings of the 24th ACM SIGKDD international conference on knowledge discovery & data mining, pages 974–983, 2018.
  * [3] Will Hamilton, Zhitao Ying, and Jure Leskovec.  Inductive representation learning on large graphs.  Advances in neural information processing systems, 30, 2017.
  * [4] Thomas N Kipf and Max Welling.  Semi-supervised classification with graph convolutional networks.  arXiv preprint arXiv:1609.02907, 2016.
  * [5] Takuo Hamaguchi, Hidekazu Oiwa, Masashi Shimbo, and Yuji Matsumoto.  Knowledge transfer for out-of-knowledge-base entities: A graph neural network approach.  arXiv preprint arXiv:1706.05674, 2017.
  * [6] Zhichun Wang, Qingsong Lv, Xiaohan Lan, and Yu Zhang.  Cross-lingual knowledge graph alignment via graph convolutional networks.  In Proceedings of the 2018 conference on empirical methods in natural language processing, pages 349–357, 2018.
  * [7] Johannes Gasteiger, Aleksandar Bojchevski, and Stephan Günnemann.  Predict then propagate: Graph neural networks meet personalized pagerank.  arXiv preprint arXiv:1810.05997, 2018.
  * [8] Meng Liu, Hongyang Gao, and Shuiwang Ji.  Towards deeper graph neural networks.  In Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery & data mining, pages 338–348, 2020.
  * [9] 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, pages 680–688, 2021.
  * [10] Yushun Dong, Ninghao Liu, Brian Jalaian, and Jundong Li.  Edits: Modeling and mitigating data bias for graph neural networks.  In Proceedings of the ACM Web Conference 2022, pages 1259–1269, 2022.
  * [11] 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, pages 1938–1948, 2022.
  * [12] Alvin Rajkomar, Michaela Hardt, Michael D Howell, Greg Corrado, and Marshall H Chin.  Ensuring fairness in machine learning to advance health equity.  Annals of internal medicine, 169(12):866–872, 2018.
  * [13] Michael Feldman, Sorelle A Friedler, John Moeller, Carlos Scheidegger, and Suresh Venkatasubramanian.  Certifying and removing disparate impact.  In proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining, pages 259–268, 2015.
  * [14] Ninareh Mehrabi, Fred Morstatter, Nripsuta Saxena, Kristina Lerman, and Aram Galstyan.  A survey on bias and fairness in machine learning.  ACM Computing Surveys (CSUR), 54(6):1–35, 2021.
  * [15] Hongyi Ling, Zhimeng Jiang, Youzhi Luo, Shuiwang Ji, and Na Zou.  Learning fair graph representations via automated data augmentations.  In The Eleventh International Conference on Learning Representations, 2023.
  * [16] Avishek Bose and William Hamilton.  Compositional fairness constraints for graph embeddings.  In International Conference on Machine Learning, pages 715–724. PMLR, 2019.
  * [17] O Deniz Kose and Yanning Shen.  Fair node representation learning via adaptive data augmentation.  arXiv preprint arXiv:2201.08549, 2022.
  * [18] Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl.  Neural message passing for quantum chemistry.  In International conference on machine learning, pages 1263–1272. PMLR, 2017.
  * [19] Yao Ma, Xiaorui Liu, Tong Zhao, Yozen Liu, Jiliang Tang, and Neil Shah.  A unified view on graph neural networks as graph signal denoising.  In Proceedings of the 30th ACM International Conference on Information & Knowledge Management, pages 1202–1211, 2021.
  * [20] Xuran Pan, Shiji Song, and Gao Huang.  A unified framework for convolution-based graph neural networks.  2020\.
  * [21] Meiqi Zhu, Xiao Wang, Chuan Shi, Houye Ji, and Peng Cui.  Interpreting and unifying graph neural networks with an optimization framework.  In Proceedings of the Web Conference 2021, pages 1215–1226, 2021\.
  * [22] Siheng Chen, Yonina C Eldar, and Lingxiao Zhao.  Graph unrolling networks: Interpretable neural networks for graph signal denoising.  IEEE Transactions on Signal Processing, 69:3699–3713, 2021.
  * [23] Fangda Gu, Heng Chang, Wenwu Zhu, Somayeh Sojoudi, and Laurent El Ghaoui.  Implicit graph neural networks.  Advances in Neural Information Processing Systems, 33:11984–11995, 2020.
  * [24] Guoji Fu, Yifan Hou, Jian Zhang, Kaili Ma, Barakeel Fanseu Kamhoua, and James Cheng.  Understanding graph neural networks from graph signal denoising perspectives.  arXiv preprint arXiv:2006.04386, 2020.
  * [25] Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini.  The graph neural network model.  IEEE transactions on neural networks, 20(1):61–80, 2008.
  * [26] Joan Bruna, Wojciech Zaremba, Arthur Szlam, and Yann LeCun.  Spectral networks and locally connected networks on graphs.  arXiv preprint arXiv:1312.6203, 2013.
  * [27] Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst.  Convolutional neural networks on graphs with fast localized spectral filtering.  Advances in neural information processing systems, 29, 2016.
  * [28] Mingguo He, Zhewei Wei, Hongteng Xu, et al.  Bernnet: Learning arbitrary graph spectral filters via bernstein approximation.  Advances in Neural Information Processing Systems, 34:14239–14251, 2021.
  * [29] Mingqi Yang, Yanming Shen, Rui Li, Heng Qi, Qiang Zhang, and Baocai Yin.  A new perspective on the effects of spectrum in graph neural networks.  In International Conference on Machine Learning, pages 25261–25279. PMLR, 2022.
  * [30] Xiyuan Wang and Muhan Zhang.  How powerful are spectral graph neural networks.  In International Conference on Machine Learning, pages 23341–23362. PMLR, 2022.
  * [31] Mingguo He, Zhewei Wei, and Ji-Rong Wen.  Convolutional neural networks on graphs with chebyshev approximation, revisited.  arXiv preprint arXiv:2202.03580, 2022.
  * [32] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio.  Graph attention networks.  arXiv preprint arXiv:1710.10903, 2017.
  * [33] Enyan Dai, Tianxiang Zhao, Huaisheng Zhu, Junjie Xu, Zhimeng Guo, Hui Liu, Jiliang Tang, and Suhang Wang.  A comprehensive survey on trustworthy graph neural networks: Privacy, robustness, fairness, and explainability.  arXiv preprint arXiv:2204.08570, 2022.
  * [34] Tahleen Rahman, Bartlomiej Surma, Michael Backes, and Yang Zhang.  Fairwalk: towards fair graph embedding.  In Proceedings of the 28th International Joint Conference on Artificial Intelligence, pages 3289–3295, 2019.
  * [35] Jiaqi Ma, Junwei Deng, and Qiaozhu Mei.  Subgroup generalization and fairness of graph neural networks.  Advances in Neural Information Processing Systems, 34:1048–1061, 2021.
  * [36] Yushun Dong, Jian Kang, Hanghang Tong, and Jundong Li.  Individual fairness for graph neural networks: A ranking based approach.  In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pages 300–310, 2021.
  * [37] Peizhao Li, Yifei Wang, Han Zhao, Pengyu Hong, and Hongfu Liu.  On dyadic fairness: Exploring and mitigating bias in graph connections.  In International Conference on Learning Representations, 2021.
  * [38] O Deniz Kose and Yanning Shen.  Fairnorm: Fair and fast graph neural network training.  arXiv preprint arXiv:2205.09977, 2022.
  * [39] Chirag Agarwal, Himabindu Lakkaraju, and Marinka Zitnik.  Towards a unified framework for fair and stable graph representation learning.  In Uncertainty in Artificial Intelligence, pages 2114–2124. PMLR, 2021.
  * [40] Zhimeng Jiang, Xiaotian Han, Chao Fan, Zirui Liu, Na Zou, Ali Mostafavi, and Xia Hu.  Fmp: Toward fair graph message passing against topology bias.  arXiv preprint arXiv:2202.04187, 2022.
  * [41] Zhimeng Jiang, Xiaotian Han, Chao Fan, Zirui Liu, Xiao Huang, Na Zou, Ali Mostafavi, and Xia Hu.  Topology matters in fair graph learning: a theoretical pilot study.  2023\.
  * [42] Arthur Gretton, Karsten Borgwardt, Malte Rasch, Bernhard Schölkopf, and Alex Smola.  A kernel method for the two-sample-problem.  Advances in neural information processing systems, 19, 2006.
  * [43] Bharath K Sriperumbudur, Arthur Gretton, Kenji Fukumizu, Gert Lanckriet, and Bernhard Schölkopf.  Injective hilbert space embeddings of probability measures.  In 21st Annual Conference on Learning Theory (COLT 2008), pages 111–122. Omnipress, 2008.
  * [44] Christos Louizos, Kevin Swersky, Yujia Li, Max Welling, and Richard Zemel.  The variational fair autoencoder.  arXiv preprint arXiv:1511.00830, 2015.
  * [45] Luca Oneto, Michele Donini, Giulia Luise, Carlo Ciliberto, Andreas Maurer, and Massimiliano Pontil.  Exploiting mmd and sinkhorn divergences for fair and transferable representation learning.  Advances in Neural Information Processing Systems, 33:15360–15370, 2020.
  * [46] Novi Quadrianto and Viktoriia Sharmanska.  Recycling privileged learning and distribution matching for fairness.  Advances in neural information processing systems, 30, 2017.
  * [47] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka.  How powerful are graph neural networks?  arXiv preprint arXiv:1810.00826, 2018.
  * [48] Sahil Verma and Julia Rubin.  Fairness definitions explained.  In Proceedings of the international workshop on software fairness, pages 1–7, 2018.
  * [49] David Madras, Elliot Creager, Toniann Pitassi, and Richard Zemel.  Learning adversarially fair and transferable representations.  In International Conference on Machine Learning, pages 3384–3393. PMLR, 2018.
  * [50] Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra.  Beyond homophily in graph neural networks: Current limitations and effective designs.  NeurIPS, pages 7793–7804, 2020.
  * [51] Diederik P Kingma and Jimmy Ba.  Adam: A method for stochastic optimization.  arXiv preprint arXiv:1412.6980, 2014.

##  Appendix A Omitted Derivation of Fairness Aware Message Passing based on
MMD

###  A.1 Derivation of Fairness-aware Message Passing based on MMD

In this section, we provide the details of derivations of our fairness-aware
message passing in Eq.(4). As shown in the Eq.(1), the optimization objective
can be split into two parts $h_{s}(\mathbf{F})$ and $h_{f}(\mathbf{F})$.
Following previous research [19], we perform one-step gradient to obtain the
fairness-aware message passing. The one-step gradient on $h_{s}(\mathbf{F})$
can be written as:

$-\frac{\partial
h_{s}(\mathbf{F})}{\partial\mathbf{F}}=-(\lambda_{s}\tilde{\mathbf{L}}\mathbf{F}+\mathbf{F}-\mathbf{X}_{\text{in}}).$
(9)

Then, we use $h_{f}(\mathbf{F})=l_{\text{MMD}}(\mathbf{F})$ in Eq.(2). To
simplify the notation, we denote
$k_{ij}=e^{-\alpha\left\|\mathbf{F}_{i}-\mathbf{F}_{j}\right\|^{2}}$. One-step
gradient is performed on $h_{s}(\mathbf{F})$ to obtain:

$-\frac{\partial
h_{f}(\mathbf{F})}{\partial{\mathbf{F}}_{i}}=\left\\{\begin{array}[]{l}\frac{4\alpha}{N_{0}^{2}}\sum_{v_{j}\in\mathcal{S}_{0}}({\mathbf{F}}_{i}-{\mathbf{F}}_{j})k_{ij}-\frac{4\alpha}{N_{0}N_{1}}\sum_{v_{j}\in\mathcal{S}_{1}}({\mathbf{F}}_{i}-{\mathbf{F}}_{j})k_{ij},~{}~{}i\in\mathcal{S}_{0},\\\
\frac{4\alpha}{N_{1}^{2}}\sum_{v_{j}\in\mathcal{S}_{1}}({\mathbf{F}}_{i}-{\mathbf{F}}_{j})k_{ij}-\frac{4\alpha}{N_{0}N_{1}}\sum_{v_{j}\in\mathcal{S}_{0}}({\mathbf{F}}_{i}-{\mathbf{F}}_{j})k_{ij},~{}~{}i\in\mathcal{S}_{1}.\end{array}\right.$
(10)

This equation can be re-written as:

$\displaystyle\left\\{\begin{array}[]{l}(\frac{4\alpha}{N^{2}_{0}}\sum_{v_{j}\in\mathcal{S}_{0}}k_{ij}-\frac{4\alpha}{N_{0}N_{1}}\sum_{v_{j}\in\mathcal{S}_{1}}k_{ij}){\mathbf{F}}_{i}+\frac{1}{N_{0}}\sum_{v_{j}\in\mathcal{S}_{0}}{\mathbf{F}}_{j}k_{ij}-\frac{1}{N_{1}}\sum_{v_{j}\in\mathcal{S}_{1}}{\mathbf{F}}_{j}k_{ij},~{}~{}i\in\mathcal{S}_{0},\\\
(\frac{4\alpha}{N^{2}_{1}}\sum_{v_{j}\in\mathcal{S}_{1}}k_{ij}-\frac{4\alpha}{N_{0}N_{1}}\sum_{v_{j}\in\mathcal{S}_{0}}k_{ij}){\mathbf{F}}_{i}+\frac{1}{N_{1}}\sum_{v_{j}\in\mathcal{S}_{1}}{\mathbf{F}}_{j}k_{ij}-\frac{1}{N_{0}}\sum_{v_{j}\in\mathcal{S}_{0}}{\mathbf{F}}_{j}k_{ij},~{}~{}i\in\mathcal{S}_{1}.\end{array}\right.$
(11) $\displaystyle=\sum_{j=1}^{N}4\alpha
P_{ij}{\mathbf{F}}_{j}=-\frac{\partial
h_{f}(\mathbf{F})}{\partial{\mathbf{F}}_{i}},$

where for $i\neq j$, if $v_{i}$ and $v_{j}$ are in the same sensitive group
${\mathcal{S}}_{0}$,
${P}_{ij}=-k({\mathbf{F}}^{(k-1)}_{i},{\mathbf{F}}^{(k-1)}_{j})/N_{0}^{2}$. If
$v_{i}$ and $v_{j}$ are in the same sensitive group $\mathcal{S}_{1}$,
$P_{ij}=-k({\mathbf{F}}^{(k-1)}_{i},{\mathbf{F}}^{(k-1)}_{j})/N_{1}^{2}$. If
$v_{i}$ and $v_{j}$ are in different sensitive groups,
$P_{ij}=k({\mathbf{F}}^{(k-1)}_{i},\mathbf{F}^{(k-1)}_{j})/N_{0}N_{1}$. And
$\widetilde{P}_{ii}=-\sum_{k=1,m\neq i}^{N}\widetilde{P}_{im}$. Finally, we
can get the fairness-aware message passing by performing gradient descent on
the Eq.(1) with $h_{f}({\mathbf{F}})=l_{\text{MMD}}({\mathbf{F}})$:

$\displaystyle{\mathbf{F}}^{(k)}$
$\displaystyle={\mathbf{F}}^{(k-1)}-\gamma\nabla
h\left(\mathbf{F}^{k-1}\right)={\mathbf{F}}^{(k-1)}-\gamma\frac{\partial
h_{s}({\mathbf{F}}^{(k-1)})}{\partial{\mathbf{F}}^{(k-1)}}-\gamma\frac{\partial
h_{f}({\mathbf{F}}^{(k-1)})}{\partial{\mathbf{F}}^{(k-1)}},$ (12)
$\displaystyle={\mathbf{F}}^{(k-1)}-\gamma(\lambda_{s}\tilde{{\mathbf{L}}}{\mathbf{F}}^{(k-1)}+{\mathbf{F}}^{(k-1)}-{\mathbf{X}}_{\text{in}})+4\gamma\lambda_{f}\alpha{\mathbf{P}}{\mathbf{F}}^{(k-1)},$
$\displaystyle=((1-\gamma){\mathbf{I}}-\gamma\lambda_{s}\tilde{{\mathbf{L}}}+4\gamma\lambda_{f}\alpha{\mathbf{P}}){\mathbf{F}}^{(k-1)}+\gamma{\mathbf{X}}_{\text{in}}.$

###  A.2 Derivation of Simplified Fairness-aware Message Passing

In this section, we provide the details of derivations of our simplied
fairness-aware message passing in Eq.(7). Similarly, we can obtain the
gradient of the smoothness function as that in Eq.(9). When
$\tilde{h}_{f}({\mathbf{F}})=-\frac{2}{N_{0}N_{1}}\sum_{v_{i}\in{\mathcal{S}}_{0}}\sum_{v_{j}\in{\mathcal{S}}_{1}}k\left({\mathbf{F}}_{i},{\mathbf{F}}_{j}\right)$.
One-step gradient is performed on $\tilde{h}_{f}({\mathbf{F}})$, which gives
us:

$\displaystyle-\frac{\partial\tilde{h}_{f}({\mathbf{F}})}{\partial{F}_{i,m}}=$
$\displaystyle\left\\{\begin{array}[]{l}-\frac{4\alpha}{N_{0}N_{1}}\sum_{v_{j}\in{\mathcal{S}}_{1}}({\mathbf{F}}_{i}-{\mathbf{F}}_{j})k_{ij},i\in\mathcal{S}_{0},\\\
-\frac{4\alpha}{N_{0}N_{1}}\sum_{v_{j}\in{\mathcal{S}}_{0}}({\mathbf{F}}_{i}-{\mathbf{F}}_{j})k_{ij},i\in\mathcal{S}_{1}.\end{array}\right.$
(13) $\displaystyle=$
$\displaystyle\left\\{\begin{array}[]{l}-\frac{4\alpha}{N_{0}N_{1}}\sum_{v_{j}\in{\mathcal{S}}_{1}}k_{ij}{\mathbf{F}}_{i}+\frac{4\alpha}{N_{0}N_{1}}\sum_{v_{j}\in{\mathcal{S}}_{1}}{\mathbf{F}}_{j}k_{ij},i\in\mathcal{S}_{0},\\\
-\frac{4\alpha}{N_{0}N_{1}}\sum_{v_{j}\in{\mathcal{S}}_{0}}k_{ij}{\mathbf{F}}_{i}+\frac{4\alpha}{N_{0}N_{1}}\sum_{v_{j}\in{\mathcal{S}}_{0}}{\mathbf{F}}_{j}k_{ij},i\in{\mathcal{S}}_{1}.\end{array}\right.$
$\displaystyle=$
$\displaystyle\sum_{j=1}^{N}4\alpha\widetilde{{P}}_{i,j}{\mathbf{F}}_{j},$

where for $i\neq j$, if $v_{i}$ and $v_{j}$ are in the same sensitive group,
$\widetilde{{P}}_{ij}=0$. If $v_{i}$ and $v_{j}$ are in different sensitive
groups, $\widetilde{P}_{ij}=-k(\mathbf{F}_{i},{\mathbf{F}}_{j})/N_{0}N_{1}$.
And $\widetilde{{P}}_{ii}=-\sum_{k=1,m\neq i}^{N}\widetilde{{P}}_{im}$.
Finally, we can get the fairness-aware message passing by performing gradient
descent on the Eq.(1) with $h_{f}({\mathbf{F}})=\tilde{h}_{f}({\mathbf{F}})$:

$\displaystyle{\mathbf{F}}^{(k)}$
$\displaystyle={\mathbf{F}}^{(k-1)}-\gamma\nabla
h\left({\mathbf{F}}^{(k-1)}\right)={\mathbf{F}}^{(k-1)}-\gamma\frac{\partial
h_{s}({\mathbf{F}}^{(k-1)})}{\partial{\mathbf{F}}^{(k-1)}}-\gamma\frac{\partial\tilde{h}_{f}({\mathbf{F}}^{(k-1)})}{\partial{\mathbf{F}}^{(k-1)}},$
(14)
$\displaystyle={\mathbf{F}}^{(k-1)}-\gamma(\lambda_{s}\tilde{{\mathbf{L}}}{\mathbf{F}}^{(k-1)}+{\mathbf{F}}^{(k-1)}-{\mathbf{X}}_{\text{in}})+4\gamma\lambda_{f}\alpha\widetilde{{\mathbf{P}}}{\mathbf{F}}^{(k-1)},$
$\displaystyle=((1-\gamma){\mathbf{I}}-\gamma\lambda_{s}\tilde{{\mathbf{L}}}+4\gamma\lambda_{f}\alpha\widetilde{{\mathbf{P}}}){\mathbf{F}}^{(k-1)}+\gamma{\mathbf{X}}_{\text{in}}.$

##  Appendix B The Training Algorithm

Input: $G=(\mathcal{V},\mathcal{E})$

Output: Feature Extractor MLP with parameters $\theta$.

Initialize MLP’s parameter $\theta$

repeat

${\mathbf{X}}_{\text{in}}\leftarrow\text{MLP}_{\theta}({\mathbf{X}})$

Randomly select a set nodes from $\mathcal{V}$ to obtain
${\mathcal{S}}^{\prime}_{0}$ and ${\mathcal{S}}^{\prime}_{1}$

Obtain the prediction results $\hat{{\mathbf{Y}}}$ by Eq.(8) ($K=2$) with the
softmax function

$\mathcal{L}\leftarrow-\sum_{v_{i}\in\mathcal{V}_{L}}\sum_{j=1}^{c}Y_{i,j}\log\hat{Y}_{i,j}$

Update the parameters $\theta$ based on $\mathcal{L}$

until  _convergence or reaching max iteration_ ;

Algorithm 1 Training Algorithm of GMMD and GMMD-S

The overall training algorithm is shown in Algorithm 1. We first obtain the
encoded feature of nodes, ${\mathbf{X}}_{\text{in}}$, with $M$ layers MLP.
Then, we sample a set of nodes (${\mathcal{S}}^{\prime}_{0}$ and
${\mathcal{S}}^{\prime}_{1}$) for fairness regularization of GMMD or GMMD-S.
We then adopt a $K$-layer GNN with each layer performing fairness-aware
message passing in Eq.(8) with the softmax function. Finally, we update the
parameters $\theta$ with the Cross-Entropy Loss $\mathcal{L}$ and
$Y_{i,j}=\mathbbm{1}(y_{i}=j)$ is a binary value represents whether node $i$
belongs to class $j$.

##  Appendix C Different Backbones

In this section, we will illustrate our model with various backbones. As
discussed in section 4.4, for the fairness-aware message passing in Eq.(4) and
Eq.(7), the first term of these equations is the message passing method of
GCN, $\mathbf{I}-\tilde{\mathbf{L}}$. Therefore, we can replace the first term
with message passing of other GNNs. Specifically, we use GAT and GIN as
examples to demonstrate how to change different message passing methods. Note
that our model can be generalized to most GNN models.

###  C.1 GMMD with GIN

Graph Isomorphism Network (GIN) adopts the message passing by the following
equation [47]:

${\mathbf{F}}^{(K)}=({\mathbf{A}}+(1+\epsilon){\mathbf{I}}){\mathbf{F}}^{(K-1)},$
(15)

Hence, the fairness aware message passing by combining GMMD with GIN can be
written as:

${\mathbf{F}}^{(k)}=\big{(}(1-\gamma)({\mathbf{A}}+(1+\epsilon){\mathbf{I}})+4\gamma\lambda_{f}\alpha{\mathbf{P}}\big{)}{\mathbf{F}}^{(k-1)}+\gamma{\mathbf{X}}_{\text{in}}$
(16)

###  C.2 GMMD with GAT

Graph Attention Networks (GAT) adopts the message passing by assigning
different weights to neighbor nodes as [32]:

${\mathbf{F}}^{(K)}_{i}=\sum_{i\in\mathcal{N}(i)}a^{(K-1)}_{ij}{\mathbf{F}}^{(K-1)}_{j}\;\;\text{with}\;\;a^{(K-1)}_{ij}=\frac{\exp\left(e^{(K-1)}_{ij}\right)}{\sum_{j\in\mathcal{N}}(i)\exp\left(e^{(K-1)}_{ij}\right)},$
(17)

where ${\mathcal{N}}(i)$ is the set of neighbors of $v_{i}$ and
$a^{(K-1)}_{ij}$ is a learnable attention score to denote the importance of
node $v_{j}$ to $v_{i}$. Specifically, $a^{(K-1)}_{ij}$ is a normalized form
of $e^{(K-1)}_{ij}$ for the $(K-1)$-th layer and $e^{(K-1)}_{ij}$ is
calculated as:

$e^{(K-1)}_{ij}=\operatorname{LeakyReLU}\left(\left[{\mathbf{F}}^{(K-1)}_{i}\|{\mathbf{F}}^{(K)}_{j}\right]\mathbf{b}\right),$
(18)

where $[:\|:]$ denotes the concatenation operation and
$\mathbf{b}\in\mathbb{R}^{2c}$ is a learnable vector. We can denote the
attention score $a^{(K-1)}_{ij}$ to a new adjaceny matrix
${\mathbf{A}}^{\text{att}}$, where $A^{\text{att}}_{ij}=a^{(K-1)}_{ij}$ for
$(v_{i},v_{j})\in{\mathcal{E}}$; otherwise $A^{\text{att}}_{ij}=0$. Then, we
can obtain our proposed GMMD with GAT:

${\mathbf{F}}^{(k)}=\big{(}(1-\gamma){\mathbf{A}}^{\text{att}}+4\gamma\lambda_{f}\alpha{\mathbf{P}}\big{)}{\mathbf{F}}^{(k-1)}+\gamma{\mathbf{X}}_{\text{in}}.$
(19)

In summary, we can replace the first term of Eq.(4) and Eq.(7) with other
message passing methods for most GNNs. Moreover, we can also obtain GMMD-S
with GAT and GIN backbones by replacing ${\mathbf{P}}$ in Eq.(16) and Eq.(19)
with $\widetilde{{\mathbf{P}}}$.

##  Appendix D Efficiency Analysis

###  D.1 Time Complexity Analysis

We give the detailed time complexity per iteration of both GMMD and GMMD-S.
Since our GMMD is agnostic to GNN models, for the time complexity analysis, we
consider $K$-layer GCN as backbone, i.e., the fairness aware message passing
is given in Eq.(4) and Eq.(7). A $K$-layer GCN with $c$ hidden dimensions has
$\mathcal{O}\left(cK|\mathcal{E}|+Nc^{2}K\right)$, where $|\mathcal{E}|$ is
the number of edges. For our model GMMD and GMMD-S, the extra time complexity
is from our proposed fairness constrained message passing. The time complexity
for the fairness constrained message passing part of GMMD and GMMD-S are
$\mathcal{O}(c^{2}KN^{2})$ and $\mathcal{O}(c^{2}KN_{0}N_{1})$ with $K$
layers. The exact time complexity for these two models are
$\mathcal{O}(c^{2}KN^{2}+DK|\mathcal{E}|+Nc^{2}K)$ and
$\mathcal{O}(c^{2}KN_{0}N_{1}+cK|\mathcal{E}|+Nc^{2}K)$. To further improve
the efficiency of our model, we randomly sample $N_{s}$ nodes from each
sensitive group equally as discussed in the section D, the time complexity of
each iteration with sampling are
$\mathcal{O}(4c^{2}KN_{s}^{2}+cK|\mathcal{E}|+Nc^{2}K)$ and
$\mathcal{O}(c^{2}KN_{s}^{2}+DK|\mathcal{E}|+Nc^{2}K)$. Note that we can also
change hidden dimensions $c$ to any values.

##  Appendix E Fairness Metric for Group Fairness

In this section, we discuss the group fairness metric for the binary
classification problem with binary sensitive attributes. Following existing
work on fair models [14, 48], we adopt the difference in equal opportunity
$\Delta_{EO}$ and demographic parity $\Delta_{DP}$ as the fairness metrics.
They are defined as:

Equal Opportunity [14]: Equal opportunity requires the probability of
assigning positive instances to positive class should be equal for both
subgroup members, which can be written as:

$\mathbb{E}(\hat{y}\mid S=0,y=1)=\mathbb{E}(\hat{y}\mid S=1,y=1),$ (20)

where $\hat{y}$ is the predicted label and $S$ represents the sensitive
attribute.The equal opportunity expects the classifier to give equal true
positive rates across the subgroups. In this paper, we report the difference
for equal opportunity ($\Delta_{\text{EO}}$) [49], which is defined as:

$\Delta_{\text{EO}}=|\mathbb{E}(\hat{y}\mid S=0,y=1)-\mathbb{E}(\hat{y}\mid
S=1,y=1)|.$ (21)

Demographic Parity [14]: Demographic Parity requires the predictions to be
independent with the sensitive attribute $S$, where $\hat{y}\perp S$. It can
be formally written as:

$\mathbb{E}(\hat{y}\mid S=0)=\mathbb{E}(\hat{y}\mid S=1).$ (22)

The difference in Demographic Parity [49] is defined as :

$\Delta_{\text{DP}}=|\mathbb{E}(\hat{y}\mid S=0)-\mathbb{E}(\hat{y}\mid S=1)|$
(23)

Note that the difference between equal opportunity and demographic parity
measures fairness from different dimensions. Difference of equal opportunity
needs similar performance across sensitive groups; while demographic parity
focuses more on fair demographics. The smaller $\Delta_{EO}$ and $\Delta_{DP}$
are, the more fair the model is.

##  Appendix F Proof of Theorems

###  F.1 Proof of Theorem 4.1

Theorem 4.1. Minimizing representation discrepancy between two sensitive
groups
$\Delta_{\text{DP}}^{\text{Rep}}({\mathbf{F}}^{(K)})=\|\mathbb{E}({\mathbf{F}}^{(K)}\mid
S=0)-\mathbb{E}(\mathbf{F}^{(K)}\mid S=1)\|$ is equivalent to minimizing
$\Delta_{\text{DP}}$ of the model prediction for a binary classification
problem, and ${\mathbf{F}}^{(K)}$ is the final output of a $K$ layer model
before the softmax function. When $K$ is set as 2, we have:

$\displaystyle\Delta_{\text{DP}}\leq\frac{L}{2}\left\|{\mathbf{W}}\right\|\left(\Delta_{\text{DP}}^{\text{Rep}}({\mathbf{F}}^{(K)})+C_{1}\left\|\bm{\Delta}\right\|\right),$
(24)

where
$C_{1}=(2+\frac{4}{N_{0}}+\frac{4}{N_{1}})^{2}+6+\frac{8}{N_{0}}+\frac{8}{N_{1}}$
and $\bm{\Delta}$ is the maximal deviation of ${\mathbf{X}}$ from $\mu$ i.e.,
$\bm{\Delta}_{m}=\max_{i}|\mu_{m}-{\mathbf{X}}_{i,m}|$. $L<1$ is the Lipschitz
constant for the Softmax function.

###### Proof.

To simplify the notation, we use $g(*)$ to replace the Softmax function
$\mathrm{Softmax}(*)$ in the following part. $c$ is the number of the classes
and we consider $c$ as 2 following current papers on group fairness. For the
binary classification problem, the demographic parity distance
$\Delta_{\text{DP}}$ is equivalent to the absolute expected difference in
classifier outcomes between the two groups
$\Delta_{\text{DP}}=\left|\frac{1}{N_{0}}\sum_{i\in{\mathcal{S}}_{0}}\hat{y}_{i,1}-\frac{1}{N_{1}}\sum_{j\in{\mathcal{S}}_{1}}\hat{y}_{j,1}\right|$
[49], where $\hat{{\mathbf{y}}}_{j}=[\hat{y}_{j,0},\hat{y}_{j,1}]^{T}$ and
$\hat{y}_{j,1}$ denotes the predicted probability of being positive for node
$v_{j}$. $D$ is the dimension of ${\mathbf{F}}^{(K)}$. Before discussing the
derivation of our theorem, we will introduce some properties of the Softmax
function for the binary classification function. Considering the Softmax
function $g(*)$ on two vectors with two dimensions,
$\mathbf{x}\in\mathbb{R}^{2}$ and $\mathbf{y}\in\mathbb{R}^{2}$, the output of
the Softmax function on these two vectors can be written as
${\mathbf{x}}\in[1-a_{1},a_{1}]$ and $\mathbf{y}\in[1-b_{1},b_{1}]$.
$\mathrm{Softmax}(*)$ is Lipschitz continuous with Lipschitz constant $L$,
i.e., $\left\|g({\mathbf{x}})-g({\mathbf{y}})\right\|\leq
L\left\|{\mathbf{x}}-{\mathbf{y}}\right\|$. We can have the following
equation:

$\displaystyle\left\|g(\mathbf{x})-g(\mathbf{y})\right\|=|a_{1}-b_{1}|+|1-a_{1}-(1-b_{1})|=2|a_{1}-b_{1}|$
(25) $\displaystyle=2|g(\mathbf{x})_{1}-g(\mathbf{y})_{1}|\leq
L\left\|\mathbf{x}-\mathbf{y}\right\|,$

where $g({\mathbf{x}})_{1}$ represents the value of the dimension $1$ for the
output of $g({\mathbf{x}})_{1}$. Based on these properties, we can get the
equations for $\Delta_{\text{DP}}$ and $\Delta_{\text{DP}}^{\text{Rep}}$:

$\displaystyle\Delta_{\text{DP}}=\Big{|}\frac{1}{N_{0}}\sum_{i\in{\mathcal{S}}_{0}}g({\mathbf{F}}^{(K)}_{i}{\mathbf{W}})_{1}-\frac{1}{N_{1}}\sum_{j\in{\mathcal{S}}_{1}}g({\mathbf{F}}^{(K)}_{j}\mathbf{W})_{1}\Big{|},$
(26)
$\displaystyle\Delta_{\text{DP}}^{\text{Rep}}=\Big{\|}\frac{1}{N_{0}}\sum_{i\in{\mathcal{S}}_{0}}{\mathbf{F}}^{(K)}_{i}-\frac{1}{N_{1}}\sum_{j\in{\mathcal{S}}_{1}}{\mathbf{F}}^{(K)}_{j}\Big{\|}=\left\|\mathbf{\mu}^{(0)}_{K}-\mathbf{\mu}^{(1)}_{K}\right\|.$

For a node $v_{i}\in\mathcal{S}_{0}$, we can write
$\mathbf{F}_{i}^{(K)}=\mathbf{\mu}_{K}^{(0)}+\mathbf{\sigma}^{K}_{i}$, where
$\mathbf{\mu}_{K}^{(0)}$ is the mean of node representation from group 0, and
$\mathbf{\sigma}^{K}_{i}$ represents the difference between the mean
representation and the representation of node $v_{i}$. Similarly, for a node
$v_{i}\in\mathcal{S}_{1}$,
$\mathbf{F}_{i}^{(K)}=\mathbf{\mu}_{K}^{(1)}+\mathbf{\sigma}^{K}_{i}$, where
$\mathbf{\mu}_{K}^{(1)}$ is the mean of node representation from group 1. From
Eq.(25) and using node $v_{i}$ from the group 0 as an example, we can get:

$2\big{|}g(\mathbf{F}_{i}^{(K)}\mathbf{W})_{1}-g(\mu_{K}^{(0)}\mathbf{W})_{1}\big{|}\leq
L\|\sigma_{i}^{K}\mathbf{W}\|$ (27)

This gives us

$\displaystyle
g(\mu_{K}^{(0)}\mathbf{W})_{1}-\frac{L}{2}\|\mathbf{\sigma}^{K}_{i}\mathbf{W}\|\leq
g((\mathbf{\mu}_{K}^{(0)}+\mathbf{\sigma}_{K,i})\mathbf{W})_{1}=g(\mathbf{F}^{(K)}_{i}\mathbf{W})_{1}\leq
g(\mu_{K}^{(0)}\mathbf{W})_{1}+\frac{L}{2}\|\mathbf{\sigma}^{K}_{i}\mathbf{W}\|.$
(28)

Based on Equations (25), (28), we have the following inequality holds:

$\displaystyle
g(\mu_{K}^{(0)}{\mathbf{W}})_{1}-g(\mu_{K}^{(1)}{\mathbf{W}})_{1}-\frac{1}{N_{0}}\sum_{i=1}^{N_{0}}\frac{L}{2}\|\mathbf{\sigma}^{K}_{i}{\mathbf{W}}\|-\frac{1}{N_{1}}\sum_{j=1}^{N_{1}}\frac{L}{2}\|\mathbf{\sigma}^{K}_{j}{\mathbf{W}}\|$
(29)
$\displaystyle\leq\frac{1}{N_{0}}\sum_{i\in{\mathcal{S}}_{0}}g({\mathbf{F}}^{(K)}_{i}{\mathbf{W}})_{1}-\frac{1}{N_{1}}\sum_{j\in{\mathcal{S}}_{1}}g({\mathbf{F}}^{(K)}_{j}{\mathbf{W}})_{1}\leq$
$\displaystyle
g(\mu_{K}^{(0)}{\mathbf{W}})_{1}-g(\mu_{K}^{(1)}{\mathbf{W}})_{1}+\frac{1}{N_{0}}\sum_{i=1}^{N_{0}}\frac{L}{2}\|\mathbf{\sigma}^{K}_{i}{\mathbf{W}}\|+\frac{1}{N_{1}}\sum_{j=1}^{N_{1}}\frac{L}{2}\|\mathbf{\sigma}^{K}_{i}{\mathbf{W}}\|$

Define
$a=g(\mu_{K}^{(0)}{\mathbf{W}})_{1}-g(\mu_{K}^{(1)}{\mathbf{W}})_{1}-\frac{1}{N_{0}}\sum_{i=1}^{N_{0}}\frac{L}{2}\|\mathbf{\sigma}^{K}_{i}{\mathbf{W}}\|-\frac{1}{N_{1}}\sum_{j=1}^{N_{1}}\frac{L}{2}\|\mathbf{\sigma}^{K}_{j}{\mathbf{W}}\|$
and
$b=g(\mu_{K}^{(0)}{\mathbf{W}})_{1}-g(\mu_{K}^{(1)}{\mathbf{W}})_{1}+\frac{1}{N_{0}}\sum_{i=1}^{N_{0}}\frac{L}{2}\|\mathbf{\sigma}^{K}_{i}{\mathbf{W}}\|+\frac{1}{N_{1}}\sum_{j=1}^{N_{1}}\frac{L}{2}\|\mathbf{\sigma}^{K}_{i}{\mathbf{W}}\|$.
Eq.(29) leads to:

$\displaystyle\Delta_{\text{DP}}=|\frac{1}{N_{0}}\sum_{i\in{\mathcal{S}}_{0}}g({\mathbf{F}}^{(K)}_{i}{\mathbf{W}})_{1}-\frac{1}{N_{1}}\sum_{j\in{\mathcal{S}}_{1}}g({\mathbf{F}}^{(K)}_{j}{\mathbf{W}})_{1}|\leq\max(|a|,|b|).$
(30)

If we consider the case, $|a|\geq|b|$:

$\displaystyle\Delta_{\text{DP}}$
$\displaystyle\leq\Big{|}g(\mu_{K}^{(0)}{\mathbf{W}})_{1}-g(\mu_{K}^{(1)}{\mathbf{W}})_{1}-\frac{1}{N_{0}}\sum_{i=1}^{N_{0}}\frac{L}{2}\|\mathbf{\sigma}^{K}_{i}{\mathbf{W}}\|-\frac{1}{N_{1}}\sum_{j=1}^{N_{1}}\frac{L}{2}\|\mathbf{\sigma}^{K}_{j}{\mathbf{W}}\|\Big{|}$
(31)
$\displaystyle\leq\left|g(\mu_{K}^{(0)}{\mathbf{W}})_{1}-g(\mu_{K}^{(1)}{\mathbf{W}})_{1}\right|+\frac{1}{N_{0}}\sum_{i=1}^{N_{0}}\frac{L}{2}\|\mathbf{\sigma}^{K}_{i}{\mathbf{W}}\|+\frac{1}{N_{1}}\sum_{j=1}^{N_{1}}\frac{L}{2}\|\mathbf{\sigma}^{K}_{j}{\mathbf{W}}\|$
$\displaystyle\leq\left|g(\mu_{K}^{(0)}{\mathbf{W}})_{1}-g(\mu_{K}^{(1)}{\mathbf{W}})_{1}\right|+\frac{1}{N_{0}}\sum_{i=1}^{N_{0}}\frac{L}{2}\|\mathbf{\sigma}^{K}_{i}\|\|{\mathbf{W}}\|+\frac{1}{N_{1}}\sum_{j=1}^{N_{1}}\frac{L}{2}\|\mathbf{\sigma}^{K}_{j}\|\|{\mathbf{W}}\|$
$\displaystyle\leq\left|g(\mu_{K}^{(0)}{\mathbf{W}})_{1}-g(\mu_{K}^{(1)}{\mathbf{W}})_{1}\right|+\frac{L}{2}\|{\mathbf{W}}\|\left\|\bm{\Delta}^{K}\right\|+\frac{L}{2}\|{\mathbf{W}}\|\left\|\bm{\Delta}^{K}\right\|,$

where $\bm{\Delta}^{K}_{m}=\max_{i}|\sigma^{K}_{i,m}|$ and $\sigma^{K}_{i,m}$
represents the $m$-th dimension of $\sigma^{K}_{i,m}$. Similarly, we can get
the same inequality for the case $|a|<|b|$. Based on Eq.(25), we can get:

$\displaystyle\Delta_{\text{DP}}$
$\displaystyle\leq\left|g(\mu_{K}^{(0)}{\mathbf{W}})_{1}-g(\mu_{K}^{(1)}{\mathbf{W}})_{1}\right|+\frac{L}{2}\|{\mathbf{W}}\|(\left\|\bm{\Delta}^{K}\right\|)+\frac{L}{2}\|\mathbf{W}\|(\left\|\bm{\Delta}^{K}\right\|)$
(32)
$\displaystyle\leq\frac{L}{2}\left\|\mu_{K}^{(0)}\mathbf{W}-\mu_{K}^{(1)}{\mathbf{W}}\right\|+\frac{L}{2}\|{\mathbf{W}}\|\left\|\bm{\Delta}^{K}\right\|+\frac{L}{2}\|{\mathbf{W}}\|\left\|\bm{\Delta}^{K}\right\|$
$\displaystyle\leq\frac{L}{2}\left\|{\mathbf{W}}\right\|\left\|\mu_{K}^{(0)}-\mu_{K}^{(1)}\right\|+\frac{L}{2}\|{\mathbf{W}}\|\left\|\bm{\Delta}^{K}\right\|+\frac{L}{2}\|\mathbf{W}\|\left\|\bm{\Delta}^{K}\right\|$
$\displaystyle=\frac{L}{2}\left\|{\mathbf{W}}\right\|\left(\Delta_{\text{DP}}^{\text{Rep}}+2\left\|\bm{\Delta}^{K}\right\|\right).$

Then, we can build the relation between $\|\bm{\Delta}^{K}\|$ and
$\|\bm{\Delta}^{K-1}\|$. We first introduce some inequalities. For each node
$v_{i}$, we have
$\mu^{K}_{m}-\max_{i}|\sigma^{K}_{i,m}|\leq{F}^{(K)}_{i,m}\leq\mu^{K}_{m}+\max_{i}|\sigma^{K}_{i,m}|$,
where $\mu_{m}^{K}=\frac{1}{N}\sum_{i=1}^{N}{F}^{(K)}_{i,m}$ and
$\max_{i}|\sigma^{K}_{i,m}|=|\Delta^{K}_{m}|$. To simplify notation, we write
it as ${F}^{(K)}_{i,m}\in\left[\mu^{K}_{m}\pm|\Delta_{m}|\right]$ For the node
representation $F^{K}_{i,m}$ based on Eq.(4) and the previous inequalities, we
have the following inequality:

$\displaystyle{F}^{(K)}_{i,m}=$ $\displaystyle
X_{q,m}+\frac{1}{|\mathcal{N}_{i}|}\sum_{v_{q}\in{\mathcal{N}}_{i}}{F}^{(K-1)}_{q,m}-\frac{1}{N^{2}_{0}}\sum_{q\in
S_{0}}k({\mathbf{F}}^{(K-1)}_{q},{\mathbf{F}}^{(K-1)}_{i}){F}^{(K-1)}_{q,m}+\frac{1}{N_{0}N_{1}}\sum_{q\in
S_{1}}k({\mathbf{F}}^{(K-1)}_{q},{\mathbf{F}}^{(K-1)}_{i}){F}^{(K-1)}_{q,m}$
(33) $\displaystyle+\Big{(}\frac{1}{N^{2}_{0}}\sum_{q\in
S_{0}}k({\mathbf{F}}^{(K-1)}_{q},{\mathbf{F}}^{(K-1)}_{i})-\frac{1}{N_{0}N_{1}}\sum_{q\in
S_{1}}k({\mathbf{F}}^{(K-1)}_{q},{\mathbf{F}}^{(K-1)}_{i})\Big{)}{F}^{(K-1)}_{q,m}$
$\displaystyle\in\left[\mu^{K}_{m}+\mu^{0}_{m}\pm(1+\frac{2}{N_{0}}+\frac{2}{N_{1}})|\Delta^{K-1}_{m}|+|\Delta^{0}_{m}|\right],$

where $\mathcal{N}_{i}$ represents the neighbors set of the node $v_{i}$.
Then, we can get the inequality for $\sigma^{K}_{i,m}$:

$\displaystyle\sigma^{K}_{i,m}={F}^{(K)}_{i,m}-\frac{1}{N}\sum_{j=1}^{N}{F}^{(K)}_{j,m}\in\left[\pm(2+\frac{4}{N_{0}}+\frac{4}{N_{0}})|\Delta^{K-1}_{m}|+2|\Delta^{0}_{m}|\right],$
(34)
$\displaystyle\Delta^{K}_{m}=\max_{i}|\sigma^{K}_{i,m}|\leq(2+\frac{4}{N_{0}}+\frac{4}{N_{1}})|\Delta^{K-1}_{m}|+2|\Delta^{0}_{m}|.$

We finish building the relation between $\|\bm{\Delta}^{K}\|$ and
$\|\bm{\Delta}^{K-1}\|$:

$\|\bm{\Delta}^{K}\|\leq(2+\frac{4}{N_{0}}+\frac{4}{N_{1}})\|\bm{\Delta}^{K-1}\|+2\|\bm{\Delta}^{0}\|.$
(35)

In this paper, we consider the two layer GNN, where $K=2$. We can get:

$\displaystyle\|\bm{\Delta}^{2}\|\leq\Big{(}(2+\frac{4}{N_{0}}+\frac{4}{N_{1}})^{2}+6+\frac{8}{N_{0}}+\frac{8}{N_{1}}\Big{)}\|\bm{\Delta}^{0}\|.$
(36)

Finally, from Eq.(32) and the previous equation, we have:

$\Delta_{\text{DP}}\leq\frac{L}{2}\left\|{\mathbf{W}}\right\|\left(\Delta_{\text{DP}}^{\text{Rep}}+C_{1}\left\|\bm{\Delta}\right\|\right),$
(37)

where
$C_{1}=(2+\frac{4}{N_{0}}+\frac{4}{N_{1}})^{2}+6+\frac{8}{N_{0}}+\frac{8}{N_{1}}$
and we use $\left\|\bm{\Delta}\right\|$ to represent
$\left\|\bm{\Delta}^{K}\right\|$ for $K=0$. This completes our proof. ∎

###  F.2 Proof of Theorem 4.2

Theorem 4.2. For an arbitrary graph, after $K$-layer fairness-aware message
passing with Eq.(4) on the original feature ${\mathbf{X}}$ to obtain
${\mathbf{F}}^{(K)}$, when $K=2$, the consequent representation discrepancy on
${\mathbf{F}}^{(K)}$ between two sensitive groups is up bounded as:

$\Delta_{\text{DP}}^{\text{Rep}}({\mathbf{F}}^{(K)})\leq\big{(}3-(\frac{1}{N_{0}N^{2}_{1}}+\frac{1}{N^{2}_{0}N_{1}})\sum_{i\in
S_{0}}\sum_{j\in
S_{1}}k({\mathbf{F}}^{(K-1)}_{i},{\mathbf{F}}^{(K-1)}_{j})\big{)}C_{3}+C_{2},$
(38)

where
$C_{2}=\|\mu^{(0)}-\mu^{(1)}\|+8(1+\frac{1}{N_{0}}+\frac{1}{N_{1}})^{2}\|\bm{\Delta}\|+2\|\bm{\Delta}\|$.
Also, the constant value $C_{3}$ is
$C_{3}=(3-\frac{1}{N_{0}}-\frac{1}{N_{1}})\|(\mu^{(0)}-\mu^{(1)})\|+(4+\frac{2}{N_{0}}+\frac{2}{N_{1}})\|\bm{\Delta}\|$.

###### Proof.

$\Delta_{\text{DP}}^{\text{Rep}}({\mathbf{F}}^{(K)})=\left\|\frac{1}{N_{0}}\sum_{i\in{\mathcal{S}}_{0}}{\mathbf{F}}^{(K)}_{i}-\frac{1}{N_{1}}\sum_{j\in\mathcal{S}_{1}}{\mathbf{F}}^{(K)}_{j}\right\|$.
The feature representation of conducting one fair-aggregation for $v\in S_{0}$
is based on the Eq.(4):

$\displaystyle{\mathbf{F}}^{(K)}_{i}={\mathbf{X}}_{i}+\frac{1}{|{\mathcal{N}}_{i}|}\sum_{v_{u}\in{\mathcal{N}}_{u}}{\mathbf{F}}_{u}^{(K-1)}-\frac{1}{N^{2}_{0}}\sum_{u\in
S_{0}}k({\mathbf{F}}^{(K-1)}_{u},{\mathbf{F}}^{(K-1)}_{i}){\mathbf{F}}_{u}^{(K-1)}+\frac{1}{N_{0}N_{1}}\sum_{u\in
S_{1}}k({\mathbf{F}}^{(K-1)}_{u},{\mathbf{F}}^{(K-1)}_{i}){\mathbf{F}}_{u}^{(K-1)}$
(39) $\displaystyle+(\frac{1}{N^{2}_{0}}\sum_{u\in
S_{0}}k({\mathbf{F}}^{(K-1)}_{u},{\mathbf{F}}^{(K-1)}_{i})-\frac{1}{N_{0}N_{1}}\sum_{u\in
S_{1}}k({\mathbf{F}}^{(K-1)}_{u},{\mathbf{F}}^{(K-1)}_{i}){\mathbf{F}}_{i}^{(K-1)}$
$\displaystyle={\mathbf{X}}_{i}+\frac{1}{|{\mathcal{N}}_{i}|}\Big{(}\sum_{v_{u}\in{\mathcal{N}}_{i}\cap
S_{0}}{\mathbf{F}}_{u}^{(K-1)}+\sum_{u\in{\mathcal{N}}_{i}\cap
S_{1}}{\mathbf{F}}_{u}^{(K-1)}\Big{)}+\frac{1}{N_{0}N_{1}}\sum_{u\in
S_{1}}k({\mathbf{F}}^{(K-1)}_{u},{\mathbf{F}}^{(K-1)}_{i}){\mathbf{F}}_{u}^{(K-1)}$
$\displaystyle-\frac{1}{N^{2}_{0}}\sum_{u\in
S_{0}}k({\mathbf{F}}^{(K-1)}_{u},{\mathbf{F}}^{(K-1)}_{i}){\mathbf{F}}_{u}^{(K-1)}+(\frac{1}{N^{2}_{0}}\sum_{u\in
S_{0}}k({\mathbf{F}}^{(K-1)}_{u},{\mathbf{F}}^{(K-1)}_{i})-\frac{1}{N_{0}N_{1}}\sum_{u\in
S_{1}}k({\mathbf{F}}^{(K-1)}_{u},{\mathbf{F}}^{(K-1)}_{i})){\mathbf{F}}_{i}^{(K-1)}$

For the node $u\in\mathcal{S}_{0}$, a vector ${\mathbf{F}}^{(K)}_{u}$
satisfies
$\mathbf{\mu}^{(0)}_{K}-\Delta^{K}\preccurlyeq{\mathbf{F}}_{u}^{(K)}\preccurlyeq\mu^{(0)}_{K}+\Delta^{K}$,
where ${\mathbf{F}}_{u}^{(K)}\preccurlyeq\mu^{(0)}_{K}+\Delta^{K}$ means that
$\forall m\in\\{1,2,...,D\\},{F}_{u,m}\leq\mu^{(0)}_{K,m}+\Delta^{K}_{m}$. We
abbreviate this as
${\mathbf{F}}^{(K)}_{u}\in\left[\mu^{(0)}_{K}\pm\Delta^{K}\right]$. Similarly,
for the node $u\in{\mathcal{S}}_{1}$,
${\mathbf{F}}^{(K)}_{u}\in\left[\mu^{(1)}_{K}\pm\Delta^{K}\right]$. And we
denote $\mu^{(0)}_{K}$ and $\mu^{(1)}_{K}$ as $\mu^{(0)}$ and $\mu^{(1)}$ with
$K=2$. Considering the unilateral case $v_{i}\in S_{0}$ and the above
inequalities, we have:

$\displaystyle{\mathbf{F}}^{(K)}_{i}\in\Big{[}\mu^{(0)}+(\frac{|{\mathcal{N}}_{i}\cap{\mathcal{S}}_{0}|}{|{\mathcal{N}}_{i}|}\mu^{(0)}_{K-1}+\frac{|{\mathcal{N}}_{i}\cap{\mathcal{S}}_{1}|}{|{\mathcal{N}}_{i}|}\mu^{(1)}_{K-1})-\frac{1}{N_{0}^{2}}\sum_{u\in
S_{0}}k({\mathbf{F}}^{(K-1)}_{u},\mathbf{F}^{K-1}_{i}){\mathbf{F}}^{(K-1)}_{u}$
(40) $\displaystyle\left.+\frac{1}{N_{0}N_{1}}\sum_{u\in
S_{1}}k({\mathbf{F}}^{(K-1)}_{u},{\mathbf{F}}^{(K-1)}_{i})\mu_{K-1}^{(1)}+\frac{1}{N^{2}_{0}}\sum_{u\in
S_{0}}k({\mathbf{F}}^{(K-1)}_{u},{\mathbf{F}}^{(K-1)}_{i}){\mathbf{F}}^{(K-1)}_{i}\right.$
$\displaystyle-\frac{1}{N_{0}N_{1}}\sum_{u\in
S_{1}}k({\mathbf{F}}^{(K-1)}_{u},{\mathbf{F}}^{(K-1)}_{i})\mu_{K-1}^{(0)}\pm((1+\frac{2}{N_{0}})\bm{\Delta}^{K-1}+\bm{\Delta})\Big{]}$
$\displaystyle\in\left[\mu^{(0)}+\left(\mu^{(0)}_{K-1}+\frac{|{\mathcal{N}}_{i}\cap{\mathcal{S}}_{1}|}{|{\mathcal{N}}_{i}|}\left(\mu^{(1)}_{K-1}-\mu^{(0)}_{K-1}\right)\right)+\frac{1}{N_{0}N_{1}}\sum_{u\in
S_{1}}k({\mathbf{F}}^{(K-1)}_{u},{\mathbf{F}}^{(K-1)}_{i})(\mu^{(1)}_{K-1}-\mu^{(0)}_{K-1})\right.$
$\displaystyle\left.-\frac{1}{N_{0}^{2}}\sum_{u\in
S_{0}}k({\mathbf{F}}^{(K-1)}_{u},{\mathbf{F}}^{(K-1)}_{i}){\mathbf{F}}^{(K-1)}_{u}+\frac{1}{N^{2}_{0}}\sum_{u\in
S_{0}}k({\mathbf{F}}^{(K-1)}_{u},{\mathbf{F}}^{(K-1)}_{i}){\mathbf{F}}^{(K-1)}_{i}\pm((1+\frac{2}{N_{0}})\bm{\Delta}^{K-1}+\bm{\Delta})\right]$

Let $\beta_{i}=|{\mathcal{S}}_{\text{opp}(v_{i})}|/|{\mathcal{N}}_{i}|$ where
${\mathcal{S}}_{\text{opp}(v_{i})}$ is the opposite sensitive group
${\mathcal{N}}_{i}\cap\mathcal{S}_{1}$ that $v_{i}$ belongs. For nodes in
$S_{0}$, from Eq.(40), we have

$\displaystyle\frac{1}{N_{0}}\sum_{i\in{\mathcal{S}}_{0}}{\mathbf{F}}^{(K)}_{i}\in\Big{[}\mu^{(0)}+\Big{(}\mu^{(0)}_{K-1}+\frac{1}{N_{0}}\sum_{i\in{\mathcal{S}}_{0}}\beta_{i}(\mu^{(1)}_{K-1}-\mu^{(0)}_{K-1})\Big{)}$
(41)
$\displaystyle+\frac{1}{N^{2}_{0}N_{1}}\sum_{i\in{\mathcal{S}}_{0}}\sum_{u\in{\mathcal{S}}_{1}}k({\mathbf{F}}^{(K-1)}_{u},{\mathbf{F}}^{(K-1)}_{i})(\mu^{(1)}_{K-1}-\mu^{(0)}_{K-1})\pm\big{(}(1+\frac{2}{N_{0}})\bm{\Delta}^{K-1}+\bm{\Delta}\big{)}\Big{]}$

For nodes in ${\mathcal{S}}_{1}$:

$\displaystyle\frac{1}{N_{1}}\sum_{j\in{\mathcal{S}}_{1}}{\mathbf{F}}^{(K)}_{j}\in\left[\mu^{(1)}+\left(\mu^{(1)}_{K-1}+\frac{1}{N_{1}}\sum_{j\in{\mathcal{S}}_{1}}\beta_{j}\left(\mu^{(0)}_{K-1}-\mu^{(1)}_{K-1}\right)\right)\right.$
(42)
$\displaystyle\left.+\frac{1}{N_{0}N^{2}_{1}}\sum_{j\in{\mathcal{S}}_{1}}\sum_{u\in{\mathcal{S}}_{0}}k({\mathbf{F}}^{(K-1)}_{u},{\mathbf{F}}^{(K-1)}_{j})(\mu^{(0)}_{K-1}-\mu^{(1)}_{K-1})\pm((1+\frac{2}{N_{1}})\bm{\Delta}^{K-1}+\bm{\Delta})\right]$

The fairness objective can be written as:

$\displaystyle\frac{1}{N_{0}}\sum_{i\in{\mathcal{S}}_{0}}{\mathbf{F}}^{(K)}_{i}-\frac{1}{N_{1}}\sum_{j\in{\mathcal{S}}_{1}}{\mathbf{F}}^{(K)}_{j}\in$
(43)
$\displaystyle\left[(1-(\frac{1}{N_{0}}\sum_{i\in{\mathcal{S}}_{0}}\beta_{i}+\frac{1}{N_{1}}\sum_{j\in{\mathcal{S}}_{1}}\beta_{j})-(\frac{1}{N_{0}N^{2}_{1}}+\frac{1}{N^{2}_{0}N_{1}})\sum_{i\in
S_{0}}\sum_{j\in
S_{1}}k({\mathbf{F}}^{(K-1)}_{i},{\mathbf{F}}^{(K-1)}_{j}))(\mu^{(0)}_{K-1}-\mu^{(1)}_{K-1})\right.$
$\displaystyle+(\mu^{(0)}-\mu^{(1)})\pm\left.((2+\frac{2}{N_{0}}+\frac{2}{N_{1}})\bm{\Delta}^{K-1}+2\bm{\Delta})\right]$

To obtain the upper bound for
$\Delta_{\text{DP}}^{\text{Rep}}({\mathbf{F}}^{(K)})=\left\|\frac{1}{N_{0}}\sum_{i\in{\mathcal{S}}_{0}}{\mathbf{F}}^{(K)}_{i}-\frac{1}{N_{1}}\sum_{j\in{\mathcal{S}}_{1}}{\mathbf{F}}^{(K)}_{j}\right\|$,
we have the following inequality:

$\displaystyle\Delta_{\text{DP}}^{\text{Rep}}({\mathbf{F}}^{(K)})=\Big{\|}\frac{1}{N_{0}}\sum_{i\in{\mathcal{S}}_{0}}{\mathbf{F}}^{(K)}_{i}-\frac{1}{N_{1}}\sum_{j\in{\mathcal{S}}_{1}}{\mathbf{F}}^{(K)}_{j}\Big{\|}$
(44)
$\displaystyle\leq|1-(\frac{1}{N_{0}}\sum_{i\in{\mathcal{S}}_{0}}\beta_{i}+\frac{1}{N_{1}}\sum_{j\in{\mathcal{S}}_{1}}\beta_{j})-(\frac{1}{N_{0}N^{2}_{1}}+\frac{1}{N^{2}_{0}N_{1}})\sum_{i\in
S_{0}}\sum_{j\in
S_{1}}k({\mathbf{F}}^{(K-1)}_{i},{\mathbf{F}}^{(K-1)}_{j})|\left\|(\mu^{(0)}_{K-1}-\mu^{(1)}_{K-1})\right\|$
$\displaystyle+\left\|\mu^{(0)}-\mu^{(1)}\right\|+((2+\frac{2}{N_{0}}+\frac{2}{N_{1}})\left\|\bm{\Delta}^{K-1}\right\|+2\left\|\bm{\Delta}\right\|)$
$\displaystyle\leq(\frac{1}{N_{0}}\sum_{i\in{\mathcal{S}}_{0}}\beta_{i}+\frac{1}{N_{1}}\sum_{j\in{\mathcal{S}}_{1}}\beta_{j})+1-(\frac{1}{N_{0}N^{2}_{1}}+\frac{1}{N^{2}_{0}N_{1}})\sum_{i\in
S_{0}}\sum_{j\in
S_{1}}k({\mathbf{F}}^{(K-1)}_{i},{\mathbf{F}}^{(K-1)}_{j})\left\|(\mu^{(0)}_{K-1}-\mu^{(1)}_{K-1})\right\|$
$\displaystyle+\left\|\mu^{(0)}-\mu^{(1)}\right\|+((2+\frac{2}{N_{0}}+\frac{2}{N_{1}})\left\|\bm{\Delta}^{K-1}\right\|+2\left\|\bm{\Delta}\right\|)$
$\displaystyle\leq(3-(\frac{1}{N_{0}N^{2}_{1}}+\frac{1}{N^{2}_{0}N_{1}})\sum_{i\in
S_{0}}\sum_{j\in
S_{1}}k({\mathbf{F}}^{(K-1)}_{i},{\mathbf{F}}^{(K-1)}_{j}))\left\|(\mu^{(0)}_{K-1}-\mu^{(1)}_{K-1})\right\|$
$\displaystyle+\left\|\mu^{(0)}-\mu^{(1)}\right\|+((2+\frac{2}{N_{0}}+\frac{2}{N_{1}})\left\|\bm{\Delta}^{K-1}\right\|+2\left\|\bm{\Delta}\right\|)$

The upper bound of the fairness metric based on the Eq.(44) can be written as:

$\displaystyle\Delta_{\text{DP}}^{\text{Rep}}({\mathbf{F}}^{(K)})\leq(3-(\frac{1}{N_{0}N^{2}_{1}}+\frac{1}{N^{2}_{0}N_{1}})\sum_{i\in
S_{0}}\sum_{j\in
S_{1}}k({\mathbf{F}}^{(K-1)}_{i},{\mathbf{F}}^{(K-1)}_{j}))\left\|(\mu^{(0)}_{K-1}-\mu^{(1)}_{K-1})\right\|$
(45)
$\displaystyle+\left\|\mu^{(0)}-\mu^{(1)}\right\|+((2+\frac{2}{N_{0}}+\frac{2}{N_{1}})\left\|\bm{\Delta}^{K-1}\right\|+2\left\|\bm{\Delta}\right\|).$

In this paper, we consider the case with two-layer GNNs with $K=2$, where
$\mu^{(0)}_{K-2}-\mu^{(1)}_{K-2}=\mu^{(0)}-\mu^{(1)}$,
$\bm{\Delta}_{K-2}=\bm{\Delta}$, ${\mathbf{F}}^{(K-2)}={\mathbf{X}}$. We
denote $3-(\frac{1}{N_{0}N^{2}_{1}}+\frac{1}{N^{2}_{0}N_{1}})\sum_{i\in
S_{0}}\sum_{j\in S_{1}}k({\mathbf{F}}^{(K-1)}_{i},{\mathbf{F}}^{(K-1)}_{j})$
as $U$, where $U\leq 3-1/N_{0}-1/N_{1}$. Based on the Eq.(35) and the previous
equation, we can get:

$\displaystyle U\left\|\mu^{(0)}_{K-1}-\mu^{(1)}_{K-1}\right\|\leq
U\left(\left(3-(\frac{1}{N_{0}N^{2}_{1}}+\frac{1}{N^{2}_{0}N_{1}})\sum_{i\in
S_{0}}\sum_{j\in
S_{1}}k({\mathbf{X}}_{i},{\mathbf{X}}_{j})\right)\left\|(\mu^{(0)}-\mu^{(1)})\right\|\right.$
(46)
$\displaystyle\left.+\left\|\mu^{(0)}-\mu^{(1)}\right\|+(2+\frac{2}{N_{0}}+\frac{2}{N_{1}})\left\|\bm{\Delta}\right\|+2\left\|\bm{\Delta}\right\|\right)$
$\displaystyle\leq
U\left((3-\frac{1}{N_{0}}-\frac{1}{N_{1}})\left\|(\mu^{(0)}-\mu^{(1)})\right\|+(4+\frac{2}{N_{0}}+\frac{2}{N_{1}})\left\|\bm{\Delta}\right\|\right),$
$\displaystyle(2+\frac{2}{N_{0}}+\frac{2}{N_{1}})\|\bm{\Delta}^{K-1}\|\leq(2+\frac{2}{N_{0}}+\frac{2}{N_{1}})\left((2+\frac{4}{N_{0}}+\frac{4}{N_{1}})\|\bm{\Delta}\|+2\|\bm{\Delta}\|\right)$
$\displaystyle=8(1+\frac{1}{N_{0}}+\frac{1}{N_{1}})^{2}\|\bm{\Delta}\|$

We can finally get the upper bound of
$\Delta_{\text{DP}}^{\text{Rep}}({\mathbf{F}}^{(K)})$:

$\displaystyle\Delta_{\text{DP}}^{\text{Rep}}({\mathbf{F}}^{(K)})\leq(3-(\frac{1}{N_{0}N^{2}_{1}}+\frac{1}{N^{2}_{0}N_{1}})\sum_{i\in
S_{0}}\sum_{j\in
S_{1}}k({\mathbf{F}}^{(K-1)}_{i},{\mathbf{F}}^{(K-1)}_{j}))C_{3}+C_{2},$ (47)

where
$C_{2}=\left\|\mu^{(0)}-\mu^{(1)}\right\|+8(1+\frac{1}{N_{0}}+\frac{1}{N_{1}})^{2}\|\bm{\Delta}\|+2\|\bm{\Delta}\|$.
Also, the constant value $C_{3}$ is
$C_{3}=(3-\frac{1}{N_{0}}-\frac{1}{N_{1}})\left\|(\mu^{(0)}-\mu^{(1)})\right\|+(4+\frac{2}{N_{0}}+\frac{2}{N_{1}})\left\|\bm{\Delta}\right\|$.
∎

##  Appendix G Experimental Details

###  G.1 Datasets Details and Statistics

Table 4: Statistics of used homophily and heterophily graph datasets in this paper. Dataset | #Nodes | # Edges | #Features | $\mathcal{H}(\mathcal{G})$ | $\mathcal{H}_{f}(\mathcal{G})$ | Sens | Label
---|---|---|---|---|---|---|---
German | 1,000 | 22,242 | 27 | 0.59 | 0.81 | Gender | Good/bad Credi
Credit | 3,327 | 4,552 | 13 | 0.74 | 0.97 | Age | Default/no default Payment
Bail | 19,717 | 44,324 | 18 | 0.81 | 0.52 | Race | Bail/no bail

####  G.1.1 Homophily Ratio based on labels

We utilize the following edge homophily ratio [50] to measure the one-hop
neighbor homophily of the graph. Specifically, the edge homophily ratio
$\mathcal{H}(\mathcal{G})$ is the proportion of edges that connect two nodes
of the same class:

$\mathcal{H}(\mathcal{G})=\frac{\left|\left\\{(u,v):(u,v)\in\mathcal{E}\wedge
y_{u}=y_{v}\right\\}\right|}{|\mathcal{E}|}$ (48)

####  G.1.2 Sensitive Attribute Homophily

We utilize the following sensitive attribute homophily ratio [41] to measure
the one-hop neighbor homophily of the graph based on sensitive attributes.
Given a graph ${\mathcal{G}}=({\mathcal{V}},{\mathcal{E}},{\mathbf{X}})$ and
sensitive attributes $\mathbf{s}$, the sensitive homophily ratio
${\mathcal{H}}_{f}$ for $\mathcal{G}$ is defined as:

${\mathcal{H}}_{f}=\frac{\left|\left\\{(u,v):(u,v)\in\mathcal{E}\wedge
s_{u}=s_{v}\right\\}\right|}{|\mathcal{E}|}.$ (49)

It measures the ratio of edges connecting nodes from the same sensitive
attributes. Intuitively, GNNs may give biased predictions on graphs with more
intra sensitive group edges (higher ${\mathcal{H}}_{f}$) [9, 10, 41] because
more intra group edges may lead to similar representations of nodes from the
same sensitive groups, resulting in biased predictions, i.e., predictions
highly correlated with sensitive attributes.

###  G.2 Datasets

The statistics of datasets, including their homophily ratio based on labels
and sensitive homophily ratio, are given in Table 4. We can observe all graphs
exhibit higher sensitive homophily ratio so original message passing on the
graph structure can exacerbate the fairness issues on graphs.

German Credit (German) [39]: In this graph, nodes represent clients in a
German bank and attributes of nodes are gender, loan amount, and other account
related details. Edges between two nodes (clients) mean their credit accounts
are similar. The label is weather the credit risk of the clients as high or
low. The attribute “gender” is treated as a sensitive feature.

Recidivism (Bail) [39]: In this graph, defendants released on bail during
1990-2009 are represented as nodes. If two defendants share similar past
criminal records and demographics, an edge is added between these two nodes.
The task is to predict whether a defendant would be more likely to commit a
violent or nonviolent crime once released on bail. The attribute “race” is the
sensitive feature.

Credit Defaulter (Credit) [39]: Nodes in this dataset represent credit card
users and edges indicate if two users share a similar pattern in
purchases/payments. The class labels of nodes represent whether a user will
default on credit card payment with “age” being the sensitive feature.

The statistics of datasets are given in Table 4. We follow the split
introduced in the previous papers for graph group fairness [39, 10].

###  G.3 Baselines

GCN [4]: GCN is one of the most popular spectral GNN models based on graph
Laplacian, which has shown great performance for node classification.

GIN [47]: GIN proposed a powerful GNN by approximating injective set functions
with multi-layer perceptrons (MLPs), which can be as powerful as the 1-WL
test.

GAT [32]: Instead of treating each neighbor nodes equally, GAT utilizes an
attention mechanism to assign different weights to nodes in the neighborhood
during the aggregation step.

NIFTY [39]: NIFTY has been introduced to enhance counterfactual fairness and
stability of node representations. This involves a novel triplet-based
objective function and layer-wise weight normalization using the Lipschitz
constant.

EDITS [10]: EDITS employs the Wasserstein distance approximator to alternately
debias node features and network topology

FairGNN [9]: FairGNN uses a sensitive feature estimator to increase the
quantity of sensitive attributes, which is highly effective in promoting
fairness within their algorithm.

FairVGNN [11]: FairVGNN automatically masks feature channels that are
correlated with sensitive attributes and adaptively adjusts the encoder
weights to absorb less sensitive information during feature propagation,
leading to a more fair and unbiased machine learning algorithm.

FMP [40]: FMP uses a unified optimization framework to develop an effective
message passing to learn fair node representations while preserving prediction
performance.

MMD [42]: MMD is about measuring the discrepancy between two distribution and
it can be used as fairness regularization to train fair predictors [44]. For
this baseline, we immediately add this regularization at the prediction level
of GNN models.

###  G.4 Setup and Hyper-parameter settings

We use official implementation publicly released by the authors on Github of
the baselines or implementation from Pytorch Geometric. For fair comparison,
we used grid search to find the best hyperparameters of the baselines. Note
that we use two-layer GNN models for all methods. We run experiments on a
machine with a NVIDIA Tesla V100 GPU with 32GB of GPU memory. In all
experiments, we use the Adam optimizer [51]. A small grid search is used to
select the best hyperparameter for all methods. In particular, for our GMMD.
we search $\lambda_{s}$ from {0, 0.1, 0.5, 1, 2}, $\lambda_{f}$ from {0, 0.1,
0.5, 1, 5, 10}
$\times|{\mathcal{S}}^{\prime}_{0}||{\mathcal{S}}^{\prime}_{1}|$, where The
values of $\lambda_{f}$ shown in Figure 1 also represent the product of
$|{\mathcal{S}}^{\prime}_{0}||{\mathcal{S}}^{\prime}_{1}|$. The hidden
dimension of $M$ layers MLP is fixed as 16, $\alpha$ from {0.1, 0.3, 0.7, 1}
and $M$ from {1, 2, 4, 6}. We tune the learning rate over {0.003, 0.001,
0.0001} and weight decay over {0, 0.4, 0.0001, 0.00001}. We select the best
configuration of hyper-parameters based on accuracy, f1 score, AUC,
$\Delta_{\text{DP}}$ and $\Delta_{\text{EO}}$ only based on the validation
set. The sampled number for German, Bail and Credit are 100, 200 and 6000.

##  Appendix H Additional Experiments

###  H.1 Additional Results of Different Backbones

Table 5: Model performance with GIN and GAT as backbones. The best and runner-
up results of different backbones are colored in red and blue.

Dataset | Metric | GIN | GAT
---|---|---|---
Vanilla | FairVGNN | GMMD | GMMD-S | Vanilla | FairVGNN | GMMD | GMMD-S
German |  AUC ($\uparrow$) | 72.71$\pm$1.44 | 71.65$\pm$1.90 |  71.42$\pm$0.80 |  71.30$\pm$1.24 | 70.95$\pm$2.34 |  68.59$\pm$3.80 | 70.32$\pm$0.20 |  70.10$\pm$2.08
F1 ($\uparrow$) | 82.46$\pm$0.89 |  82.14$\pm$1.40 |  82.11$\pm$0.35 | 82.48$\pm$0.18 |  81.18$\pm$0.69 |  82.07$\pm$0.55 | 82.57$\pm$0.13 | 82.43$\pm$0.32
ACC ($\uparrow$) | 73.44$\pm$1.09 |  70.16$\pm$0.32 |  70.27$\pm$0.38 | 70.53$\pm$0.75 |  68.32$\pm$2.10 |  69.76$\pm$0.48 | 70.67$\pm$0.19 | 70.27$\pm$0.68
$\Delta_{\text{DP}}$ ($\downarrow$) |  35.17$\pm$7.27 |  0.43$\pm$0.53 | 0.18$\pm$0.26 | 0.09$\pm$0.13 |  4.68$\pm$4.27 |  1.83$\pm$3.66 | 0.39$\pm$0.26 | 0.60$\pm$0.51
$\Delta_{\text{EO}}$ ($\downarrow$) |  25.17$\pm$5.89 | 0.34$\pm$0.41 |  0.74$\pm$1.05 | 0.26$\pm$0.37 |  4.35$\pm$3.28 |  1.64$\pm$3.28 | 1.02$\pm$0.36 | 0.51$\pm$0.36
Credit |  AUC ($\uparrow$) | 74.36$\pm$0.21 | 71.36$\pm$0.72 |  70.63$\pm$0.67 |  70.35$\pm$0.53 | 72.94$\pm$1.84 | 71.68$\pm$3.57 |  70.52$\pm$0.15 |  69.26$\pm$0.05
F1 ($\uparrow$) |  82.28$\pm$0.64 | 87.44$\pm$0.23 | 87.60$\pm$0.04 |  86.23$\pm$0.75 | 85.43$\pm$0.63 |  85.04$\pm$2.09 | 85.83$\pm$2.52 | 85.43$\pm$0.54
ACC ($\uparrow$) |  74.02$\pm$0.73 | 78.18$\pm$0.20 | 78.23$\pm$0.45 |  77.62$\pm$0.82 | 77.31$\pm$0.54 |  76.41$\pm$1.45 | 76.82$\pm$2.04 |  76.75$\pm$0.43
$\Delta_{\text{DP}}$ ($\downarrow$) |  14.48$\pm$1.24 |  2.85$\pm$2.10 | 0.12$\pm$0.12 | 2.69$\pm$1.13 |  19.42$\pm$4.52 |  7.13$\pm$6.58 | 1.38$\pm$1.32 | 1.67$\pm$0.42
$\Delta_{\text{EO}}$ ($\downarrow$) |  12.35$\pm$2.68 | 1.72$\pm$1.80 | 0.16$\pm$0.16 |  1.99$\pm$1.00 |  15.79$\pm$5.00 |  5.90$\pm$5.82 | 1.32$\pm$1.27 | 3.08$\pm$1.10
Bail |  AUC ($\uparrow$) |  86.14$\pm$0.25 |  83.22$\pm$1.60 | 86.53$\pm$1.54 | 86.50$\pm$1.61 |  88.10$\pm$3.52 |  87.46$\pm$0.69 | 90.58$\pm$0.74 | 89.77$\pm$0.74
F1 ($\uparrow$) |  76.49$\pm$0.57 |  76.36$\pm$2.20 | 76.62$\pm$1.88 | 76.64$\pm$1.71 |  76.80$\pm$5.54 |  76.12$\pm$0.92 | 78.45$\pm$3.21 | 77.34$\pm$0.47
ACC ($\uparrow$) |  81.70$\pm$0.67 |  83.86$\pm$1.57 | 84.08$\pm$1.35 | 84.04$\pm$1.26 | 83.71$\pm$4.55 |  81.56$\pm$0.94 |  83.39$\pm$4.50 | 83.44$\pm$2.13
$\Delta_{\text{DP}}$ ($\downarrow$) |  8.55$\pm$1.61 |  5.67$\pm$0.76 | 3.57$\pm$1.11 | 3.61$\pm$1.42 |  5.66$\pm$1.78 |  5.41$\pm$3.25 | 1.24$\pm$0.28 | 3.27$\pm$1.79
$\Delta_{\text{EO}}$ ($\downarrow$) |  6.99$\pm$1.51 |  5.77$\pm$1.26 | 4.69$\pm$0.69 | 4.71$\pm$0.66 |  4.34$\pm$1.35 | 2.25$\pm$1.61 | 1.18$\pm$0.34 |  2.52$\pm$2.22
| Avg.(Rank) | 3.13 | 2.80 | 1.87 | 2.20 | 3.00 | 3.27 | 1.47 | 2.27

In this section, we show the performance of models with different backbones
and we select the state-of-the-art method FairVGNN as baselines to verify the
effectiveness of our proposed model. These results also echo the conclusion in
the main text: our model can achieve great performance with regard to both
utility metric and fairness metric compared with state-of-the-art method
FairVGNN. It shows the flexibility of our model by adopting different message
passing approaches.

###  H.2 Additional Hyper-parameter Analysis

In this section, we investigate the hyperparameters of $\alpha$ and the number
of MLP layers $M$.

Figure 5: Hyperparameter Analysis of $\alpha$ on German and Credit.

Hyperparameter Analysis of $\alpha$. We provide the hyperparameter analysis of
$\alpha$ for the kernel similarity calculation. $\alpha$ is varied as {0.1,
0.3, 0.7, 1}. Figure 5 shows the results on Bail and Credit. We can first
observe that $\alpha$ is only used for the fairness regularization term so it
doesn’t have too much influence on the accuracy performance. Moreover, larger
values of $\alpha$ (i.e. 0.7, 1) can promote the performance on the fairness
metric. One possible reason is that larger $\alpha$ can also increase the
weight for the fairness regularization in Eq.(7) and Eq.(4) to learn a more
fair model.

Hyperparameter Analysis of $M$. We run a sweep over the number of layers for
MLP $M$ to study how it affects the performance. We vary $M$ as {1, 2, 4, 6}.
Figure 6 shows the corresponding results on Bail and Credit datasets. Larger
number of $M$ represents deeper MLP layers and can first increase the
performance on Accuracy and then decrease it. This is because deeper MLP can
increase the expressive power of the initial representation for our message
passing. However, too many layers will lead to a large number of parameters
and can easily overfit the training data, which will achieve worse
performance. Also, a small number of layers (i.e, $M=2$ or $M=4$) is enough to
achieve good performance on the fairness metric.

Figure 6: Hyperparameter Analysis of $M$ on German and Credit.

###  H.3 Addtional Results on Case Study

Figure 7: Additional Case Study on all three datasets.

In Figure 7, we provide the additional case studies on all three datasets. We
can find that, in most cases, our model can successfully assign higher weights
to inter sensitive group edges which connect two nodes from the same label.
This observation interprets the reason why GMMD can also achieve good utility
performance when aggregating nodes from different sensitive groups to mitigate
fairness issues.

Table 6: Comparison of the running time where "s" indicates seconds. Dataset | NIFTY | FairGNN | EDITS | FairVGNN | FMP | GMMD | GMMD-S
---|---|---|---|---|---|---|---
German | 26.1s | 20.8s | 25.7s | 104.3s | 15.1s | 16.8s | 15.2s
Bail | 27.5s | 20.1s | 33.3s | 99.2s | 19.2s | 21.3s | 19.8s
Credit | 38.1s | 26.3s | 260.5s | 92.4s | 22.7s | 25.5s | 23.6s

###  H.4 Running Time Comparison

We also conduct experiments to compare our training time with baselines. For
comparison, we consider five representative and state-of-the-art baselines
that achieve great performance in mitigating fairness issues for node
classification, including NIFTY, FairGNN and EDITS, FMP, GMMD and GMMD-S. For
all methods, we use GCN as the backbone for running time calculation. We
conduct all running time experiments on the same machine with a NVIDIA Tesla
V100 GPU (32GB of GPU memory). Furthermore, we count the running time of the
models with multiple epochs which achieve the best results. Table 6 shows the
results of running time for all models. Note that we include the total
training time for the two steps of the EDITS model in our table, reflecting
the combined time required for both steps. Specifically, the first step of
EDITS is to learn a new adjacency matrix that removes sensitive information
related to the graph structure. The second step is to train a GNN model with
this new adjacency matrix. The results show the efficiency of GMMD and GMMD-S,
and we can find the superior performance of GMMD and GMMD-S does not benefit
from a larger model complexity.

##  Appendix I Additional Discussion on Potential Limitations and Future
directions

In this paper, we proposed a novel message passing method called GMMD, along
with an efficient and simplified version called GMMD-S to mitigate biased
prediction results of GNNs. The theoretical analysis and our experiment
results validate the effectiveness of our model.

Despite the theoretical analysis and great performance of our model, one
limitation of current work and some interesting directions we want to explore
are: our message passing method is derived from smoothness and fairness
regularization, Maximum Mean Discrepancy (MMD), which can provide a better
intuitive and theoretical understanding. However, there are various fairness
regularization methods and it’s also promising to design a new regularization
term for learning fair representation of graph structure. Moreover, it’s an
interesting direction to conduct a theoretical analysis of the utility
performance of the proposed fairness-aware message passing, which can help us
have a better understanding of controlling the trade-off between utility and
fairness.