In high-stakes domains like credit scoring or hiring, Graph Neural Networks (GNNs) are often used to make predictions based on how individuals are connected. To ensure these models are fair, researchers typically use sensitive attributes—such as race or gender—to measure and mitigate bias.
However, a significant problem arises in the real world: sensitive data is often missing. Most existing fairness techniques assume that this data is "Missing Completely at Random" (MCAR). But as Debolina Halder Lina and Arlei Lopes da Silva demonstrate in Fair Graph Machine Learning under Adversarial Missingness Processes, this assumption creates a "fairness mirage." If data is missing in a structured or strategic way, a model can appear perfectly equitable while actually harboring deep systemic disparities.
The Failure of Average Case Imputation
When sensitive attributes are missing, the standard approach is to use an imputer to predict the most likely values for the missing data. These imputers are usually optimized for reconstruction accuracy—they want to be "right" as often as possible.
The insight from Lina and da Silva is that accuracy-driven imputation is fundamentally misaligned with fairness. If a dataset has "adversarial missingness"—where sensitive information is withheld specifically for individuals where the model's bias is most extreme—an accurate imputer will likely smooth over these outliers. By filling in the "most likely" values, the imputer hides the very disparities the fairness auditor is looking for. In some graph-based scenarios, this can lead models to report bias levels that are 400% lower than the actual disparity.
Better Fair than Sorry: A Three Player Game
To solve this, the researchers propose a framework called Better Fair than Sorry (BFtS). Instead of trying to guess the "true" missing values, BFtS adopts a minimax strategy: it prepares for the worst-case scenario.
The framework operates as a three-player adversarial game:
- The Classifier: Tries to predict the target label (e.g., "will this person repay a loan?") while minimizing bias.
- The Auditor: Evaluates the classifier’s predictions to detect any correlation with sensitive attributes.
- The Imputation Adversary: This is the key innovation. Instead of trying to be accurate, the imputer strategically fills in missing values to maximize the bias detected by the auditor.
By forcing the imputer to act as an adversary, the system uncovers the "worst-case" fairness scenario. It asks: "If the missing data were distributed in the most damaging way possible, would my model still be fair?"
Why Adversarial Imputation Works
This approach shifts the goal from "predicting the missing" to "bounding the bias." When the classifier is trained against an adversarial imputer, it cannot rely on the absence of data to hide its discriminatory patterns.
In a graph context, this is particularly powerful. Nodes with low connectivity often have their attributes withheld, and standard GNNs struggle to generalize to these "isolated" points. By simulating a worst-case distribution of sensitive attributes for these nodes, the minimax optimization forces the GNN to develop representations that are robust to structured omissions.
The result is a model that doesn't just look fair on a spreadsheet of incomplete data, but remains equitable even when the missingness process is designed to obscure systemic bias.