GFairHint: Improving Individual Fairness for Graph Neural Networks via
  Fairness Hint
Given the growing concerns about fairness in machine learning and the
impressive performance of Graph Neural Networks (GNNs) on graph data learning,
algorithmic fairness in GNNs has attracted significant attention. While many
existing studies improve fairness at the group level, only a few works promote
individual fairness, which renders similar outcomes for similar individuals. A
desirable framework that promotes individual fairness should (1) balance
between fairness and performance, (2) accommodate two commonly-used individual
similarity measures (externally annotated and computed from input features),
(3) generalize across various GNN models, and (4) be computationally efficient.
Unfortunately, none of the prior work achieves all the desirables. In this
work, we propose a novel method, GFairHint, which promotes individual fairness
in GNNs and achieves all aforementioned desirables. GFairHint learns fairness
representations through an auxiliary link prediction task, and then
concatenates the representations with the learned node embeddings in original
GNNs as a "fairness hint". Through extensive experimental investigations on
five real-world graph datasets under three prevalent GNN models covering both
individual similarity measures above, GFairHint achieves the best fairness
results in almost all combinations of datasets with various backbone models,
while generating comparable utility results, with much less computational cost
compared to the previous state-of-the-art (SoTA) method.
Paiheng Xu, Yuhang Zhou, Bang An, Wei Ai, Furong Huang
# GFairHint: Improving Individual Fairness for Graph Neural Networks via Fairness Hint

###### Abstract.

Given the growing concerns about fairness in machine learning and the impressive performance of Graph Neural Networks (GNNs) on graph data learning, algorithmic fairness in GNNs has attracted significant attention. While many existing studies improve fairness at the group level, only a few works promote individual fairness, which renders similar outcomes for similar individuals. A desirable framework that promotes individual fairness should (1) balance between fairness and performance, (2) accommodate two commonly-used individual similarity measures (externally annotated and computed from input features), (3) generalize across various GNN models, and (4) be computationally efficient. Unfortunately, none of the prior work achieves all the desirabes. In this work, we propose a novel method, _GFairHint_, which promotes individual fairness in GNNs and achieves all aforementioned desirabes. GFairHint learns fairness representations through an auxiliary link prediction task, and then concatenates the representations with the learned node embeddings in original GNNs as a _"fairness hint"_. Through extensive experimental investigations on five real-world graph datasets under three prevalent GNN models covering both individual similarity measures above, GFairHint achieves the best fairness results in almost all combinations of datasets with various backbone models, while generating comparable utility results, with much less computational cost compared to the previous state-of-the-art (SoTA) method.

+
Footnote †: journal:
0 or below a certain threshold. We then learn a fairness representation for each node from the constructed fairness graph via link prediction, where we encourage the model to recover randomly masked edges. The learned fairness representation is then used as _fairness hint_ to be concatenated with the node embeddings from the original graph, which is trained in parallel to maximize utility with the main GNN model. We feed the concatenated representations to multilayer perceptrons (MLPs) to make fair and accurate predictions.

GFairHint focuses on learning an additional fair representation and is compatible with various GNN model designs. It is orthogonal and complementary to a strategy adopted by most previous work (Kang et al., 2018; Li et al., 2019; Li et al., 2019), i.e., adding a fairness regularization term to the training objective. Meanwhile, GFairHint is a light-weighted framework. It is more computationally efficient and especially works better with large network datasets in terms of computation cost and both utility and fairness performance, while previous work either takes much longer training time (Kang et al., 2018) or requires large memory allocation, and therefore may fail on some large datasets (Li et al., 2019). Furthermore, GFairHint can benefit from these existing methods with fairness regularized objective functions when integrated together to further improve the performance.

To demonstrate the effectiveness of our proposed method, we conduct extensive empirical evaluations on five datasets for node classification. These datasets apply either continuous similarity measures derived from the input space or binary measures provided by external annotators to quantify the similarity between individuals. Additionally, we experiment with three popular GNN backbone models, resulting in a total of 15 models \(\times\) dataset comparisons. Our GFairHint framework consistently outperforms other methods in terms of fairness, achieving the best results in 12 out of the 15 comparisons. Furthermore, in 9 out of the 15 comparisons, GFairHint achieves the best utility performance, while in the remaining comparisons, it achieves comparable utility results. We summarize our main contributions as follows:

* **Plug-and-play Framework**: We present GFairHint, a plug-and-play framework for enhancing individual fairness in GNNs. This framework learns a fairness hint through an auxiliary link prediction task. We provide a theoretical analysis on the fairness hint and prove that for any two nodes, the learned hints are individually fair.
* **Satisfied Desiderata**: GFairHint is compatible with two distinct settings for similarity measures among individuals and can achieve comparable accuracy while generating more individually fair predictions. Additionally, the method is computationally efficient and seamlessly integrates with various model designs.
* **Rigorous Experiments**: We empirically show that the proposed method achieves the best fairness results in most comparisons (12/15), with the best utility results in the 9/15 comparisons, and comparable utility performance in the other comparisons.

## 2. Related Work

Fairness for Graph-structured DataMost previous efforts focus on promoting group fairness in graphs (Kang et al., 2018; Li et al., 2019; Li et al., 2019; Li et al., 2019; Li et al., 2019), which

Figure 1. The proposed individual fairness promotion framework, GFairHint. Colored rectangles denote the representations of corresponding nodes (i.e., individuals). GFairHint learns the fairness hint from the fairness graph and concatenates it with the utility node embedding from the original backbone GNN model. Finally, it feeds the concatenated node embedding into an MLP to make fair predictions. The loss function for GFairHint can be a single utility loss (cross-entropy loss) or a combination of utility loss and fairness loss (e.g., ranking-based loss).
encourages the same results across different sensitive groups (e.g., demographics). Another line of research work is on counterfactual fairness (Zhou et al., 2017; Zhang et al., 2018), which aims to generate the same prediction results for each individual and its counterfactuals.

Few research studies individual fairness in graphs (Zhou et al., 2017; Zhang et al., 2018). Individual fairness intends to render similar predictions to similar individuals for a specific task. Kang et al. (2017) propose a framework called InFoRM (Individual Fairness on Graph Mining) to debias a graph mining pipeline from the input graph (preprocessing), the mining model (processing), and the mining results (postprocessing), but not specifically for GNN models. Song et al. (2018) identify a new challenge to enforce individual fairness informed by group equality. Promoting group and individual fairness at the same time requires group information, which is not available in some real-life scenarios, such as the academic networks studied in this paper. The work closest to ours is REDRESS (Kang et al., 2017). They propose to model individual fairness from a ranking-based perspective and design a ranking-based loss accordingly. However, their method does not generalize well when the similarity measure is binary, especially binary, because calculating the ranking-based loss requires to rank the individuals based on the similarity values but with binary similarity measures (i.e., many individuals on the same similarity level) the rankings are not as informative as in the cases with continuous similarity measures. Moreover, despite their effort on reducing the computation cost and the effectiveness of the ranking-based loss, high computational cost is unavoidable when computing the rank.

Individual FairnessThere are other works focusing on individual fairness, but not specifically for graph-structured data. The definition of individual fairness, similar predictions for similar individuals, can be formulated by the Lipschitz constraint, which inspires works such as Pairwise Fair Representation (PFR) (Zhou et al., 2017) to learn fair representation as input. This can be considered as a pre-processing method for GNN models. However, the transformation from the original input feature to fair representation may distort the original information in the input features and cause a detriment in the utility performance of the model (Kang et al., 2017). Because it is computationally difficult to enforce Lipschitz constraint, Yurochkin and Sun (Yurochkin and Sun, 2018) propose an in-process method with a lifted constraint and Petersen et al. (Petersen et al., 2019) propose a post-processing method with Laplacian smoothing. In this work, we compare with REDRESS (Kang et al., 2017) and adapt PFR (Zhou et al., 2017) and InFoRM (Kang et al., 2017) to work with GNN models. We do not compare with Dwork et al. (Zhou et al., 2017) because their contribution is mainly conceptual and it was not included as baseline in previous works (Kang et al., 2017; Zhang et al., 2018; Zhang et al., 2018).

## 3. Proposed Method - Gfairhint

### Problem Formulation

The generic definition of individual fairness is _individuals who are similar should have similar outcomes_(Zhou et al., 2017). We can formulate the similarity between individuals with an **oracle similarity matrix**\(\mathcal{S}_{F}\), where the value of \((i,j)\)-th entry is the similarity between the node \(i\) and \(j\). We follow the same setting from previous works (Kang et al., 2017; Zhang et al., 2018; Zhang et al., 2018), where the oracle similarity matrix \(\mathcal{S}_{F}\) is given apriori (annotated by external experts or calculated by input features). Depending on the definition of similarity measure, the entry of \(\mathcal{S}_{F}\) could be continuous or binary. For graph data and GNN models, we denote the **outcome similarity matrix** as \(\mathcal{S}_{\hat{Y}}\) with the predicted outcome \(\hat{Y}\) from GNN model, where the \((i,j)\)-th entry is the similarity between the embeddings \(z_{i}\) and \(z_{j}\) of the nodes \(i\) and \(j\) from the last model layer.

Inspired by the individual fairness definition from the previous work (Zhou et al., 2017; Zhang et al., 2018), we define the fair condition of GNN model as follows:

Definition 1.: _Let \(x_{i}\) and \(x_{j}\) be two nodes in a graph. The output of the model \(f(x_{i})\) and \(f(x_{j})\) are **individually fair** w.r.t. to the node similarity measure \(S\) and output distance measure \(D\) if the following condition holds._

\[D(f(x_{i}),f(x_{j}))\leq\frac{\epsilon}{S(x_{i},x_{j})}\forall x,y=1,..,n \tag{1}\]

_where \(\epsilon>0\) is a constant for fairness tolerance and \(0<S(x_{i},x_{j})<1\) if \(i\neq j\). \(n\) is the number of nodes in a graph. We define \(\frac{\epsilon}{S(x_{i},x_{j})}\) as the **fairness bound**._

With this definition, our goal to promote the individual fairness can be achieved by narrowing the difference between \(\mathcal{S}_{F}\) and \(\mathcal{S}_{\hat{Y}}\).

### Overall Structure

To achieve a good balance between utility and fairness, GNN models need to utilize input information from both sides. We first apply a representation learning method to extract the fairness information from the input and add the learned fairness representation to the original GNN model to promote individual fairness. Our proposed **GFairHint** framework, as shown in Figure 1, consists of three steps. First (Section 3.3), we construct an unweighted fairness graph, \(\mathcal{G}_{F}\), with the same set of nodes in the original input graph. The undirected edges of \(\mathcal{G}_{F}\) represent that two nodes have a high similarity value in \(\mathcal{S}_{F}\). Next (Section 3.4), we obtain the individual fairness hint through a representation learning method that learns fairness representations for the nodes in \(\mathcal{G}_{F}\). Specifically, the representation learning model predicts whether two nodes in \(\mathcal{G}_{F}\) have an edge through a GNN link prediction model whose final hidden layer output is used as the fairness hint. Finally (Section 3.5), we concatenate the node fairness hint with the learned node embedding of the GNN for original tasks and use the joint embedding for further training.

### Construction of Fairness Graph

To extract fairness information for each individual via a link-prediction-based representation learning method, we first construct a fairness graph \(\mathcal{G}_{F}\) based on the apriori oracle similarity matrix \(\mathcal{S}_{F}\). Note that \(\mathcal{S}_{F}\) can be given by incorporating various types of data sources and our fairness graph construction complies with the data sources of \(\mathcal{S}_{F}\). Here, we show two commonly utilized data sources, i.e., external annotation and input feature.

Oracle Similarity Matrix based on External AnnotationConstructing \(\mathcal{S}_{F}\) is straightforward when external pairwise judgments are available on whether two individuals \(i,j\) should be treated similarly given a specific task (Zhou et al., 2017). The entry \(\mathcal{S}_{I}^{F}\) in \(\mathcal{S}_{F}\) is \(1\) when individual \(i\) and \(j\) are labeled as similar, and \(0\) otherwise. In this case, \(\mathcal{S}_{F}\) is the adjacency matrix for the fairness graph \(\mathcal{G}_{F}\). An alternative
type of judgments is to map individuals into binary equivalence classes. A pair of individuals \(i,j\) is linked in the fairness graph, \(\mathcal{G}_{F}\), only if they belong to the same class (Kal
We extract the fairness hint \(v_{i}^{f}\) using the learned fairness representation learning model before training the original GNN model, and the fairness hint is fixed during the optimization process. For node classification tasks, we apply _softmax_ to the final node embedding \(z_{i}\in\mathbb{R}^{c}\) to obtain the predictions where \(c\) is the number of classes and apply \(\mathcal{L}_{utility}\) to optimize the parameters in the backbone GNN models. We empirically show that the fairness hint is fully involved in models' decision-making process via gradient-based interpretability method in Section 5.2 and the MLP layers can learn to balance between utility and fairness hint when we integrate the loss function with fairness regularization which we introduce next.

### Extension: Integration with Fairness Loss

Our GFairHint framework can simply utilize the utility loss \(\mathcal{L}_{utility}\) as the final loss. Moreover, we can further encourage the model to learn fairness information by adding the "fairness" loss into the final loss function. Previous fairness promotion methods have designed various fairness loss to enforce a good balance between utility and fairness (Garfinkel, 2015; Garfinkel, 2015), which are complementary to our fairness hint. In our work, we integrate the ranking-based fairness loss in REDRESS (Garfinkel, 2015) to our framework GFairHint.

The objective of the loss is to minimize the difference between the oracle similarity matrix \(\mathcal{S}_{F}\) and the outcome similarity matrix \(\mathcal{S}_{\hat{\mathcal{V}}}\). For each node, when \(\mathcal{S}_{F}\) is based on input features, we can obtain two top-k ranking lists derived from \(\mathcal{S}_{F}\) and \(\mathcal{S}_{\hat{\mathcal{V}}}\) respectively. The fairness loss of node \(i\) can be calculated as

\[\hat{P}_{j,m}(i)=\frac{1}{1-e^{(\hat{z}_{i,j}-\hat{z}_{i,m})}} \tag{6}\] \[P_{j,m}(i)=\begin{cases}1&\text{if }s_{i,j}>s_{i,m}\\ 0.5&\text{if }s_{i,j}=s_{i,m}\\ 0&\text{if }s_{i,j}<s_{i,m}\end{cases}\] (7) \[\mathcal{L}_{j,m}(i)=-P_{j,m}\log\hat{P}_{j,m}-(1-P_{j,m})(1-\log \hat{P}_{j,m})\] (8) \[\mathcal{L}_{fairness}(i)=\sum_{j,m}\mathcal{L}_{j,m}(i)|\Delta _{\hat{\text{G}}\in\hat{\text{k}}}|_{j,m} \tag{5}\]

where \(z_{\hat{\text{G}}\in\hat{\text{k}}}(\cdot,\cdot)\) is the similarity metric (NDCG or ERR (Garfinkel, 2015; Garfinkel, 2015)) between the two top-k ranking lists and node \(j\) or \(m\) are selected from the ranking lists. Specifically, \(s_{i,j}\) and \(\hat{s}_{i,j}\) are the entries from \(\mathcal{S}_{F}\) and \(\mathcal{S}_{\hat{\mathcal{V}}}\) respectively. However, when \(\mathcal{S}_{F}\) is from external annotations where only pairwise judgements are available, the entries \(S_{ij}^{F}\) in \(\mathcal{S}_{F}\) are binary. Therefore, it is meaningless to calculate the ranking-based loss of the constructed fairness graph \(\mathcal{G}_{F}\) in this case. In this work, to apply REDRESS related models to fairness datasets with external annotations, we made an adjustment by replacing \(\mathcal{S}_{F}\) from external annotations with the one derived from input features. Details will be discussed in Section 4.2.

The total fairness loss \(\mathcal{L}_{fairness}\) is then calculated as the sum of the fairness loss on each node. The final objective is to combine the fairness loss and the utility loss.

\[\mathcal{L}_{total}=\mathcal{L}_{utility}+\gamma\mathcal{L}_{ fairness} \tag{9}\]

where \(\gamma\) is an adjustable hyperparameter. By changing the value of \(\gamma\), we can control the weight of fairness and utility during training according to the task requirement. The details discussion is in Section 5.3.

## 4. Experiment Setup

### Dataset Collection

In our work, we focus on the node classification task to evaluate the fairness promotion ability of our proposed GFairHint. We collect five real-word datasets to assess the model performance in multiple domains (see statistics in Table 1). Coauthor-CS (CS) and Coauthor-Phy (Phy) are two co-authorship network datasets (Zhu et al., 2017), where each node represents an author, and they connect the nodes if two authors have published a paper together. ACM is a dataset of citation network (Zhu et al., 2017), where each node represents a paper, and the edge denotes the citation relationship. These three datasets (ACM, CS, Phy) are also applied in the REDRESS paper as the experiment benchmarks (Garfinkel, 2015). In addition, we use another citation network OGRN-ArXiv dataset (Krizhevsky et al., 2015), which is several magnitude orders larger than the ACM, CS, and Phy datasets.

For ACM, CS, and Phy datasets, we follow the preprocessing procedure in REDRESS and use the bag-of-word model to transform the title and abstract of a paper as its node feature. We use the pre-split training, validation, and test datasets from the REDRESS paper1. Regarding the ArXiv dataset, we directly use the processed 128-dimensional feature vectors from a pre-trained skip-gram model (Zhu et al., 2017). We then follow the train/validation/test splits from the official release of Open Graph Benchmark (OGB).2 We repeat the experiments for each model setting twice, because the split of the dataset is fixed by the previous work. Since the citation and co-authorship network datasets do not contained human annotated similarity, we follow previous work (Garfinkel, 2015) and use the cosine similarities between node features as the entries in \(\mathcal{S}_{F}\). 3

Footnote 1: [https://github.com/yushundong/REDRESS/tree/main/node#20classification/data](https://github.com/yushundong/REDRESS/tree/main/node#20classification/data)

Footnote 2: [https://gob.stanford.edu/docs/node/prop/](https://gob.stanford.edu/docs/node/prop/)

Footnote 3: We also tested with euclidean distance. We do not develop or evaluate different individual fairness measures but rather show that our method is compatible with various existing measures.

Additionally, we curate a dataset with external human annotation on individual fairness similarity in the binary setting to demonstrate our framework's compatibility when external annotation is available. The Crime dataset (Zhu et al., 2017) consists of socioeconomic, demographic and law / police data records for neighborhoods in the US. We follow Lahoti et al. (Lahoti et al., 2017) for most of the preprocessing and introduce additional information on the geometric adjacency of the country4 to form a graph-structured dataset. The nodes are the neighborhoods, and the edges indicate that two neighborhoods reside in the same country or adjacent countries. We have a binary outcome variable for whether the neighborhood is violent and consider other data records as input features. For the similarity measure of individual fairness, we also follow (Lahoti et al., 2017) to collect human reviews on Crime & Safety for neighborhoods in the U.S. from a neighborhood review website, Niche.5 The judgments are given in the form of 1-star to 5-star ratings by current and past residents of these neighborhoods. We then use aggregated mean ratings to construct the fairness graph as described in Section 3.3, where the neighborhoods with the same rating level (e.g., 5 stars) are linked in the fairness graph. As there is no predefined train/validation/test split, we randomly split the dataset and repeat five times for each model setting.
### Methods for Comparison

To show the superiority of our proposed framework, we implement the vanilla GNN models and previous SOTA as baseline models with sensitivity analysis. Note that some existing works (Beng et al., 2019; Liu et al., 2020) for group fairness promotion cannot be used as baseline models because our work focuses on individual fairness. We explain these **baseline methods** below.

**Vanilla**: Vanilla denotes the vanilla GNN models without any individual fairness promotion method.

**PFR**: PFR (Zhou et al., 2019) learns fair representation and can be considered as a pre-processing method for GNN models, and we adapt the implementation of PFR6 to GNN models by transforming the input features to the fairness representations and use the transformed representations as node features in vanilla GNN models. The PFR method requires computing the Laplacian matrix and the eigenvectors of the oracle similarity matrix \(\mathcal{S}_{F}\)(Zhou et al., 2019), so we have to explicitly store \(\mathcal{S}_{F}\) in memory. The experiment of PFR on the Arxiv dataset with 90,941 nodes will cause out-of-memory issues. Since Dong et al. (2018) has already shown REDRESS's priority over PFR on the ACM, Coauthor-Phy and Coauthor-CS datasets, we only experiment with PFR on the Crime dataset.

Footnote 6: [https://github.com/plahoti-Igtm/PairwiseFairRepresentations](https://github.com/plahoti-Igtm/PairwiseFairRepresentations)

**InFoRM**: InFoRM (Liu et al., 2020) is a framework to promote individual fairness in conventional machine learning tasks on graphs. Similarly, due to the previous work's experiments showing the better performance of REDRESS than InFoRM on ACM, CS and Phy datasets, we only experiment with InFoRM on the Crime and Arxiv datasets by combining its fairness promotion loss with the utility loss of the GNN models.

**REDRESS**: REDRESS is the previous SOTA framework for individual fairness promotion in GNN models (Deng et al., 2019). They formulate the conventional individual fairness promotion into a ranking-based optimization problem. By optimizing the ranking-based loss \(\mathcal{L}_{fairness}\) and the utility loss \(\mathcal{L}_{utility}\), REDRESS can achieve the goal of maximization of utility and promotion of individual fairness simultaneously. For the implementation of its framework and ranking-based loss, we adapt the codebase released by the authors7.

Footnote 7: [https://github.com/yushundong/REDRESS](https://github.com/yushundong/REDRESS)

**REDRESS + MLP** As mentioned in Section 3.5, after concatenating the utility node embeddings and fairness hint, our proposed framework GFairHint uses additional MLP layers to process the concatenated embeddings, which increases the model complexity. This variant of REDRESS adds the MLP layers with the same size after the GNN models along with the original REDRESS loss for a fair comparison. We use the output of MLP layers from this variation model to calculate the loss and optimize the parameters in the GNN and MLP layers. REDRESS + MLP model can show the effectiveness of GFairHint without interference of the model complexity confounder.

**Our methods:** We study the performance of GFairHint and examine its effectiveness with the combination of REDRESS loss:

**GFairHint**: We combine the fairness hint with the utility node embedding and only use the \(\mathcal{L}_{utility}\) loss to update the model parameters.

**GFairHint + REDRESS**: As described in Section 3.6, we combine the ranking-based loss \(\mathcal{L}_{fairness}\) in REDRESS with the utility loss \(\mathcal{L}_{utility}\) to further encourage the models to learn individual fairness. The only difference between this method and REDRESS + MLP is that GFairHint + REDRESS incorporates the fairness hint.

We note that for the Crime dataset, since the entries of oracle similarity matrix \(\mathcal{S}_{F}\) are binary (0-1), we cannot calculate the ranking-based loss of the constructed fairness graph \(\mathcal{G}_{F}\). Therefore, we adapt the REDRESS-related methods to calculate the ranking-based loss based on input feature similarity. As a result, for the Crime dataset, REDRESS and REDRESS + MLP do not have any access to the fairness information (i.e., fairness graph \(\mathcal{G}_{F}\)), while GFairHint + REDRESS get fairness information only through the fairness hint but not the ranking-based loss.

### Evaluation Metric

We evaluate both the _utility performance_ and the _fairness performance_ of the models. A desired model should achieve the highest fairness performance without sacrificing much, if it must, utility performance. For utility performance, we follow previous work (Deng et al., 2019) and the official OGB leaderboard to use classification accuracy (ACC). As for fairness performance, we use different evaluation metrics in accordance with two different settings of the oracle similarity, i.e., continuous and binary.

For the co-authorship and citation networks (ACM, ArXiv, CS, Phy), the oracle similarity matrix is continuous, where the entry is the input feature similarity. We follow previous work (Deng et al., 2019) to utilize ERR@K (Chen et al., 2019) and NDCG@K (Liu et al., 2020), where \(k\) is the same as the threshold of to determine the edge existence in fairness graph in Section 3.3 for \(\mathcal{S}_{F}\) based on input features. Higher ERR and NDCG values represent better individual fairness promotion. These two metrics measure the similarity between the ranking lists obtained from the oracle similarity matrix \(\mathcal{S}_{F}\) and the outcome similarity matrix \(\mathcal{S}_{\tilde{y}}\). In the following experiments, we choose \(k=10\) and report the results of NDCG@10 and ERR@10 for all models for comparison. We also provide the sensitivity analysis of difference choices of \(k\) values on the model performance in Appendix F.

For the Crime dataset, where the entry of the oracle similarity matrix is binary, we follow (Zhou et al., 2019) and use **Consistency** as the evaluation metric. It measures the consistency of outcomes between individuals who are similar to each other. The formal definition regarding a fairness similarity matrix \(S_{F}\) is

\[Consistency=1-\frac{\Sigma_{i}\Sigma_{j}|y_{i}-\hat{y_{j}}|\cdot S_{ij}^{F}}{ \Sigma_{i}\Sigma_{j}S_{ij}^{F}}\qquad\forall i\neq j.\]

\begin{table}
\begin{tabular}{l l c c c} \hline \hline \(\mathcal{S}_{F}\) Type & Dataset & \# Nodes & \# Features & \# Classes \\ \hline \multirow{3}{*}{Input Feature} & Coauthor-CS & 916 & 6,805 & 15 \\  & Coauthor-Phy & 1,724 & 8,415 & 5 \\  & ACM & 824 & 8,337 & 9 \\  & ArXiv & 90,941 & 128 & 40 \\ \hline External & Crime & 1,994 & 122 & 2 \\ \hline \hline \end{tabular}
\end{table}
Table 1. Statistics of the datasets used for node classification experiments. # Nodes stands for the number of nodes for training dataset.
Consistency measures how the predictions align with the oracle fairness similarity \(S_{F}\). ERR and NDCG measure a similar concept from a ranking perspective.

### Implementation Details

All the backbone GNN models and our auxiliary link prediction models are implemented in the Pytorch framework, especially the package PyTorch Geometric (Kingmare et al., 2014; Krizhevsky et al., 2014). For each of our five datasets, we experiment with two backbone GNN settings, small and large model size. For the small model size setting, the number of layers and the dimension of the embeddings in the hidden layers are set to 2 and 16. For the big model size setting, we set these two numbers to 10 and 128 respectively. For all experiments, we fix the values of the hyperparameters \(\gamma\) and \(k\) at 1 and 10 as suggested in the previous work (Krizhevsky et al., 2014), where \(\gamma\) is the weighting factor when integrating with the ranking-based loss (Equation 9) and \(k\) is the number of top entries used to calculate the ranking loss and fairness evaluation metrics NDCG@K and ERR@K.

Our learned fairness hint for each node contains individual fairness information, and we expect that the fairness hint helps promote fairness in various GNN models. We choose three popular GNN models: GCN (Krizhevsky et al., 2014), GraphSAGE (Krizhevsky et al., 2014), and Graph Attention Networks (GAT) (Krizhevsky et al., 2014) to demonstrate the compatibility of GFAirHint with various GNN model designs. Note that we do not need to re-learn the fairness hint for the same dataset even if the backbone models have changed. Other details of the implementation are in Appendix A.

## 5. Experimental Results

We aim to answer the questions in the following sections. Section 5.1: How well can GFAirHint and its extension method promote individual fairness compared with other baselines with different similarity measures? Section 5.2: How important are the fairness

\begin{table}
\begin{tabular}{l l l c c c} \hline \hline
**Dataset** & **Backbone** & **Method** & **Fairness: NDCG@10** & **Fairness: ERR@10** & **Utility: ACC** \\ \hline \multirow{8}{*}{GCN} & & Vanilla & 75.01 \(\pm\) 0.19 & 91.45 \(\pm\) 0.01 & 70.19 \(\pm\) 0.02 \\  & & InFoRM & 74.66 \(\pm\) 0.05 & 91.47 \(\pm\) 0.09 & 68.86 \(\pm\) 0.68 \\  & & REDRESS & 75.25 \(\pm\) 0.71 & 91.57 \(\pm\) 0.10 & 68.65 \(\pm\) 1.13 \\  & & REDRESS + MLP & 75.01 \(\pm\) 0.26 & 91.47 \(\pm\) 0.01 & 69.85 \(\pm\) 0.27 \\  & & GfairHint & 81.93 \(\pm\) 0.27 & 94.28 \(\pm\) 0.09 & **70.62 \(\pm\) 0.91** \\  & & GFAirHint + REDRESS & **85.48 \(\pm\) 3.47** & **95.22 \(\pm\) 0.80** & 69.80 \(\pm\) 0.47 \\ \cline{2-6}  & & Vanilla & 75.47 \(\pm\) 0.37 & 91.71 \(\pm\) 0.13 & **70.44 \(\pm\) 0.69** \\  & & InFoRM & 74.82 \(\pm\) 0.18 & 91.60 \(\pm\) 0.14 & 69.20 \(\pm\) 1.45 \\ ArXiv & SAGE & REDRESS & 75.51 \(\pm\) 0.73 & 91.58 \(\pm\) 0.16 & 69.34 \(\pm\) 0.55 \\  & & REDRESS + MLP & 74.45 \(\pm\) 0.53 & 91.40 \(\pm\) 0.09 & 69.75 \(\pm\) 0.18 \\  & & GFAirHint & 81.92 \(\pm\) 0.17 & 94.34 \(\pm\) 0.04 & 70.40 \(\pm\) 0.34 \\  & & GaiFirHint + REDRESS & **85.32 \(\pm\) 3.45** & **95.22 \(\pm\) 0.79** & 68.98 \(\pm\) 0.25 \\ \cline{2-6}  & & Vanilla & 76.64 \(\pm\) 0.21 & 92.04 \(\pm\) 0.09 & 70.86 \(\pm\) 0.64 \\  & & InFoRM & 76.37 \(\pm\) 0.04 & 91.92 \(\pm\) 0.11 & 69.73 \(\pm\) 0.40 \\  & & REDRESS & 77.46 \(\pm\) 0.09 & 92.18 \(\pm\) 0.02 & 69.74 \(\pm\) 0.19 \\  & & REDRESS + MLP & 76.23 \(\pm\) 0.98 & 91.86 \(\pm\) 0.25 & 70.45 \(\pm\) 0.30 \\  & & GFAirHint & 81.80 \(\pm\) 0.14 & 94.20 \(\pm\) 0.04 & **71.06 \(\pm\) 0.45** \\  & & GFAirHint + REDRESS & **85.49 \(\pm\) 4.73** & **95.20 \(\pm\) 1.19** & 69.89 \(\pm\) 0.11 \\ \hline \multirow{8}{*}{GCN} & & Vanilla & 33.90 \(\pm\) 0.73 & 76.99 \(\pm\) 0.08 & **70.78 \(\pm\) 0.18** \\  & & REDRESS & 34.82 \(\pm\) 0.80 & 76.98 \(\pm\) 0.13 & 70.15 \(\pm\) 1.77 \\ \cline{2-6}  & & REDRESS + MLP & 30.93 \(\pm\) 0.46 & 76.66 \(\pm\) 0.19 & 70.64 \(\pm\) 1.89 \\  & & GFAirHint & 35.12 \(\pm\) 0.34 & 76.39 \(\pm\) 0.52 & 69.70 \(\pm\) 0.77 \\  & & GFAirHint + REDRESS & **35.58 \(\pm\) 2.85** & **77.00 \(\pm\) 0.16** & 69.77 \(\pm\) 0.95 \\ \cline{2-6}  & & Vanilla & 30.55 \(\pm\) 1.86 & 76.63 \(\pm\) 0.18 & 69.26 \(\pm\) 0.60 \\  & & REDRESS & 31.58 \(\pm\) 1.06 & 76.68 \(\pm\) 0.04 & 68.23 \(\pm\) 0.97 \\ ACM & SAGE & REDRESS + MLP & 28.73 \(\pm\) 0.12 & 76.29 \(\pm\) 0.78 & **69.32 \(\pm\) 0.44** \\  & & GFAirHint & 36.12 \(\pm\) 0.72 & 76.39 \(\pm\) 0.25 & 69.24 \(\pm\) 0.11 \\  & & GFAirHint + REDRESS & **37.83 \(\pm\) 3.78** & **77.37 \(\pm\) 0.55** & 67.52 \(\pm\) 0.16 \\ \cline{2-6}  & & Vanilla & 34.62 \(\pm\) 0.28 & 77.00 \(\pm\) 0.20 & **71.14 \(\pm\) 1.14** \\  & & REDRESS & 34.83 \(\pm\) 0.45 & 77.40 \(\pm\) 0.28 & 70.49 \(\pm\) 0.87 \\ GAT & REDRESS + MLP & 32.82 \(\pm\) 1.36 & 76.22 \(\pm\) 0.09 & 69.87 \(\pm\) 0.70 \\  & & GFAirHint & 37.52 \(\pm\) 0.54 & 76.79 \(\pm\) 0.27 & 71.04 \(\pm\) 0.74 \\  & & GFAirHint + REDRESS & **43.01 \(\pm\) 2.02** & **77.50 \(\pm\) 0.36** & 69.65 \(\pm\) 0.88 \\ \hline \hline \end{tabular}
\end{table}
Table 2. Node classification results for citation datasets: ArXiv and ACM with cosine similarity as similarity measures. The number of layers and the hidden layer dimension of the backbone GNN models are 10 and 128 respectively. All values are reported in percentage. The first-best performance is marked in bold, and the second-best performance is underlined.
hint for GNN models when making predictions? Section 5.3: How does the fairness constraint hyperparemter \(\gamma\) influence the performance of GFairHint? Section 5.4: How computationally efficient is GFairHint and how does it compare with other baselines?

### Effectiveness of GFairHint

In this section, we present the results of our proposed methods and baselines on collected datasets. For each dataset, we choose model hyperparameter settings with better average utility between two large and small model size settings as described in Section 4.4.

_Oracle Similarity Matrix based on Input Feature_. For the citation and coauthorship networks, we use the input feature similarity as the entry of the oracle similarity matrix to construct the fairness graph. The results are shown in Table 2 for the citation networks (i.e., Arxiv and ACM) and Table 5 Appendix B for the co-authorship networks (i.e., Phy and CS). 8 For utility performance, our proposed GFairHint and GFairHint + REDRESS models achieve comparable results with vanilla backbone GNN models and other fairness promotion models. Indeed, in 5 cases out of 6 experiments for co-authorship datasets, our models achieve the best utility performance. Regarding the fairness performance, our proposed models achieve the best fairness performance in nearly all settings, except for the ERR value of the GNN models on the Phy dataset. We also achieve comparable ERR values with the SoTA REDRESS model for the Phy dataset. Moreover, our proposed GairHint also behave better than the REDRESS model in the most scenarios of the citation network dataset. InFoRM method does not improve the fairness performance on the Arxiv dataset, which is consistent with the results on the other academic networks from the REDRESS paper (Fan et al., 2017).

Footnote 8: We follow previous works (Fan et al., 2017; Chen et al., 2017) to use cosine similarity as the oracle similarity measure. We additionally include the results and discussion of using similarity measure based on Euclidean distance in Appendix B.

_Oracle Similarity Matrix based on External Annotation_. For the Crime dataset, we construct a fairness graph from collected human expert judgements. We show the results in Table 3. We find that for all three backbone GNN models, GFairHint and GFairHint + REDRESS are the best two methods in the fairness (Consistency) evaluation. This is as expected since Vanilla and REDRESS models do not have access to fairness information in this setting, and InFoRM and PFR methods are not specifically designed for GNN models. GFairHint and GfairHint + REDRESS have close performance in consistency, demonstrating the effectiveness of fairness hint even when it is used alone. Although GFairHint + REDRESS has slightly better results, it has much higher computational cost because of the ranking-based loss. Detailed discussion on computation efficiency is in Section 5.4. For GCN and GAT backbone models, our proposed methods achieve the best two results in utility (accuracy) evaluation.

_Summary._ We systematically evaluate the utility performance and fairness performance in \(5\times 3=15\) combinations of dataset and backbone model, which results in 15 utility comparisons and 27 fairness comparisons.9 Our proposed GFairHint + REDRESS method achieved best fairness performance in almost all comparisons (\(24/27\)), while GFairHint performed second best in \(16/27\) of the comparisons when applied alone. These two methods also have comparable utility performance with the Vanilla model, as they ranked top two in \(12/15\) utility comparisons. Although GFairHint + REDRESS achieved better fairness performance than GFairHint in general, the gaps are small. GFairHint even ranked higher in \(6/15\) utility performance, especially for large dataset (\(3/3\)). These observations empirically show that GFairHint achieves a good balance between utility and fairness, and demonstrate that while GFairHint is better than previous work on individual fairness promotion in most cases, it is also complementary to other methods with fairness regularization loss and can further improve the performance.

Footnote 9: For the four academic networks with oracle similarity matrix based on input feature, we evaluated two fairness metrics, which leads to \((4\times 2+1)\times 3=27\) comparisons for fairness

### Importance of Fairness Hint

In Section 3.4, we prove that our learned fairness hints are individually fair and integrate the fairness hints into the training of backbone GNN models to achieve better fairness promotion. We further evaluate: _Does GNN backbone model utilize the concatenated fairness hints in the node label prediction?_

We answer this question by borrowing the idea of saliency map (Zhu et al., 2017) to demonstrate the relative importance of utility node embedding, \(u\), and fairness hints, \(v^{f}\), when making predictions. We calculate the gradient of the model output w.r.t. each dimension of the node embedding as the importance score for the dimension. We then average the importance score for utility node embedding and fairness hint as \(\text{Score}(u)\) and \(\text{Score}(v^{f})\) respectively. The details are shown in Appendix D.

\begin{table}
\begin{tabular}{l l c c} \hline \hline
**Backbone** & **Method** & **Consistency** & **Acc** \\ \hline \multirow{8}{*}{**GCN**} & Vanilla & \(54.80\pm 0.23\) & \(73.83\pm 0.34\) \\  & PFR & \(52.20\pm 0.55\) & \(71.53\pm 1.10\) \\  & InFoRM & \(56.84\pm 1.77\) & \(72.93\pm 0.96\) \\  & REDRESS & \(54.07\pm 0.96\) & \(73.98\pm 0.70\) \\  & REDRESS + MLP & \(53.06\pm 1.04\) & \(73.58\pm 1.80\) \\  & GFairHint & \(62.76\pm 2.74\) & \(75.44\pm 0.71\) \\  & GFairHint + REDRESS & \(\mathbf{63.61\pm 4.4}\) & \(\mathbf{75.54\pm 0.90}\) \\ \hline \multirow{8}{*}{**SAGE**} & Vanilla & \(62.09\pm 0.50\) & \(\mathbf{82.16\pm 0.33}\) \\  & PFR & \(56.75\pm 0.95\) & \(80.15\pm 0.67\) \\  & InFoRM & \(60.93\pm 2.59\) & \(79.05\pm 0.51\) \\ \cline{1-1}  & REDRESS & \(61.46\pm 1.91\) & \(82.11\pm 0.52\) \\ \cline{1-1}  & REDRESS + MLP & \(61.46\pm 1.36\) & \(81.35\pm 0.34\) \\ \cline{1-1}  & GFairHint & \(62.26\pm 0.98\) & \(80.60\pm 0.98\) \\ \cline{1-1}  & GFairHint + REDRESS & \(\mathbf{62.49\pm 4.86}\) & \(80.85\pm 1.21\) \\ \hline \multirow{8}{*}{**GAT**} & Vanilla & \(55.17\pm 0.81\) & \(73.68\pm 0.79\) \\ \cline{1-1}  & PFR & \(54.06\pm 1.20\) & \(73.83\pm 0.90\) \\ \cline{1-1}  & InFoRM & \(53.44\pm 2.24\) & \(71.38\pm 1.43\) \\ \cline{1-1}  & REDRESS & \(53.55\pm 1.15\) & \(72.88\pm 0.74\) \\ \cline{1-1}  & REDRESS + MLP & \(51.84\pm 0.42\) & \(72.08\pm 1.24\) \\ \cline{1-1}  & GFairHint & \(64.04\pm 2.74\) & \(\mathbf{75.34\pm 0.74}\) \\ \cline{1-1}  & GFairHint + REDRESS & \(\mathbf{65.30\pm 3.60}\) & \(74.94\pm 1.05\) \\ \hline \end{tabular}
\end{table}
Table 3. Node classification results on the Crime dataset. Consistency measures the fairness of the model. The number of layers and the hidden layer dimension of backbone GNN models are 2 and 16 respectively. All values are reported in percentage. Best results are in bold, and second-best results are underlined.
From Table 4, we observe that the magnitude of importance score of utility node embedding and fairness hint for our framework is comparable, which indicates that GNNs in our method actually apply the fairness hint to predict the node labels. Moreover, the values of \(\frac{\text{Score}(u)}{\text{Score}(u^{f})}\) for GFairHint + REDBRESS are lower than the ones for GFairHint, suggesting that the fairness hint becomes more important when integrated with fairness loss. This further demonstrates that GFairHint is a plug-and-play framework as the fairness hint can be effectively utilized by the previous SoTA fairness promotion method with fairness regularization.

### Trade-off between Fairness and Utility

GFairHint + REDBESS achieves the best fairness performance, where we integrate fairness hint with ranking-based loss. The value of the hyperparameter \(\gamma\) in Equation 9 controls the strength of the fairness constraint. There is a trade-off between utility and fairness when adjusting the \(\gamma\) value (Beng et al., 2015). To demonstrate the effectiveness of GFairHint, we perform experiments with multiple values of \(\gamma\) for the REDBESS and GFairHint + REDBESS models on the Arxiv dataset with GCN as the backbone GNN model. Figure 2 shows the trade-off between accuracy and fairness (NDCG@10) with varying values of \(\gamma\) for the REDBESS and GFairHint + REDBESS methods. The curves in the figure for REDBESS and GFairHint + REDBESS are generated by changing a range of fairness coefficients \(\gamma\) from 0.01 to 100 and computing the Pareto frontiers. We also further visualize the accuracy and NDCG@10 values for the vanilla and GFairHint models as two data points for reference.

With the value of \(\gamma\) being small (e.g., 0.001), REDBESS and GFairHint + REDBESS models behave similarly to the vanilla and GFairHint models respectively as expected. When increasing the value of \(\gamma\), we can observe fairness improvements for both REDBESS and the GFairHint + REDBESS models. This fairness improvement is more significant for the GFairHint + REDBESS model. We conjecture that little improvement for the REDBESS model is due to the vanishing gradient problem of deep GNN models (Chen et al., 2016), which may reduce the impact of fairness loss. GFairHint + REDBESS model is less impacted because it also directly learns from the fairness hint that is incorporated into the final GNN layers. We observe that with the same accuracy level, our proposed GFairHint + REDBESS model achieves a higher NDCG@10 value than the REDBESS model, demonstrating the effectiveness of the fairness hint.

We expect that the adjustment of the trade-off between fairness and utility can provide more flexibility in practical applications. For example, some tasks may pay more attention to fairness rather than utility.

### Efficiency Evaluation

In addition to fairness and utility results, we compare the efficiency of GFairHint models with other baseline models in terms of time complexity and empirical training time. The time complexity of training a \(l\)-layer GCN model is \(\mathcal{O}(ln+l|e|)\), where \(|e|\) is the edge number and \(n\) is the node number (Beng et al., 2015). During the training of GNN model, the ranking-based loss in REDBESS requires finding a list containing top-k similar nodes for each node and ranking the list. The additional complexity of REDBESS is \(\mathcal{O}(n\cdot\log(n)\cdot k)\)(Beng et al., 2015) and our additional time complexity is \(\mathcal{O}(n)\) since we only add two MLP layers when training GNN models

The additional cost introduced by the auxiliary link prediction task is small because the complexity is the same as the original node classification task and the learned fairness can be reused for other backbone GNN models on the same dataset, which reduces the marginal cost of this auxiliary task. Moreover, even if the fairness hint is only used once, the time required for training a link prediction GNN and a node classification GNN is significantly smaller than using the REDBESS framework. We empirically show the difference in training time in Figure 3 and the details in Appendix E. The results show that the additional cost of GFairHint is negligible compared to the Vanilla model. Therefore, the proposed GFairHint model is more scalable in practice when applied to large graph datasets.

## 6. Limitations and Future Work

One crucial question for individual fairness is the source of similarity measures. External annotation is often impractical, subjective, and potentially biased, and the input feature can be an incomplete and imperfect source. It requires comprehensive domain knowledge to develop the fairness similarity measure for a specific real-world

\begin{table}
\begin{tabular}{l l c c c} \hline \hline
**Dataset** & **Method** & **Score(\(o^{f}\))** & **Score(\(u\))** & \(\frac{\text{Score}(u)}{\text{Score}(u^{f})}\) \\ \hline \multirow{2}{*}{Arxiv} & GFairHint & 0.044 & 0.041 & 0.923 \\  & GFairHint+REDBESS & 0.051 & 0.034 & 0.677 \\ \hline \multirow{2}{*}{ACM} & GFairHint & 0.158 & 0.056 & 0.354 \\  & GFairHint+REDBESS & 0.245 & 0.045 & 0.184 \\ \hline \multirow{2}{*}{CS} & GFairHint & 0.157 & 0.164 & 1.050 \\  & GFairHint+REDBESS & 0.109 & 0.092 & 0.848 \\ \hline \multirow{2}{*}{Phy} & GFairHint & 0.169 & 0.182 & 1.073 \\  & GFairHint+REDBESS & 0.225 & 0.166 & 0.738 \\ \hline \multirow{2}{*}{Crime} & GFairHint & 0.065 & 0.228 & 3.536 \\  & GFairHint+REDBESS & 0.022 & 0.057 & 2.594 \\ \hline \hline \end{tabular}
\end{table}
Table 4. Average importance scores of utility node embedding and fairness hint for each dataset with GAT backbone model. We also report the ratio of average importance scores of two types of node embeddings.

Figure 2. Pareto frontiers of various methods on Arxiv dataset. Upper-right corner (high accuracy, high NDCG@10) is preferable. Our method outperforms baseline methods significantly in the trade-off between fairness and utility.
application. We note that our framework is compatible with different types of similarity measures as long as the construction of a fairness graph is viable. Moreover, there may be bias in the original input features, and we can have a sense of such bias by looking at the fairness evaluations of the vanilla models. However, it is unavoidable to use original information, as it is the only source of feature information available for making predictions. The intuition for promoting individual fairness is to use oracle individual fairness similarity to guide the model to utilize such fairness information, whereas in this paper we rely on the learned fairness hint. We acknowledge that there are works that debias the original information directly as pre-processing (Koshelev et al., 2019; Zhang et al., 2020), but they are not as empirically effective as the proposed method or the in-processing method (Koshelev et al., 2019) when applied along. Our method is also orthogonal to these pre-processing methods and is thus possible to integrate with them for better performance. Lastly, in this paper, we show the effectiveness of fairness hint with a simple concatenation strategy, and it is possible to develop more complex and better integration methods to utilize fairness hint, especially in compliance with the tasks and data formats at hand. We leave these directions for future work.

## 7. Conclusions

In this work, we propose **GFairHint**, a plug-and-play framework for promoting individual fairness in GNNs via fairness hint. Our method learns fairness hint through an auxiliary link prediction task on a constructed fairness graph. The fairness graph can be derived from both continuous and binary oracle similarity matrix, corresponding to two ways of obtaining similarity for individual fairness respectively, i.e., from input feature space and from external human annotations. We also integrate GFairHint with another complementary individual fairness promotion method, REDRESS. We conduct extensive empirical evaluations on node classification tasks to show the effectiveness of our proposed method in achieving good balance in utility and fairness, with much less computational cost.
