FairGU: Fairness-aware Graph Unlearning in Social Networks

AI summary

Overview

Research area: Graph machine learning, specifically machine unlearning and algorithmic fairness on graph-structured social network data.

Technical level: Intermediate. The paper assumes familiarity with graph neural networks (GNNs), fairness metrics such as statistical parity and equality of opportunity, and the unlearning problem setting (forget sets vs. retain sets), but each component is defined in the preliminaries.

Scope: The paper introduces FairGU, a framework that combines sensitive-attribute estimation, adversarial and covariance-based fairness training, and Fisher Information Matrix (FIM)-based parameter dampening so that a GNN removes requested nodes or edges without losing the fairness properties learned during training.

What This Paper Is About

Existing graph unlearning methods are built to delete a user's data (nodes or edges) from a trained GNN efficiently, but the authors observe that these methods degrade algorithmic fairness — after unlearning, predictions become more dependent on sensitive attributes such as race, region, or gender. FairGU is proposed to close this gap by integrating fairness preservation directly into the unlearning pipeline, so that a model can honor deletion requests while still producing non-discriminatory predictions.

Key Contributions

1. The authors identify and document a limitation of existing graph unlearning methods: these methods insufficiently protect sensitive attributes and often degrade algorithmic fairness relative to traditional graph learning, which they describe as a previously overlooked risk for socially responsible web applications.

2. They propose a fairness-enhanced graph unlearning framework that pairs a fairness-control module with the unlearning step, so the model's equitable behavior is maintained after unlearning without reconstructing sensitive data in a way that creates new privacy risks.

3. They develop a precise unlearning mechanism based on Fisher Information Matrix importance analysis, which selects parameters that are disproportionately important to the forget set and dampens them multiplicatively rather than pruning them.

4. They conduct extensive experiments on public benchmark datasets (Income, Pokec-z, Pokec-n), reporting that FairGU outperforms state-of-the-art graph unlearning methods and fairness-aware baselines in both fairness and utility.

Main Findings

• Unlearning harms fairness: The authors compute fairness metrics for four graph unlearning methods (GER, IDEA, MEGU, ETR) and one fairness-aware graph learning method (FairAC), and report that existing graph unlearning strategies often significantly reduce fairness, leaving models unexpectedly more sensitive to protected attributes than traditional graph learning methods.

• Fairness–utility results on Pokec-n: FairGU reports ACC of 67.05 ± 0.77%, ΔSP of 0.74 ± 0.39%, and ΔEO of 1.54 ± 0.78%. The next-best accuracy among the listed baselines on this dataset is MEGU at 67.03 ± 1.14%, and the next-best ΔSP is MEGU at 3.72 ± 0.89%.

• Fairness–utility results on Pokec-z: FairGU reports ACC of 67.63 ± 0.77%, ΔSP of 1.12 ± 1.07%, and ΔEO of 0.58 ± 0.30%. The next-best accuracy is ETR at 65.87 ± 0.89%, and the next-best ΔSP is FairAC at 1.57 ± 0.51%.

• Fairness–utility results on Income: FairGU reports ACC of 80.40 ± 0.03%, ΔSP of 0.42 ± 0.07%, and ΔEO of 1.33 ± 0.39%, the best fairness numbers in the table. On accuracy for this dataset, ETR reports the highest value at 81.59 ± 0.09%, ahead of FairGU's 80.40 ± 0.03%.

• Membership inference risk is comparable to baselines: Table 3 reports MIA AUC scores, where a value closer to 50% is preferred because it corresponds to random guessing. FairGU reports 51.2 ± 0.9% on Pokec-n, 50.7 ± 1.0% on Pokec-z, and 50.2 ± 0.3% on Income. The best listed result on Pokec-n is ETR at 51.0 ± 0.8%, on Pokec-z is MEGU at 50.6 ± 0.4%, and on Income is FairGU at 50.2 ± 0.3%.

• Large fairness gaps in baselines: Several baselines show much larger disparities, for example IDEA on Pokec-n with ΔEO of 21.39 ± 2.79% and FairGNN on Income with ΔEO of 28.30 ± 2.17%.

Methodology in Plain English

FairGU runs in two phases.

The first phase is fairness-aware training. Because sensitive attributes are often missing in real social network data, the framework first trains a graph convolutional network estimator to predict sensitive attributes from node features and graph structure, using only nodes whose sensitive attribute is actually known. These predicted values serve as proxies for all nodes; the authors emphasize that this estimator approximates the original distribution without generating synthetic data. Next, a GNN classifier is trained together with two other components: an adversary (a linear classifier) that tries to predict the sensitive attribute from the learned node representations, and a covariance constraint that directly penalizes dependence between predictions and sensitive attributes. Training alternates between minimizing the combined classifier, estimator, covariance, and adversarial objectives, and maximizing the adversary's objective, so the representations become uninformative about the sensitive attribute.

The second phase is unlearning. Instead of retraining, the framework deletes the requested nodes and their edges to form an updated graph, then computes Fisher Information Matrix importance scores. The full FIM is too expensive to compute, so the authors use its diagonal, computed from first-order derivatives. Importance is measured twice: once for the entire training set (computed once after initial training and stored, allowing the original training data to be discarded) and once for the forget set. Parameters whose importance for the forget set exceeds a threshold controlled by γ times their importance for the training set are selected. Rather than pruning them, the framework multiplies each selected parameter by a dampening factor capped at 1, so parameters specialized for forgotten data shrink toward zero while generally useful parameters stay close to their original values. Because the update only reduces magnitudes, it cannot amplify parameters.

Experiments use a 5% node deletion task with removal of associated edges, an 80/20 train/evaluation split of nodes, and hardware consisting of an NVIDIA GeForce RTX 4070 GPU with Python 3.8.10, PyTorch 1.13.0, and CUDA 11.7.0. The sensitive attribute estimator is a one-hidden-layer GCN with hidden dimension 128, and the adversary is a linear classifier. The provided content is truncated while describing the GNN architectures used for validation, so the second architecture is not fully reported. Specific values for the hyperparameters α, β, λ, and γ are not reported in the available content.

Why This Matters

Impact on research: The paper reframes graph unlearning as a fairness problem rather than only a privacy and utility problem, and it argues that debiasing mechanisms optimized on the original data distribution can be disrupted when nodes are removed. It also connects the two previously separate literatures of graph unlearning and fairness-aware GNNs, noting that existing methods address either unlearning without fairness or fairness without native unlearning.

Real-world applications:

• Social media platforms responding to deletion requests under the GDPR "right to be forgotten" while keeping recommendation and classification models non-discriminatory.
• Income or credit-related prediction services built on social or demographic graphs, where racial bias in predictions carries legal and ethical exposure.
• E-commerce and online service platforms that use graph-structured user data and must balance personalization with non-discrimination requirements.
• Public-sector or civic web systems serving vulnerable and marginalized communities, where the authors argue technical failures in fairness can exacerbate existing inequities.

Industry relevance: The method is designed for the common practical case where sensitive attributes are incomplete, avoids reconstructing sensitive data through synthetic generation, and supports deletion of nodes and edges on graphs with tens of thousands of nodes and hundreds of thousands of edges. The stored training-set importance scores also let the original training data be discarded, which reduces storage and privacy exposure.

Future Directions

• The paper identifies that fairness-aware GNNs are not built for data removal and must be retrofitted with frameworks like IDEA to be compared in unlearning settings; a native fairness-preserving unlearning design for other architectures remains open.
• The experiments use a fixed 5% node deletion task; the behavior of the FIM-based selection and dampening at other deletion ratios or under repeated sequential deletion requests is not established in the available content.
• The framework depends on a sensitive attribute estimator and adversarial training; how the approach behaves when sensitive attribute labels are extremely scarce, or when the estimator itself is biased, is not reported.
• The available content does not report ablation studies, hyperparameter sensitivity for α, β, λ, and γ, or the second GNN architecture tested, leaving the contribution of each module only partially characterized.

Target Audience

This paper is most useful to researchers and graduate students working on graph machine learning, privacy-preserving data management, and algorithmic fairness, as well as practitioners at web platforms who are implementing data deletion workflows under privacy regulations. Readers need a working understanding of GNNs, min-max adversarial training, and group fairness metrics to follow the design section; the introduction and experimental results are accessible to a broader technically literate audience.

Authors’ abstract

Graph unlearning has emerged as a critical mechanism for supporting sustainable and privacy-preserving social networks, enabling models to remove the influence of deleted nodes and thereby better safeguard user information. However, we observe that existing graph unlearning techniques insufficiently protect sensitive attributes, often leading to degraded algorithmic fairness compared with traditional graph learning methods. To address this gap, we introduce FairGU, a fairness-aware graph unlearning framework designed to preserve both utility and fairness during the unlearning process. FairGU integrates a dedicated fairness-aware module with effective data protection strategies, ensuring that sensitive attributes are neither inadvertently amplified nor structurally exposed when nodes are removed. Through extensive experiments on multiple real-world datasets, we demonstrate that FairGU consistently outperforms state-of-the-art graph unlearning methods and fairness-enhanced graph learning baselines in terms of both accuracy and fairness metrics. Our findings highlight a previously overlooked risk in current unlearning practices and establish FairGU as a robust and equitable solution for the next generation of socially sustainable networked systems. The codes are available at https://github.com/LuoRenqiang/FairGU.