FairGSE: Fairness-Aware Graph Neural Network without High False Positive Rates

AI summary

Overview

Research area: Fairness in graph machine learning, specifically fairness-aware Graph Neural Networks (GNNs) for node classification on attributed graphs.

Technical level: Intermediate — the paper is readable with a basic background in GNNs and classification metrics, but its core argument rests on structural entropy bounds and information-theoretic arguments that benefit from familiarity with information theory.

Scope in one sentence: The paper diagnoses a previously under-examined failure mode of fairness-aware GNNs (fairness achieved by predicting almost everything as positive, producing very high False Positive Rates) and proposes FairGSE, a framework that maximizes two-dimensional structural entropy over a sensitive-attribute partition to reduce FPR while retaining competitive fairness.

What This Paper Is About

Existing fairness-aware GNNs are tuned to satisfy fairness metrics such as Statistical Parity (ΔSP) and Equal Opportunity (ΔEO), but those metrics only look at positive predictions and true positive rates within sensitive groups. The authors observe that a model can score near-perfect fairness simply by labelling nearly every node positive, which in high-stakes settings means flagging almost everyone as high-risk. The goal of the paper is to improve group fairness without letting the model take this "FPR shortcut," and to give that goal a theoretical formulation rather than just an empirical one.

Key Contributions

1. Identification of the FPR shortcut. The paper pioneers the observation that fairness-aware GNNs can improve ΔSP and ΔEO primarily by inflating the False Positive Rate, a failure that standard fairness metrics do not capture.
2. A bound-based formulation. The trade-off between fairness and FPR is cast as an optimization problem constrained by an upper bound on a two-dimensional structural entropy (2D-SE) objective defined over the sensitive-attribute partition of the graph.
3. The FairGSE framework. A GNN framework that adaptively reweights graph edges to maximize 2D-SE, combined with contrastive learning to preserve original structural information and a structure bootstrapping mechanism to slowly refine the anchor view.
4. Empirical evaluation. Experiments on Credit, Pokec_n and Pokec_z against eight baselines (Vanilla GCN plus seven fairness-aware GNN methods), reporting the abstract's headline result of a 39% FPR reduction versus state-of-the-art fairness-aware GNNs with comparable fairness improvement.

Main Findings

• Fairness metrics can be gamed by predicting positives. On the Credit dataset, FairSIN reports ΔSP of 0.52 ± 0.45 and ΔEO of 0.40 ± 0.34 while its FPR reaches 99.76 ± 0.37 — the paper describes this as classifying nearly all customers as credit card defaulters. FairVGNN shows a similar pattern with FPR 90.70 ± 8.44.

• FairGSE reduces FPR on the imbalanced Credit dataset. FairGSE records an FPR of 41.45 ± 1.23, compared with 45.96 ± 11.38 for Vanilla GCN and 42.73 ± 2.32 for EDITS. The paper reports that FairGSE reduces FPR by 9.81% versus Vanilla GCN while decreasing ΔSP and ΔEO by 65.21% and 72.62% respectively.

• Comparison with the strongest fairness baseline on Credit. Relative to FairSIN, FairGSE improves AUC by 4.88% (74.53 ± 0.39 versus 71.99 ± 0.86) and reduces FPR by 58.45%, at the cost of slightly higher ΔSP and ΔEO.

• Strong results on the balanced Pokec datasets. On Pokec_n, FairGSE reaches ACC 71.10 ± 0.41, AUC 77.24 ± 0.15, F1 67.22 ± 0.70, FPR 18.46 ± 0.34, ΔSP 0.90 ± 0.46 and ΔEO 1.38 ± 1.10, with the paper stating FairGSE reduces FPR by nearly 39.34% versus the second-best method. On Pokec_z it records ACC 70.30 ± 0.07, AUC 78.08 ± 0.13, F1 70.04 ± 0.12, FPR 22.80 ± 0.75, ΔSP 0.96 ± 0.25 and ΔEO 1.38 ± 0.11.

• EDITS could not run on the Pokec graphs. EDITS is marked OOM on both Pokec_n and Pokec_z, which the paper defines as out-of-memory on a GPU with 24GB memory.

• Ablation results differ by component. Removing the graph structure learner (keeping only contrastive learning) yields much higher FPR on the imbalanced Credit data while fairness metrics stay relatively strong. Removing contrastive learning (training only on 2D-SE maximization) improves FPR and fairness over Vanilla GCN but is less stable and falls short of the full model. Removing the structure bootstrapping mechanism leaves metrics broadly comparable, but on Credit fairness improves noticeably when bootstrapping is included.

• Hyperparameter behaviour. Increasing λ1 generally improves fairness, but as λ1 grows further the anchor view pulls the model toward high FPR; λ1 = 0.5 gives the best fairness–FPR trade-off on Credit. Setting λ2 too large makes the entropy term dominate the loss and prevents effective 2D-SE maximization, so smaller λ2 gives a better fairness–FPR trade-off.

Methodology in Plain English

The paper starts from a measure called structural entropy, which quantifies how much uncertainty is needed to encode a graph given a partition of its nodes. The authors adapt this to a two-dimensional version (2D-SE) using the simplest possible partition: nodes split into two groups by their binary sensitive attribute. Intuitively, a higher 2D-SE means edges are spread more evenly across sensitive groups rather than concentrated within them, and that degrees within a sensitive group are more uniform across labels — which the authors argue reduces both group disparity and the neglect of negative labels.

They prove two things about this quantity. First, the 2D-SE is differentiable with respect to every edge weight, so it can be optimized by gradient descent. Second, maximizing it gives an upper bound on both ΔSP and ΔEO, and also an upper bound on FPR of the form r/(1+r) plus a term that shrinks as 2D-SE approaches its maximum, where r is the proportion of negative labels.

FairGSE then implements this idea in three parts. A graph structure learner assigns a trainable parameter to every existing edge, passes it through a sigmoid to produce a weight in (0,1), and minimizes the negative 2D-SE. Because continuously rewriting the whole adjacency matrix is unstable and can distort the graph, a contrastive learning component treats the original graph as an anchor view and the learned graph as a learner view, encodes both with a shared GNN encoder and projector, and aligns the two representations with an NT-Xent contrastive loss for the same node. Finally, rather than freezing the anchor view at the original (biased) graph, a structure bootstrapping mechanism updates it each epoch as a slow exponential moving average of the learned structure with a decay rate of 0.9999, so the anchor gradually absorbs the higher-entropy structure. The overall objective combines the classification loss, the contrastive loss weighted by λ1, and the negative entropy term weighted by λ2.

Implementation used a 2-layer GCN backbone with hidden size 64, a 32-dimensional 2-layer MLP projector, a 2-layer MLP classifier, learning rate 0.001, weight decay 1e-5, node splits of training 50% (or each baseline's default), validation 25% and test 25%, on a single NVIDIA RTX 3090 GPU with 24GB memory.

Why This Matters

Impact on research. The paper reframes fairness evaluation: it shows that ΔSP and ΔEO alone admit degenerate solutions and argues for FPR to be reported alongside them. It also contributes a theoretical bridge between structural entropy — previously used for robustness, node classification and anomaly detection — and fairness.

Real-world applications:

• Credit risk scoring, the Credit dataset's setting, where a high FPR means incorrectly classifying poor-credit applicants as reliable.
• Recidivism and bail decisions, the setting of the Recidivism graph mentioned in the introduction, where a high FPR means treating high-risk offenders as low-risk.
• Social network analysis, the Pokec datasets' setting, where region (used as the sensitive attribute) should not drive predictions about users.
• Any high-stakes node classification pipeline with imbalanced labels, where the positive class is the costly one to over-predict.

Industry relevance. Deployed graph models in finance, insurance, hiring and content moderation are increasingly subject to fairness auditing. A method that keeps fairness numbers competitive while producing far fewer false alarms is directly relevant to teams that must satisfy fairness constraints without generating unmanageable volumes of wrongly flagged users.

Future Directions

• Extending beyond binary settings. The framework is defined for a binary sensitive attribute and binary labels via the two-group partition; the authors state they intend to handle multi-class and edge prediction tasks.
• Limited or unavailable sensitive attributes. The paper's future work explicitly targets the case where sensitive attributes are missing or incomplete, which is common in practice.
• Generalizing the partition. Because 2D-SE is defined over a one-step partition, a natural question is whether higher-dimensional structural entropy over richer partitions improves the fairness–FPR trade-off.
• Sensitivity of the loss weights. The hyperparameter study shows the fairness–FPR balance is governed by λ1 and λ2 and that too-large λ2 defeats the entropy objective, leaving open how to set these weights reliably across datasets.

Target Audience

Researchers and graduate students working on graph neural networks, algorithmic fairness, or trustworthy machine learning; practitioners auditing or deploying GNN-based decision systems in finance, criminal justice and social platforms; and readers interested in applications of structural entropy to learning problems, who will find the theoretical bounds the most distinctive part of the paper.

Authors’ abstract

Graph neural networks (GNNs) have emerged as the mainstream paradigm for graph representation learning due to their effective message aggregation. However, this advantage also amplifies biases inherent in graph topology, raising fairness concerns. Existing fairness-aware GNNs provide satisfactory performance on fairness metrics such as Statistical Parity and Equal Opportunity while maintaining acceptable accuracy trade-offs. Unfortunately, we observe that this pursuit of fairness metrics neglects the GNN's ability to predict negative labels, which renders their predictions with extremely high False Positive Rates (FPR), resulting in negative effects in high-risk scenarios. To this end, we advocate that classification performance should be carefully calibrated while improving fairness, rather than simply constraining accuracy loss. Furthermore, we propose Fair GNN via Structural Entropy (\textbf{FairGSE}), a novel framework that maximizes two-dimensional structural entropy (2D-SE) to improve fairness without neglecting false positives. Experiments on several real-world datasets show FairGSE reduces FPR by 39\% vs. state-of-the-art fairness-aware GNNs, with comparable fairness improvement.