BeMap: Balanced Message Passing for Fair Graph Neural Network
Fairness in graph neural networks has been actively studied recently.
However, existing works often do not explicitly consider the role of message
passing in introducing or amplifying the bias. In this paper, we first
investigate the problem of bias amplification in message passing. We
empirically and theoretically demonstrate that message passing could amplify
the bias when the 1-hop neighbors from different demographic groups are
unbalanced. Guided by such analyses, we propose BeMap, a fair message passing
method, that leverages a balance-aware sampling strategy to balance the number
of the 1-hop neighbors of each node among different demographic groups.
Extensive experiments on node classification demonstrate the efficacy of BeMap
in mitigating bias while maintaining classification accuracy. The code is
available at https://github.com/xiaolin-cs/BeMap.
Xiao Lin, Jian Kang, Weilin Cong, Hanghang Tong
# BeMap: Balanced Message Passing for Fair Graph Neural Network

###### Abstract.

Graph Neural Network (GNN) has shown strong empirical performance in many downstream tasks by iteratively aggregating information from the local neighborhood of each node, i.e., message passing. However, concrete evidence has revealed that a graph neural network could be biased against certain demographic groups, which calls for the consideration of algorithmic fairness. Despite the increasing efforts in ensuring algorithmic fairness on graph neural networks, they often do not explicitly consider the induced bias caused by message passing in GNN during training. In this paper, we first investigate the problem of bias amplification in message passing. We empirically and theoretically demonstrate that message passing could amplify the bias when the 1-hop neighbors from different demographic groups are unbalanced. Guided by such analyses, we propose BeMap, a fair message passing method, that leverages a balance-aware sampling strategy to balance the number of the 1-hop neighbors of each node among different demographic groups. Extensive experiments on node classification demonstrate the efficacy of our proposed BeMap method in mitigating bias while maintaining classification accuracy.

2017 acmcopyright 17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B177B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B177B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B17B1717B17B17B17B177B17B17B17B17B17B17B17B17B17B17B177B17B17B17B177B17B17B177B17B177B17B17B17B17B17B17B17B17B177B17B177B17B17B177B17B17B17B17B177B17B17B177B17B17B17B177B177B17B17B177B177B17B17B17B177B17B17B1717B17B17B17B17B17B17B17B17B177B17B17B177B177B17B17B177B17B17B177B17B177B17B17B17B177B1717B17B17B177B17B17B17B1717B17B177B17B177B17B177B17B17B17B177B17B17B17B17B177B177B17B17B17B177B17B177B17B17B17B177B17B177B17B17B177B17B17B177B17B177B17B177B17B17B177B17B177B17B177B177B177B17B177B177B17B177B17B177B17B177B177B17B177B177B17B17B17B177B17B177B17B177B17B177B17B17B1717B177B17B177B17B1717B177B177B17B177B177B17B177B17B177B17B177B177B17B177B17B177B17B177B177B17B177B177B177B1717B177B17B177B17B177B17B177B177B177B177B177B177B177B177B177B177B17B17B17B177B17B177B177B17B177B177B17B177B17B177B177B177B177B177B17B17B177B177B177B17B17B177B177B177B177B177B177B177B177B177B177B177B177B177B17B177B177B177B177B177B177B177B17B177B17B177B177B177B17B177B177B177B17B177B177B17B177B17B17B177B177B17B177B177B17B177B177B177B177B177B177B17B17B177B17B177B177B177B177B17B17B177B177B17B177B17B177B17B17B17B177B1717B17B17B17B17B17B17B17B17B177B17B17B177B177B17B177B177B177B17B177B177B17B177B177B177B17B177B17B177B17B177B177B17B177B17B177B17B17B177B17B177B177B17B177B17B177B177B177B177B177B17B177B177B17B177B17B177B177B177B177B17B177B177B177B177B17B177B177B17B177B177B177B177B177B177B177B177B177B177B177B177B177B177B177B1777B177B177B177B177B177B177B177B177B
* **Problems.** We study the problems of bias amplifications in message passing and fair message passing from the perspective of neighborhood balance of each node.
* **Analyses.** Our analyses _both empirically and theoretically_ reveal that the message passing schema could amplify the bias, if the demographic groups with respect to a sensitive attribute in the local neighborhood of each node are unbalanced.
* **Algorithm.** Guided by our analyses, we propose an easy-to-implement sampling-based method named BeMap, which leverages a balance-aware sampling strategy to mitigate bias.
* **Evaluations.** We conduct extensive experiments on real-world datasets, which demonstrate that BeMap could significantly mitigate bias while maintaining a competitive accuracy compared with the baseline methods.

## 2. Preliminaries

In this section, we first briefly introduce the Graph Convolutional Network (GCN) and the commonly used group fairness definitions. Then, we formally define the problem of bias amplification in message passing and fair message passing in GCN.

**Notation Convention.** We use bold uppercase/lowercase letters for matrices/vectors (e.g., \(\mathbf{A}\), \(\mathbf{x}\)), italic letters for scalars (e.g., \(d\)), and calligraphic letters for sets (e.g., \(\mathcal{N}\)). For matrix indexing, the \(i\)-th row of a matrix is denoted as its corresponding bold lowercase letter with subscript \(i\) (e.g., the \(i\)-th row of matrix \(\mathbf{X}\) is \(\mathbf{x}_{i}\)).

**Graph Convolutional Networks.** In this paper, we study the message passing schema in Graph Convolutional Network (GCN) (GCN, 2018), which is one of the most classic graph neural networks. Let \(\mathcal{G}=\{\mathcal{V},\mathbf{A},\mathbf{X}\}\) denote a graph with node set \(\mathcal{V}=\{v_{1},\ldots,v_{n}\}\), adjacency matrix \(\mathbf{A}\), and node feature matrix \(\mathbf{X}\), where \(n\) is the number of nodes in the graph. For any node \(v_{i}\), we denote its degree and the feature as \(d_{i}\) and \(\mathbf{x}_{i}\). In this work, we consider the binary adjacency matrix, meaning that \(\mathbf{A}_{ij}=1\) if there exists an edge connecting the node \(v_{i}\) and the node \(v_{j}\), and \(\mathbf{A}_{ij}=0\) otherwise.2 Given an \(L\)-layer GCN, the weight matrix in the \(l\)-th hidden layer is represented as \(\mathbf{W}^{(l)}\). The input and output node representations of node \(v_{i}\) in the \(l\)-th hidden layer are denoted as \(\mathbf{h}_{i}^{(l)}\) and \(\mathbf{h}_{i}^{(l+1)}\), respectively.3 Then the message passing schema in GCN is \(\widehat{\mathbf{h}}_{i}^{(l)}=\sum_{v_{j}\in\widehat{\mathcal{N}}(v_{i})}a_{ ij}\mathbf{h}_{j}^{(l)}\), where \(\widehat{\mathcal{N}}(v_{i})=\mathcal{N}(v_{i})\cup\{v_{i}\}\) is the self-augmented neighborhood (i.e., the union of node \(v_{i}\) and its \(1\)-hop neighborhood \(\mathcal{N}(v_{i})\)) and \(a_{ij}\) is the aggregation weight with the source node being \(v_{i}\) and the target node being \(v_{j}\) (e.g., \(a_{ij}=\frac{1}{\sqrt{d_{i}+1}\sqrt{d_{j}+1}}\) for renormalized graph Laplacian and \(a_{ij}=\frac{1}{d+1}\) for row-normalized graph Laplacian). Based on the message passing schema, the graph convolution for \(v_{i}\) in GCN can be formulated as \(\mathbf{h}_{i}^{(l+1)}=\sigma(\widehat{\mathbf{h}}_{i}^{(l)}\mathbf{W}^{(l)})\), where \(\sigma(\cdot)\) is the nonlinear activation (e.g., ReLU).

Footnote 2: Although we only consider binary adjacency matrix, our theoretical analysis and proposed method can be naturally generalized to graph with weighted edges by replacing 0/1 edge weight to other values.

Footnote 3: For notation simplicity, we denote \(\mathbf{h}_{i}^{(l)}=\mathbf{x}_{i}\) for all \(v_{i}\in\mathcal{V}\).

**Group Fairness.** Group fairness aims to ensure the parity of model predictions among the demographic groups of data points, where the demographic groups are often determined by a sensitive attribute (e.g., gender and race). Specifically, we adopt two widely used fairness criteria, _i.e._, statistical parity (Kohn and Sham, 2015) and equal opportunity (Kohn and Sham, 2015), which are defined in Definitions 1 and 2, respectively.

**Definition 1**.: _(**Statistical parity (Kohn and Sham, 2015)**) Given any target label \(y\in\{0,1\}\), any sensitive attribute \(s\in\{0,1\}\) and the prediction \(\widetilde{y}\in\{0,1\}\) inferred by a model, a model satisfies statistical parity if and only if the acceptance rate with respect to the model predictions are equal for different demographic groups. Mathematically, statistical parity can be expressed as_

\[P(\widetilde{y}=1\mid s=0)=P(\widetilde{y}=1\mid s=1). \tag{1}\]

_where \(P(\cdot)\) refers to the probabililty of an event._

**Definition 2**.: _(**Equal opportunity (Kohn and Sham, 2015)**) Following the settings of Definition 1, a model satisfies equal opportunity if and only if the true positive rate with respect to the model predictions are equal for different demographic groups. Mathematically, equal opportunity can be expressed as_

\[P(\widetilde{y}=1\mid y=1,s=0)=P(\widetilde{y}=1\mid y=1,s=1). \tag{2}\]

_where \(P(\cdot)\) refers to the probability of an event._

Given Definitions 1 and 2, the bias with respect to statistical parity and equal opportunity are naturally defined as the discrepancies in the acceptance rate and the true positive rate across different demographic groups. Mathematically, the quantitative measures of bias with respect to statistical parity and equal opportunity are defined as Eq. (3) and Eq. (4), respectively.

\[\Delta_{\text{SP}}=|P(\widetilde{y}=1\mid s=1)-P(\widetilde{y}=1\mid s=0)|, \tag{3}\]

\[\Delta_{\text{EO}}=|P(\widetilde{y}=1\mid y=1,s=1)-P(\widetilde{y}=1\mid y= 1,s=0)|. \tag{4}\]

From the information-theoretic perspective, minimizing Eq. (3) and Eq. (4) is essentially equivalent to eliminating the statistical dependence between the model prediction \(\widetilde{y}\) and the sensitive attribute \(s\). Consequently, existing works could only ensure group fairness by imposing the statistical dependence (e.g., mutual information, Wasserstein distance) between \(\widetilde{y}\) and \(s\) as regularization in the optimization problem (Beng and Yang, 2015; Kohn and Sham, 2015; Kohn and Sham, 2015). Nevertheless, they could not explicitly consider the bias caused by the message passing schema. To this end, we seek to understand the role of message passing in the context of algorithmic fairness. Based on that, we define the problem of bias amplification in message passing as follows:

**Problem 1**.: _Bias amplification in message passing._

**Given:** (1) An undirected graph \(\mathcal{G}=\{\mathcal{V},\mathbf{A}\}\) of \(n\) nodes; (2) an \(L\)-layer GCN; (3) the vanilla message passing schema in any \(l\)-th hidden layer \(\widehat{\mathbf{h}}_{i}^{(l)}=\sum_{v_{j}\in\mathcal{N}(v_{i})\cup\{v_{j}\}}a_ {ij}\mathbf{h}_{j}^{(l)};(4)\) a sensitive attribute \(s\); (5) a bias measure bias for statistical parity.

**Find**: A binary decision regarding whether or not the bias will be amplified after message passing.

Based on the answer to Problem 1, our goal is to develop a generic fair message passing such that the bias measure in Problem 1 will decrease after message passing. We define the problem of fair message passing as follows:

**Problem 2**.: _Fair message passing._

**Given**: (1) An undirected graph \(\mathcal{G}=\{\mathcal{V},\mathbf{A},\mathbf{X}\}\) of \(n\) nodes; (2) an \(L\)-layer GCN; (3) a sensitive attribute \(s\); (4) a bias measure bias for statistical parity.
**Find:** A fair message passing schema \(\mathbf{\widehat{h}}_{i}^{(I)}=\textit{MP}(\mathbf{h}_{i}^{(I)})\) such that the bias will decrease after message passing.

## 3. Bias Amplification in Message Passing

In this section, we provide the empirical evidence that message passing does amplify bias, followed by the theoretical analysis on bias amplification in message passing.

### Empirical Evidence

We first empirically illustrate that message passing could amplify the bias. The design of our experiment is based on the assumption that the mining results (e.g., class probabilities) from a fair mining model (e.g., GCN) should be independent of the sensitive attribute (Beng et al., 2017). Therefore, we propose to use a logistic regression classifier to predict the sensitive attribute of a node using its corresponding mining result output by a mining model, where the accuracy of the sensitive attribute estimator naturally serves as an indicator of how biased a mining model is.

We investigate the effect of bias amplification of message passing on the Pokec-z dataset by comparing the behavior of a two-layer multi-layer perception (MLP) and a two-layer GCN. 4 Note that the only difference between the MLP and the GCN is whether the message passing is utilized or not, while the hidden dimensions and the nonlinear activation function are consistent with each other. The details for the empirical evaluation are as follows. First, we train the MLP or the GCN to predict labels using the node features with sensitive attributes excluded as input. When the graph neural networks reach the best performance, we freeze the parameters of the first layer of both the MLP and the GCN. Hence, the first layer of the MLP and the GCN can serve as extractors for label-related features. Second, we train a logistic regression classifier to predict sensitive attributes with the label-related features extracted by the MLP and the GCN. If an accurate prediction towards sensitive attributes can be obtained with label-related features, it implies that those label-related features contain rich sensitive attribute-related information. In this way, we are able to compare the relevance between sensitive attributes and those label-related features extracted by the two models.

Footnote 4: Details about the Pokec-z dataset is deferred to Section 5.

The evaluation results are presented in Figure 1. From the figure, we have three key observations. First, from Figure 1(b), we can observe a strong positive correlation between the sensitive attribute of a node and the sensitive attribute of its neighbors, i.e., a node tends to have the same sensitive attribute as the majority of its neighbors. Second, as shown in Figure 1(c), the MLP predicts the sensitive attribute of all nodes to the majority demographic group, even when a node and all its neighbors do not belong to the majority demographic group. Third, in Figure 1(c), the GCN makes much more accurate predictions than the MLP when the neighbors of a node are more likely to be in the minority group. The first and second observations imply that the label-related features extracted by MLP have little correlation with sensitive attributes, thus leading to the unbiased prediction in order to reach a high accuracy. On the contrary, the GCN extracts the node features containing rich sensitive attribute-related information for those nodes which belong to the same demographic group as their neighbors, as indicated in the third observation. This tendency of the GCN is clear for both the minority group and the majority group as well. These results demonstrate that message passing could aggregate the sensitive attribute-related information from the neighborhood, which further amplifies the bias and guides the logistic regression classifier to correctly predict the sensitive attribute.

### Theoretical Analysis

For analysis purposes, we consider a binary sensitive attribute and an \(L\)-layer linear GCN with row normalization (i.e., \(\alpha_{ij}=\frac{1}{d_{i}+1}\)) for binary node classification, where linear GCN is a special type of GCN model without the nonlinear activation (e.g., (Zhu et al., 2017)).5 Although our analysis relies on the linear GCN, recent works have shown that lack of non-linearity in GCN enjoys almost the same expressive power as nonlinear GCN (Zhu et al., 2017; Wang et al., 2018). Moreover, as shown in Figure 2, linear GCN exhibits similar or even slightly better node classification accuracy on the NBA dataset than its nonlinear counterpart, which also demonstrates that linearizing GCN is a good alternative to understand the behavior of GNN models.

Footnote 5: Our analysis can be naturally generalized to non-binary sensitive attribute and multi-class node classification with minor modifications.

To analyze the bias amplification phenomenon in message passing, we make the following assumption (Assumption 1) on the

Figure 1. The empirical evidence of bias amplification in GCN on the Pokec-z dataset. Best viewed in color. In (b), majority neighbor ratio is grouped into 10 equal-width bins with width being \(0.1\), i.e., \([0,0.1)\), \([0.1,0.2)\), \(\ldots\), \([0.9,1.0]\).
linearity of the node features in a graph. Similar linear relationship assumptions have been implicitly established in several existing works [32; 49]. For example, [32] utilizes linear orthogonal projection to mitigate the leakage of the sensitive attribute information (e.g., the projection direction is parallel to \(\mathbf{b}^{(1)}\) in Figure 3); [49] finds features in relation to the sensitive attribute using Pearson correlation coefficient and proposes a linear constraint to ensure the group fairness.

**Assumption 1**: _The feature vector \(\mathbf{x}_{i}=\mathbf{h}_{i}^{(1)}\) of any node \(\mathbf{\mathbf{\mathbf{\mathbf{\mathbf{\mathbf{\mathbf{\mathbf{\mathbf{\mathbf{\mathbf{ \mathbf{\mathbf{\mathbf{\mathbf{\mathbf{\mathbf{\mathbf{\mathbf{         }}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}\)))))   \}}} \} \} \} \} \} \} \ \} \} \ \ \ \ \ \\ \ \\ \ \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\}\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\}\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\}\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\}\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\}\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\}\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\}
of each node to the prototype of the demographic group it belongs to. Therefore, we could formulate the distance-based bias as_

\[\text{bias}^{(I)}\left(\mathcal{G},\mathbf{Z}^{(I)},s\right)=\frac{1}{\mathbb{E} _{\mathbb{M}}\left[\|\mathbf{z}_{i}^{(I)}-\mu(\mathbb{z}_{i})\|_{2}^{2}\right]} \tag{6}\]

_where \(\mathbf{z}_{i}^{(I)}\) is the \(i\)-th row of \(\mathbf{Z}^{(I)}\) and \(\mu(\mathbb{z}_{i})\) is the prototype corresponding to the demographic group of node \(\mathbb{e}_{i}\)._

Since message passing in GNNs without nonlinear activation is essentially a weighted summation, the Gaussian distribution of sensitive characteristic vector is retained after message passing. In other words, all the sensitive characteristic vectors in any hidden layer share the same distribution, i.e., Gaussian distribution. Therefore, the expected squared distance in different hidden layers can be directly compared with each other to reflect the bias. Then we furthermore show that the expected squared distance would shrink after message passing in any \(l\)-th hidden layer, which is equivalent to the amplification of the distance-based bias. Proof is deferred to Appendix B.

Theorem 1 ().: _(**Distance shrinkage**) Suppose we have an \(L\)-layer linear GCN and an input graph \(\mathcal{G}=\{\mathcal{V},\mathbf{A},\mathbf{X}\}\). In the \(l\)-th hidden layer, let \(\mathbf{z}_{i}^{(I)}\) be the sensitive characteristic vector of any \(\mathbb{e}_{i}\in\mathcal{V}\) and \(\mathbf{\widetilde{z}}_{i}^{(I)}\) be the sensitive attribute vector of the same node after message passing. For any \(l\)-th hidden layer, we have_

\[\mathbb{E}_{\mathbb{M}}\left[\|\mathbf{z}_{i}^{(I)}-\mu(\mathbb{z}_{i})\|_{2 }^{2}\right]>\mathbb{E}_{\mathbb{M}}\left[\|\mathbf{\widetilde{z}}_{i}^{(I)} -\mu(\mathbb{z}_{i})\|_{2}^{2}\right] \tag{7}\]

_which means the distance-based bias is amplified after message passing, i.e., \(\text{bias}^{(I)}(\mathcal{G},\mathbf{Z}^{(I)},s)<\text{bias}^{(I)}(\mathcal{ G},\mathbf{\widetilde{Z}}^{(I)},s)\)_

**Distance-based Bias vs. Statistical Parity.** Here we discuss how the amplification of distance-based bias would affect the statistical parity. Recall that statistical parity is satisfied if and only if the output of GCN is independent to the sensitive attribute. Suppose we have a well-trained \(L\)-layer GCN whose output for node \(\mathbb{e}_{i}\) is \(\mathbf{h}_{i}^{(L+1)}\) and a classifier \(g\) to predict the label of each node in the label set \(\mathcal{Y}\). By Lemma 1, we have \(\mathbf{h}_{i}^{(L+1)}=c_{i}\mathbf{\widetilde{t}}_{i}^{(L)}\mathbf{W}^{(L)} +c_{2}f(\mathbf{\widetilde{z}}_{i}^{(L)})\mathbf{W}^{(L)}\). Since the bias information vector \(\mathbf{b}_{i}^{(L)}=\mathbf{\widetilde{t}}_{i}^{(L)}\mathbf{W}^{(L)}=f( \mathbf{\widetilde{z}}_{i}^{(L)})\mathbf{W}^{(L)}\) determines the sensitive attribute of each node and the label information vector \(\mathbf{t}_{i}^{(I)}\) determines the label of each node, a fair classifier should always output the same predictions for a specific label information vector \(\mathbf{t}_{i}^{(I)}\). Mathematically, we have \(g(\mathbf{h}_{i}^{(L\pm 1)})=c_{1}g(\mathbf{\widetilde{t}}_{i}^{(L)} \mathbf{W}^{(L)})\), i.e., \(g(f(\mathbf{\widetilde{z}}_{i}^{(L)})\mathbf{W}^{(L)})=\mathbf{0}\) where \(\mathbf{0}\) is the vector filled with \(0\). Note that \(\mu_{0}\) and \(\mu_{1}\) are the prototypes of the minority group and the majority group, respectively. If the GCN output is biased, the classifier tends to give different predictions for the minority group and the majority group. Thus, for any label \(y\in\mathcal{Y}\), we have

\[g(f(\mu_{0})\mathbf{W}^{(L)})[y]\cdot g(f(\mu_{1})\mathbf{W}^{(L)})[y]<0 \tag{8}\]

Eq. (8) means that, for any class \(y\in\mathcal{Y}\) the probability of being predicted as label \(y\) will increase for the majority group (i.e., \(g(f(\mu_{1})\mathbf{W}^{(L)})[y]>0\)) and decrease for the minority group (i.e., \(g(f(\mu_{0})\mathbf{W}^{(L)})[y]<0\)), or vice versa. However, as shown in Theorem 1, if the expected distance to the prototypes would shrink after message passing, for any node \(\mathbb{e}_{i}\), it is likely that \(\mathbf{\widetilde{z}}_{i}^{(I)}\) will gradually approach the corresponding prototype \(\mu(\mathbb{e}_{i})\in\{\mathbb{\mu}_{0},\mathbb{\mu}_{1}\}\), which makes \(g(\mathbf{\widetilde{z}}_{i}^{(L)}\mathbf{W}^{(L)})[y]\neq 0\), \(\forall y\in\mathcal{Y}\), and causes unfair predictions.

## 4. BEMAP: A fair message passing schema

In this section, we first present how to avoid bias amplification in message passing and then propose a fair message passing method named BeMap.

### Fair Message Passing

Following the settings in Section 3.2, Eq. (8) states that an unfair GCN would give opposite estimates on the prototypes of the majority group and the minority group. By the intermediate zero theorem, it is trivial that there exists a fair prototype \(\bar{\mu}\) on the line segment of the prototypes \(\mu_{0}\) and \(\mu_{1}\) such that \(g(f(\bar{\mu})\mathbf{W}^{(L)})=0\). To ensure group fairness, the intuition to make sure the sensitive characteristic vector \(\mathbf{\widetilde{z}}_{i}\) would move towards the fair prototype. An illustrative example is presented in Figure 4.

It is non-trivial to find the fair prototype. By Theorem 1, in addition to letting the sensitive characteristic vectors move towards the fair prototype, we consider an alternative goal: the expected squared Euclidean distance between the sensitive characteristic vector of each node and the corresponding prototype it belongs to would increase after message passing. Combining these two goals, we empirically set the fair prototype as \(\bar{\mu}=\frac{1}{2}\mu_{0}+\frac{1}{2}\mu_{1}\). When the sensitive characteristic vectors move towards \(\bar{\mu}\), it maximizes the expected squared distance to the prototype of the corresponding demographic group of each node. To obtain the fair prototype, we provide a sufficient condition in Lemma 2. Proof is deferred to Appendix C.

Lemma 2 ().: _(**Sufficient condition for fair prototype**) Suppose Assumption 1, Assumption 2 and Assumption 3 hold, and we are given an input graph \(\mathcal{G}=\{\mathcal{V},\mathbf{A},\mathbf{X}\}\) and an \(L\)-layer linear GCN with \(L-1\) parameter-free hidden layers,6 i.e., \(\mathbf{h}^{(L+1)}=\mathbf{\widetilde{h}}^{(I)}=\mathbf{\Sigma}_{\mathbb{H} ^{(I)}}\) and \(\sum_{\mathbb{e}_{j}\in\widetilde{N}(\mathbb{e}_{j})}\alpha_{ij}\mathbf{h}^{(I)}\) for \(\mathbb{\mathbb{\nu}}_{i}\in\mathcal{V},l\in\{1,\dots,L-1\}\) where \(\alpha_{ij}=\frac{1}{d_{i}+1}\). For any node \(\mathbb{\mathbb{\nu}}_{i}\in\mathcal{V}\), let \(\widetilde{N}_{0}(\mathbb{\mathbb{\nu}}_{i})\) and \(\widetilde{N}_{1}(\mathbb{\mathbb{\nu}}_{i})\) be the number of neighbors in \(\widetilde{N}(\mathbb{\mathbb{\nu}}_{i})=\mathcal{N}(\mathbb{\mathbb{\nu}}_{i})\cup \{\mathbb{\nu}_{i}\}\) that belong to the minority group and majority group, respectively. In the \(l\)-th hidden layer, the mean of the sensitive characteristic vector \(\mathbf{z}_{i}^{(I)}\) for \(\mathbb{\mathbb{\nu}}_{i}\in\mathcal{V}\) is the fair prototype \(\bar{\mu}=\frac{1}{2}\mu_{0}+\frac{1}{2}\mu\) when_

Footnote 6: For linear GCN, \(\mathbf{H}^{(L+1)}=\widetilde{\mathbf{\Sigma}}^{\mathrm{\mathbf{\mathbf{\mathbf{ \mathbf{\mathbf{\mathbf{\mathbf{\mathbf{\mathbf{\mathbf{\mathbf{\mathbf{\mathbf{\mathbf{\mathbf{\mathbf{\mathbf{\mathbf{\mathbf{\mathbb
between the sensitive characteristic vector \(\mathbf{z}_{i}^{(l)}\) and the fair prototype \(\hat{\rho}\) will shrink after message passing. Mathematically, we have_

\[\mathbb{E}_{u}\left[\|\widetilde{\mathbf{z}}_{i}^{(I)}-\hat{\rho}\|_{2}^{2} \right]<\mathbb{E}_{u}\left[\|\mathbf{z}_{i}^{(I)}-\hat{\rho}\|_{2}^{2}\right],\quad l\in\{1,\ldots,L\}. \tag{10}\]

### BeMap Algorithm

Based on our results in Theorem 2, we propose a fair message passing algorithm named BeMap, whose key idea is to perform message passing on a sufficiently large and balanced self-augmented neighborhood (which we call fair neighborhood). To obtain the fair neighborhood, we consider sampling (i.e., edge deletion) over the original self-augmented neighborhood in BeMap. Note that other types of neighborhood augmentation techniques (e.g., edge addition, edge rewiring) could also be applied to obtain the fair neighborhood, which we leave for future work. Hereafter, BeMap is referred to as message passing over the sampled fair neighborhood.

In practice, there are two main challenges in obtaining the fair neighborhood in BeMap due to the long-tailed in many real-world networks. First, there could exist some node \(v_{i}\) such that \(\widetilde{N}_{0}(v_{i})=\widetilde{N}_{1}(v_{i})\) and \(\widetilde{N}_{0}(v_{i})+\widetilde{N}_{1}(v_{i})\geq 4\) cannot be satisfied simultaneously. In this case, we apply the following two empirical remedies.

* If all neighbors in \(\widetilde{\mathcal{N}}(v_{i})\) of a node \(v_{i}\) belong to one demographic group, we sample a subset of \(k\) nodes where \(k=\max\{\beta|\mathcal{N}(v_{i})|,m\}\), \(|\mathcal{N}(v_{i})|\) is the cardinality of \(\mathcal{N}(v_{i})\) and \(\beta\) as well as \(m\) are two hyperparameters. The intuition is that decreasing the number of neighbors (i.e., the degree \(d_{i}\) of node \(v_{i}\)) helps reduce the difference between the expected squared distances before and after message passing as shown in Eq. (18). Thus, it helps decelerate the sensitive characteristic vectors moving towards the prototype of the demographic group of \(v_{i}\).
* Otherwise, we keep the sampled neighborhood to be balanced, i.e., \(\widetilde{N}_{0}(v_{i})=\widetilde{N}_{1}(v_{i})\), by sampling over \(\mathcal{N}_{0}(v_{i})\) if \(\widetilde{N}_{0}(v_{i})>\widetilde{N}_{1}(v_{i})\) or \(\mathcal{N}_{1}(v_{i})\) if \(\widetilde{N}_{0}(v_{i})<\widetilde{N}_{1}(v_{i})\). By balancing the sampled neighborhood, though it may not be guaranteed to decrease the expected squared distance to the fair prototype, it helps keep the mean of the sensitive characteristic vector to be the fair prototype.

Second, there might exist some node \(v_{i}\) such that its neighbors within \(L\) hops could contain node(s) whose neighbors always belong to only one demographic group. Note that the receptive field of the \(l\)-th hidden layer in an \(L\)-layer GCN is the \(l\)-hop neighborhood of a node. Then, for such node \(v_{i}\), it is hard to maintain a balanced \(l\)-hop neighborhood if we apply uniform sampling, so as to satisfy Lemma 2. To alleviate the aforementioned scenario, we propose _balance-aware sampling_ whose key idea is to adjust the sampling probability based on the difference between the numbers of neighbors in the majority group and in the minority group. Specifically, for any node \(v_{i}\in\mathcal{V}\), we define the balance score as

\[\text{balance}_{i}=\frac{1}{|\widetilde{N}_{0}(v_{i})-\widetilde{N}_{1}(v_{i} )|+\delta} \tag{11}\]

where \(\delta\) is a hyperparameter to avoid division by zero and \(\widetilde{N}_{0}(v_{i})\) as well as \(\widetilde{N}_{1}(v_{i})\) are the numbers of all neighbors within \(L\) hops that belong to the minority group and majority group, respectively. Then in the balance-aware sampling, for any node \(v_{i}\in\mathcal{V}\), the sampling probability of node \(v_{j}\in\mathcal{N}(v_{i})\) is defined as

\[P(v_{j}|v_{i})=\frac{\text{balance}_{j}}{\sum_{v_{k}\in\mathcal{N}(v_{i})}\text {balance}_{k}} \tag{12}\]

The general workflow of BeMap is presented in Algorithm 1. Before training, we precompute the sampling probability in the balance-aware sampling (lines 3 - 5). During each epoch, we first generate the fair neighborhood using the balance-aware sampling (lines 7 - 11). Then for each hidden layer, the fair node representation of each node is learned on the fair neighborhood (lines 12 - 15). Finally, we update the model parameters with back-propagation (lines 16 - 17).

**Extension to Non-binary Sensitive Attribute.** We consider a non-binary sensitive attribute \(s\) which forms \(n_{s}\) demographic groups, i.e., \(s\in\{1,\ldots,n_{s}\}\). The key idea of BeMap is to balance the number of neighbors across different demographics. We discuss two cases for balancing the neighborhood in the following.

Figure 4. An illustrative example on the intuition of BeMap. After BeMap, the sensitive characteristic vectors will move towards the fair prototype (the green point), whereas, after the vanilla message passing in GCN, they will move towards the prototype of the majority group and the minority group (the red points).
* _When all neighbors belong to one demographic group:_ We adopt the same strategy as the case of binary sensitive attribute by sampling a subset of \(k\) neighbors for any node \(v_{i}\) such that \(k=\max\{\beta|\mathcal{N}(v_{i})|,m\}\).
* _When the neighbors belong to different demographic groups:_ In this case, for any node \(v_{i}\), we first count the number of neighbors in each demographic group \(\{\widetilde{\mathcal{N}}_{\text{s}}(v_{i})|\forall s=1,\ldots,n_{\text{s}}\}\). Then we set the number of neighbors to be sampled for any demographic group \(k\) as the smallest non-zero value in \(\{\widetilde{\mathcal{N}}_{\text{s}}(v_{i})|\forall s=1,\ldots,n_{\text{s}}\}\). After that, for each demographic group in the neighborhood of \(v_{i}\), we sample \(k\) neighbors to create a balanced neighborhood.

Regarding the balance-aware sampling probability in the above sampling steps, we modify Eq. (11) by replacing the absolute difference \(|\widetilde{\mathcal{N}}_{\text{0}}(v_{i})-\widetilde{\mathcal{N}}_{\text{1}} (v_{i})|\) in the cardinalities of two demographic groups in binary case to the average squared difference between the cardinalities of any two demographic groups.

\[\text{balance}_{i}=\frac{1}{\sqrt{\frac{2}{n_{\text{s}}(n_{ \text{s}}-1)}\sum_{s=1}^{n_{\text{s}}}(\widetilde{\mathcal{N}}_{k}(v_{i})- \widetilde{\mathcal{N}}_{j}(v_{i}))^{2}}+\delta}\] \[\forall k,j\in\{1,\ldots,n_{\text{s}}\},k\neq j \tag{13}\]

It should be noted that when \(\text{s}\) is binary sensitive attribute, Eq. (13) is equivalent to Eq. (11). In this way, we could adopt similar training procedure in Algorithm 1 to train the fair graph neural network.

## 5. Experiments

In this section, we answer two research questions through experiments: (1) How effective is BeMap in bias mitigation? (2) How does the fairness impact the utility of the downstream task?

### Experimental Settings

**Datasets.** We conduct experiments on 4 real-world datasets, including _Pokee-z_, _NBA_, _Credit_, and _Recidivism_. The detailed statistics of the datasets are provided in Table 2. The _Pokee-z_ dataset (Pokee, 2017) is drawn from Pokec, a Facebook-like social network in Slovakia, based on regional information. In Pokec-z, we set the sensitive attribute as the region of a user and aim to predict the field of work of a user. The _NBA_ dataset (Kipper, 2017) includes the age, nationality (US vs. overseas), salary of a NBA player for the 2016 - 2017 season. Two players are connected if one follows another on Twitter. In this dataset, the nationality is used as the sensitive attribute, and the goal is to predict whether the salary of a player is above the median. The _Credit_ dataset (Kipper, 2017) contains age, education and payment patterns of a credit card customer. The links among customers are determined by the pairwise similarity of their credit accounts. Here, age is set as the sensitive attribute and the label is whether a user will default on credit card payments. The _Recidivism_ dataset (Beng et al., 2017) consists of defendants who were released on bail during 1990 - 2009. Two defendants are connected if they share similar demographic information and criminal records. The goal is to predict whether a defendant is likely to commit a crime when released (i.e., bail) or not (i.e., no bail) with race as the sensitive attribute.

**Baselines.** We compare BeMap with two classic graph neural networks, including _GCN_(Kipper, 2017) and _GraphSAGE_(Kipper, 2017), as well as five fair graph neural networks, including _FairGNN_(Kipper, 2017), _EDITS_(Kipper, 2017), _FairDrop_(Kipper, 2017), _NIFTY_(Beng et al., 2017) and _FMP_(Kipper, 2017). More specifically, (1) _GCN_(Kipper, 2017) learns the representation of a node by iteratively aggregating the representations of its 1-hop neighbors; (2) _GraphSAGE_(Kipper, 2017) aggregates node representations from a subset of 1-hop neighbors; (3) _FairGNN_(Kipper, 2017) leverages adversarial learning to debias the node representations; (4) _EDITS_(Kipper, 2017) defines attribute bias and structural bias, and removes these biases in the input data by minimizing the Wasserstein distance; (5) _FairDrop_(Kipper, 2017) breaks sensitive attribute homophily by randomly masking edges in the input graph, thus mitigating bias; (6) _NIFTY_(Beng et al., 2017) utilizes a layer-wise weight normalization limited by the Lipschitz constant to improve counterfactual
fairness in a contrastive learning framework; and (7) _FMP_(Krizhevsky et al., 2015) redesigns a unified framework for fairness objectives which aggregates useful information from neighbors with reduced topology bias.

**Parameter Settings.** Unless otherwise specified, we use default hyperparameter settings in the released code of corresponding publications. Regarding BeMap, we set the learning rate as \(1e-3\), \(m\) as \(4\), \(\beta\) as \(\frac{1}{4}\) and \(\delta\) as \(1\). We set the backbone model of BeMap as a 2-layer GCN with \(128\) hidden dimensions and the optimizer as Adam optimizer with \(1e-5\) weight decay. To be consistent with the number of hidden layers, for each node, all neighbors within 2-hops are used to calculate the balance score in Eq. (11).

**Metrics.** We consider the task of semi-supervised node classification. To measure the utility, we use the classification accuracy (ACC) and the area under the receiver operating characteristic curve (AUC). Regarding fairness, we use \(\Delta_{\text{SP}}\) and \(\Delta_{\text{EO}}\) mentioned in Section 2, which are the two most commonly used metrics to evaluate the effectiveness of bias mitigation. For ACC and AUC, the higher the better; while for \(\Delta_{\text{SP}}\) and \(\Delta_{\text{EO}}\), the lower the better.

### Experimental Results

**Main Results.** The evaluation results on the utility (ACC and AUC) and fairness (\(\Delta_{\text{EO}}\) and \(\Delta_{\text{SP}}\)) are presented in Table 1. Regarding fairness, we can see that our proposed BeMap is the only method that can consistently mitigate bias (i.e., a smaller value of \(\Delta_{\text{EO}}\) and \(\Delta_{\text{SP}}\) than GCN and GraphSAGE without fairness consideration) for all datasets. Moreover, compared with the vanilla GCN without fairness consideration, BeMap could reduce \(\Delta_{\text{EO}}\) (\(\Delta_{\text{SP}}\)) by \(86.8\%\) (\(83.6\%\)), \(70.8\%\) (\(0.12\%\)), \(53.4\%\) (\(79.31\%\)), \(45.7\%\) (\(40.1\%\)) on the Pokec-z, NBA, Recidivism and Credit datasets, respectively. Other than the superior performance in bias mitigation, BeMap also achieves comparable performance with the baseline methods in terms of the utility of node classification (ACC and AUC). It is because BeMap generates a new balanced graph for each epoch, analogous to data augmentation. This data augmentation effectively prevents the graph neural network from overfitting during training, thus improving the utility of the model. For example, on NBA dataset, BeMap even achieves a higher AUC (\(78.76\%\)) than the vanilla GCN (\(78.45\%\)) when significantly reducing fairness-related metrics \(\Delta_{\text{SP}}\) and \(\Delta_{\text{EO}}\) In short words, BeMap could achieve a good balance between mitigating the bias and maintaining the classification accuracy.

**Ablation Study.** To evaluate the effectiveness of the balance-aware sampling utilized in BeMap, we compare it with two other heuristic sampling strategies: (1) _uniform sampling_ (Uniform), which assigns the same probability to all neighbors of a node, and (2) _degree-based sampling_ (Degree), which sets the probability of node \(v_{i}\) in the neighborhood of node \(u\) as \(P(v_{i})\propto d_{i}^{0.75},\forall v_{i}\in\mathcal{N}(u)\)(Kumar et al., 2017). From the results in Table 3, we can see that the balance-aware sampling achieves the lowest \(\Delta_{\text{EO}}\) and \(\Delta_{\text{SP}}\) on all datasets and maintains a comparable classification accuracy, which demonstrates the superiority of the balance-aware sampling in balancing the utility and fairness.

## 6. Related Work

**Graph Neural Network.** Graph neural network (GNN) has demonstrated state-of-the-art performance in various learning tasks, including anomaly detection (Krizhevsky et al., 2015), crime rate prediction (Zhu et al., 2017), and recommender systems (Krizhevsky et al., 2015). (Zhu et al., 2017) proposes the Graph Convolutional Network (GCN) by utilizing a localized first-order approximation of spectral graph convolutions. (Glorot and Bengio, 2015) introduces graph neural networks

\begin{table}
\begin{tabular}{c|c|c|c|c|c|c|c|c} \hline \hline \multirow{2}{*}{**Dataset**} & \multirow{2}{*}{**Metric**} & \multicolumn{6}{c|}{**Compared Methods**} \\ \cline{3-10}  & & GCN & GraphSAGE & FairGNN & EDITS & FairDrop & NIFTY & FMP & BeMap \\ \hline \multirow{5}{*}{**Pokec-z**} & ACC(\(\%\))\(\uparrow\) & \(70.62\pm 0.22\) & \(70.27\pm 0.32\) & \(65.74\pm 2.49\) & \(67.25\pm 0.61\) & \(67.45\pm 0.80\) & \(67.55\pm 0.79\) & \(\mathbf{72.05\pm 0.42}\) & \(68.94\pm 0.46\) \\  & AUC(\(\%\))\(\uparrow\) & \(76.41\pm 0.61\) & \(75.73\pm 0.30\) & \(72.54\pm 4.21\) & \(73.05\pm 0.57\) & \(73.77\pm 0.50\) & \(73.87\pm 0.23\) & \(\mathbf{80.50\pm 0.11}\) & \(73.01\pm 0.29\) \\ \cline{2-10}  & \(\Delta_{\text{SP}}\)(\(\%\))\(\downarrow\) & \(8.86\pm 2.32\) & \(7.11\pm 2.69\) & \(\mathbf{4.31\pm 0.80}\) & \(\mathbf{10.36\pm 1.20}\) & \(\mathbf{9.46\pm 2.06}\) & \(8.83\pm 1.60\) & \(5.03\pm 1.22\) & \(\mathbf{1.45\pm 0.40}\) \\  & \(\Delta_{\text{EO}}\)(\(\%\))\(\downarrow\) & \(\mathbf{7.81\pm 1.99}\) & \(6.97\pm 2.65\) & \(\mathbf{4.34\pm 1.22}\) & \(\mathbf{9.09\pm 1.34}\) & \(7.91\pm 1.59\) & \(7.00\pm 1.70\) & \(1.72\pm 0.64\) & \(\mathbf{1.03\pm 0.42}\) \\ \hline \multirow{5}{*}{**NBA**} & ACC(\(\%\))\(\uparrow\) & \(72.16\pm 0.46\) & \(\mathbf{75.21\pm 0.86}\) & \(72.39\pm 0.46\) & \(66.19\pm 0.75\) & \(70.81\pm 0.63\) & \(60.84\pm 3.32\) & \(68.57\pm 1.58\) & \(65.37\pm 1.77\) \\  & AUC(\(\%\))\(\uparrow\) & \(78.45\pm 0.25\) & \(77.83\pm 2.00\) & \(77.74\pm 1.24\) & \(69.94\pm 0.72\) & \(70.75\pm 0.46\) & \(65.94\pm 1.30\) & \(77.73\pm 0.35\) & \(\mathbf{78.76\pm 0.62}\) \\ \cline{1-1}  & \(\Delta_{\text{SP}}\)(\(\%\))\(\downarrow\) & \(4.00\pm 2.15\) & \(78.1\pm 3.45\) & \(3.96\pm 1.81\) & \(18.15\pm 3.64\) & \(5.42\pm 1.59\) & \(10.03\pm 5.46\) & \(31.41\pm 1.11\) & \(\mathbf{5.54\pm 0.97}\) \\ \cline{1-1}  & \(\Delta_{\text{EO}}\)(\(\%\))\(\downarrow\) & \(13.07\pm 3.34\) & \(8.87\pm 5.58\) & \(4.94\pm 2.35\) & \(13.19\pm 3.48\) & \(7.30\pm 1.34\) & \(5.70\pm 3.21\) & \(27.17\pm 3.19\) & \(\mathbf{3.31\pm 0.98}\) \\ \hline \multirow{5}{*}{**Recidivism**} & ACC(\(\%\))\(\uparrow\) & \(85.89\pm 0.18\) & \(85.00\pm 0.52\) & \(69.54\pm 5.70\) & \(83.88\pm 0.84\) & \(\mathbf{91.81\pm 0.36}\) & \(83.43\pm 0.83\) & \(56.80\pm 10.83\) & \(77.66\pm 0.35\) \\  & AUC(\(\%\))\(\uparrow\) & \(88.74\pm 0.23\) & \(89.41\pm 0.36\) & \(80.79\pm 5.33\) & \(86.82\pm 0.40\) & \(\mathbf{92.17\pm 0.86}\) & \(84.56\pm 0.33\) & \(61.79\pm 4.87\) & \(80.77\pm 1.02\) \\ \cline{1-1} \cline{2-10}  & \(\Delta_{\text{SP}}\)(\(\%\))\(\downarrow\) & \(8.51\pm 0.48\) & \(8.99\pm 0.37\) & \(6.61\pm 2.29\) & \(7.63\pm 0.57\) & \(6.80\pm 0.22\) & \(4.75\pm 0.92\) & \(22.43\pm 9.72\) & \(\mathbf{1.76\pm 0.14}\) \\ \cline{1-1}  & \(\Delta_{\text{EO}}\)(\(\%\))\(\uparrow\) & \(5.75\pm 1.08\) & \(6.14\pm 0.54\) & \
for inductive learning via neighborhood sampling and aggregation. (Kang et al., 2022) leverages the self-attention mechanism to learn the attention weights for neighborhood aggregation. (Kang et al., 2022) scales up the training on large graphs by importance sampling. (Kang et al., 2022) learns node representations by randomly dropping nodes to augment data and enforcing the consistency of predictions among augmented data. Similarly, (Kang et al., 2022) randomly drops nodes for several runs and aggregates the predictions for the final prediction by ensemble. Different from (Kang et al., 2022; Kang et al., 2022; Kang et al., 2022) that drop nodes for scalable training or improving the generalization and/or expressiveness of GNN, our work drops edges (i.e., dropping nodes in the local neighborhood of a node) to mitigate bias in GNN. (Kang et al., 2022) randomly drops edges to perform data augmentation and prevent over-smoothing. Different from (Kang et al., 2022) that randomly drops edges to alleviate over-smoothing, our work selectively removes edges to obtain balanced graph structures to improve the model fairness. For comprehensive literature reviews on graph neural networks, please refer to (Kang et al., 2022; Kang et al., 2022; Kang et al., 2022; Kang et al., 2022).

**Fairness in Graph Neural Network.** Fairness has been actively studied in the context of graph neural networks, e.g., group fairness (Kang et al., 2022; Kang et al., 2022), individual fairness (Kang et al., 2022; Kang et al., 2022), and counterfactual fairness (Kang et al., 2022). A common strategy to learn fair graph neural networks is through optimizing a regularization-based optimization problem (Kang et al., 2022; Kang et al., 2022; Kang et al., 2022; Kang et al., 2022). For group fairness, (Kang et al., 2022) ensures group fairness by imposing mutual information between sensitive attributes and node embeddings as the regularization term and mitigates the bias via adversarial learning. (Kang et al., 2022) leverages a similar debiasing strategy to learn fair graph neural networks with limited sensitive attributes. For individual fairness, (Kang et al., 2022) measures individual bias as the debiasing norm with respect to the pairwise node similarity matrix and Laplacian matrix, and regularizes it in the optimization problem. (Kang et al., 2022) learns individually fair graph neural networks by regularizing a ranking-based individual fairness measure. In terms of counterfactual fairness, (Kang et al., 2022) learns counterfactually fair node embeddings by imposing the contrastive loss as the regularization term. (Kang et al., 2022) follows the similar contrastive learning strategy while generating the negative examples via variational graph auto-encoder (Kang et al., 2022). Different from the aforementioned techniques, our work does not require any regularization in the objective function. Other than regularization-based formulation, (Kang et al., 2022) preprocesses the input graph by pre-training a neural network to minimize the Wasserstein distance between the node feature distributions of majority nodes and minority nodes. (Kang et al., 2022) proposes a novel message passing schema that essentially solves a minimax problem to promote group fairness. (Kang et al., 2022) proposes biased edge dropout that promotes the existence of edges connecting nodes in different demographic groups. However, the message passing schema proposed by (Kang et al., 2022) bears little resemblance to the original message passing schema, and thus completely changes the training procedures of graph neural networks; (Kang et al., 2022) requires a pretrained model to preprocess the input graph. Compared to (Kang et al., 2022; Kang et al., 2022), our work concisely and efficiently tunes message passing via a theory-guided node sampling strategy to ensure both utility and fairness.

## 7. Conclusion

In this paper, we study the problems of bias amplification in message passing and fair message passing. We empirically and theoretically prove that message passing amplifies the bias as long as the numbers of neighbors from different demographic groups for each node are unbalanced. Guided by our analyses, we propose BeMap, which relies on a balance-aware sampling strategy to generate a fair neighborhood among different demographic groups. Then, BeMap performs message passing over the generated fair neighborhood. Extensive evaluations on the real-world datasets demonstrate the effectiveness of our proposed method in mitigating bias while maintaining utility.
