GFairHint: Improving Individual Fairness for Graph Neural Networks via Fairness Hint

The generic definition of individual fairness is individuals who are similar should have similar outcomes (Dwork et al., 2012). 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 (Dong et al., 2021; Kang et al., 2020; Lahoti et al., 2019), 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 (Dwork et al., 2012; Kang et al., 2020), we define the fair condition of GNN model as follows:

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}}$.

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.

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.

To incorporate the fairness information into the original GNN model, we learn fairness node representation with a separate GNN model using an auxiliary link prediction task on the fairness graph, $\mathcal{G}_{F}$. Similarly to masked language modeling in NLP to learn the contextual word embeddings by randomly masking words (Devlin et al., 2018), we expect that predicting whether two nodes share a “similarity” edge inside the fairness graph can yield a valid fairness hint. We provide a theoretical analysis of this expectation later.

We use Graph Convolutional Network (GCN) model (Kipf and Welling, 2016) with GCN layers for link prediction, i.e., predicting whether two nodes in $\mathcal{G}_{F}$ share an edge. The initial input node features of the link prediction model are the same as the features of the original task. For any node embedding $h_{i}^{l}$ (the embedding of node $i$ from the $l$th hidden layer), GCN layer combines the node embedding $h_{i}^{l}$ and other node embeddings from its neighbor node set $\mathcal{N}(i)$, which is formally denoted as

If setting the output of the last layer in the link prediction model for node $i$ and node $j$ as $v_{i}^{f}$ and $v_{j}^{f}$ respectively, we use the inner product and sigmoid function $\sigma(v_{i}^{f}\cdot v_{j}^{f})$ as the probability of node $i$ and node $j$ sharing an edge, as well as the similarity between the outcome. We use cross entropy loss to optimize the link prediction model.

We train this fairness representation learning model separately from the original task GNN model to avoid overfitting. We extract the output $v_{i}^{f}$ of the last layer for each node as the fairness hint, and the fairness hint is reusable for different backbone GNN models. As we show next, after training a link prediction model on the fairness graph, we can obtain individually fair fairness hints. When we feed the fairness hints to the original GNNs, the models can receive similar fairness hints for similar individuals and render similar outcomes.

Theoretical Analysis In our link prediction model, we use the inner product and sigmoid function as the similarity measure between the outcome and the cross entropy loss to optimize the GCN model, so the corresponding loss can be calculated as

where $y_{ij}$ is the label of the fairness edge existence and $P_{i}j$ is the probability of link existence between node $i$ and node $j$. Ideally, after optimizing the GNN model to minimize the cross entropy loss to 0, $P_{ij}$ should be 1 for two nodes connected by an edge and 0 for two nodes without any edge. We can then make an assumption that after the model training converges, $P_{ij}<\delta$ if $y_{ij}=0$ and $P_{ij}>1-\delta$ if $y_{ij}=1$, for any $i$ and $j$ where $\delta$ is a small number. Given the inner product as the similarity measure, we can define the distance function of model outputs as $D(v_{i}^{f},v_{j}^{f})=1-\sigma(v_{i}^{f}\cdot v_{j}^{f})$. The following conditions should hold.

With Definition 1 and Equation 4, we can deduce the following theorem.

We provide the proof and the justification of how the assumption $\epsilon>\delta$ is achievable in practice in Appendix C. The intuition behind this theorem is that, with the current representation learning setup, if nodes $i$ and $j$ share an edge in $\mathcal{G}_{F}$, the generated embeddings $v_{i}^{f}$ and $v_{j}^{f}$ from the link prediction model should be more similar than the other nodes without edges and thus similar nodes have similar fairness hints as the representations. Theorem 2 supports that our representation learning method encodes the fairness information of each node with the fairness hint. Next, we describe how to integrate the fairness hints with the learning of backbone GNN model for node classification tasks.

Our GFairHint framework is compatible with various GNN model architectures for the original tasks. The basic operations of each GNN layer are similar to the GCN operation in Equation (2), but the convolutional operations are replaced with other message-passing mechanisms for different GNN models. We train the chosen GNN backbone models with utility loss $\mathcal{L}_{utility}$ (i.e., cross entropy loss) and obtain the utility node embedding $u_{i}$ from the last GNN hidden layer. We then concatenate $u_{i}$ with the fairness hint $v_{i}^{f}$ to form a joint node embedding $[u_{i},v_{i}^{f}]$. We add two layers of multilayer perceptron (MLP) with weights $W_{1}$ and $W_{2}$ to encourage the model to learn both utility and fairness information from the joint node embeddings. The final embedding $z_{i}$ of the node $i$ can be calculated as

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.

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 (Dong et al., 2021; Petersen et al., 2021), which are complementary to our fairness hint. In our work, we integrate the ranking-based fairness loss in REDRESS (Dong et al., 2021) 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{Y}}$. 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{Y}}$ respectively. The fairness loss of node $i$ can be calculated as

where $z_{@k}(\cdot,\cdot)$ is the similarity metric (NDCG or ERR (Chapelle et al., 2009; Järvelin and Kekäläinen, 2002)) 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{Y}}$ respectively. However, when $\mathcal{S}_{F}$ is from external annotations where only pairwise judgements are available, the entries $S^{F}_{ij}$ 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.

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.

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 (Shchur et al., 2018), 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 (Tang et al., 2008), 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 (Dong et al., 2021). In addition, we use another citation network OGBN-ArXiv dataset (Hu et al., 2020a), 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 paper¹¹1https://github.com/yushundong/REDRESS/tree/main/node%20classification/data. Regarding the ArXiv dataset, we directly use the processed 128-dimensional feature vectors from a pre-trained skip-gram model (Mikolov et al., 2013). We then follow the train/validation/test splits from the official release of Open Graph Benchmark (OGB).²²2https://ogb.stanford.edu/docs/nodeprop/ 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 (Dong et al., 2021) and use the cosine similarities between node features as the entries in $\mathcal{S}_{F}$. ³³3We 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 (Redmond, 2009) consists of socioeconomic, demographic and law / police data records for neighborhoods in the US. We follow Lahoti et al. (2019) for most of the preprocessing and introduce additional information on the geometric adjacency of the county⁴⁴4https://pypi.org/project/county-adjacency/ to form a graph-structured dataset. The nodes are the neighborhoods, and the edges indicate that two neighborhoods reside in the same county or adjacent counties. 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., 2019) to collect human reviews on Crime $\&$ Safety for neighborhoods in the U.S. from a neighborhood review website, Niche.⁵⁵5http://niche.com 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.

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 (Bose and Hamilton, 2019; Rahman et al., 2019b) 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 (Lahoti et al., 2019) learns fair representation and can be considered as a pre-processing method for GNN models, and we adapt the implementation of PFR⁶⁶6https://github.com/plahoti-lgtm/PairwiseFairRepresentations 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}$ (Lahoti 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. (2021) 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.

InFoRM: InFoRM (Kang 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 (Dong et al., 2021). 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 authors⁷⁷7https://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.

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.

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 (Dong et al., 2021) 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 (Dong et al., 2021) to utilize ERR@K (Chapelle et al., 2009) and NDCG@K (Järvelin and Kekäläinen, 2002), 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}_{\hat{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 (Lahoti 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 measures how the predictions align with the oracle fairness similarity $S_{F}$. ERR and NDCG measure a similar concept from a ranking perspective.

All the backbone GNN models and our auxiliary link prediction models are implemented in the Pytorch framework, especially the package PyTorch Geometric (Paszke et al., 2017; Fey and Lenssen, 2019). 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 (Dong et al., 2021), 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 (Kipf and Welling, 2016), GraphSAGE (Hamilton et al., 2017), and Graph Attention Networks (GAT) (Veličković et al., 2017) to demonstrate the compatibility of GFairHint with various GNN model designs. Note that we do not need to relearn the fairness hint for the same dataset even if the backbone models have changed. Other details of the implementation are in Appendix A.

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.

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 (Simonyan et al., 2013) 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.

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}(v^{f})}$ for GFairHint + REDRESS 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.

GFairHint + REDRESS 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 (Dong et al., 2021). To demonstrate the effectiveness of GFairHint, we perform experiments with multiple values of $\gamma$ for the REDRESS and GFairHint + REDRESS 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 REDRESS and GFairHint + REDRESS methods. The curves in the figure for REDRESS and GFairHint + REDRESS 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$), REDRESS and GFairHint + REDRESS 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 REDRESS and the GFairHint + REDRESS models. This fairness improvement is more significant for the GFairHint + REDRESS model. We conjecture that little improvement for the REDRESS model is due to the vanishing gradient problem of deep GNN models (Demir et al., 2021), which may reduce the impact of fairness loss. GFairHint + REDRESS 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 + REDRESS model achieves a higher NDCG@10 value than the REDRESS 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.

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}(l\textperiodcentered n+l\textperiodcentered|e|)$, where $|e|$ is the edge number and $n$ is the node number (Blakely et al., 2021). During the training of GNN model, the ranking-based loss in REDRESS requires finding a list containing top-k similar nodes for each node and ranking the list. The additional complexity of REDRESS is $\mathcal{O}(n\cdot\log(n)\cdot k)$ (Dong et al., 2021) 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 REDRESS 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.