TL;DR
When users exercise their "right to be forgotten" by deleting their data from social networks, existing graph unlearning methods inadvertently destroy the model's fairness guarantees, making downstream predictions significantly more biased. FairGU solves this problem by integrating a private sensitive attribute estimator, adversarial debiasing, and a Fisher Information Matrix-based parameter dampening mechanism to erase requested data while strictly preserving both model utility and algorithmic fairness.
What Problem Does This Paper Address?
Privacy regulations like GDPR mandate that platforms honor a user's "right to be forgotten." In graph-structured environments like social networks or e-commerce platforms, this requires graph unlearning—efficiently removing a node (and its connected edges) from a trained Graph Neural Network (GNN) without the massive computational cost of retraining the model from scratch.
However, the authors uncover a critical, previously overlooked flaw in current state-of-the-art (SOTA) graph unlearning techniques: they severely degrade algorithmic fairness. When nodes are forcibly removed, the resulting structural and informational gaps disrupt pre-trained fairness regularizers. As a result, the unlearned models become unexpectedly sensitive to protected attributes (like race, gender, or region), amplifying discrimination against marginalized subgroups.
Methods
To bridge the gap between privacy (unlearning) and equity (fairness), the authors introduce FairGU, a framework consisting of three tightly integrated components:
- Sensitive Attribute Estimator (SAE): Real-world datasets often have missing or incomplete sensitive attributes due to privacy choices. FairGU pre-trains a Graph Convolutional Network (GCN) to privately infer these missing attributes as proxies, avoiding the privacy risks of generating synthetic data.
- Fairness-aware Controlling: During the primary training phase, FairGU employs a dual-pronged approach to learn attribute-invariant node representations. It pairs a GNN classifier with an adversarial debiasing module (a min-max game where the adversary tries to guess the sensitive attribute from the embeddings) and applies a covariance constraint to minimize the statistical dependence between predictions and sensitive attributes.
- FIM-based Graph Unlearning: When an unlearning request arrives, instead of completely retraining or crudely pruning nodes, FairGU calculates the diagonal elements of the Fisher Information Matrix (FIM). This allows the framework to identify which model parameters are highly specialized for the "forget set" versus the "retain set." It then applies a targeted dampening factor to selectively reduce the magnitude of those specific parameters, erasing the influence of the deleted data without breaking the model's learned fairness properties.
Datasets
The framework was evaluated on three real-world datasets commonly used in fairness and graph learning literature:
- Income: A social network graph derived from the UCI Adult dataset, where edges represent individual similarities, the target is predicting high income, and the sensitive attribute is race.
- Pokec-z & Pokec-n: Large-scale social network datasets sampled from two different Slovakian provinces. The task is to predict a user's working field, with gender and region serving as the sensitive attributes.
Key Insights and Ideas
- Unlearning is Not Fairness-Neutral: Forcibly removing nodes creates structural blind spots that break built-in fairness constraints. Unlearning algorithms cannot just focus on erasing data; they must actively protect the model's ethical boundaries post-erasure.
- Dampening Beats Pruning: Completely removing or zeroing out parameters to forget data degrades overall model utility. Proportional parameter dampening based on FIM importance effectively "fades" specific memories while keeping general knowledge intact.
- Decoupled Pre-training is Crucial: The authors' ablation study revealed that trying to train the sensitive attribute estimator concurrently with the main model degrades fairness. Pre-training the estimator separately provides much more stable and robust fairness proxies.
Key Results
FairGU was tested against four SOTA graph unlearning methods (GER, IDEA, MEGU, ETR) and three fairness-enhanced GNN baselines adapted for unlearning.
- Massive Fairness Gains: FairGU achieved the lowest statistical parity disparity ($\Delta_{SP}$) and equal opportunity disparity ($\Delta_{EO}$) across all datasets. On the Pokec-n dataset, FairGU reduced statistical parity disparity by over 75% compared to standard unlearning baselines.
- No Sacrifice in Utility: Despite the strict fairness constraints, FairGU maintained node classification accuracies on par with or superior to the best-performing unlearning baselines (e.g., 67.05% accuracy on Pokec-n).
- Robust Privacy Protection: To ensure the data was truly forgotten, the authors ran a Membership Inference Attack (MIA). FairGU achieved an MIA AUC score close to 50% (equivalent to random guessing), proving that an adversary cannot reliably infer whether an unlearned node was ever part of the training set.
Limitations and Future Work
While FairGU demonstrates excellent performance, the authors note that it is highly sensitive to its hyperparameters—specifically the selectivity factor ($\gamma$) and the dampening strength ($\lambda$). In practical deployments, engineering teams will need to invest time into careful hyperparameter tuning to balance the exact trade-off between forgetting speed, accuracy, and bias mitigation.
Summary updated