Abstract
Dynamic Graph Neural Networks (DGNNs) are critical for capturing temporal dependencies in evolving graph data. However, complying with data deletion requests (e.g., GDPR) remains a significant challenge due to the computational complexity of retraining and the memory overhead of influence-based unlearning methods. We propose Gradient Transformation (GT), a general and efficient post-processing method for DGNN unlearning. GT employs a lightweight MLP-Mixer to transform gradients from unlearning requests into parameter updates, avoiding the $O(n^2)$ space complexity of Hessian-based approaches. Evaluated on six real-world datasets, GT demonstrates up to a 32x speedup over retraining from scratch while maintaining high model utility and unlearning effectiveness.
Introduction
In the era of the "right to be forgotten," AI models must be able to delete specific user data upon request. While machine unlearning is well-studied for static images or text, Dynamic Graphs—where nodes and edges evolve over time (e.g., financial transactions or social interactions)—present unique challenges. Existing solutions often fall short due to temporal dependencies, prohibitive resource requirements (calculating Hessian matrices for state-of-the-art DGNNs can require terabytes of storage), and inflexibility regarding pre-trained models.
Methodology
The authors propose a post-processing method called Gradient Transformation. Instead of retraining the model from scratch or calculating complex mathematical influences, they treat unlearning as a learning task itself.
The Transformation Model
GT uses a two-layer MLP-Mixer that takes the initial gradient of the unlearning request as input and transforms it into the optimal parameter update ($\\Delta\\theta$). This makes the method architecture-invariant, allowing it to function regardless of whether the underlying DGNN is based on Transformers, MLPs, or Random Walks.
The Loss Function
To ensure the model "forgets" correctly without degrading performance on remaining data, a four-part loss function is utilized:
- Unlearning Loss: Forces the model to change predictions on the data to be deleted.
- Remaining Loss: Ensures predictions on the rest of the training data stay consistent.
- Generalization Loss: Uses Central Moment Discrepancy (CMD) to maintain performance on unseen test data.
- Utility Regularization: Prevents overfitting to the unlearning request.
Experiments and Results
The researchers evaluated GT across six diverse, real-world dynamic link prediction datasets (Wikipedia, Reddit, MOOC, LastFM, UCI, and Enron) against state-of-the-art DGNN backbones: DyGFormer, GraphMixer, and CAWN.
Key Findings
- Efficiency: Compared to retraining from scratch, GT achieved an average speedup of 7.23x for initial requests. For subsequent requests using the pre-trained transformation model, the speedup increased to 32.59x.
- Effectiveness: The method maintained high utility (AUC/Accuracy) on remaining data, often outperforming fine-tuning baselines that tend to "damage" the model's general knowledge.
- Unlearning Rate: On the Wikipedia dataset, GT achieved an average unlearning similarity rate of 81.33% compared to the gold standard of retraining.
Conclusion
Gradient Transformation provides a scalable, Hessian-free, and model-agnostic solution for dynamic graph unlearning. By bypassing the massive memory overhead of traditional methods, it enables efficient compliance with data privacy regulations. Future work will explore scaling bottlenecks for extremely large models and the complex causal relationships between temporal events during the unlearning process.
Summary updated