Gradient Transformation: Towards Efficient and Model-Agnostic Unlearning for Dynamic Graph Neural Networks

He Zhang, Bang Wu, Xiangwen Yang, Xingliang Yuan, Chengqi Zhang, Shirui Pan

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:

  1. Unlearning Loss: Forces the model to change predictions on the data to be deleted.
  2. Remaining Loss: Ensures predictions on the rest of the training data stay consistent.
  3. Generalization Loss: Uses Central Moment Discrepancy (CMD) to maintain performance on unseen test data.
  4. Utility Regularization: Prevents overfitting to the unlearning request.
The Gradient Transformation workflow, illustrating how unlearning requests are processed through the MLP-Mixer to update the DGNN parameters.

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.
Comparison of average time costs for retraining versus Gradient Transformation (Ours) across multiple datasets and DGNN architectures.

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

BibTeX
@inproceedings{zhang2025gradient,
  author = {He Zhang and Bang Wu and Xiangwen Yang and Xingliang Yuan and Chengqi Zhang and Shirui Pan},
  title = {{Gradient Transformation: Towards Efficient and Model-Agnostic Unlearning for Dynamic Graph Neural Networks}},
  booktitle = {The Web Conference},
  year = {2025},
  doi = {10.1145/3696410.3714911},
}
Figure