Fair Graph Machine Learning under Adversarial Missingness Processes

## Abstract

Abstract Graph Neural Networks (GNNs) have achieved state-of-the-art results in many relevant tasks where decisions might disproportionately impact specific communities. However, existing work on fair GNNs often assumes that either sensitive attributes are fully observed or they are missing completely at random. We show that an adversarial missingness process can inadvertently disguise a fair model through the imputation, leading the model to overestimate the fairness of its predictions. We address this challenge by proposing Better Fair than Sorry (BFtS), a fair missing data imputation model for sensitive attributes. The key principle behind BFtS is that imputations should approximate the worst-case scenario for fairness—i.e. when optimizing fairness is the hardest. We implement this idea using a 3-player adversarial scheme where two adversaries collaborate against a GNN classifier, and the classifier minimizes the maximum bias. Experiments using synthetic and real datasets show that BFtS often achieves a better fairness × \times accuracy trade-off than existing alternatives under an adversarial missingness process.

## 1 Introduction

With the increasing popularity of machine learning in high-stakes decision-making, it has become a consensus that these models carry implicit biases, and these biases should be addressed to improve the fairness of algorithmic decisions ghallab2019responsible. The disparate treatment of such models towards African Americans and women has been illustrated in the well-documented COMPAS b1 and Apple credit card apple cases, respectively. While there has been extensive research on fair machine learning, the proposed solutions have mostly disregarded important challenges that arise in real-world settings. For instance, in many applications, data can be naturally modeled as graphs (or networks), representing different objects, their relationships, and attributes instead of as sequences or images.

Figure: (a) Missing values.
Refer to caption: x1.png

Another challenge for fair machine learning is the pervasiveness of missing data little2019statistical. This is particularly critical because fair algorithms often require knowledge of sensitive attributes that are more likely to be missing due to biases in the collection process or privacy concerns. As an example, the absence of data in census surveys and health surveys is correlated with sensitive attributes such as gender, age, race, etc. o2019potential; weber2021gender. Missing data is also a concern in networked data, especially when tracking the transmission of diseases ghani1998sampling.
As a result, many fair machine learning algorithms rely on imputation methods to handle missing data and mitigate associated biases. However, when the missingness mechanism is not random, standard imputation techniques can introduce systematic errors that propagate through the pipeline and compromise downstream fairness mansoor2022impact; jeong2022fairness.

This work investigates the impact of adversarial sensitive value missingness processes on fairness, where the pattern of missing sensitive data is structured to obscure true disparities. If the predictions from the imputation method fail to capture the true distribution of a sensitive attribute, any fairness-aware model trained on the imputed data is prone to inheriting the underlying true bias. More specifically, a key challenge arises when an adversarial missingness process makes the imputed dataset appear to be fair. In graphs, an adversary can exploit the graph structure to manipulate the imputed values and, as a consequence, the fairness-aware model. Prior work on the fairness of graph machine learning assumes sensitive values are Missing Completely At Random (MCAR). However, this assumption rarely holds in practice o2019potential; weber2021gender; ghani1998sampling; jeong2022fairness. Methods that overlook the adversarial missingness process risk producing misleading fairness guarantees w.r.t. the complete data.

Figure [1](https://arxiv.org/html/2311.01591v4#S1.F1) motivates our problem setting using a toy example. A machine learning algorithm is applied to decide whether individuals should or should not receive credit. Figure [1(a)](https://arxiv.org/html/2311.01591v4#S1.F1.sf1) shows both the gender and outcome for each individual. The genders of some samples are unknown in Figure [1(a)](https://arxiv.org/html/2311.01591v4#S1.F1.sf1), and the demographic parity ($\Delta DP$) considering only the observed values is $0.25$ ($\Delta DP$ is a bias metric described in Section [5](https://arxiv.org/html/2311.01591v4#S5)). We illustrate how different missing data imputations affect the fairness of credit decisions in Figures [1(b)](https://arxiv.org/html/2311.01591v4#S1.F1.sf2) and [1(c)](https://arxiv.org/html/2311.01591v4#S1.F1.sf3). A straightforward imputation is demonstrated in Figure [1(b)](https://arxiv.org/html/2311.01591v4#S1.F1.sf2), where the gender of the majority of neighbors is assigned to the missing attribute, resulting in a best-case scenario in terms of fairness with a $\Delta DP$ of $0.09$. However, in the worst-case scenario, shown in Figure [1(c)](https://arxiv.org/html/2311.01591v4#S1.F1.sf3), $\Delta DP$ is $0.47$. If an adversarial missingness process can induce the imputation model to generate the imputation from Figure [1(b)](https://arxiv.org/html/2311.01591v4#S1.F1.sf2) but the complete data is Figure [1(c)](https://arxiv.org/html/2311.01591v4#S1.F1.sf3), a fair model trained on the imputed data will still be biased w.r.t. the complete data.

To counter an adversarial missingness process for sensitive values on graphs, we propose Better Fair than Sorry (BFtS), a 3-player adversarial learning framework for missing sensitive value imputation based on Graph Neural Networks (GNNs).
Our experiments show that BFtS achieves a better accuracy $\times$ fairness trade-off than existing approaches, especially under adversarial missing sensitive values.

We summarize the contributions of this paper as follows: (1) We investigate theoretically and empirically the potential of an adversarial missingness process to bias a fair graph machine learning model; (2) We propose Better Fair than Sorry (BFtS), a novel 3-player adversarial learning framework for the imputation of missing sensitive data that produces worst-case imputed values for fair GNNs and is effective under adversarial missingness processes and even when sensitive attribute information is completely unavailable; and (3) We show empirically that BFtS achieves a better fairness $\times$ accuracy trade-off than the existing alternatives.

### 1.1 Related Work

Fairness in graph machine learning. We divide the work in this area into three main directions (pre-processing, extended objective functions, and adversarial learning). FairOT, FairDrop, FairSIN, EDITS, and Graphair are pre-processing techniques that remove the bias from the graph before training fairot; fairdrop; fairsin; edits; graphair.
Fairwalk, Crosswalk, Debayes, MONET, NIFTY, FairVGNN, PFR-AX, FairSAD, and FairGAE modify the objective function of GNNs to learn fair representations during training fairwalk; crosswalk; debayes; monet; agarwal2021towards; wang2022improving_short; merchant2023disparity; zhu2024fair; fan2021fair. CFC, FLIP, DKGE, and Debias train adversarial networks along with GNN for fair prediction cfc; cfc2; kg; zhang2018mitigating. However, different from our work, all these methods require fully observed sensitive attributes to incorporate fairness considerations.

Missing Data Imputation and fairness. Missing data can be imputed using unconditional mean, reconstruction, preferential attachment, autoencoders, etc. donders2006gentle; pereira2020reviewing; huisman2009imputation. The traditional procedure for handling missing data is independent imputation—i.e., to first impute the missing values and then solve the task rossi2021unreasonable; buck1960method. SAT is a matching-based GNN for graphs with missing attributes chen2020learning, but it does not account for fairness. Training a classifier from imputed data can amplify the bias of a machine learning model, as discussed in subramoniandiscrimination; zhang2021assessing; feng2023adapting; guha2024automated; martinez2019fairness; fricke2020missing; mansoor2022impact. Some studies try to generate fair feature imputations subramoniandiscrimination; feng2023adapting; jeong2022fairness; zhang2022fairness. However, as the approaches discussed earlier, these methods do not consider missing sensitive information and require full knowledge of the sensitive attributes for fairness intervention.

Fairness with missing sensitive attributes. These studies are the most related to ours. One extreme assumption is the complete unavailability of sensitive information. For instance, hashimoto2018fairness takes into account the worst-case distribution across a given group size, and lahoti2020fairness adversarially reweighs training samples to optimize the average loss. In chai2022self, a top $k$ average loss minimization scheme is applied for fairness. In zhao2022towards, the correlation between the predictions and other features associated with sensitive attributes is minimized. Other approaches to achieve fairness are class re-balancing yan2020fair and chai2022fairness using soft labels from an overfitted teacher model. However, in practice, some sensitive information is often available and can significantly improve fairness chai2022self. The above-mentioned models fail to utilize the accessible sensitive values. FairGNN fairgnn assumes limited sensitive information and learns a fair GNN by predicting the missing values with an independent imputation model. FairAC guo2023fair assumes that both node features and the sensitive attribute are missing for a subset of nodes, and utilizes only the observed sensitive attributes without applying any imputation. RNF du2021fairness generates proxy annotations for missing attributes using generalized cross-entropy zhang2018generalized. Similar to RNF, our approach (BFtS) handles completely or partially missing sensitive information. BFtS applies a 3-player scheme to minimize the maximum possible bias and outperforms FairGNN and RNF in terms of fairness $\times$ accuracy. Minimizing the maximum instead of the average risk, similar to our method, has been shown to achieve better guarantees shalev2016minimizing. A similar minmax approach has been applied to maximize the robustness and accuracy of uncertainty models lofberg2003minimax; lanckriet2002robust; chen2017robust; fauss2021minimax.
In nguyen2017dual; vandenhende2019three, a 3-player adversarial network is proposed to improve the classification and stability of adversarial learning.

Adversarial attacks on fairness. Recent work has investigated data poisoning as a means to adversarially degrade model fairness mehrabi2021exacerbating; solans2020poisoning. Some approaches, such as UnfairTrojan and TrojFair introduce backdoor attacks specifically aimed at reducing model fairness furth2024unfair; zheng2023trojfair. In the context of graph neural networks (GNNs), adversarial fairness attacks have predominantly focused on modifying graph topology. For instance, hussain2022adversarial; zhang2023adversarial alter the structure of the graph to compromise the fairness of GNN predictions. NIFA luo2024your attacks GNN fairness by injecting new nodes guided by an uncertainty-maximization and homophily-enhancement strategy. Similarly, FATE kang2023deceptive employs a bilevel optimization-based meta-learning framework to carry out poisoning attacks on GNNs. These existing approaches primarily target fairness through data poisoning, node injection, or structural perturbations. To the best of our knowledge, no prior work has explored attacks that can only manipulate the missingness process for sensitive attributes as a means to compromise model fairness.

## 2 Preliminaries

In this section, we formalize the setting considered in this paper and introduce the Graph Neural Network model, which is our base model for node classification. For simplicity, we only consider binary-sensitive attributes. By modifying the loss function in Eq. [2](https://arxiv.org/html/2311.01591v4#S4.E2) to categorical cross entropy and MSE, our work can be generalized for non-binary and continuous sensitive attributes, respectively.

### 2.1 Notation and Problem Definition

Let $\mathcal{G}=(\mathcal{V},\mathcal{E},\mathcal{X},\mathcal{S})$ be an undirected graph where $\mathcal{V}$ is the set of nodes, $\mathcal{E}\subseteq\mathcal{V}\times\mathcal{V}$ is the set of edges, $\mathcal{X}$ are node attributes, and $\mathcal{S}$ is the set of sensitive attributes. The matrix $A\in\mathbb{R}^{N\times N}$ is the adjacency matrix of $\mathcal{G}$ where $A_{uv}=1$ if there is an edge between $u$ and $v$ and $A_{uv}=0$, otherwise. We focus on the setting where sensitive attributes might be missing and only $\mathcal{V}_{S}\subseteq\mathcal{V}$ nodes include the information of the sensitive attribute $s_{v}$ for a node $v$. The sensitive attribute forms two groups, which are often called sensitive ($s_{v}=1$) and non-sensitive ($s_{v}=0$).

We consider the fair node classification task, where the goal is to learn a classifier $f_{C}$ to predict node labels $y_{v}\in\{0,1\}$ based on a training set $\mathcal{V}_{L}\subseteq\mathcal{V}$. Without loss of generality, we assume that the class $y=1$ is the desired one (e.g., receive credit or bail). Given a classification loss $\mathcal{L}_{C}$ and a fairness loss $\mathcal{L}_{A}$, the goal is to minimize their combination:

$$ $f_{C}^{*}=\arg\min_{f_{C}}\mathcal{L}_{C}(f_{C})+\alpha\mathcal{L}_{A}(f_{C})$ $$

Computing fairness loss $\mathcal{L}_{A}$ requires sensitive attributes $s_{v}$. The main challenge addressed in this paper is due to our assumption that sensitive attributes can be missing. In this scenario, one can apply an independent imputation model $s_{v}\approx f_{I}(v)$ to predict missing sensitive attributes before training the fair classifier. However, the fairness of the resulting classifier will be highly dependent on the accuracy of $f_{I}$, which is the key motivation for our work. Two of the models (or players) learned by our model are GNNs. The details about Graph Neural Networks are provided in Appendix A.

## 3 Introducing Bias via an Adversarial Missingness Process

Our work investigates the role of missing sensitive values in the fairness of graph machine learning. Datasets with prevalent missing values often require the application of a missing data imputation method before they can be processed by a fair machine learning model. In this section, we focus on how the missingness process (i.e., the process that generates missing values) can lead to (intended or unintended) biases in a fair model trained using the imputed data. More specifically, the missingness process can induce the fair model to underestimate the bias in the imputed data. As a consequence, the fair model applied to the imputed data can still be inadvertently biased w.r.t. the complete data.

The simplest missingness process for sensitive values is missing completely at random—i.e., the probability of a value being missing is independent of the data. However, in practical scenarios, missing values are rarely random o2019potential; weber2021gender; ghani1998sampling. We focus on the particular case where the missingness process is adversarial and unknown. We prove that manipulating the missingness process to induce bias optimally is computationally hard. However, we show empirically that a simple heuristic can effectively introduce bias to an independent imputation model that simply tries to maximize imputation accuracy. We formulate the problem for a given number of observed sensitive values $k$.

###### Definition 1 .

Adversarial Missingness for Minimizing Classification Bias (AMMCB): Given a graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$ with a feature matrix $\mathcal{X}$, hypothesis spaces $\Theta_{C}$ and $\Theta_{I}$ and a training dataset $\mathcal{V}_{L}$, select a set of nodes $\mathcal{V}_{S}^{*}\subset\mathcal{V}$ such that $|\mathcal{V}_{S}^{*}|=k$ as to minimize the fairness loss $\mathcal{L}_{A}$ of the optimal classifier $f_{C}^{*}\in\Theta_{C}$ when it is trained with sensitive values imputed from the optimal imputation model $f_{I}^{*}$ that itself is trained with $\mathcal{V}_{S}^{*}$.

AMMCB is a discrete tri-level optimization problem as $f_{I}^{*}$ depends on $\mathcal{V}_{S}^{*}$ and $f_{C}^{*}$ depends on $f_{I}^{*}$.
We note that by minimizing the bias loss $\mathcal{L}_{A}$, the adversary prevents the fair classifier from reducing the bias in its predictions w.r.t. the complete data. Moreover, AMMCB requires knowledge of the hypothesis spaces $\Theta_{C}$ and $\Theta_{I}$, which might not be accessible by the adversary in practice. It is still convenient to formalize AMMCB because it defines the ultimate goal of the adversary. However, instead of solving this problem, we focus on the following more tractable surrogate.

###### Definition 2 .

Adversarial Missingness for Minimizing the Bias in the Data (AMMBD): Given a graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$ with a feature matrix $\mathcal{X}$, a hypothesis space $\Theta_{I}$, and a training dataset $\mathcal{V}_{L}$, select $\mathcal{V}_{S}\subset\mathcal{V}$ such that $|\mathcal{V}_{S}|=k$ as to minimize the dataset bias generated by an imputation model $f_{I}^{*}\in\Theta$ over $\mathcal{V}_{L}$.

AMMBD does not depend on $\Theta_{C}$ and its objective is constrained to the training data. The relationship between AMMBD and AMMCB is due to generalization—i.e., the expectation that the bias in $\mathcal{V}_{L}$ will generalize to the predictions from $f_{C}$. However, we show that even AMMDB is NP-hard.

###### Theorem 1 .

The AMMBD problem is NP-hard.

See proof of Theorem [1](https://arxiv.org/html/2311.01591v4#Thmtheorem1) in Appendix A. The idea of our proof is to frame AMMBD as an adversarial version of active learning where the goal is to strategically minimize the accuracy of the model for certain nodes by selecting labels. More specifically, we apply a popular formulation of active learning as a coverage problem yehuda2022active; ren2021survey. The adversary will target nodes either (1) with sensitive attribute $s_{v}=1$ and in the undesired class $y_{v}=0$ or (2) with sensitive attribute $s_{v}=1$ and in the desired class $y_{v}=1$. Targeting these nodes will decrease the bias in the imputed data.

Theorem [1](https://arxiv.org/html/2311.01591v4#Thmtheorem1) can be interpreted as a positive result, as it shows that, in theory, a simpler surrogate of the adversary’s objective is hard to optimize. The best-known approximation for the minimum k-union problem chlamtavc2017minimizing used in our reduction is $O(n^{1/4+\epsilon})$, where $n$ is the number of sets, which is mapped to the size of the graph in our problem. This means that approximately $k/n^{1/4}$ nodes would have to be selected to achieve the optimal coverage for $k$ nodes. However, we show empirically that a simple heuristic based on node degrees often achieves good results for the problem when an independent imputation model $f_{I}$ based on a GNN is applied.

Heuristic for AMMBD: We generate missing values synthetically in our experiments. To simulate an adversarial missingness process, we select low-degree nodes to have missing values. This choice is based on previous work showing that low-degree nodes have lower prediction accuracy tang2020investigating; liu2023generalized; ju2024graphpatcher. To generate $k$ nodes with missing sensitive data, we choose the $k$ nodes with the lowest degree.

To see the impact of adversarial missingness, we compare the imputation of adversarial missingness and random missingness.
We show the correlation of sensitive information and true class labels for different datasets in Figure [2](https://arxiv.org/html/2311.01591v4#S3.F2). We use a Graph Convolutional Network (GCN) to predict the missing sensitive values for independent imputation. Figures [2](https://arxiv.org/html/2311.01591v4#S3.F2)(a) and [2](https://arxiv.org/html/2311.01591v4#S3.F2)(b) show the correlation with adversarial missingness and random missingness, respectively. When $<50\%$ sensitive information is available, the predicted value with independent imputation underrepresents the true underlying bias in all datasets with adversarial missingness. For random missingness, the performance is slightly better. Figure [2](https://arxiv.org/html/2311.01591v4#S3.F2) (c) and (d) show results for BFtS, which will be introduced in the next section. BFtS rarely underestimates the true bias in the datasets. Our results provide strong evidence that off-the-shelf imputation methods often misguide fair graph machine learning algorithms due to underestimated bias, especially with adversarial missingness processes.

Figure: Figure 2: Empirical results showing that a simple degree-based adversarial missingness process is effective at minimizing the bias of an independent imputation model (GNN) compared with a random missingness process. The last column of each matrix shows the true bias in the data, and lower values show that the bias is underestimated. We also show results for our approach (BFtS) described in Section [4](https://arxiv.org/html/2311.01591v4#S4) that addresses this problem using a 3-player adversarial imputation method.
Refer to caption: x4.png

As our proposed model operates under a worst-case bias assumption, it may overestimate the bias in the complete data, as illustrated in Figure [2](https://arxiv.org/html/2311.01591v4#S3.F2) using the Bail dataset. This results in a trade-off between fairness and utility, which is governed by a hyperparameter $\beta$. Figures [3](https://arxiv.org/html/2311.01591v4#S3.F3)(a), (b), and (c) show the F1 score, $1-\Delta\text{DP}$, and $1-\Delta\text{EQOP}$, respectively, as $\beta$ varies and with $30\%$ of sensitive values observed. Here, F1 serves as the utility metric, while $1-\Delta\text{DP}$ and $1-\Delta\text{EQOP}$ quantify fairness (see Section [5](https://arxiv.org/html/2311.01591v4#S5)). We compare the performance of our BFtS model against a fair adversarial model trained with complete data. Adjusting $\beta$ enables controlling the balance between utility and robustness to worst-case bias, with appropriate tuning yielding an effective trade-off.

Figure: Figure 3: Fairness–utility trade-off of BFtS on the Bail dataset as $\beta$ varies, compared to a fair adversarial model trained with complete data. Lower $\beta$ yields higher accuracy but lower fairness.
Refer to caption: x5.png

###### Definition 1 .

###### Definition 2 .

###### Theorem 1 .

## 4 Fairness-Aware Adversarial Missing Data Imputation for Graphs

We introduce a framework called BFtS (Better Fair than Sorry) that allows fair GNN training with adversarial missing sensitive data. BFtS applies a 3-player adversarial learning scheme, where the fair GNN is trained jointly with two adversaries—one to predict sensitive attributes based on GNN embeddings and another to impute missing values that minimize fairness. As a result, fairness assessments by the GNN are based on the worst-case imputed values from the adversarial imputation.

### 4.1 Proposed Model (BFtS)

Figure: Figure 4: 3-player framework for fair GNN training with missing data imputation (BFtS). $f_{C}$ generates node representations by minimizing the classification loss $\mathcal{L}_{C}$ (Eqn. [1](https://arxiv.org/html/2311.01591v4#S4.E1)) and the maximizing sensitive attribute prediction loss $\mathcal{L}_{A}$ (Eqn. [3](https://arxiv.org/html/2311.01591v4#S4.E3)). $f_{A}$ predicts sensitive attributes using representations from $f_{C}$ by minimizing $\mathcal{L}_{A}$. $f_{I}$ predicts missing values by minimizing the imputation loss $\mathcal{L}_{I}$ (Eqn. [2](https://arxiv.org/html/2311.01591v4#S4.E2)) and maximizing $\mathcal{L}_{A}$. $\hat{y}$, $\hat{si}$, $\hat{sa}$ are predictions from $f_{C}$, $f_{I}$ and $f_{A}$, respectively.
Refer to caption: x6.png

Our goal is to learn a fair and accurate GNN $\hat{y}=f_{C}(\mathcal{G},\mathcal{X})$ for node classification with missing sensitive values. The proposed solution is model-agnostic and based on adversarial learning. It formulates the imputation model as a second adversary of the GNN. Figure [4](https://arxiv.org/html/2311.01591v4#S4.F4) depicts the flow diagram of the proposed model. The model has three primary components: a missing sensitive attribute imputation GNN $f_{I}$, a node classification GNN $f_{C}$, and a sensitive attribute Deep Neural Net (DNN) prediction $f_{A}$. $f_{C}$ takes $\mathcal{X}$ and $\mathcal{G}$ as inputs and predicts the node labels. $f_{A}$ is an adversarial neural network that attempts to estimate the sensitive information from the final layer representations of $f_{C}$ to assess the bias. More specifically, it $f_{C}$ is assumed to be biased if the adversary $f_{A}$ can accurately predict the sensitive attribute information from the representations of $f_{C}$. To train $f_{C}$, we need to know the values of the missing sensitive attributes. The model $f_{I}$ predicts the missing sensitive attributes by taking $\mathcal{X}$ and $\mathcal{G}$ as inputs and generating the missing sensitive attributes $\hat{si}$. The goal of $f_{I}$ is to generate sensitive values that minimize the fairness of $f_{C}$ and, thus, it works as a second adversary to $f_{C}$.

#### 4.1.1 Player architectures

##### GNN classifier f C f_{C} :

Node classification model $\hat{y}_{v}=f_{C}(x_{v},\mathcal{G})$ implemented using a GNN. We assume that $f_{C}$ does not apply sensitive attributes but uses other attributes in $\mathcal{X}$ that might be correlated with sensitive ones. The goal of $f_{C}$ is to achieve both accuracy and fairness. To improve fairness, $f_{C}$ tries to minimize the loss of adversary $f_{A}$.

##### Sensitive attribute predictor (Adversary 1) f A f_{A} :

Neural network that applies representations $\mathbf{h}_{v}$ generated by $f_{C}$ to predict sensitive attributes as $\hat{sa}_{v}=f_{A}(\mathbf{h}_{v})$. $f_{C}$ is fair if $f_{A}$ performs poorly.

##### Missing data imputation GNN (Adversary 2) f I f_{I} :

Predicts missing sensitive attributes as $\hat{si}_{v}=f_{I}(x_{v},\mathcal{G})$. However, besides being accurate, $f_{I}$ plays the role of an adversary to $f_{C}$ by predicting values that maximize the accuracy of $f_{A}$.

#### 4.1.2 Loss Functions

##### Node Classification Loss

We apply the cross-entropy loss to learn $f_{C}$ as follows:

$$ $\mathcal{L}_{C}=-\frac{1}{|\mathcal{V_{L}}|}\sum_{v\in\mathcal{V_{L}}}\hat{y}_{v}log(\hat{y}_{v})+(1-\hat{y}_{v})log(1-\hat{y}_{v}).$ (1) $$

##### Sensitive Attribute Imputation Loss

Because sensitive attributes tend to be imbalanced, $f_{I}$ applies the Label-Distribution-Aware Margin (LDAM) loss ldam. Let $\hat{si}=f_{I}(X,G)$ be the one-hot encoded predictions and $\hat{si}^{s}_{v}$ be the output of node $v$ for $s_{v}$. The LDAM loss of $f_{I}$ is defined as:

$$ $\mathcal{L}_{I}=\frac{1}{|\mathcal{V_{S}}|}\sum_{v=1}^{|\mathcal{V}_{S}|}-log\frac{e^{\hat{si}^{s}_{v}-\Delta^{s}}}{e^{\hat{si}^{s}_{v}-\Delta^{s}}+\sum_{k\neq s}e^{\hat{si}^{k}_{v}}}.$ (2) $$

where $\Delta^{j}=C/n_{j}^{\frac{1}{4}}$ and $j\in\{0,1\}$, $C$ is a constant independent of the sensitive attribute $s$, and $n_{j}$ is the number of samples that belong to $s=j$.

The LDAM loss is a weighted version of the negative log-likelihood loss. Intuitively, since $\Delta^{j}$ is larger for smaller values of $n_{j}$, it ensures a higher margin for the smaller classes.

BFtS with no sensitive information: BFtS can generate fair outputs when very little or no sensitive information is provided by letting $f_{I}$ impute the sensitive values from the ground truth training labels $y$ using the LDAM loss. We replace $\mathcal{V}_{S}$ with $\mathcal{V}_{L}$ and $s$ with $y$ for each node $v\in\mathcal{V}_{L}$ in Eqn [2](https://arxiv.org/html/2311.01591v4#S4.E2). The reasoning is that the worst-case fairness model generally assigns a more desired outcome to the non-sensitive group and a less desired outcome to the sensitive one. Therefore, the nodes predicted as the minority class will fall into the sensitive group, and vice versa. This is consistent with the worst-case assumption of BFtS. RNF du2021fairness applies a similar solution with a different loss function.

##### Sensitive Attribute Prediction Loss

Given the sensitive information for $\mathcal{V}_{s}$, we first replace $\hat{si}_{v}$ by ${s}_{v}$ for $v\in\mathcal{V}_{s}$ and thereby generate $\hat{s}$.
The parameters of $f_{A}$ are learned using:

$$ $\mathcal{L}_{A}=\mathbb{E}_{\mathbf{h}\sim p(\mathbf{h}|\hat{s}=1)}[\log f_{A}(\mathbf{h})]+\mathbb{E}_{\mathbf{h}\sim p(\mathbf{h}|\hat{s}=0)}[\log(1-f_{A}(\mathbf{h}))]$ (3) $$

#### 4.1.3 Learning the parameters of BFtS

Let $\theta_{C},\theta_{A}$, and $\theta_{I}$ be the parameters of $f_{C}$, $f_{A}$, and $f_{I}$, respectively. We learn these parameters via a 3-player adversarial learning scheme described in Figure [4](https://arxiv.org/html/2311.01591v4#S4.F4). Parameters $\theta_{C}$ are optimized as follows:

$$ $\theta_{C}^{*}=\arg\min_{\theta_{C}}\mathcal{L}_{C}+\alpha\mathcal{L}_{A}.$ (4) $$

where $\alpha$ is a hyperparameter that controls the trade-off between accuracy and fairness.

The parameters of the sensitive attribute predictor $\theta_{A}$ are learned by maximizing $\mathcal{L}_{A}$:

$$ $\theta_{A}^{*}=\arg\max_{\theta_{A}}\mathcal{L}_{A}.$ (5) $$

To learn the parameters $\theta_{I}$ of the imputation model to generate predictions that are accurate and represent the worst-case scenario for fairness, we apply the following:

$$ $\theta_{I}^{*}=\arg\min_{\theta_{I}}\mathcal{L}_{I}-\beta\mathcal{L}_{A}.$ (6) $$

Here $\beta$ is a hyperparameter that controls the trade-off between imputation accuracy and worst-case imputation. The min-max objective between the three players is therefore:

$$ $\begin{split}\min_{\theta_{C}}\max_{\theta_{I},\theta_{A}}\mathbb{E}_{\mathbf{h}\sim p(\mathbf{h}|\hat{s}=1)}[\log f_{A}(\mathbf{h})]+\mathbb{E}_{\mathbf{h}\sim p(\mathbf{h}|\hat{s}=0)}[\log(1-f_{A}(\mathbf{h}))].\end{split}$ (7) $$

The training algorithm and time complexity analysis of BFtS are discussed in Appendix A.

### 4.2 Theoretical analysis

We will analyze some theoretical properties of BFtS. All the proofs are provided in Appendix A.

###### Theorem 2 .

The optimal $f^{*}_{I}$ generates the worst-case (minimum fairness) imputation so that $\Delta DP_{f_{C},f^{*}_{I}}\geq\Delta DP_{f_{C},f_{I}}$ where,
$\Delta DP_{f_{C},f_{I}}=|p(\hat{y}=1|\hat{s}=1)-p(\hat{y}=1|\hat{s}=0)|$,
$\hat{y}=f_{C}(\mathcal{G},\mathcal{X})$ and, $\hat{s}=f_{I}(\mathcal{G},\mathcal{X}).$

$f_{I}$ generates imputations such that $\Delta DP$ in Sec [5](https://arxiv.org/html/2311.01591v4#S5)) is maximized for a given classifier $f_{C}$ .

###### Theorem 3 .

The maximal $\Delta DP$ of BFtS is minimal among all estimators of $s$.

The optimal GNN classifier $f^{*}_{C}$, will achieve demographic parity ($\Delta DP=0$ in Sec [5](https://arxiv.org/html/2311.01591v4#S5)) for the worst-case imputation (minimum fairness) $\hat{s}$ generated by $f_{I}$.

###### Corollary 1 .

Let $s^{\prime}=f(G,X)$ be an imputation method independent of models $f_{C}$ and $f_{A}$, then the Jensen Shannon divergence $JS(p(\mathbf{h}|s^{\prime}=1);p(\mathbf{h}|s^{\prime}=0))\leq JS(p(\mathbf{h}|\hat{s}=1);p(\mathbf{h}|\hat{s}=0))$.

The value of $JS(p(\mathbf{h}|s^{\prime}=1);p(\mathbf{h}|s^{\prime}=0))$ is related to the convergence of adversarial learning. For FairGNN, if $s^{\prime}$ is inaccurate, $JS(p(\mathbf{h}|s^{\prime}=1);p(\mathbf{h}|s^{\prime}=0))\approx 0$ and $\mathcal{L}_{A}$ in Eq. [4](https://arxiv.org/html/2311.01591v4#S4.E4) will be constant. The interplay between the three players makes BFtS more robust to convergence issues because the objective minimizes the upper bound on the JS divergence. This reduces the probability that the divergence vanishes during training (see details in Appendix A).

###### Theorem 2 .

###### Theorem 3 .

###### Corollary 1 .

## 5 Experiments and Results

Figure: Figure 5: Performance of the methods using the Simulation dataset for different values of assortativity coefficients. In the x-axis, we plot the F1 score, and in the y-axis of the top row, we plot $1-\Delta DP$, and in the y-axis of the bottom row, we plot $1-\Delta EQOP$. The top right corner of the plot, therefore, represents a high F1 with low bias. When the assortativity is low, other methods fail to learn the node labels. With higher assortativity, though other methods learn the class labels, BFtS is less biased and has similar accuracy. Note that the X-axes have different ranges.
Refer to caption: x7.png

We compare our approach for learning fair GNNs for node classification (BtFS) against the state-of-the-art in terms of accuracy and fairness using real and synthetic data. The size of $\mathcal{V}_{S}$ was set to $30\%$ of $|\mathcal{V}|$ unless stated otherwise. The details of the datasets, baselines, hyperparameters, additional experiments with graph attention network, and ablation studies are in Appendix A.

Figure: Figure 6: Fairness vs. accuracy for all the methods. The x-axis of each plot shows the F1 score. We plot $1-\Delta DP$ and $1-\Delta EQOP$ on the y-axis of rows 1 and 2, respectively. Therefore, the top right corner of the plot represents a high F1 with low bias. Our approach (BFtS) often achieves better fairness for a similar value of F1 compared to the baselines.
Refer to caption: x8.png

**Table 1: AVPR, F1 score, $\%\Delta DP$, and $\%\Delta EQOP$ without any sensitive information of BFtS and RNF. Amongst the baselines, only RNF works without any sensitive information. BFtS outperforms RNF in terms of fairness and accuracy for all baselines.**
|  | RNF | BFtS |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- |
|  | %AVPR($\uparrow$) | %F1($\uparrow$) | $\%\Delta DP$($\downarrow$) | $\%\Delta EQ(\downarrow$) | %AVPR($\uparrow$) | % F1($\uparrow$) | $\%\Delta DP$ ($\downarrow$) | $\%\Delta EQ(\downarrow)$ |
| BAIL | 81.0±0.1 | 85.3±0.3 | 11.65±0.02 | 8.51±0.02 | 83.1±0.2 | 86.2±0.3 | 8.01±0.03 | 4.12±0.01 |
| Credit | 80.4±0.4 | 75.9±0.1 | 8.01±0.08 | 7.25±0.08 | 82.1±0.4 | 76.8±0.0 | 5.97±0.10 | 4.96±0.06 |
| German | 73.2±0.2 | 74.4±0.1 | 9.42±0.04 | 8.92±0.12 | 74.1±0.3 | 74.7±0.4 | 6.42±0.11 | 7.68±0.17 |
| NBA | 70.1±0.2 | 70.2±0.1 | 6.47±0.03 | 5.89±0.05 | 72.9±0.3 | 69.8±0.1 | 5.19±0.01 | 3.59±0.05 |
| Pokek-z | 73.1±0.4 | 71.2±0.1 | 6.18±0.05 | 6.29±0.07 | 73.4±0.2 | 73.2±0.3 | 5.10±0.02 | 3.20±0.06 |
| Pokek-n | 71.6±0.2 | 72.2±0.1 | 7.58±0.01 | 7.09±0.04 | 72.6±0.1 | 69.6±0.4 | 4.29±0.02 | 3.01±0.03 |

Evaluation:
For utility evaluation, we use average precision (AVPR) and F1 score. For measuring bias we use $\Delta DP$ and $\Delta EQOP$. Details of these metrics are in Appendix A.

### 5.1 Results and Analysis

Figure [5](https://arxiv.org/html/2311.01591v4#S5.F5) shows the F1 score, $1-\Delta DP$, and $1-\Delta EQOP$ for different methods while varying their hyperparameter. We have generated the simulation graph using a stochastic block model with different assortativity coefficients, i.e., the extent to which links exist within clusters compared with across clusters. Learning missing sensitive values and node labels with a low assortativity coefficient is hard and graphs with assortativity $0.17$ and $0.37$ represent the scenario described in Corollary 1, therefore, the JS divergence tends to be small for independent imputation, which may result in a lack of convergence for the baselines. Figure [5](https://arxiv.org/html/2311.01591v4#S5.F5) shows that for assortativity $0.17$ and $0.37$, FairGNN and Debias fail to predict node labels in multiple cases. As we increase the assortativity, all baselines can predict the labels, but BFtS still achieves a better fairness vs. accuracy trade-off in all cases.

We demonstrate the accuracy vs. fairness trade-off for real datasets in Figure [6](https://arxiv.org/html/2311.01591v4#S5.F6). For BFtS, we vary $\alpha$ and $\beta$ to generate different values of fairness and accuracy. For other models, we vary their respective regularizers. The top right corner of the plot represents high fairness and accuracy. Our model achieves better fairness and similar accuracy to the best baseline for the Bail, NBA, German, pokec-n and pokec-z.
For all datasets, BFtS achieves a better fairness-accuracy tradeoff.

Table [1](https://arxiv.org/html/2311.01591v4#S5.T1) shows the accuracy and fairness results for Bail, Credit, German, Pokec-z, Pokek-n and NBA without any sensitive attribute information. Amongst the baselines, only RNF works in this setting. The results show that BFtS outperforms RNF for the Bail, German, and Credit. Our approach also outperforms RNF in terms of fairness on Pokec-z,Pokec-n, and NBA with similar AVPR and F1. As expected, we note that when we have $30\%$ of the sensitive attributes available (Figure [6](https://arxiv.org/html/2311.01591v4#S5.F6)), we obtain higher fairness than when we have no sensitive attribute information (Table [1](https://arxiv.org/html/2311.01591v4#S5.T1)).

## 6 Conclusion

We present BFtS, a 3-player adversarial learning framework for the imputation of adversarially missing sensitive attributes that produce challenging values for graph-based fairness. Our theoretical analysis showed that our approach is more robust to convergence challenges during adversarial training than existing alternatives. We evaluate BFtS using synthetic and real datasets. Our experimental results provide strong evidence that our approach achieves a better fairness $\times$ accuracy trade-off than the baselines.

Limitations and societal impact: We note the following as limitations of our work: (1) our experiments do not consider large-scale graph datasets for fairness as they are currently unavailable, and (2) our theoretical analysis shows that BFtS achieves demographic parity at equilibrium but not other fairness notions. In terms of social impact, our approach enables fair graph ML with missing data. However, one can leverage our method to predict private information.

## References

- [1]
Chirag Agarwal, Himabindu Lakkaraju, and Marinka Zitnik.
Towards a unified framework for fair and stable graph representation learning.
In UAI, 2021.
- [2]
J Angwin, J Larson, S Mattu, and L Kirchner.
Machine bias.
Auerbach Publications, 2022.
- [3]
Mario Arduini, Lorenzo Noci, Federico Pirovano, Ce Zhang, Yash Raj Shrestha, and Bibek Paudel.
Adversarial learning for debiasing knowledge graph embeddings.
arXiv preprint, 2020.
- [4]
Derrick Blakely, Jack Lanchantin, and Yanjun Qi.
Time and space complexity of graph convolutional networks.
Accessed on: Dec, 31:2021, 2021.
- [5]
Avishek Bose and William Hamilton.
Compositional fairness constraints for graph embeddings.
In ICML, 2019.
- [6]
Samuel F Buck.
A method of estimation of missing values in multivariate data suitable for use with an electronic computer.
Journal of the Royal Statistical Society: Series B, 1960.
- [7]
Maarten Buyl and Tijl De Bie.
Debayes: a bayesian method for debiasing network embeddings.
In ICML, 2020.
- [8]
Kaidi Cao, Colin Wei, Adrien Gaidon, Nikos Arechiga, and Tengyu Ma.
Learning imbalanced datasets with label-distribution-aware margin loss.
In NeurIPS, 2019.
- [9]
Junyi Chai, Taeuk Jang, and Xiaoqian Wang.
Fairness without demographics through knowledge distillation.
In NeurIPS, 2022.
- [10]
Junyi Chai and Xiaoqian Wang.
Self-supervised fair representation learning without demographics.
In NeurIPS, 2022.
- [11]
Robert S Chen, Brendan Lucier, Yaron Singer, and Vasilis Syrgkanis.
Robust optimization for non-convex objectives.
In NeurIPS, 2017.
- [12]
Xu Chen, Siheng Chen, Jiangchao Yao, Huangjie Zheng, Ya Zhang, and Ivor W Tsang.
Learning on attribute-missing graphs.
TPAMI, 2020.
- [13]
Eden Chlamtáč, Michael Dinitz, and Yury Makarychev.
Minimizing the union: Tight approximations for small set bipartite vertex expansion.
In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 881–899. SIAM, 2017.
- [14]
Enyan Dai and Suhang Wang.
Say no to the discrimination: Learning fair graph neural networks with limited sensitive attribute information.
In WSDM, 2021.
- [15]
A. Rogier T. Donders, Geert J.M.G. van der Heijden, Theo Stijnen, and Karel G.M. Moons.
A gentle introduction to imputation of missing values.
Journal of Clinical Epidemiology, 2006.
- [16]
Yushun Dong, Ninghao Liu, Brian Jalaian, and Jundong Li.
Edits: Modeling and mitigating data bias for graph neural networks.
In WebConf, 2022.
- [17]
Mengnan Du, Subhabrata Mukherjee, Guanchu Wang, Ruixiang Tang, Ahmed Awadallah, and Xia Hu.
Fairness via representation neutralization.
In NeurIPS, 2021.
- [18]
Wei Fan, Kunpeng Liu, Rui Xie, Hao Liu, Hui Xiong, and Yanjie Fu.
Fair graph auto-encoder for unbiased graph representations with wasserstein distance.
In ICDM, 2021.
- [19]
Michael Fauß, Abdelhak M Zoubir, and H Vincent Poor.
Minimax robust detection: Classic results and recent advances.
IEEE TSP, 2021.
- [20]
Raymond Feng, Flavio P Calmon, and Hao Wang.
Adapting fairness interventions to missing values.
arXiv preprint, 2023.
- [21]
Christian Fricke.
Missing fairness: The discriminatory effect of missing values in datasets on fairness in machine learning.
2020.
- [22]
Nicholas Furth, Abdallah Khreishah, Guanxiong Liu, NhatHai Phan, and Yasser Jararweh.
Unfair trojan: Targeted backdoor attacks against model fairness.
In Handbook of Trustworthy Federated Learning, pages 149–168. Springer, 2024.
- [23]
Malik Ghallab.
Responsible ai: requirements and challenges.
AI Perspectives, 2019.
- [24]
AC Ghani, CA Donnelly, and GP Garnett.
Sampling biases and missing data in explorations of sexual partner networks for the spread of sexually transmitted diseases.
Statistics in Medicine, 1998.
- [25]
Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl.
Neural message passing for quantum chemistry.
In ICML, 2017.
- [26]
Shubha Guha, Falaah Arif Khan, Julia Stoyanovich, and Sebastian Schelter.
Automated data cleaning can hurt fairness in machine learning-based decision making.
IEEE Transactions on Knowledge and Data Engineering, 36(12):7368–7379, 2024.
- [27]
Dongliang Guo, Zhixuan Chu, and Sheng Li.
Fair attribute completion on graph with missing attributes.
arXiv preprint arXiv:2302.12977, 2023.
- [28]
Moritz Hardt, Eric Price, and Nati Srebro.
Equality of opportunity in supervised learning.
In NeurIPS, 2016.
- [29]
Tatsunori Hashimoto, Megha Srivastava, Hongseok Namkoong, and Percy Liang.
Fairness without demographics in repeated loss minimization.
In ICML, 2018.
- [30]
Hans Hofmann.
Statlog (German Credit Data).
UCI Machine Learning Repository, 1994.
- [31]
Mark Huisman.
Imputation of missing network data: Some simple procedures.
Journal of Social Structure, 2009.
- [32]
Hussain Hussain, Meng Cao, Sandipan Sikdar, Denis Helic, Elisabeth Lex, Markus Strohmaier, and Roman Kern.
Adversarial inter-group link injection degrades the fairness of graph neural networks.
In 2022 IEEE International Conference on Data Mining (ICDM), pages 975–980. IEEE, 2022.
- [33]
Haewon Jeong, Hao Wang, and Flavio P Calmon.
Fairness without imputation: A decision tree approach for fair prediction with missing values.
In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 9558–9566, 2022.
- [34]
Kareem L Jordan and Tina L Freiburger.
The effect of race/ethnicity on sentencing: Examining sentence type, jail length, and prison length.
Journal of Ethnicity in Criminal Justice, 13(3):179–196, 2015.
- [35]
Mingxuan Ju, Tong Zhao, Wenhao Yu, Neil Shah, and Yanfang Ye.
Graphpatcher: mitigating degree bias for graph neural networks via test-time augmentation.
In NeurIPS, 2024.
- [36]
Faisal Kamiran and Toon Calders.
Classifying without discriminating.
In ICCCC, 2009.
- [37]
Jian Kang, Yinglong Xia, Ross Maciejewski, Jiebo Luo, and Hanghang Tong.
Deceptive fairness attacks on graphs via meta learning.
arXiv preprint arXiv:2310.15653, 2023.
- [38]
Ahmad Khajehnejad, Moein Khajehnejad, Mahmoudreza Babaei, Krishna Gummadi, Adrian Weller, and Baharan Mirzasoleiman.
Crosswalk: Fairness-enhanced node representation learning.
In AAAI, 2022.
- [39]
C Laclau, I Redko, M Choudhary, and C Largeron.
All of the fairness for edge prediction with optimal transport.
In AISTATS, 2021.
- [40]
Preethi Lahoti, Alex Beutel, Jilin Chen, Kang Lee, Flavien Prost, Nithum Thain, Xuezhi Wang, and Ed Chi.
Fairness without demographics through adversarially reweighted learning.
In NeurIPS, 2020.
- [41]
Gert RG Lanckriet, Laurent El Ghaoui, Chiranjib Bhattacharyya, and Michael I Jordan.
A robust minimax approach to classification.
JMLR, 2002.
- [42]
Hongyi Ling, Zhimeng Jiang, Youzhi Luo, Shuiwang Ji, and Na Zou.
Learning fair graph representations via automated data augmentations.
In ICLR, 2023.
- [43]
Roderick JA Little and Donald B Rubin.
Statistical analysis with missing data.
John Wiley & Sons, 2019.
- [44]
Zemin Liu, Trung-Kien Nguyen, and Yuan Fang.
On generalized degree fairness in graph neural networks.
In AAAI, 2023.
- [45]
Johan Löfberg.
Minimax approaches to robust model predictive control.
Linköping University, 2003.
- [46]
Zihan Luo, Hong Huang, Yongkang Zhou, Jiping Zhang, Nuo Chen, and Hai Jin.
Are your models still fair? fairness attacks on graph neural networks via node injections.
In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024.
- [47]
Haris Mansoor, Sarwan Ali, Shafiq Alam, Muhammad Asad Khan, Umair Ul Hassan, and Imdadullah Khan.
Impact of missing data imputation on the fairness and accuracy of graph node classifiers.
In BigData, 2022.
- [48]
Fernando Martínez-Plumed, Cèsar Ferri, David Nieves, and José Hernández-Orallo.
Fairness and missing values.
arXiv preprint arXiv:1905.12728, 2019.
- [49]
Farzan Masrour, Tyler Wilson, Heng Yan, Pang-Ning Tan, and Abdol Esfahanian.
Bursting the filter bubble: Fairness-aware network link prediction.
In AAAI, 2020.
- [50]
Ninareh Mehrabi, Muhammad Naveed, Fred Morstatter, and Aram Galstyan.
Exacerbating algorithmic bias through fairness attacks.
In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 8930–8938, 2021.
- [51]
Arpit Merchant and Carlos Castillo.
Disparity, inequality, and accuracy tradeoffs in graph neural networks for node classification.
In CIKM, 2023.
- [52]
Tu Nguyen, Trung Le, Hung Vu, and Dinh Phung.
Dual discriminator generative adversarial nets.
NeurIPS, 2017.
- [53]
William P O’Hare and William P O’Hare.
Potential explanations for why people are missed in the us census.
Differential Undercounts in the US Census: Who is Missed?, 2019.
- [54]
John Palowitch and Bryan Perozzi.
Monet: Debiasing graph embeddings via the metadata-orthogonal training unit.
arXiv preprint, 2019.
- [55]
Ricardo Cardoso Pereira, Miriam Seoane Santos, Pedro Pereira Rodrigues, and Pedro Henriques Abreu.
Reviewing autoencoders for missing data imputation: Technical trends, applications and outcomes.
JAIR, 2020.
- [56]
Tahleen Rahman, Bartlomiej Surma, Michael Backes, and Yang Zhang.
Fairwalk: towards fair graph embedding.
In AAAI, 2019.
- [57]
Pengzhen Ren, Yun Xiao, Xiaojun Chang, Po-Yao Huang, Zhihui Li, Brij B Gupta, Xiaojiang Chen, and Xin Wang.
A survey of deep active learning.
ACM computing surveys (CSUR), 54(9):1–40, 2021.
- [58]
Emanuele Rossi, Henry Kenlay, Maria I Gorinova, Benjamin Paul Chamberlain, Xiaowen Dong, and Michael Bronstein.
On the unreasonable effectiveness of feature propagation in learning on graphs with missing node features.
arXiv preprint, 2021.
- [59]
Shai Shalev-Shwartz and Yonatan Wexler.
Minimizing the maximal loss: How and why.
In ICML, 2016.
- [60]
David Solans, Battista Biggio, and Carlos Castillo.
Poisoning attacks on algorithmic fairness.
In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 162–177. Springer, 2020.
- [61]
I Spinelli, S Scardapane, A Hussain, and A Uncini.
Fairdrop: Biased edge dropout for enhancing fairness in graph representation learning.
TAI, 2021.
- [62]
Arjun Subramonian, Kai-Wei Chang, and Yizhou Sun.
On the discrimination risk of mean aggregation feature imputation in graphs.
In NeurIPS, 2022.
- [63]
Lubos Takac and Michal Zabovsky.
Data analysis in public social networks.
In DTI, 2012.
- [64]
Xianfeng Tang, Huaxiu Yao, Yiwei Sun, Yiqi Wang, Jiliang Tang, Charu Aggarwal, Prasenjit Mitra, and Suhang Wang.
Investigating and mitigating degree-related biases in graph convoltuional networks.
In CIKM, 2020.
- [65]
Hoang Thanh-Tung and Truyen Tran.
Catastrophic forgetting and mode collapse in gans.
In 2020 international joint conference on neural networks (ijcnn), pages 1–10. IEEE, 2020.
- [66]
Simon Vandenhende, Bert De Brabandere, Davy Neven, and Luc Van Gool.
A three-player gan: generating hard samples to improve classification networks.
In MVA, 2019.
- [67]
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, Yoshua Bengio, et al.
Graph attention networks.
stat, 1050(20):10–48550, 2017.
- [68]
Neil Vigdor.
Apple card investigated after gender discrimination complaints.
New York Times, 2019.
- [69]
Wang et al.
Improving fairness in graph neural networks via mitigating sensitive attribute leakage.
In KDD, 2022.
- [70]
Ann M Weber, Ribhav Gupta, Safa Abdalla, Beniamino Cislaghi, Valerie Meausoone, and Gary L Darmstadt.
Gender-related data missingness, imbalance and bias in global health surveys.
BMJ Global Health, 2021.
- [71]
Lilian Weng.
From gan to wgan.
arXiv preprint arXiv:1904.08994, 2019.
- [72]
Shen Yan, Hsien-te Kao, and Emilio Ferrara.
Fair class balancing: Enhancing model fairness without observing sensitive attributes.
In CIKM, 2020.
- [73]
Cheng Yang, Jixi Liu, Yunhe Yan, and Chuan Shi.
Fairsin: Achieving fairness in graph neural networks through sensitive information neutralization.
In AAAI, 2024.
- [74]
I-Cheng Yeh and Che-hui Lien.
The comparisons of data mining techniques for the predictive accuracy of probability of default of credit card clients.
Expert systems with applications, 36(2):2473–2480, 2009.
- [75]
Ofer Yehuda, Avihu Dekel, Guy Hacohen, and Daphna Weinshall.
Active learning through a covering lens.
Advances in Neural Information Processing Systems, 35:22354–22367, 2022.
- [76]
Binchi Zhang, Yushun Dong, Chen Chen, Yada Zhu, Minnan Luo, and Jundong Li.
Adversarial attacks on fairness of graph neural networks.
arXiv preprint arXiv:2310.13822, 2023.
- [77]
Brian Hu Zhang, Blake Lemoine, and Margaret Mitchell.
Mitigating unwanted biases with adversarial learning.
In AIES, 2018.
- [78]
Yiliang Zhang and Qi Long.
Assessing fairness in the presence of missing data.
In NeurIPS, 2021.
- [79]
Yiliang Zhang and Qi Long.
Fairness-aware missing data imputation.
In Workshop on Trustworthy and Socially Responsible Machine Learning, NeurIPS 2022, 2022.
- [80]
Zhilu Zhang and Mert Sabuncu.
Generalized cross entropy loss for training deep neural networks with noisy labels.
In NeurIPS, 2018.
- [81]
Tianxiang Zhao, Enyan Dai, Kai Shu, and Suhang Wang.
Towards fair classifiers without sensitive attributes: Exploring biases in related features.
In WSDM, 2022.
- [82]
Mengxin Zheng, Jiaqi Xue, Yi Sheng, Lei Yang, Qian Lou, and Lei Jiang.
Trojfair: trojan fairness attacks.
arXiv preprint arXiv:2312.10508, 2023.
- [83]
Yuchang Zhu, Jintang Li, Zibin Zheng, and Liang Chen.
Fair graph representation learning via sensitive attribute disentanglement.
In Proceedings of the ACM Web Conference 2024, pages 1182–1192, 2024.

## Appendix A Technical Appendices and Supplementary Material

This supplementary material includes the following:

- •
Details of Graph Neural Network (GNN)
- •
Evaluation Metrics
- •
Dataset Details
- •
Baselines
- •
Software and Hardware
- •
Hyperparameter Setting
- •
Proof of theorems and corollaries
- •
Training algorithm
- •
Complexity and Running time comparison
- •
Imputation accuracy
- •
Additional experiments
- •
Ablation Study

## Graph Neural Network

Two of the models (or players) learned by our model are GNNs. Without loss of generality, we will assume that they are message-passing neural networks [25], which we will simply refer to as GNNs. A GNN learns node representations $\mathbf{h}_{v}$ for each node $v$ that can be used to predict (categorical or continuous) values $y_{v}=f(\mathbf{h}_{v})$. These representations are learned via successive $\mathsf{AGGREGATE}$ and $\mathsf{COMBINE}$ operations defined as follows:

$$ $\mathbf{h}_{v}^{k}\!=\!\mathsf{COMBINE}^{k}(\mathbf{h}_{v}^{k-1},\mathsf{AGGREGATE}^{k-1}({\mathbf{h}_{u}^{k-1},A_{u,v}\!=\!1})).$ $$

where $\mathbf{a}_{v}^{k}$ aggregates the messages received by the neighbors of $v$ in $\mathcal{G}$ and $\mathbf{h}_{v}^{k}$ are representations learned at the $k$-th layer.

## Evaluation Metrices

Utility Evaluation: As with many datasets in the fairness literature, our datasets are imbalanced. To evaluate their accuracy, we apply average precision (AVPR) and the F1 score.

Fairness Evaluation: In machine learning literature, fairness is often measured with bias. We apply two bias metrics that will be defined based on a sensitive attribute $s$. Let $s=1$ be the sensitive group and $s=0$ be the non-sensitive group. The Demographic Parity (DP) requires the prediction to be independent of the sensitive attribute [36]. We evaluate demographic parity as:

$$ $\Delta DP(\hat{y},s)=|p(\hat{y}=1|s=1)-p(\hat{y}=1|s=0)|.$ (8) $$

Equality of Opportunity (EQOP) calculates the difference between true positive rates between sensitive and non-sensitive groups [28] as follows:

$$ $\begin{split}\Delta EQOP(\hat{y},s,y)=|p(\hat{y}=1|s=1,y=1)-p(\hat{y}=1|s=0,y=1)|.\end{split}$ (9) $$

We can get corresponding fairness by subtracting $\Delta DP$ and $\Delta EQOP$ from $1$.

## Dataset Details

Simulation: We simulate a synthetic graph consisting of $1000$ nodes based on the stochastic block model with blocks of sizes $600$ and $400$, for the majority and minority classes, respectively. We can have different edge probabilities within and across blocks and generate graphs with different assortativity coefficients.
The sensitive attribute $s$ is simulated as $s\!\sim\!Bernoulli(p)$ if $y=1$ and $s\!\sim\!Bernoulli(1-p)$ otherwise. The probability $p=0.5$ generates a random assignment of the sensitive attribute, while $p$ close to $1$ or 0 indicates an extremely biased scenario. For our simulation, we use $p=0.7$ so that the dataset is unfair. Each node has 20 attributes, of which 8 are considered noisy. The noisy attributes are simulated as $Normal(0,1)$ and the remaining ones as $\gamma*y+Normal(0,1)$, where $\gamma$ is the strength of the signal in important features.

Bail [34]: Contains 18,876 nodes representing people who committed a criminal offense and were granted bail by US state courts between 1990 and 2009. Defendants are linked based on similarities in their demographics and criminal histories. The objective is to categorize defendants as likely to post bail vs. no bail. No-bail defendants are expected to be more likely to commit violent crimes if released. Race information is considered a sensitive attribute. Features include education, marital status, and profession.

Credit [74]: The dataset has $30,000$ nodes representing people each with $25$ features, including education, total overdue counts, and most recent payment amount. The objective is to forecast if a person will or won’t miss a credit card payment while considering age as a sensitive attribute. Nodes are connected based on payment patterns and spending similarities.

German [30]: The dataset consists of 1000 nodes and 20 features (e.g., credit amount, savings, profession) representing clients at a German bank. Labels are credit decisions for a person (good or bad credit). The sensitive attribute is gender. The goal is to predict who should receive credit.

NBA [14]: Dataset based on a Kaggle dataset about the National Basketball Association (US). It contains 403 players as nodes connected based on their Twitter activity. Attributes represent player statistics and nationality is considered the sensitive attribute. The goal is to predict the players’ salaries (above/under the median).

Pokec [63]: This dataset has two variations: Pokec-z and pokec-n. The pokec dataset is based on a popular social network in Slovakia. The sensitive attribute in pokec-z and pokec-n are two different regions of Slovakia. The goal is to predict the working field of users.

## Baselines

Vanilla: The vanilla model is the basic GNN model trained with cross-entropy loss without any fairness intervention.

Debias [77]: Debias is an adversarial learning method that trains a classifier and an adversary simultaneously. The adversary is trained using the softmax output of the last layer of the classifier. It does not handle missing sensitive data. Hence, we only use $\mathcal{V}_{S}\in\mathcal{V}$ to calculate the adversarial loss.

FairGNN [14]: FairGNN first uses a GNN to estimate the missing sensitive attributes. It then trains another GNN-based classifier and a DNN adversary. The adversary helps to eliminate bias from the representations learned by the GNN classifier.

RNF [17]: RNF imputes the missing sensitive attributes by first training the model with generalized cross entropy [80]. It eliminates bias from the classification head. RNF uses samples with the same ground-truth label but distinct sensitive attributes and trains the classification head using their neutralized representations.

FairVGNN [69]: FairVGNN learns fair node representations via automatically identifying and masking sensitive-correlated features. It requires complete sensitive information, so we use the same imputation method as FairGNN for the missing values.

FairSIN [73]:
FairSIN learns fair representations by adding additional fairness-facilitating features. It also requires complete sensitive information, so we use the same independent imputation method as FairGNN for the missing values.
[73]:

## Software and Hardware

- •
Operating System: Linux (Red Hat Enterprise Linux 8.9 (Ootpa))
- •
GPU: NVIDIA A40
- •
Software: Python 3.8.10, torch 2.2.1, dgl==0.4.3

## Hyperparameter settings

Each GNN has two layers and a dropout probability of $0.5$. In practice, some sensitive information is often available, unless otherwise stated. Therefore, we concentrate the majority of our experiments on the assumption that there is a limited amount of sensitive information available, and we generate the imputations using the available sensitive information in Equation 2. The $\mathcal{V}_{S}$ was set to $30\%$ for all experiments unless stated otherwise. $\mathcal{V}_{L}$ is $300,400,1400,100,500,500$, and $800$ for the Simulation, German, Credit, NBA, pokec-z, pokec-n and Bail datasets, respectively. We adjust the values of $\alpha$ and $\beta$ for each dataset using cross-validation based on the F1 score. For all baselines, we choose the respective regularizers using cross-validation based on the same metrics. Every model, except RNF, combines the training of several networks with various convergence rates. We stop training RNF based on early stopping to eliminate overfitting. We train the rest of the models for certain epochs and choose the model with the best AVPR. All the results shown in the following section are the average of $10$ runs. We use GCN as the GNN architecture for all experiments unless mentioned otherwise.

## Proof of Theorems

### Theorem 1

We will consider an adversarial active learning setting, where the goal of the adversary is to select $k$ labels (i.e., observed sensitive values) to minimize the bias $\mathcal{L}_{A}$ of the data imputed by $f_{I}$. More specifically, our proof will use the coverage model for active learning, where an unlabeled data point $x_{i}^{u}$ can be correctly predicted iff it is covered by at least one labeled point $x_{j}^{l}$, so the goal is for the labeled points $\{x_{1}^{l},x_{2}^{l},\ldots x_{k}^{l}\}$ to cover as many unlabeled data points $\{x_{1}^{u},x_{2}^{u},\ldots x_{n-k}^{u}\}$ as possible [75, 57]. Thus, in our setting, the adversary’s goal is to select labels to minimize the coverage of the following sets of nodes: (1) nodes in the sensitive group ($s_{v}=1$) and the negative class ($y=0$) and (2) nodes in the non-sensitive group ($s_{v}=0$) and the positive class ($y=1$). Without loss of generality, we will focus on the second set $(s_{v}=0,y=1)$ because it impacts demographic parity as a bias metric. This can be achieved by minimizing the coverage of such nodes. We provide a reduction from the minimum k-union problem.

Minimum k-union problem (MkU, [13]): Given a set of sets $\mathcal{S}={S_{1},S_{2},\ldots S_{q}}$, where each set $S_{i}\subseteq\mathcal{I}$ and $\mathcal{I}$ is a set of items. The problem consists of selecting $r$ sets $S_{1},S_{2},\ldots S_{r}$ from $\mathcal{S}$ to minimize the coverage $S_{1}\cap S_{2}\cap\ldots S_{r}$.

Under our coverage model, the reduction is straightforward.

Given an instance of MkU, we define a corresponding instance of the Adversarial Missingness for Minimizing the Bias in the Data (AMMBD) problem as follows. We represent each item in $\mathcal{I}$ and each set in $\mathcal{S}$ as a data point $x$ and assign all data points to both the non-sensitive group ($s_{v}=0$) and the positive class ($y=1$). Moreover, we will add one data point $x^{\prime}$ that will belong to the sensitive group ($s_{v}=1$) and the positive class ($y=1$). Therefore, the resulting set of data points is $\{x_{1},x_{2},\ldots x_{n}\}$, where $n=|\mathcal{S}|+|\mathcal{I}|+1$. Moreover, let $x_{i}$ cover $x_{j}$ iff $x_{i}$ represents a set $S_{i}\in\mathcal{S}$, $x_{j}$ represents an item $i_{j}\in\mathcal{I}$, and $i_{j}\in S_{i}$. It follows that minimizing the bias in the AMMBD instance by selecting data points $x_{j}$ to be labeled is equivalent to minimizing the coverage in the corresponding MkU instance.

In terms of approximation, the best-known approximation algorithm for the minimum k-union problem used in our reduction is $O(n^{1/4+\epsilon})$, where $n$ is the number of sets and $\epsilon>0.$, which is mapped to the size of the graph in our problem [13]. This means that at least $O(kn^{1/4})$ nodes would have to be selected to achieve the optimal coverage for $k$ nodes. We note that this is a worse approximation than the classical $O(\log(n))$-approximation for set cover achieved by a greedy algorithm.

### Theorem 2

###### Proof.

From Eq. 7, the min-max objective of BFtS is:

$$ $\displaystyle\mathbb{E}_{\mathbf{h}\sim p(\mathbf{h}|\hat{s}=1)}$ $\displaystyle[\log(f_{A}(\mathbf{h}))]+\mathbb{E}_{\mathbf{h}\sim p(\mathbf{h}|\hat{s}=0)}[\log(1-f_{A}(\mathbf{h}))]$ $\displaystyle=\sum_{h}p(\mathbf{h}|\hat{s}=1)\log(f_{A}(\mathbf{h}))+\sum_{h}p(\mathbf{h}|\hat{s}=0)\log(1-f_{A}(\mathbf{h}))$ $$

If we fix $\theta_{C}$ and $\theta_{I}$, then the optimal $f_{A}^{*}$ is $\frac{p(\mathbf{h}|\hat{s}=1)}{p(\mathbf{h}|\hat{s}=1)+p(\mathbf{h}|\hat{s}=0)}.$
By substituting the optimal $f_{A}^{*}$ in Eq. 7 we get:

$$ $\displaystyle\min_{\theta_{C}}\max_{\theta_{I}}~$ $\displaystyle\mathbb{E}_{\mathbf{h}\sim p(\mathbf{h}|\hat{s}=1)}[\log\frac{p(\mathbf{h}|\hat{s}=1)}{p(\mathbf{h}|\hat{s}=1)+p(\mathbf{h}|\hat{s}=0)}]+$ $\displaystyle\mathbb{E}_{\mathbf{h}\sim p(\mathbf{h}|\hat{s}=0)}[\log(1-\frac{p(\mathbf{h}|\hat{s}=1)}{p(\mathbf{h}|\hat{s}=1)+p(\mathbf{h}|\hat{s}=0)})]$ $$

We further simplify the objective function and get:

$$ $\displaystyle\mathbb{E}_{\mathbf{h}\sim p(\mathbf{h}|\hat{s}=1)}$ $\displaystyle[\log\frac{p(\mathbf{h}|\hat{s}=1)}{p(\mathbf{h}|\hat{s}=1)+p(\mathbf{h}|\hat{s}=0)}]+$ $\displaystyle\mathbb{E}_{\mathbf{h}\sim p(\mathbf{h}|\hat{s}=0)}[\log\frac{p(\mathbf{h}|\hat{s}=0)}{p(\mathbf{h}|\hat{s}=1)+p(\mathbf{h}|\hat{s}=0)}]$ $\displaystyle=\sum_{h}p(\mathbf{h}|$ $\displaystyle\hat{s}=1)\log\frac{p(\mathbf{h}|\hat{s}=1)}{p(\mathbf{h}|\hat{s}=1)+p(\mathbf{h}|\hat{s}=0)}+$ $\displaystyle\sum_{h}p(\mathbf{h}|\hat{s}=0)\log\frac{p(\mathbf{h}|\hat{s}=0)}{p(\mathbf{h}|\hat{s}=1)+p(\mathbf{h}|\hat{s}=0)}$ $\displaystyle=-\log 4$ $\displaystyle+2JS(p(\mathbf{h}|\hat{s}=1);p(\mathbf{h}|\hat{s}=0))$ $$

By removing the constants, we can further simplify the min-max optimization with optimal $f_{A}^{*}$ to:

$$ $\min_{\theta_{C}}\max_{\theta_{I}}JS(p(\mathbf{h}|\hat{s}=1);p(\mathbf{h}|\hat{s}=0))$ $$

The optimal $f_{I}^{*}$ thereby maximizes the following objective:

$$ $JS(p(\mathbf{h}|\hat{s}=1);p(\mathbf{h}|\hat{s}=0))$ $$

Since $\hat{y}=\sigma(\mathbf{h.w})$, $f^{*}_{I}$ generates imputation so that

$$ $\min_{\theta_{C}}\sup_{\hat{s}}JS(p(\hat{y}|\hat{s}=1);p(\hat{y}|\hat{s}=0))$ $$

The supremum value will make the two probabilities maximally different. Therefore, for the optimal $f^{*}_{I}$ we get,

$$ $\min_{\theta_{C}}\sup_{\hat{s}}|p(\hat{y}|\hat{s}=1)-p(\hat{y}|\hat{s}=0)|$ $$

Let $\Delta DP_{f_{C},f_{I}}=|p(\hat{y}=1|\hat{s}=1)-p(\hat{y}=1|\hat{s}=0)|$, then, the optimal $f^{*}_{I}$ generates the worst-case (minimum fairness) imputation so that
$\Delta DP_{f_{C}.f^{*}_{I}}\geq\Delta DP_{f_{C},f^{*}_{I}}$
∎

###### Proof.

### Theorem 3

###### Proof.

From Theorem 1, we get,

$$ $\min_{\theta_{C}}\sup_{\hat{s}}|p(\hat{y}|\hat{s}=1)-p(\hat{y}|\hat{s}=0)|$ $$

Let us assume that there can be $m$ different $\hat{s}$ that produce sensitive attributes $\hat{s}_{1},\hat{s}_{2},...,\hat{s}_{m}$. If we let $D_{i}$ be the uniform distribution over each $s_{i}$, then BFtS minimizes the $|p(\hat{y}|\hat{s}=1)-p(\hat{y}|\hat{s}=0)|$ in the worst case over these different distributions $D_{i}$. Therefore, $f^{*}_{C}$ is a minimax estimator. The objective of Eq. 7 with optimal $f^{*}A,f^{*}I$ and $f^{*}_{C}$ becomes:

$$ $\inf_{\hat{y}}\sup_{\hat{s}}|p(\hat{y}|\hat{s}=1)-p(\hat{y}|\hat{s}=0)|$ $$

Therefore, $f_{C}$ is a minimax estimator.
As $f_{C}$ is a minimax estimator, the maximal $\Delta DP$ of BFtS is minimum amongst all estimators of $s$

∎

At the global minima of $f_{C}$, $|p(\hat{y}|\hat{s}=1)-p(\hat{y}|\hat{s}=0)|$ will be minimum. Its minimum value is 0. Therefore, $p(\mathbf{h}|\hat{s}=1)-p(\mathbf{h}|\hat{s}=0)=0$.
The optimal $f^{*}_{C}$ achieves demographic parity for the worst case.

###### Proof.

### Corollary 1

###### Proof.

If $s^{\prime}$ is a separate imputation independent of $f_{C}$ and $f_{A}$, then the min max game according to [14] is the following:

$$ $\begin{split}\min_{\theta_{C}}\max_{\theta_{A}}~&\mathbb{E}_{\mathbf{h}\sim p(\mathbf{h}|s^{\prime}=1)}[\log f_{A}(\mathbf{h})]\\ &+\mathbb{E}_{\mathbf{h}\sim p(\mathbf{h}|s^{\prime}=0)}[\log(1-f_{A}(\mathbf{h}))].\end{split}$ $$

With optimal $f^{*}_{A}$, the optimization problem simplifies to-

$$ $\min_{\theta_{C}}-\log 4+JS(p(\mathbf{h}|s^{\prime}=1);p(\mathbf{h}|s^{\prime}=0)).$ $$

With independent imputation $s^{\prime}$, the adversary $f_{A}$ tries to approximate the lower bound of Jensen Shannon Divergence [71]. In BFtS, the adversarial imputation $f_{I}$ tries to approximate the upper bound of the JS divergence, and the classifier $f_{C}$ tries to minimize the upper bound on the JS divergence provided by the adversarial imputation (see Proposition 1). Therefore,

$$ $\displaystyle JS((p(\mathbf{h}|s^{\prime}\!=\!1);p(\mathbf{h}|s^{\prime}\!=\!0)))\!\leq\!JS(p(\mathbf{h}|\hat{s}\!=\!1);p(\mathbf{h}|\hat{s}\!=\!0)).$ $$

∎

###### Proof.

### Convergence of adversarial learning for three players vs two players with independent imputation

Let us consider a scenario when the independent missing sensitive value imputation [14] fails to converge. There are three possible reasons for the convergence to fail:

- 1.
$s^{\prime}$ is always $1$
- 2.
$s^{\prime}$ is always 0
- 3.
$s^{\prime}$ is uniform, i.e. $p(\mathbf{h}|s^{\prime}=1)=p(\mathbf{h}|s^{\prime}=0)$

In scenario $1$ and $2$ the supports of $p(\mathbf{h}|s^{\prime}=1)$ and $p(\mathbf{h}|s^{\prime}=0)$ are disjoint. According to [14], the optimization for the classifier with an optimal adversary is

$$ $\min_{\theta_{C}}-\log 4+2JS(p(\mathbf{h}|s^{\prime}=1);p(\mathbf{h}|s^{\prime}=0))$ $$

As the supports of $p(\mathbf{h}|s^{\prime}=1)$ and $p(\mathbf{h}|s^{\prime}=0)$ are disjoint, $JS(p(\mathbf{h}|s^{\prime}=1);p(\mathbf{h}|s^{\prime}=0))$ is always 0. The gradient of the JS divergence vanishes, and the classifier gets no useful gradient information—it will minimize a constant function. This results in extremely slow training of the node classifier, and it may not converge.

In scenario 3, $\hat{s}$ is uniform. Therefore, $p(\mathbf{h}|s^{\prime}=1)$ will be equal to $p(\mathbf{h}|s^{\prime}=0)$ which results in $JS(p(\mathbf{h}|s^{\prime}=1);p(\mathbf{h}|s^{\prime}=0))$ being equal to 0. Moreover, the classifier may assign all training samples to a single class and yet have an adversary that may not be able to distinguish the sensitive attributes of the samples as $\hat{s}$ is random. If the classifier assigns all samples to the majority class, it will achieve low classification loss $L_{C}$ along with minimum $L_{A}$. The training of the classifier may get stuck in this local minima (see Eq. 4). This phenomenon is similar to the mode collapse of GANs [65].

Based on Corollary 1, our approach is more robust to the convergence issues described above.

### Training Algorithm

Algorithm [1](https://arxiv.org/html/2311.01591v4#alg1) is a high-level description of the key steps applied for training BFtS. It receives the graph $\mathcal{G}$, labels $y$, labeled nodes $\mathcal{V}_{L}$, nodes with observed sensitive attributes $\mathcal{V}_{S}$ and hyperparameters, $\alpha$ and $\beta$ as inputs and outputs the GNN classifier $f_{C}$, sensitive attribute predictor, $f_{A}$ and missing data imputation GNN $f_{I}$. We first estimate $\hat{si}$
and then fix $\theta_{C}$ and $\theta_{A}$ to update $\theta_{I}$. Then we update $\theta_{A}$ with Eq. 5. After that, we fix $\theta_{A}$ and $\theta_{I}$ and update $\theta_{C}$ with Eq. 4 and repeat these steps until convergence.

Figure: Algorithm 1 Training BFtS

## Complexity analysis

BFtS model consists of two GNNs and one DNN. If we consider GCN for training the GNN, the complexity is $\mathcal{O}(L|V|F^{2}+L|E|F)$, where $L$ is the number of layers and $F$ is the nodes in each layer (We assume that the number of nodes in each layer is the same) [4]. The complexity is polynomial, and therefore, BFtS is scalable. The complexity of FairGNN [14] is the same as the complexity of BFtS. FairGNN makes an additional forward pass to the trained sensitive attribute imputation network. Therefore, the empirical running time of FairGNN is higher than BFtS as described in the next section.

## Running Time

Table [2](https://arxiv.org/html/2311.01591v4#Ax9.T2) shows that Debias has the lowest runtime but performs the worst in fairness (See Fig. 4 and 5). BFtS had the second-lowest runtime. While the 3-player network adds complexity, it removes the requirement of training a separate imputation method (as for other benchmarks).

**Table 2: Running time (secs) of different methods**
|  | German | Credit | Bail | NBA | pokec-z | pokec-n |
| --- | --- | --- | --- | --- | --- | --- |
| Debias | 21.74 | 110.99 | 170.95 | 14.85 | 650.67 | 647.62 |
| FairGNN | 31.43 | 229.41 | 340.48 | 29.12 | 1356.57 | 1234.62 |
| FairVGNN | 212.64 | 10557.79 | 2554.72 | 234.57 | 15956.62 | 15632.75 |
| RNF | 136.67 | 432.31 | 655.54 | 138.31 | 1945.58 | 2012.13 |
| FairSIN | 615.74 | 15142.25 | 2884.34 | 342.14 | 20565.13 | 20456.34 |
| BFtS | 28.91 | 168.88 | 242.88 | 22.34 | 942.35 | 956.42 |

Figure: Figure 7: Sensitivity analysis of $\alpha$ and $\beta$. BFtS is more sensitive to $\alpha$ than $\beta$. These parameters can be optimized using automated techniques, such as grid-search.
Refer to caption: x9.png

Figure: Figure 8: Performance of the models on different datasets for varying amounts of observed data $\mathcal{V}_{S}$. In the majority of the settings, our approach (BFtS) achieves a better fairness $\times$ accuracy trade-off than the baselines.
Refer to caption: x10.png

**Table 3: AVPR, F1 score, $\%\Delta DP$, and $\%\Delta EQOP$ of different methods. For the Bail, and NBA dataset, we outperform all baselines in terms of accuracy and fairness. For other datasets, we improve fairness while slightly sacrificing accuracy.**
|  |  | VANILLA | DEBIAS | FairGNN | RNF | FairVGNN | FairSIN | BFtS (Ours) |
| --- | --- | --- | --- | --- | --- | --- | --- | --- |
| Bail | AVPR ($\uparrow$) | 0.86±0.00 | 0.81±0.00 | 0.82±0.00 | 0.81±0.00 | 0.80 ±0.00 | 0.81±0.00 | 0.83±0.00 |
| F1 score ($\uparrow$) | 0.88±0.00 | 0.85 ±0.00 | 0.84±0.00 | 0.84±0.01 | 0.84 ±0.00 | 0.84±0.00 | 0.85±0.00 |  |
| $\%\Delta DP$ ($\downarrow$) | 19.10±0.03 | 8.78±0.02 | 7.9±0.03 | 8.50±0.04 | 9.81 ±0.09 | 8.64 ±0.20 | 6.70±0.03 |  |
| $\%\Delta EQOP$ ($\downarrow$) | 14.20±0.04 | 7.50±0.03 | 4.10±0.04 | 4.70±0.05 | 4.79±0.06 | 3.92 ±0.09 | 2.70±0.01 |  |
| Credit | AVPR ($\uparrow$) | 0.85±0.00 | 0.82±0.00 | 0.83±0.00 | 0.81±0.00 | 0.81 ±0.02 | 0.81 ±0.02 | 0.83±0.00 |
| F1 score ($\uparrow$) | 0.79±0.00 | 0.73 ±0.00 | 0.76±0.00 | 0.75±0.01 | 0.73 ±0.00 | 0.75 ±0.00 | 0.76±0.00 |  |
| %$\Delta DP$ ($\downarrow$) | 12.10±0.10 | 8.80±0.20 | 5.60±0.08 | 5.30±0.09 | 7.77 ±0.25 | 5.21 ±0.12 | 5.40±0.02 |  |
| $\%\Delta EQOP$ ($\downarrow$) | 14.50±0.10 | 9.20±0.10 | 5.90±0.10 | 5.10±0.00 | 5.56 ±0.21 | 4.95 ±0.13 | 4.50±0.01 |  |
| German | AVPR ($\uparrow$) | 0.75±0.00 | 0.72 ±0.00 | 0.73±0.00 | 0.72±0.01 | 0.70 ±0.01 | 0.73 ±0.00 | 0.74±0.00 |
| F1 score ($\uparrow$) | 0.78±0.01 | 0.73 ±0.00 | 0.73±0.00 | 0.72±0.01 | 0.72±0.00 | 0.72 ±0.00 | 0.74±0.00 |  |
| %$\Delta DP$ ($\downarrow$) | 8.30±0.10 | 5.02±0.20 | 5.70 ±0.30 | 4.20±0.00 | 4.37 ±3.06 | 4.05 ±0.08 | 2.74±0.02 |  |
| $\%\Delta EQOP$ ($\downarrow$) | 7.40±0.08 | 6.24±0.20 | 5.70±0.20 | 5.90±0.01 | 3.63 ±3.03 | 4.2 ±0.13 | 1.70±0.04 |  |
| NBA | AVPR ($\uparrow$) | 0.76±0.00 | 0.73±0.00 | 0.73±0.00 | 0.73±0.00 | 0.73 ±0.07 | 0.73 ±0.01 | 0.74±0.00 |
| F1 score ($\uparrow$) | 0.73±0.00 | 0.67 ±0.00 | 0.70±0.00 | 0.69±0.00 | 0.69 ±0.05 | 0.70 ±0.02 | 0.71±0.00 |  |
| %$\Delta DP$ ($\downarrow$) | 13.10±0.02 | 6.40±0.04 | 1.20±0.03 | 1.50±0.05 | 2.39 ±1.2 | 1.5 ±0.21 | 1.10±0.04 |  |
| $\%\Delta EQOP$ ($\downarrow$) | 11.50±0.02 | 5.50±0.02 | 5.30±0.00 | 3.10±0.03 | 4.19 ±2.1 | 3.9 ±0.07 | 2.70±0.01 |  |
| pokec-z | AVPR ($\uparrow$) | 0.76±0.00 | 0.72±0.00 | 0.72±0.00 | 0.73±0.00 | 0.72 ±0.07 | 0.71 ±0.05 | 0.73±0.00 |
| F1 score ($\uparrow$) | 0.73±0.00 | 0.69 ±0.00 | 0.70±0.00 | 0.69±0.00 | 0.68 ±0.01 | 0.71 ±0.03 | 0.71±0.00 |  |
| %$\Delta DP$ ($\downarrow$) | 12.10±0.01 | 7.40±0.02 | 5.20±0.01 | 5.51±0.04 | 5.69 ±1.1 | 5.98 ±1.06 | 4.10±0.04 |  |
| $\%\Delta EQOP$ ($\downarrow$) | 16.50±0.01 | 8.50±0.06 | 3.30±0.00 | 2.10±0.03 | 4.19 ±1.9 | 2.1 ±1.09 | 1.70±0.03 |  |
| pokec-n | AVPR ($\uparrow$) | 0.74±0.00 | 0.71±0.00 | 0.72±0.00 | 0.72±0.00 | 0.70 ±0.08 | 0.71 ±0.02 | 0.72±0.00 |
| F1 score ($\uparrow$) | 0.75±0.00 | 0.70 ±0.00 | 0.71±0.00 | 0.71±0.00 | 0.70 ±0.03 | 0.72 ±0.04 | 0.73±0.00 |  |
| %$\Delta DP$ ($\downarrow$) | 11.10±0.02 | 5.40±0.01 | 2.10±0.01 | 2.50±0.01 | 2.39 ±1.7 | 2.12 ±0.98 | 1.89±0.02 |  |
| $\%\Delta EQOP$ ($\downarrow$) | 10.50±0.01 | 5.50±0.02 | 3.10±0.00 | 2.90±0.01 | 3.19 ±2.2 | 2.1 ±0.85 | 1.80±0.01 |  |

**Table 4: AVPR, F1, % $\Delta$DP, and % $\Delta$ EQOP of different methods. GAT is the GNN architecture for all models. For the Bail dataset, our model outperforms every other baseline in terms of fairness and accuracy. For the German, NBA and Credit datasets, we perform more fairly but less accurately.**
|  |  | VANILLA | DEBIAS | FAIRGNN | RNF | FairVGNN | FairSIN | BFtS (Ours) |
| --- | --- | --- | --- | --- | --- | --- | --- | --- |
| Bail | AVPR ($\uparrow$) | 0.88±0.00 | 0.81±0.00 | 0.81±0.00 | 0.82±0.00 | 0.82 ±0.01 | 0.83 ±0.01 | 0.84±0.00 |
| F1 ($\uparrow$) | 0.71±0.00 | 0.59 ±0.00 | 0.68±0.00 | 0.62±0.003 | 0.66±0.01 | 0.69 ±0.02 | 0.70±0.00 |  |
| $\%\Delta$DP ($\downarrow$) | 11.10±0.04 | 12.70±0.04 | 8.20±0.03 | 9.80±0.05 | 8.48 ±0.51 | 8.31 ±0.03 | 7.9±0.04 |  |
| $\%\Delta$EQOP ($\downarrow$) | 8.90±0.01 | 6.50±0.06 | 4.30±0.03 | 5.90±0.01 | 5.88 ±0.08 | 3.96 ±0.21 | 2.80±0.02 |  |
| Credit | AVPR ($\uparrow$) | 0.79±0.00 | 0.73±0.00 | 0.75±0.00 | 0.75 ±0.01 | 0.76±0.00 | 0.74 ±0.00 | 0.74±0.00 |
| F1 ($\uparrow$) | 0.71±0.00 | 0.68 ±0.00 | 0.69±0.00 | 0.71±0.00 | 0.70 ±0.00 | 0.70 ±0.00 | 0.71±0.00 |  |
| $\%\Delta$DP ($\downarrow$) | 14.20±0.02 | 9.10 ±0.02 | 8.02±0.05 | 6.40±0.04 | 6.70 ±0.05 | 5.01 ±0.20 | 4.20±0.02 |  |
| $\%\Delta$EQOP ($\downarrow$) | 18.30±0.20 | 15.12±0.08 | 12.15±0.10 | 10.95±0.06 | 9.75±0.09 | 9.31 ±0.09 | 8.60±0.04 |  |
| German | AVPR ($\uparrow$) | 0.73±0.00 | 0.70 ±0.00 | 0.71±0.00 | 0.72±0.00 | 0.71±0.00 | 0.70 ±0.00 | 0.71±0.00 |
| F1 ($\uparrow$) | 0.74±0.00 | 0.71 ±0.00 | 0.70±0.00 | 0.72±0.01 | 0.71 ±0.00 | 0.71 ±0.01 | 0.72±0.00 |  |
| $\%\Delta$DP ($\downarrow$) | 9.80±0.07 | 6.12±0.06 | 6.70 ±0.10 | 7.10±0.00 | 6.01±0.06 | 5.01 ±0.02 | 4.1±0.04 |  |
| $\%\Delta$EQOP ($\downarrow$) | 10.80±0.04 | 6.70±0.10 | 5.80±0.04 | 6.10±0.06 | 5.20±0.07 | 4.13 ±0.09 | 3.90±0.04 |  |
| NBA | AVPR ($\uparrow$) | 0.74±0.00 | 0.70±0.00 | 0.71±0.00 | 0.72±0.00 | 0.71±0.00 | 0.70 ±0.00 | 0.71±0.00 |
| F1 ($\uparrow$) | 0.79±0.00 | 0.75 ±0.00 | 0.75±0.00 | 0.75±0.00 | 0.75±0.01 | 0.74 ±0.08 | 0.76±0.00 |  |
| $\%\Delta$DP ($\downarrow$) | 7.60±0.03 | 4.20±0.03 | 2.30±0.01 | 3.10±0.04 | 2.10±0.04 | 3.19 ±0.10 | 2.01±0.01 |  |
| $\%\Delta$EQOP ($\downarrow$) | 11.20±0.03 | 5.40±0.04 | 3.30±0.01 | 3.30±0.01 | 3.12±0.05 | 2.91 ±0.05 | 2.10±0.01 |  |
| pokec-z | AVPR ($\uparrow$) | 0.78±0.00 | 0.73±0.00 | 0.74±0.00 | 0.73±0.00 | 0.73 ±0.07 | 0.74 ±0.05 | 0.74±0.00 |
| F1 score ($\uparrow$) | 0.75±0.00 | 0.71 ±0.00 | 0.72±0.00 | 0.72±0.00 | 0.73 ±0.01 | 0.73 ±0.03 | 0.74±0.00 |  |
| %$\Delta DP$ ($\downarrow$) | 10.19±0.07 | 8.21±0.08 | 5.98±0.07 | 5.18±0.08 | 5.79 ±1.08 | 4.98 ±2.01 | 3.90±0.05 |  |
| $\%\Delta EQOP$ ($\downarrow$) | 12.13±0.01 | 6.85±0.02 | 2.98±0.02 | 2.38±0.07 | 3.15 ±2.01 | 2.90 ±1.07 | 1.98±0.01 |  |
| pokec-n | AVPR ($\uparrow$) | 0.75±0.00 | 0.72±0.00 | 0.72±0.00 | 0.72±0.00 | 0.71±0.08 | 0.72 ±0.04 | 0.73±0.00 |
| F1 score ($\uparrow$) | 0.78±0.00 | 0.75 ±0.00 | 0.75±0.00 | 0.74±0.00 | 0.74 ±0.02 | 0.75 ±0.01 | 0.76±0.00 |  |
| %$\Delta DP$ ($\downarrow$) | 14.10±0.01 | 6.51±0.02 | 3.40±0.02 | 4.12±0.02 | 2.98 ±1.9 | 2.75 ±1.2 | 1.89±0.02 |  |
| $\%\Delta EQOP$ ($\downarrow$) | 12.50±0.07 | 5.50±0.02 | 3.10±0.00 | 2.90±0.01 | 3.19 ±2.2 | 2.1 ±0.85 | 1.80±0.01 |  |

### Imputation Accuracy

Table [5](https://arxiv.org/html/2311.01591v4#Ax9.T5) shows the imputation accuracy of the methods. We exclude results for Debias, which is based only on the sensitive information available, and for FairVGNN and FairSIN, as they are identical to FairGNN (same imputation method). The results show that BFtS imputation outperforms independent imputation methods. BFtS worst-case imputation based on the LDAM loss outperforms the alternatives in terms of accuracy. This is due to the adversarial missingness process where low-degree nodes are selected to have missing values. Independent imputation methods are less effective in this adversarial setting.

**Table 5: Accuracy of missing sensitive imputation.**
|  | German | Credit | Bail | NBA | pokec-z | pokec-n |
| --- | --- | --- | --- | --- | --- | --- |
| FairGNN | 0.70 | 0.90 | 0.56 | 0.78 | 0.81 | 0.84 |
| RNF | 0.59 | 0.73 | 0.53 | 0.64 | 0.65 | 0.68 |
| BFtS | 0.72 | 0.94 | 0.63 | 0.78 | 0.83 | 0.87 |

Figure: Figure 9: 2-D kernel PCA node representations for the Bail dataset generated by the FairGNN and BFtS (our approach). We use different markers for nodes depending on their predicted class, sensitive attribute (race), and whether the sensitive attribute is missing. The results show that representations for nodes with missing values are more biased for FairGNN where they are concentrated in a negative class region. On the other hand, nodes with missing values are better spread over the space for BFtS representations. In BFtS, there are more "Race = Black" nodes than in FairGNN that have missing sensitive values in training but are predicted to be positive.
Refer to caption: x11.png

## Additional Experiments

Table [3](https://arxiv.org/html/2311.01591v4#Ax9.T3) shows the average results for Bail, Credit, German, and NBA datasets. In terms of accuracy and fairness, BFtS outperforms all baseline approaches for the Bail and NBA datasets. We also outperform competitors on the Credit and German datasets in terms of fairness, with a slight AVPR loss. Although we lose some AVPR in the German and Credit datasets, we win in F1 and the AVPR loss is negligible when compared to the fairness benefit.
Table [4](https://arxiv.org/html/2311.01591v4#Ax9.T4) shows the average results for Bail, Credit, German, and NBA datasets. We have used GAT [67] to train $f_{C}$ and $f_{I}$. In terms of accuracy and fairness, BFtS outperforms all baseline approaches for the Bail dataset. We also outperform competitors on the Credit, German, and NBA datasets in terms of fairness with a slight AVPR loss. The AVPR loss is negligible when compared to the fairness benefit.
Figure [9](https://arxiv.org/html/2311.01591v4#Ax9.F9) shows kernel PCA node representations produced by FairGNN and BFtS using the Bail dataset. We show the samples with missing "Race" with a navy dot in the middle and samples predicted as positive class and negative class in green and red, respectively. The representations generated by FairGNN are noticeably more biased than the ones generated by our approach. A higher number of "Race = Black" samples with missing sensitive values in training are predicted as positive by BFtS than for FairGNN. Moreover, BFtS spreads nodes with missing values more uniformly over the space. This illustrates how the missing value imputation of FairGNN underestimates the bias in the training data and, therefore, the model could not overcome the bias in the predictions.

## Ablation Study

To see the impact of $\alpha$ and $\beta$, we train BFtS on the German dataset with different values of $\alpha$ and $\beta$. We consider values between $[10^{-3},10^{-2},10^{-1},1,10]$ for both $\alpha$ and $\beta$. Figure [7](https://arxiv.org/html/2311.01591v4#Ax9.F7) shows the $\Delta$DP and F1 of BFtS on the German dataset. $\alpha$ and $\beta$ control the impact of the adversarial loss $\mathcal{L}_{A}$ on the GNN classifier and the missing value imputation GNN, respectively. The figure shows that $\alpha$ has a larger impact than $\beta$ on the fairness and accuracy of the model.

We also vary the amount of observed data $\mathcal{V}_{S}$ and plot the results in Figure [8](https://arxiv.org/html/2311.01591v4#Ax9.F8). We use $20\%,30\%,40\%$, and $50\%$ of training nodes as $\mathcal{V}_{S}$. For nearly all models, fairness increases and accuracy decreases with $|\mathcal{V}_{S}|$. With BFtS, both accuracy and bias often decline with the increase of $\mathcal{V}_{S}$. In the majority of the settings, our approach (BFtS) achieves a better fairness $\times$ accuracy trade-off than the baselines.

To see the impact of LDAM loss, we train $f_{I}$ with cross-entropy loss and compare the performance with $f_{I}$ trained with LDAM loss in Table [6](https://arxiv.org/html/2311.01591v4#Ax11.T6). Evidently, LDAM achieves a better trade-off between accuracy and fairness.

**Table 6: Ablation study using LDAM loss and cross-entropy loss for $f_{I}$. Using LDAM loss gives a better fairness and accuracy trade-off.**
|  | Cross Entropy $f_{I}$ | LDAM $f_{I}$ |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- |
| AVPR ($\uparrow$) | F1 ($\uparrow$) | $\%\Delta$DP ($\downarrow$) | $\%\Delta$EQOP ($\downarrow$) | AVPR($\uparrow$) | F1($\uparrow$) | $\%\Delta$DP ($\downarrow$) | $\%\Delta$EQOP ($\downarrow$) |  |
| German | 0.75 ±0.00 | 0.73 ±0.00 | 4.10 ±0.05 | 3.70 ±0.03 | 0.74 ±0.00 | 0.74 ±0.00 | 2.74 ±0.02 | 1.7 ±0.04 |
| Credit | 0.83 ±0.00 | 0.77 ±0.01 | 5.55 ±0.03 | 4.70 ±0.05 | 0.83 ±0.00 | 0.76 ±0.00 | 5.4 ±0.02 | 4.5 ±0.01 |
| Bail | 0.85 ±0.00 | 0.85 ±0.00 | 7.10 ±0.02 | 3.1 ±0.06 | 0.83 ±0.00 | 0.85 ±0.00 | 6.70 ±0.03 | 2.7 ±0.01 |
| NBA | 0.75 ±0.00 | 0.72 ±0.00 | 2.11 ±0.03 | 3.5 ±0.02 | 0.74 ±0.00 | 0.71 ±0.00 | 1.10 ±0.04 | 2.70 ±0.01 |
| Simulation | 0.94 ±0.00 | 0.96 ±0.00 | 16.00 ±0.03 | 8.00 ±0.08 | 0.92 ±0.00 | 0.96 ±0.01 | 12.00 ±0.03 | 5.10 ±0.04 |

## Ethical Considerations

Some of the ethical considerations related to our work include privacy, fairness, sustainability, and transparency. Our work is motivated by fairness and privacy. More specifically, missing sensitive values might be because users do not want to disclose their private data. Sustainability and transparency are not the focus of our work. However, we believe that existing methods for interpretable machine learning can improve the transparency of our model. The datasets used in our method are all public information and do not disclose private information from users.

### Reproducibility

Our code can be found in an anonymous repository(^1^11[https://anonymous.4open.science/r/BFtS-6ADA](https://anonymous.4open.science/r/BFtS-6ADA)).

## Peer Reviews

confidence: 3
contribution: 3
initial_rating: 6
presentation: 3
questions: 1. Limited theoretical depth
The theoretical results provide general insights but remain high-level. The proofs are brief and do not include convergence or generalization guarantees for the proposed min–max training objective. A more formal analysis of the optimization dynamics would strengthen the paper.

2. Comparison to related methods
While the paper compares BFtS with existing fair graph learning approaches, it could more clearly articulate how its mechanism differs from other fairness-aware imputation or robustness frameworks. The conceptual novelty may appear incremental without deeper discussion.

3. Experimental diversity
The adversarial missingness is modeled primarily through degree bias, which may not capture all possible real-world scenarios. Including other structural or attribute-based missingness patterns would make the empirical evaluation more convincing.

4. Fairness metrics and discussion
The choice of fairness metrics (Demographic Parity and Equality of Opportunity) is standard, but the paper could briefly justify why these particular measures were selected and whether the method generalizes to others.
soundness: 3
strengths: 1. Novel and important problem
The paper targets a realistic setting where sensitive attributes are not missing at random, which is often overlooked in existing fair graph learning literature. Formulating this as an adversarial missingness problem is both intuitive and practically meaningful.

2. Methodological soundness
The three-player adversarial design is conceptually well-motivated and integrates ideas from fairness, robust optimization, and adversarial learning into a unified framework. The training procedure is clearly described and the objectives are well defined.

3. Comprehensive experiments
The evaluation covers both synthetic and real-world datasets, reporting multiple fairness and accuracy metrics. The results consistently show that BFtS outperforms baseline methods under different missingness settings.
summary: This paper investigates the problem of fair graph learning when sensitive attributes are missing under an adversarial missingness process. The authors propose Better Fair than Sorry (BFtS), a three-player adversarial framework involving a graph classifier, a bias discriminator, and a missing-value imputer. The method aims to enhance fairness robustness by simulating worst-case imputations. Both theoretical arguments and empirical evaluations are presented, demonstrating that BFtS achieves superior fairness–accuracy trade-offs on multiple graph datasets compared to existing methods.
weaknesses: 1. Limited theoretical depth
The theoretical results provide general insights but remain high-level. The proofs are brief and do not include convergence or generalization guarantees for the proposed min–max training objective. A more formal analysis of the optimization dynamics would strengthen the paper.

2. Comparison to related methods
While the paper compares BFtS with existing fair graph learning approaches, it could more clearly articulate how its mechanism differs from other fairness-aware imputation or robustness frameworks. The conceptual novelty may appear incremental without deeper discussion.

3. Experimental diversity
The adversarial missingness is modeled primarily through degree bias, which may not capture all possible real-world scenarios. Including other structural or attribute-based missingness patterns would make the empirical evaluation more convincing.

4. Fairness metrics and discussion
The choice of fairness metrics (Demographic Parity and Equality of Opportunity) is standard, but the paper could briefly justify why these particular measures were selected and whether the method generalizes to others.

5. Presentation details
Some notations are inconsistent between equations, and the visual presentation of a few figures could be improved for clarity.

---

confidence: 2
contribution: 3
initial_rating: 4
presentation: 2
questions: Please see Weaknesses
soundness: 3
strengths: - The work identifies a realistic yet overlooked issue: adversarial missingness of sensitive attributes, which can mislead fairness evaluations in graph learning, and formalizes two adversarial missingness problems (AMAFC, AMADB) 

- Theorems 2 and 3 clearly demonstrate that BFtS minimizes worst-case bias and approximates robust fairness

- Extensive evaluations are conducted across synthetic and real-world datasets. Empirical results consistently show superior fairness–accuracy trade-offs and robustness under limited or missing sensitive data

- The paper is well organized and easy to follow
summary: This paper studies graph fairness when demographic attributes are partially observed under adversarial missingness processes.
It introduces BFtS (Better Fair than Sorry), a 3-player adversarial learning framework combining a GNN classifier, a fairness adversary, and an imputation adversary. BFtS imputes worst-case sensitive attributes to make fairness evaluation robust under adversarial missingness. Both theoretical analyses and empirical results demonstrate superior tradeoffs between fairness and accuracy compared to baselines.
weaknesses: - The practicality of adversarial missingness is vague. Whether a value is missing or not seems to be difficult to control by adversaries. If the adversaries can deliberately drop some values, in this case, modifying these values seems to be a stronger adversary we can think about. It would be helpful to add more discussions on the practical scenarios of adversarial missingness in real-world cases.

- It would be helpful to add an introduction of the threat model setting in the main text.

- The bilevel optimization raises concerns about training stability. Although the authors propose the loss curve in Figure 6, it seems that Figure 6 is plotted with only a few points. It would be helpful if the training stability could be better shown in the experiments.

- It seems that the proportion of missing sensitive attributes is more than 50% of the total nodes in Figure 8. It would be helpful to see more experimental results under more stealthy attack settings.

---

confidence: 4
contribution: 3
initial_rating: 6
presentation: 2
questions: 1. How sensitive is BFtS to hyperparameter tuning, especially the fairness weight (α) and imputation adversary weight (β)? Could the authors provide empirical or theoretical guidance on selecting them?
2. Does the degree-bias assumption for adversarial missingness generalize to graphs with highly non-homophilous structures?
3. Could BFtS be extended to handle multi-valued or continuous sensitive attributes rather than binary ones?
4. Is there any evidence of mode collapse or instability during the 3-player adversarial training, and if so, how is it mitigated?
soundness: 3
strengths: 1. This paper has principled theoretical grounding, clear definitions, and basic robust justification.
2. This paper proposes an innovative framework with 3-player adversarial setup elegantly unifies imputation, fairness estimation, and classification.
3. Extensive experiments on both synthetic and real-world benchmarks and the robustness is shown under varying degrees of missingness.
summary: This paper addresses a critical and underexplored problem in fair graph machine learning: the effect of adversarial missingness of sensitive attributes on fairness-aware Graph Neural Networks (GNNs). The authors argue that prior fairness methods assume that sensitive attributes are either fully available or missing completely at random (MCAR), which is unrealistic in practice. To overcome this limitation, the paper introduces Better Fair than Sorry (BFtS), a 3-player adversarial framework that jointly learns a node classifier, a fairness adversary that predicts sensitive attributes from learned embeddings, and an imputation adversary that imputes missing sensitive attributes to approximate the worst-case fairness scenario. Moreover, the authors provide theoretical analysis showing that BFtS corresponds to a min–max optimization that minimizes classifier bias under worst-case imputations.
weaknesses: 1. The 3-player adversarial training could be computationally heavy, particularly on large-scale graphs. A detailed runtime or memory comparison would strengthen the empirical analysis.
2. The study focuses on Demographic Parity (ΔDP) and Equality of Opportunity (ΔEQOP). It would be beneficial to include other fairness notions (e.g., Equalized Odds, Counterfactual Fairness) for completeness.
3. While the adversarial imputation approach is conceptually powerful, there is little discussion of how it performs under realistic partial observability (e.g., when only 5–10% of sensitive data is known).
4. The intuition behind the imputation adversary’s learned behavior could be further explored, perhaps via visualization or sensitivity analysis.


Decision: Accept (Poster)