Disparity, Inequality, and Accuracy Tradeoffs in Graph Neural Networks
  for Node Classification
Graph neural networks (GNNs) are increasingly used in critical human
applications for predicting node labels in attributed graphs. Their ability to
aggregate features from nodes' neighbors for accurate classification also has
the capacity to exacerbate existing biases in data or to introduce new ones
towards members from protected demographic groups. Thus, it is imperative to
quantify how GNNs may be biased and to what extent their harmful effects may be
mitigated. To this end, we propose two new GNN-agnostic interventions namely,
(i) PFR-AX which decreases the separability between nodes in protected and
non-protected groups, and (ii) PostProcess which updates model predictions
based on a blackbox policy to minimize differences between error rates across
demographic groups. Through a large set of experiments on four datasets, we
frame the efficacies of our approaches (and three variants) in terms of their
algorithmic fairness-accuracy tradeoff and benchmark our results against three
strong baseline interventions on three state-of-the-art GNN models. Our results
show that no single intervention offers a universally optimal tradeoff, but
PFR-AX and PostProcess provide granular control and improve model confidence
when correctly predicting positive outcomes for nodes in protected groups.
Arpit Merchant, Carlos Castillo
# Disparity, Inequality, and Accuracy Tradeoffs in Graph Neural Networks for Node Classification

###### Abstract.

Graph neural networks (GNNs) are increasingly used in critical human applications for predicting node labels in attributed graphs. Their ability to aggregate features from nodes' neighbors for accurate classification also has the capacity to exacerbate existing biases in data or to introduce new ones towards members from protected demographic groups. Thus, it is imperative to quantify how GNNs may be biased and to what extent their harmful effects may be mitigated. To this end, we propose two new GNN-agnostic interventions namely, (i) PFR-AX which decreases the separability between nodes in protected and non-protected groups, and (ii) PostProcess which updates model predictions based on a blackbox policy to minimize differences between error rates across demographic groups. Through a large set of experiments on four datasets, we frame the efficacies of our approaches (and three variants) in terms of their algorithmic fairness-accuracy tradeoff and benchmark our results against three strong baseline interventions on three state-of-the-art GNN models. Our results show that no single intervention offers a universally optimal tradeoff, but PFR-AX and PostProcess provide granular control and improve model confidence when correctly predicting positive outcomes for nodes in protected groups.

2023

Graph Neural Networks; Node Classification; Algorithmic Fairness +
Footnote †: [leftmargin=*]This work was partially completed while Arpit Merchant was visiting Universitat Pompeu Fabra, Barcelona, Spain.

+
Footnote †: [leftmargin=*]This work was partially completed while Arpit Merchant was visiting Universitat Pompeu Fabra, Barcelona, Spain.

+
Footnote †: [leftmargin=*]This work was partially completed while Arpit Merchant was visiting Universitat Pompeu Fabra, Barcelona, Spain.

+
Footnote †: [leftmargin=*]This work was partially completed while Arpit Merchant was visiting Universitat Pompeu Fabra, Barcelona, Spain.

+
Footnote †: [leftmargin=*]This work was partially completed while Arpit Merchant was visiting Universitat Pompeu Fabra, Barcelona, Spain.

+
Footnote †: [leftmargin=*]This work was partially completed while Arpit Merchant was visiting Universitat Pompeu Fabra, Barcelona, Spain.

+
Footnote †: [leftmargin=*]This work was partially completed while Arpit Merchant was visiting Universitat Pompeu Fabra, Barcelona, Spain.

+
Footnote †: [leftmargin=*]This work was partially completed while Arpit Merchant was visiting Universitat Pompeu Fabra, Barcelona, Spain.

+
Footnote †: [leftmargin=*]This work was partially completed while Arpit Merchant was visiting Universitat Pompeu Fabra, Barcelona, Spain.

## 1. Introduction

Classification on attributed graphs involves inferring labels for nodes in the test set given a training set of labels along with attributes and adjacency information for all the nodes. To address this task, Graph Neural Networks (or GNNs, for short) have exploded in popularity since they effectively combine attributes and adjacency to build a unified node representation which can be used downstream as a feature vector (Han et al., 2017; Karim et al., 2017). GNNs have found applications in a variety of high-risk application domains (as defined, e.g., in the proposed AI Act for Europe of April 20221), including credit risk applications (Kal
unfairness (Bogor et al., 2016), GUIDE uses a group-equality informed individual fairness criteria (Srivastava et al., 2017)). Second, dataset properties, training criteria, hyperparameter tuning procedures, and sometimes, even low-level elements of an implementation such as linked libraries are known to significantly influence the efficiency and effectiveness of GNNs on node classification (Krizhevsky et al., 2014; Krizhevsky et al., 2014). Third, while algorithmic discrimination may be reduced at the expense of accuracy (Krizhevsky et al., 2014), specific improvements and trade-offs depend on application contexts (Krizhevsky et al., 2014), and need to be evaluated to understand what kinds of alternatives may offer improvements over current approaches. Our goal is to address these limitations by focusing on the following questions:

1. How do we meaningfully benchmark and analyze the trade-off between algorithmic fairness and accuracy of interventions on GNNs across different graphs?
2. Is there room for improving the fairness/accuracy tradeoff, and if so, how?

Our Contributions.We categorize interventions designed to reduce algorithmic discrimination in terms of their loci in the machine learning pipeline: (a) pre-processing, before training, (b) in-processing, during learning, and (c) post-processing, during inference. Using a standardized methodological setup, we seek to maximally preserve accuracy while improving algorithmic fairness. To this end, we introduce two new, unsupervised (independent of ground-truth labels), model-agnostic (independent of the underlying GNN architecture) interventions; PFR-AX that debiases data prior to training, and PostProcess that debiases model outputs after training (before issuing final predictions).

In PFR-AX, we first use the PFR method (Krizhevsky et al., 2014) to transform node attributes to better capture data-driven similarity for operationalizing individual fairness. Then, we construct a DeepWalk embedding (Krizhevsky et al., 2014) of the graph, compute its PFR transformation, and reconstruct a graph from the debiased embedding using a method we call EmbeddingReverser. To our knowledge, this is a novel application of a previously known method with suitable augmentations.

In PostProcess, we randomly select a small fraction, referred to as \(\gamma\), of nodes from the minority demographic for whom the model has predicted a negative outcome and update the prediction to a positive outcome. This black-box policy aims to ensure that error rates of a model are similar across demographic groups. This is a simple and natural post-processing strategy which, to the best of our knowledge, has not been studied in the literature on GNNs.

We conduct extensive experiments to evaluate the efficacies of interventions grouped by their aforementioned loci. To measure accuracy, we use _AUC-ROC_; to measure algorithmic fairness, we use _disparity_ and _inequality_ (cf. Section 3). We compare the accuracy-fairness tradeoff for PFR-AX and PostProcess (plus three additional variants) against three powerful baseline interventions (two for pre-training, one for in-training) on three widely used GNN models namely, GCN, GraphSAGE, and GIN (Gin et al., 2017). Our experiments are performed on two semi-synthetic and two real-world datasets with varying levels of edge homophily with respect to labels and sensitive attributes, which is a key driver of accuracy and algorithmic fairness in the studied scenarios. We design ablation studies to measure the effect of the components of PFR-AX and the sensitivity of PostProcess to the \(\gamma\) parameter. Finally, we analyze the impact of interventions on model confidence. Our main findings are summarized below:

* No single intervention offers universally optimal tradeoff across models and datasets.
* PFR-AX and PostProcess provide granular control over the accuracy-fairness tradeoff compared to baselines. Further, they serve to improve model confidence in correctly predicting positive outcomes for nodes in protected groups.
* PFR-A and PFR-X that debias only adjacency and only attributes respectively, offer steeper tradeoffs than PFR-AX which debiases both.
* When imbalance between protected and non-protected groups and model bias are both large, small values of \(\gamma\) offer large benefits to PostProcess.

## 2. Related Work

Legal doctrines such as GDPR (in Europe), the Civil Rights Act (in the US), or IPC Section 153A (in India) restrict decision-making on the basis of protected characteristics such as nationality, gender, caste (Krizhevsky et al., 2014). While _direct discrimination_, i.e., when an outcome directly depends on a protected characteristic, may be qualitatively reversed, addressing _indirect discrimination_, i.e., discrimination brought by apparently neutral provisions, requires that we define concrete, quantifiable metrics in the case of machine learning (ML) that can be then be optimized for (Krizhevsky et al., 2014). Numerous notions of algorithmic fairness have been proposed and studied (Krizhevsky et al., 2014). Two widely used definitions include the _separation criteria_, which requires that some of the ratios of correct/incorrect positive/negative outcomes across groups are equal, and the _independence criterion_, which state that outcomes should be completely independent from the protected characteristic (Bogor et al., 2016).

Algorithmic Fairness-Accuracy Tradeoffs.However, including fairness constraints often results in classifiers having lower accuracy than those aimed solely at maximizing accuracy. Traditional ML literature (Krizhevsky et al., 2014; Krizhevsky et al., 2014) has extensively studied the inherent tension that exists between technical definitions of fairness and accuracy: Corbett-Davies et al. (Corbett-Davies et al., 2016) theoretically analyze the cost of enforcing disparate impact on the efficacy of decision rules; Lipton et al. (Lipton et al., 2017) explore how correlations between sensitive and nonsensitive features induces within-class discrimination; Fish et al. (Fish et al., 2018) study the resilience of model performance to random bias in data. In turn, characterizing these tradeoffs has influenced the design of mitigation strategies and benchmarking of their utility. Algorithmic interventions such as reweighting training samples (Fish et al., 2018), regularizing training objectives to dissociate outcomes from protected attributes (Krizhevsky et al., 2014), and adversarially perturbing learned representations to remove sensitive information (Krizhevsky et al., 2014) are framed by their ability to reduce bias without significantly compromising accuracy.

Algorithmic Fairness in GNNs.The aforementioned approaches are not directly applicable for graph data due to the availability of adjacency information and the structural and linking bias it may contain. GNNs, given their message-passing architectures, are particularly susceptible to exacerbating this bias. This has prompted attention towards mitigation strategies for GNNs. For instance, at the
pre-training phase, REDFESS (Beng et al., 2017) seeks to promote individual fairness for the ranking task, and at the in-training phase, FairGNN (Beng et al., 2017) estimates missing protected attribute values for nodes using a GCN-estimator for adversarial debiasing and GUIDE (Srivastava et al., 2017) proposes a novel GNN model for a new group-equality preserving individual fairness metric. We do not compare against these since they are designed for a different task than ours, operate in different settings altogether, and since FairGNN (in particular) exhibits a limited circular dependency on using vanilla GNN for a sensitive task to overcome limitations of a different GNN for classification. We refer the reader to Dai et al. (Dai et al., 2017) for a recent survey. More relevant to our task, EDITS (Dai et al., 2017) reduces attribute and structural bias using a Wasserstein metric and so we use it as a baseline for comparison. At the in-training phase, NIFTY (Beng et al., 2017) promotes a model-agnostic fair training framework for any GNN using Lipschitz enhanced message-passing. However, an explicit fairness-accuracy tradeoff analysis is lacking from literature which, along with methodological differences, makes it difficult to benchmark the comparative utilities of these approaches. Therefore, we include these as baselines. We frame our study in the context of such an analysis and design one pre-training and one post-training intervention that offer different, but useful tradeoffs.

## 3. Problem Setup

GraphsLet \(\mathcal{G}=(\mathcal{V},\mathcal{E})\) be an unweighted, undirected graph where \(\mathcal{V}\) is a set of \(n\) nodes and \(\mathcal{E}\) is a set of \(m\) edges. Denote \(\mathbf{A}=[a_{uv}]\in\{0,1\}^{n\times n}\) as its binary adjacency matrix where each element \(a_{uv}\) indicates the presence or absence of an edge between nodes \(u\) and \(v\). Define \(\mathbf{D}=\operatorname{diag}\left(\delta_{1},\delta_{2},\ldots,\delta_{n}\right)\) to be a diagonal degree matrix where \(\delta_{u}=\sum_{v}a_{uv}\). Let each node \(u\) in \(\mathcal{G}\) be associated with one binary sensitive attribute variable \(s_{u}\) indicating membership in a protected demographic group along with \(d-1\) additional real or integer-valued attributes. Together, in matrix form, we denote node attributes as \(\mathbf{X}\in\mathbb{R}^{n\times d}\). Lastly, \(\forall u\in\mathcal{V}\), its binary, ground-truth, categorical label is depicted as \(\mathbf{y}_{u}\).

Graph Neural NetworksTypically, GNNs comprise of multiple, stacked graph filtering and non-linear activation layers that leverage \(\mathbf{X}\) and \(\mathbf{A}\) to learn joint node representations (see, e.g., Kipf and Welling (Kipf and Welling, 2015)). Such a GNN with \(L\) layers captures the \(L\)-hop neighborhood information around nodes. For each \(v\in\mathcal{V}\) and \(l\in[L]\), let \(\mathbf{h}_{v}^{(l)}\) denote the representation of node \(v\) at the \(l\)-th GNN layer. In general, \(\mathbf{h}_{v}^{(l)}\) is formulated via message-passing as follows:

\[\mathbf{h}_{v}^{(l)}=\textsc{CB}^{(l)}\left(\mathbf{h}_{v}^{(l-1)},\textsc{ AGG}^{(l-1)}\left(\left\{\mathbf{h}_{v}^{(l-1)}:u\in\mathcal{N}(v)\right\} \right)\right) \tag{1}\]

where \(\mathcal{N}(v)\) is the neighborhood of \(v\), \(\mathbf{h}_{v}^{(l-1)}\) is the representation of \(v\) at the \((l-1)\)-th layer, AGG is an aggregation operator that accepts an arbitrary number of inputs, i.e., messages from neighbors, and CB is a function governing how nodes update their representations at the \(l\)-th layer. At the input layer, \(\mathbf{h}_{v}^{(0)}\) is simply the node attribute \(\mathbf{x}_{v}\in\mathbf{X}\) and \(\mathbf{h}_{v}^{(L)}\) is the final representation. Finally, applying the softmax activation function on \(\mathbf{h}_{v}^{(L)}\) and evaluating cross-entropy error over labeled examples, we can obtain predictions for unknown labels \(\hat{\mathbf{y}}_{v}\). In this paper, we use AUC-ROC and F1-scores (thresholded at 0) to measure GNN accuracy.

Algorithmic FairnessWe measure the algorithmic fairness of a GNN model using two metrics. First, _Statistical Disparity_ (\(\Delta_{\text{SP}}\)), based on the _independence criterion_, captures the difference between the positive prediction rates between members in the protected and non-protected groups (Dai et al., 2017). Formally, for a set of predicted labels \(\hat{\mathbf{Y}}\):

\[\Delta_{\text{SP}}=\left|\text{Pr}\left[\hat{\mathbf{Y}}=1|\mathbf{s}=1|- \text{Pr}\left[\hat{\mathbf{Y}}=1|\mathbf{s}=0\right]\right.\right| \tag{2}\]

Second, _Inequal Opportunity_ (\(\Delta_{\text{EO}}\)), which is one _separation criterion_, measures the similarity of the true positive rate of a model across groups (Dai et al., 2017). Formally:

\[\Delta_{\text{EO}}=\left|\text{Pr}\left[\hat{\mathbf{Y}}=1|\mathbf{s}=1, \mathbf{Y}=1\right]-\text{Pr}\left[\hat{\mathbf{Y}}=1|\mathbf{s}=0,\mathbf{Y}= 1\right]\right. \tag{3}\]

Equation (3) compares the probability of a sample with a positive ground-truth label being assigned a positive prediction across sensitive and non-sensitive groups. In the following sections, we refer to \(\Delta_{\text{SP}}\) as _disparity_ and \(\Delta_{\text{EO}}\) as _inequality_ to emphasize that lower values are better since they indicate similar rates.

Having defined the various elements in our setting, we formally state our task below:

Problem 1 (Algorithmically Fair Node Classification).: _Given a graph \(\mathcal{G}\) as an adjacency matrix \(\mathbf{A}\), node features \(\mathbf{X}\) including sensitive attributes \(\mathbf{s}\), and labels \(\mathbf{Y}_{V}\) for a subset of nodes \(V\subset\mathcal{V}\), debias GNNs such that their predicted labels \(\mathbf{Y}_{\mathcal{V}\setminus V}\) are maximally accurate while having low \(\Delta_{\text{SP}}\) and \(\Delta_{\text{EO}}\)._

## 4. Algorithms

In this section, we propose two algorithms for Problem 1: PFR-AX (pre-training) and PostProcess (post-training).

### Pfr-Ax

Our motivation for a data debiasing intervention arises from recent results showing that GNNs have a tendency to exacerbate homophily (Srivastava et al., 2017). Final node representations obtained from GNNs homogenize attributes via Laplacian smoothing based on adjacency. This has contributed to their success in terms of classification accuracy. However, it has also led to inconsistent results for nodes in the protected class when their membership status is enhanced in their representations due to message-passing (Dai et al., 2017; Dai et al., 2017), particularly in cases of high homophily. Lahoti et al. (Lahoti et al., 2018) design PFR to transform attributes to learn new representations that retain as much of the original data as possible while mapping equally deserving individuals as closely as possible. The key benefit offered by PFR is that it obfuscates protected group membership by reducing their separability from points in the non-protected group. Therefore, we directly adapt PFR for graph data to debias attributes and adjacency. Algorithm 1 presents the pseudocode for PFR-AX.

Debiasing AttributesIn order to transform attributes \(\mathbf{X}\) using PFR, we build two matrices. The first, denoted by \(W^{X}\), is an adjacency matrix corresponding to a \(k\)-nearest neighbor graph over \(\mathbf{X}\) (not including \(\mathbf{s}\)) and is given as:

\[W^{X}_{uv}=\begin{cases}\exp\left(\frac{-\|\mathbf{x}_{u}-\mathbf{x}_{v}\|^{2} }{t}\right),\text{ if }u\in N_{k}\left(v\right)\text{ or }v\in N_{k}\left(u\right)\\ 0,\text{ otherwise}\end{cases} \tag{4}\]
where \(t\) is a scaling hyperparameter and \(N_{k}\left(v\right)\) is the set of \(k\) nearest neighbors of \(v\) in Euclidean space. We first normalize \(\mathbf{X}\) using Min-Max scaling to ensure that all attributes contribute equally and then compute \(W^{X}\) as per Equation 4. The second matrix, denoted by \(W^{F}\), is the adjacency matrix of a between-group quantile graph that ranks nodes within protected and non-protected groups separately based on certain pre-selected variables and connects similarly ranked nodes. In the original paper, Lahoti et al. (2019) use proprietary decile scores obtained from Northpointe for creating rankings. However, in the absence of such scores for our data, we use one directly relevant attribute for the task at hand. For instance, in the case of a credit risk application, we define rankings based on the loan amount requested. Formally, this matrix is given as:

\[W^{F}_{uw}=\begin{cases}1,\text{ if }u\in X^{P}_{s_{u}}\text{ and }v\in X^{P}_{s_{u}},\ s_{u}\neq s_{v}\\ 0,\text{ otherwise}\end{cases} \tag{5}\]

where \(X^{P}_{s}\) denotes the subset of nodes with sensitive attribute value \(s\) whose scores lie in the \(p\)-th quantile. Higher number of quantiles leads a sparser \(W^{F}\). Thus, \(W^{F}\) is a multipartite fairness graph that seeks to build connections between nodes with different sensitive attributes based on similarity of their characteristics even if they are not adjacent in the original graph. Finally, a new representation of \(\mathbf{X}\), denoted as \(\tilde{\mathbf{X}}\), is computed by solving the following problem (Krishnan and Krishnan, 2019):

\[\begin{split}\text{minimize}_{\tilde{X}}&(1-\alpha) \sum_{u,v}^{n}\|\tilde{x}_{u}-\tilde{x}_{v}\|^{2}W^{X}_{uw}\\ &+\alpha\sum_{u,v}^{n}\|\tilde{x}_{u}-\tilde{x}_{v}\|^{2}W^{F}_{ u0}\\ \text{s.t.}&\tilde{X}^{\top}\tilde{X}=\mathbb{I}\end{split} \tag{6}\]

where \(\alpha\) controls the influence of \(W^{X}\) and \(W^{F}\) on \(\tilde{\mathbf{X}}\).

_Debiasing Adjacency._ To reduce linking bias from \(\mathbf{A}\), we apply a three-step process. First, we compute an unsupervised node embedding of the graph using a popular matrix factorization approach named DeepWalk (Krishnan and Krishnan, 2019). Formally, this is computed as follows:

\[\mathbf{U}=\log\left(\text{vol}\left(\mathcal{G}\right)\left(\frac{1}{C}\sum _{c=1}^{C}\left(\mathbf{D}^{-1}\mathbf{A}\right)^{c}\right)\mathbf{D}^{-1} \right)-\log b \tag{7}\]

where \(\text{vol}\left(\mathcal{G}\right)=2m/n\) is the volume of the graph, \(C\) represents the length of the random walk, and \(b\) is a hyperparameter controlling the number of negative samples. Second, using the same aforementioned procedure for debiasing \(\mathbf{X}\), we apply PFR on U. Third, we design a new algorithm to invert this debiased embedding to reconstruct a graph with increased connectivity between nodes in protected and non-protected groups. This algorithm, which we refer to as EmbeddingReverser, proceeds as follows. We initialize an empty graph of \(n\) nodes and locate for each node \(u\), its \(\delta_{u}\) closest neighbors in the embedding space denoted as \(N_{\delta_{u}}\left(u\right)\) where \(\delta_{u}\) is the degree of \(u\) in the original graph. Starting from the first node (say) \(v\), for every \(w\in N_{\delta_{u}}\left(v\right)\), we check if \(v\) is present in \(w\)'s \(\delta_{w}\) closest neighbors. If so, we add an edge between \(v\) and \(w\) and increment counters corresponding to the current degrees for \(v\) and \(w\). We also increment a global counter maintaining the number edges added so far. If the current degree for any node (say) \(u\) reaches \(\delta_{u}\), we mark that node as completed and remove it from future consideration. This continues either for \(T_{\text{SC}}\) rounds where each round iterates over all nodes or until \(m\) edges have been added. Thus, we seek to maximally preserve the original degree distribution.

### PostProcess

_Model Predictions._ Let \(\mathcal{M}\) be a GNN model trained on a set of nodes \(V\in\mathcal{V}\). Let \(V^{\prime}=\mathcal{V}\setminus V\) represent nodes in the test set and let \(\mathbf{s}_{V^{\prime}}\) be their sensitive attribute values. For any \(u\in V^{\prime}\), denote \(r\left(u\right)\in\mathbb{R}\) as the original output (logit) score capturing the uncalibrated confidence of \(\mathcal{M}\). In our binary classification setting, we threshold \(r\left(\cdot\right)\) at \(0\) and predict a positive outcome for \(u\), i.e. \(\tilde{\mathbf{y}}_{u}=1\), if \(r\left(u\right)\geq 0\). Otherwise, we predict a negative outcome. Denote \(\tilde{\mathbf{Y}}_{V^{\prime}}\) as the set of labels predicted by \(\mathcal{M}\).

_Do-No-Harm Policy._ Next, we present our model-agnostic post-training intervention called PostProcess which operates in an unsupervised fashion independent of ground-truth labels. Different from prior interventions, especially Wei et al. (2019), PostProcess seeks to relabel model predictions following a _do-no-harm policy_, in which protected nodes with a positive outcome are never relabeled to a negative outcome. We audit \(\hat{\mathbf{Y}}_{V^{\prime}}\) and \(\mathbf{s}_{V^{\prime}}\) to identify all the nodes in the test set belonging to the protected class (\(s=1\)) that have
been assigned a negative outcome (\(\hat{y}=0\)). Denote this set as S1-Y0 (and so on for S1-Y1, etc.). For a fixed parameter \(\gamma\in[0,1]\), we randomly select a \(\gamma\) fraction of nodes from S1-Y0 and change their predicted label to a positive outcome, i.e., \(\hat{y}=1\). Then, we update \(\mathcal{M}\)'s scores for these nodes to a sufficiently large (uncalibrated) positive value. That is, we post-process \(\mathcal{M}\) to be confident about its new predicted labels. Predictions for all other nodes in the test set remain unchanged. Algorithm 2 describes the pseudocode.

```
Input: Test set \(V^{\prime}\); Sensitive attribute values \(\mathbf{s}_{V^{\prime}}\); Model predictions \(\hat{\mathbf{Y}}_{V^{\prime}}\); Model output scores \(r\) (\(\cdot\)) for \(V^{\prime}\); Flip parameter \(\gamma\); confidence (uncalibrated) MAX-SCORE; Output: Updated model predictions \(\hat{\mathbf{Y}}_{V^{\prime}}\); Updated model output scores \(r\) (\(\cdot\)); \(\textsc{S1-Y0}\leftarrow\emptyset\) for\(u\)in\(V^{\prime}\)do if\(s_{u}=1\) and \(\hat{y}_{u}=0\)then \(\textsc{S1-Y0}\leftarrow\textsc{S1-Y0}\cup\{u\}\) endif endfor \(P\leftarrow\) Randomly select \(\gamma\) fraction of nodes from S1-Y0 for\(v\)in\(P\)do \(\hat{y}_{v}\gets 1\) \(r\) (\(v\)) \(\leftarrow\) MAX-SCORE endfor
```

**Algorithm 2**PostProcess

_Choice of \(\gamma\)._ Determining a useful value for \(\gamma\) depends on two factors: (i) imbalance in the test set with respect to the number of nodes in the protected class, and (ii) bias in \(\mathcal{M}\)'s predictions towards predicting negative outcomes. If imbalance and bias are large, small \(\gamma\) values may be sufficient to reduce disparity. If imbalance is low and bias is large, then large \(\gamma\) values may be required. Let \(\hat{n}_{\textsc{S1-Y1}}\) denote the number of nodes in S1-Y1, and similarly for S1-Y0, etc. Then, disparity (Equation 2) is rewritten as:

\[\Delta_{\textsc{SP}}=\left|\frac{\hat{n}_{\textsc{S1-Y1}}}{\hat{n}_{\textsc{S1- Y1}}+\hat{n}_{\textsc{S1-Y0}}}-\frac{\hat{n}_{\textsc{S0-Y1}}}{\hat{n}_{\textsc{S0-Y1}}+ \hat{n}_{\textsc{S0-Y1}}}\right|\]

Our do-no-harm policy reduces \(\hat{n}_{\textsc{S1-Y0}}\) and increases \(\hat{n}_{\textsc{S1-Y1}}\). \(\hat{n}_{\textsc{S1-Y1}}+\hat{n}_{\textsc{S1-Y0}}\) remains constant. Thus, the first term in the equation above increases while the second remains the same. If the difference between the first and second terms is small, then PostProcess will increase disparity. Conversely, if the difference is large, then PostProcess will reduce disparity. If \(\hat{n}_{\textsc{S1-Y1}}>>\hat{n}_{\textsc{S1-Y0}}\), then PostProcess will have marginal impact on disparity. The effect on \(\Delta_{\textsc{EO}}\) follows equivalently, but may not be correlated with \(\Delta_{\textsc{SP}}\).

Note, the impact of \(\gamma\) on accuracy cannot be determined due to the unavailability of ground-truth label information during this phase. So, in Section 5.3, we empirically analyze the impact of \(\gamma\) on accuracy, averaged over \(T\) trials for smoothening.

## 5. Experiments

In this section, we describe the datasets and the methodology used in our experimental study and report our findings.

### Datasets

We evaluate our interventions on four publicly-available datasets ranging in size from 1K to 67K nodes. For consistency, we binarize sensitive attributes (\(s\)) and labels in each dataset. \(s=1\) indicates membership in the protected class and 0 indicates membership in the non-protected class. Similarly, label values set to 1 indicate a positive outcome and 0 indicate a negative outcome. Table 1 presents a summary of dataset statistics.

_Semi-Synthetic Data._ German(Geman, 2017) consists of clients of a German bank where the task is to predict whether a client has good or bad risk independent of their _gender_. Credit(McCarthy et al., 2017) comprises of credit card users and the task is to predict whether a user will default on their payments. Here, _age_ is the sensitive attribute. Edges are constructed based on similarity between credit accounts (for German) and purchasing patterns (for Credit), following Agarwal et al. (Agarwal et al., 2017). We add an edge between two nodes if the similarity coefficient between their attribute vectors is larger than a pre-specified threshold. This threshold is set to 0.8 for German and 0.7 for Credit.

_Real-world Data._ In Penn94(Penn, 2007), nodes are Facebook users, edges indicate friendship, and the task is to predict the graduation year (Krishnan et al., 2017) independent of _gender_ (sensitive attribute). Pokec-z (Agarwal et al., 2017) is a social network of users from Slovakia where edges denote friendship, _region_ is a sensitive attribute, and labels indicate professions.

### Methodology

_Processing Datasets._Agarwal et al. (Agarwal et al., 2017) and Dong et al. (Dong et al., 2017) utilize a non-standardized method for creating dataset splits that does not include all nodes. Following convention, we create new stratified random splits such that the label imbalance in the original data is reflected in each of the training, validation, and test sets. For German, Credit, and Pokec-z, we use 60% of the dataset for training, 20% for validation, and the remaining 20% for testing. For Penn94, we use only 20% for training and validation (each) because we find that is sufficient for GNNs, with the remaining 60% used for testing. Additionally, we adapt the datasets for use by PFR as described previously (cf. Section 4.1). 3 For computing between-group quantile graphs, we choose Loan Amount, Maximum Bill Amount Over

\begin{table}
\begin{tabular}{l c c c c c c} \hline \hline \multirow{2}{*}{**Dataset**} & \multicolumn{3}{c}{**Size**} & \multicolumn{3}{c}{**Properties**} \\ \cline{2-7}  & \(|\mathcal{V}|\) & \(|\mathcal{E}|\) & \(s\) & \(l\) & \(h_{s}\) & \(h_{l}\) \\ \hline German & 1K & 21K & Gender & Good Risk & 0.81 & 0.60 \\ Credit & 30K & 1.42M & Age & No Default & 0.96 & 0.74 \\ Penn94 & 41K & 1.36M & Gender & Year & 0.52 & 0.78 \\ Pokec-z & 67K & 617K & Region & Profession & 0.95 & 0.74 \\ \hline \hline \end{tabular}
\end{table}
Table 1. Dataset Statistics: number of nodes (\(|\mathcal{V}|\)), number of edges (\(|\mathcal{E}|\)), sensitive attribute \(s\), label \(l\), sensitive attribute homophily2 (\(h_{s}\)), label homophily (\(h_{l}\)).
Last 6 Months, Spoken Language, and F6 as ranking variables for German, Credit, Porec-z, and Penn94 respectively.

InterventionsEach intervention in our study is benchmarked against the performance of three vanilla GNNs namely, GCN, GraphSAGE, and GIN, referred to as Original. We construct PFR-AX to debias \(\mathbf{X}\) and \(\mathbf{A}\) as per Section 4.1. For ablation, we consider two variants: (i) PFR-X that only applies PFR on \(\mathbf{X}\), (ii) PFR-A that applies only PFR on a DeepWalk embedding and reconstructs a graph using EmbeddingReverser.

We vary \(\gamma\) from 0.1 (1%) to 0.4 (40%) in increments of 0.1. For each \(\gamma\), we use the same hyperparameters that returned the maximum accuracy for vanilla GNNs and post-process their predictions as per Algorithm 2. For each seed and \(\gamma\), we randomly select \(\gamma\) fraction of nodes from the protected class with a predicted negative outcome and smoothen over 20 trials. We define heavy and light versions of PostProcess namely, (i) PostProcess+ and (ii) PostProcess-, in terms of \(\gamma\). PostProcess+ is defined at that value of \(\gamma\) where disparity is lowest compared to Original and PostProcess- is set halfway between the disparity of Original and PostProcess+.

We compare these with three baselines: (i) Unaware (that naively deletes the sensitive attribute column from \(\mathbf{X}\)), (ii) EDITS (Chen et al., 2018), and (iii) NIFTY (Chen et al., 2018). Previous studies do not consider Unaware which is a competitive baseline according to our results (see below).

TrainingWe set \(k=128\) dimensions for DeepWalk. Depending on the dataset and interventions, we allow models to train for 500, 1000, 1500, or 2000 epochs. As per convention, we report results for each model/intervention obtained after \(T\) epochs and averaged over 5 runs. This is different from previous studies such as NIFTY that train for (say) \(T\) epochs and report results for that model instance that has the best validation score from upto \(T\) epochs. This, combined with our stratified splits, is a key factor for observing materially different scores from those reported by the original authors. To ensure fair comparison, we tune hyperparameters for each intervention and model via a combination of manual grid search and Bayesian optimization using WandB (Chen et al., 2018). The goal of this hyperparameter optimization is to find that setting of hyperparameters that results in a model with a maximal AUC-ROC score while aiming to have lower disparity and equality scores than Original.

ImplementationWe implement our models and interventions in Python 3.7. We use SNAP's C++ implementation for DeepWalk. EDITS4 and NIFTY5 are adapted from their original implementations. Our experiments were conducted on a Linux machine with 32 cores, 100 GB RAM, and an V100 GPU. Our code is available at [https://github.com/arpidm/gnn_accuracy_fairness_tradeoff](https://github.com/arpidm/gnn_accuracy_fairness_tradeoff).

Footnote 4: [https://github.com/yushundong/EDITS](https://github.com/yushundong/EDITS) (retrieved April 2022)

Footnote 5: [https://github.com/chirng126/nify](https://github.com/chirng126/nify) (retrieved April 2022)
Since higher values of AUC-ROC and lower values of \(\Delta_{\text{SP}}\) and \(\Delta_{\text{EO}}\) are better, the optimal position is towards the bottom right in each plot (cf. RQ2). For ease of presentation, we defer full results for GIN and all interventions to Table 2 in Appendix A.

Across datasets, GraphSAGE and GIN are more accurate than GCN but GraphSAGE displays higher disparity and inequality while GIN displays lower. PFR-AX and PostProcess- offer better tradeoffs than other baselines for German and Credit across models. This translates to upto 70% and 80% lower disparity than Original at less than 5% and 1% decrease in accuracy on German, respectively. In comparison, NIFTY offers 60% lower disparity (2.18% vs. 5.16% on German) at a 4.22% reduction in AUC-ROC. The lack of correlation between decreases in disparity and inequality may be explained in part by the impossibility theorem showing that these two criteria cannot be optimized simultaneously Chouldechova (2018). In Penn94 and Pokec-z, PFR-A and PFR-X are more effective than PFR-AX (cf. Table 2). We caveat the use of PostProcess in these datasets because choosing nodes randomly displays unintended consequences in maintaining accuracy without promoting fairness. Unaware proves effective across models and is especially optimal for Pokec-z. EDITS proves a heavy intervention causing large reductions in accuracy for relatively small gains in disparity.

_Sensitivity to \(\gamma\)._ Figure 2 trades off AUC (X-axis), disparity (left Y-axis, red points), and inequality (right Y-axis, purple points) for GCN, GraphSAGE, and GIN on Credit as a function of \(\gamma\). Due to large label imbalance in Credit and small number of nodes with negative predicted outcomes from the protected class, varying \(\gamma\) by 1% translates to changing predictions for 7 nodes. PostProcess thus offers granular control. As \(\gamma\) increases, AUC-ROC decreases while \(\Delta_{\text{SP}}\) first reduces and then increases again. This inflection point indicates that the post-processing policy is overcorrecting in favour of the protected class resulting in disparity towards the non-protected class. Conversely, such improvements are absent in Pokec-z since vanilla GNNs themselves are inherently less biased.

_Runtime._ Figure 3 depicts the total computation time in seconds (on log-scale) for each intervention on the four datasets for GCN, GraphSAGE, and GIN. We observe similar trends for all three GNN models. As expected, the larger the dataset, the higher the runtime. Updating a model's predictions at inference time is inexpensive and the resulting overhead for PostProcess is thus negligible. The running time for PFR-AX increases significantly with increasing dataset size. The key bottlenecks are very eigenvalue decompositions for sparse, symmetric matrices in PFR requiring \(\mathcal{O}\left(n^{3}\right)\) time and constructing DeepWalk embeddings. For instance, in the case of Pokec-z, PFR required (on average) 47 minutes in our tests while EmbeddingReverser and GNN training required less than 5 minutes each. For comparison, NIFTY required approximately 22 minutes while EDITS did not complete due to memory overflow.

Figure 3. Runtime in seconds (log-scale) of various interventions on GCN, GraphSAGE, and GIN for German, Credit, Penn94, and Pokec-z increasing with dataset size. PostProcess is fastest because updating model inference is inexpensive.

Figure 2. AUC-ROC as a function of Disparity (red) and Inequality (purple) for varying levels of the \(\gamma\) parameter of PostProcess on the Credit dataset. Higher values of \(\gamma\) are depicted by larger marker shapes and darker colors and indicate heavier interventions. As \(\gamma\) increases, AUC-ROC always decreases and Equality increases. Disparity first decreases upto an inflection point and then increases indicating an over-correction towards the protected class.
_Model Confidence._ In Figure 4, we display the impact of fairness interventions on a model's confidence about its predictions, i.e., un-calibrated density (Y-axis), compared to its logit scores (X-axis) on the Credit dataset. The plots in the top, middle, and bottom rows corresponds to GCN, GraphSAGE, and GIN, respectively. Larger positive values imply higher confidence about predicting a positive outcome and larger negative values imply higher confidence for a negative outcome prediction. While there isn't a universal desired outcome, an intermediate goal for an intervention may be to ensure that a model is equally confident about _correctly_ predicting both positive and negative labels. Blue regions show normalized density of logit values for nodes in the protected class with a positive ground-truth label (S1-Y1) and green regions show the same for nodes in the protected class with a negative outcome as ground-truth. The dashed colored lines indicate density values for these groups of nodes for the Optional model. PostProcess and Unaware induce small changes to GNN's outputs while EDITS is significantly disruptive. PFR-AX nudges the original model's output for nodes in S1-Y1 away from 0 making it more confident about its positive (correct) predictions while NIFTY achieves the reverse.

## 6. Conclusion

We presented two interventions that intrinsically differ from existing methods: PFR-AX debiases data prior to training to connect similar nodes across protected and non-protected groups while seeking to preserve existing degree distributions; PostProcess updates model predictions to reduce error rates across protected user groups. We frame our study in the context of the tension between disparity, inequality, and accuracy and quantify the scope for improvements and show that our approaches offer intuitive control over this tradeoff. Given their model-agnostic nature, we motivate future analysis by combining multiple interventions at different loci in the learning pipeline.

###### Acknowledgements.

 This work has been partially supported by: Department of Research and Universities of the Government of Catalonia (SGR 00930), EU-funded projects "SoBigData++" (grant agreement 871042), "FINDHR" (grant agreement 101070212) and MCIN/AE1/10.13039/501100011033 under the Maria de Maeztu Units of Excellence Programme (CEX2021-001195-M). We also thank the reviewers for their useful comments.

Figure 4. Density of logit scores of GCN (first row), GraphSAGE (second row), and GIN (third row) after applying different algorithmic fairness interventions for users in the protected class in the Credit dataset. The vertical dashed (black) line depicts the threshold used for label prediction (positive scores indicate positive outcomes). The colored dashed curves indicate the density of output scores of Original PFR-AX and PostProcess- improve model confidence (density) for correctly predicting a positive label for users in the protected class.
## Appendix A Additional Experimental Results