Fairness-aware Message Passing for Graph Neural Networks
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.
Huaisheng Zhu, Guoji Fu, Zhimeng Guo, Zhiwei Zhang, Teng Xiao, Suhang Wang
# Fairness-aware Message Passing for

###### 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}\wedge 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}\wedge 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}\left(\mathbf{F}^{T}\tilde{\mathbf{L}} \mathbf{F}\right)+\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.

### 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:

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

where \(h_{s}(\mathbf{F})=\frac{\lambda_{s}}{2}\operatorname{tr}\left(\mathbf{F}^{T} \tilde{\mathbf{L}}\mathbf{F}\right)+\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}^{\tilde{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 in 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:

\[\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), \tag{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:

\[\mathbf{F}^{(k)}=\mathbf{F}^{(k-1)}-\gamma\nabla h\big{(}\mathbf{ F}^{(k-1)}\big{)} =\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{PF}^{(k-1)} \tag{3}\] \[=\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}_{i}^{(k-1)},\mathbf{F}_{j}^{(k-1)})/N_{t}^{2}\), \(t\in\{0,1\}\). If \(v_{i}\) and \(v_{j}\) are in different sensitive groups, \(P_{ij}=k(\mathbf{F}_{i}^{(k-1)},\mathbf{F}_{j}^{(k-1)})/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 GMD_ 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}}. \tag{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 GIMD, we will also provide a theoretical understanding of our model for fairness performance.

### Theoretical Analysis

Next, we provide theoretical understandings of proposed GIMD. We show that GIMD 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 GIMD 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:_

\[\Delta_{\text{DP}}\leq\frac{L}{2}\left\|\mathbf{W}\right\|\left(\Delta_{\text{ DP}}^{\text{Rep}}(\mathbf{F}^{(K)})+C_{1}\left\|\boldsymbol{\Delta}\right\| \right), \tag{5}\]

_where \(C_{1}=(2+\frac{4}{N_{0}}+\frac{4}{N_{1}})^{2}+6+\frac{8}{N_{0}}+\frac{8}{N_{1}}\) and \(\boldsymbol{\Delta}\) is the maximal deviation of \(\mathbf{X}\) from \(\mu\) i.e., \(\boldsymbol{\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:_

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

_where \(C_{2}=\|\mu^{(0)}-\mu^{(1)}\|+8(1+\frac{1}{N_{0}}+\frac{1}{N_{1}})^{2}\| \boldsymbol{\Delta}\|+2\|\boldsymbol{\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}})\|\boldsymbol{\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.

### 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}}, \tag{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.

### 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:

\[\mathbf{F}^{(k)}_{i}=\mathbf{F}^{(k)}_{i}+4\gamma\lambda_{f}\alpha\mathbf{ \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}, \tag{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.

### 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.

### 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.

### Parameter Analysis and Empirical Analysis on Theory

**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

\begin{table}
\begin{tabular}{c|c|c c c c c c c c c c c} \hline
**Dataset** & **Metric** & **GCN** & **NIFTY** & **EDITS** & **FairGNN** & **FairVGNN** & **FMP** & **MMD** & **GMMD** & **GMMD** & **GMMD-S** \\ \hline \multirow{4}{*}{**German**} & AUC (\(\uparrow\)) & 74.1\(\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 \\  & Fl (\(\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\)) & 74.44\(\pm\)0.99 & 69.92\(\pm\)1.14 & 71.60\(\pm\)0.89 & 69.68\(\pm\)0.30 & 72.27\(\pm\)2.73 & 72.53\(\pm\)2.22 & 69.90\(\pm\)0.56 & 72.28\(\pm\)1.64 & 71.87\(\pm\)1.24 \\  & \(\Delta_{\text{DP}}\)(\(\downarrow\)) & 31.77\(\pm\)2.77 & 13.65\(\pm\)3.25 & 40.48\(\pm\)4.39 & 2.15\(\pm\) 1.71 & 7.11\(\pm\)8.68 & 6.48\(\pm\)4.04 & 7.56\(\pm\)7.47 & 2.09\(\pm\)1.60 & 9.09\(\pm\)0.44 \\  & \(\Delta_{\text{DP}}\)(\(\downarrow\)) & 25.17\(\pm\)5.89 & 5.08\(\pm\)4.29 & 3.89\(\pm\)4.23 & 3.40\(\pm\) 2.15 & 0.88\(\pm\)5.58 & 5.81\(\pm\)4.03 & 5.34\(\pm\)5.31 & 0.76\(\pm\)0.52 & 0.99\(\pm\) 0.33 \\ \hline \multirow{4}{*}{**Credit**} & AUC (\(\uparrow\)) & 83.02\(\pm\)0.42 & 74.30\(\pm\)2.01 & 73.01\(\pm\)0.11 & 71.95\(\pm\)4.13 & 71.94\(\pm\)5.14 & 69.42\(\pm\)4.25 & 69.94\(\pm\)0.83 & 71.62\(\pm\)0.07 & 71.78\(\pm\)0.30 \\  & **F1** (\(\uparrow\)) & 81.92\(\pm\)0.21 & 81.20\(\pm\)0.58 & 81.18\(\pm\)0.18 & 81.14\(\pm\)1.97 & 87.08\(\pm\)0.74 & 84.99\(\pm\)0.73 & 84.99\(\pm\)0.73 & 87.57\(\pm\)0.71 & 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 \\  & **Acc** (\(\downarrow\)) & 20.49\(\pm\)0.19 & 1.68\(\pm\)0.07 & 19.02\(\pm\)12.64 & 71.60\(\pm\)1.21 & 50.25\(\pm\)2.52 & 50.54\(\pm\)2.28 & 1.33\(\pm\)1.35 & 1.55\(\pm\)1.99 & 2.27\(\pm\)1.75 \\  & **Acc** (\(\downarrow\)) & 10.63\(\pm\)0.13 & 9.99\(\pm\)0.07 & 8.75\(\pm\)1.21 & 10.41\(\pm\)2.03 & 3.60\(\pm\)3.41 & 4.60\(\pm\)4.49 & 2.24\(\pm\)1.06 & 1.08\(\pm\)1.53 & 1.95\(\pm\)1.43 \\ \hline \multirow{4}{*}{**Bail**} & AUC (\(\uparrow\)) & 87.87\(\pm\)0.35 & 78.20\(\pm\)2.78 & 86.44\(\pm\)2.27 & 87.36\(\pm\)0.90 & 55.88\(\pm\)6.09 & 83.68\(\pm\)0.26 & 88.18\(\pm\)2.04 & 89.12\(\pm\)0.66 \\  & **F1** (\(\uparrow\)) & 79.02\(\pm\)0.74 & 76.49\(\pm\)0.57 & 75.83\(\pm\)3.77 & 75.01\(\pm\)0.69 & 79.11\(\pm\)0.33 & 77.46\(\pm\)0.40 & 77.51\(\pm\)0.67 & 77.92\(\pm\)1.98 & 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 \\  & **Acc** (\(\downarrow\)) & 73.55\(\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 \\  & **Acc** (\(\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
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.

**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}_{i}^{(K-1)},\mathbf{ F}_{j}^{(K-1)})\), 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.

### Ablation Study and Different Backbones

**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 method, "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

\begin{table}
\begin{tabular}{l|c c c c c c} \hline \hline \multirow{2}{*}{**Method**} & \multicolumn{5}{c}{**German**} \\  & AUC (\(\uparrow\)) & F1 (\(\uparrow\)) & ACC (\(\uparrow\)) & \(\Delta_{\text{DP}}\) (\(\downarrow\)) & \(\Delta_{\text{DP}}\) (\(\downarrow\)) \\ \hline \multirow{2}{*}{**w/o**} & \multirow{2}{*}{70.85\(\pm\)0.43} & \multirow{2}{*}{82.46\(\pm\)0.38} & \multirow{2}{*}{70.80\(\pm\)0.30} & \multirow{2}{*}{70.83\(\pm\)0.42} & \multirow{2}{*}{2.01\(\pm\)0.37} \\  & & & & & & \\ \hline w/o fair & 73.41\(\pm\)9.38 & 83.46\(\pm\)0.58 & 73.20\(\pm\)1.13 & 2.92\(\pm\)1.50 & 3.04\(\pm\)1.29 \\ w/o sample & 73.68\(\pm\)0.28 & 81.85\(\pm\)1.57 & 73.37\(\pm\)1.00 & 1.37\(\pm\)0.29 & 2.11\(\pm\)1.51 \\ \hline \multirow{2}{*}{**w/o**} & \multirow{2}{*}{74.01\(\pm\)2.86} & \multirow{2}{*}{83.13\(\pm\)0.44} & \multirow{2}{*}{22.86\(\pm\)1.60} & \multirow{2}{*}{2.09\(\pm\)1.60} & \multirow{2}{*}{2.06\(\pm\)0.65} \\ \cline{1-1} \cline{5-5} \
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.

### 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}_{i}^{(K-1)},\mathbf{F}_{j}^{(K-1)})\). 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.

## 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.

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.

\begin{table}
\begin{tabular}{l|l|l l l l l l l l l} \hline \hline \multirow{2}{*}{**Dataset**} & \multirow{2}{*}{**Metric**} & \multicolumn{4}{c|}{**GIN**} & \multicolumn{4}{c}{**GAT**} \\  & & \multicolumn{1}{c|}{**Vanilla**} & \multicolumn{1}{c|}{**FariVGNN**} & \multicolumn{1}{c|}{**GMMD**} & \multicolumn{1}{c|}{**GMMD-S**} & \multicolumn{1}{c|}{**Vanilla**} & \multicolumn{1}{c|}{**FariVGNN**} & \multicolumn{1}{c}{**GMMD**} & \multicolumn{1}{c}{**GMMD-S**} \\ \hline \multirow{4}{*}{**Ball**} & 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.31\(\pm\)4.55 & 81.65\(\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.75\(\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 \\ \hline \hline \end{tabular}
\end{table}
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.