Dynamic Graph Unlearning: A General and Efficient Post-Processing Method via Gradient Transformation

He Zhang, Bang Wu, Xiangwen Yang, Xingliang Yuan, Xiaoning Liu, Xun Yi

TL;DR

This paper introduces "Gradient Transformation," a novel post-processing method for "unlearning" data from dynamic graph neural networks (DGNNs). It addresses the critical need for privacy and compliance by efficiently removing specific user interactions from trained models without requiring a full retraining, achieving significant speedups and maintaining model performance.

What Problem Does This Paper Address?

In today's digital landscape, dynamic graph neural networks (DGNNs) are increasingly used in applications like social media and e-commerce to personalize user experiences by modeling complex, evolving relationships. However, this reliance on user interaction data raises significant privacy concerns. Users have a "right to be forgotten" (e.g., under GDPR), meaning that their data, and any knowledge derived from it by AI models, must be effectively removed. Existing "unlearning" methods, primarily designed for static data, struggle with the temporal and dynamic nature of graph data. They often require model retraining (computationally expensive), are tied to specific model architectures, or rely on pre-processing steps that aren't feasible for already deployed DGNNs. This paper tackles the challenge of efficiently and generally unlearning data from DGNNs in a post-processing manner.

Methods

The core contribution is the Gradient Transformation method. Instead of retraining the entire DGNN, this approach takes the already trained DGNN and its parameters, along with the unlearning request (specifying which data to forget), and applies a transformation to the model's gradients.

Here's a breakdown:

  • Dynamic Graph Unlearning Formulation: The authors first formally define unlearning in the context of continuous-time dynamic graphs, treating unlearning requests as sets of specific edge events to be forgotten.
  • Gradient Transformation Model: The key idea is to learn a transformation that maps the initial gradient (derived from the unlearning request) to the desired parameter update. This transformation is implemented using a two-layer MLP-Mixer.
  • Unlearning Loss Function: To guide the transformation, a multi-component loss function is proposed. This loss balances several objectives:
  • Ensuring the model's predictions change for the unlearned data (lui).
  • Maintaining performance on the remaining data (lre).
  • Improving generalization to unseen test data (lreg).
  • Preventing overfitting to the unlearning data itself (lulg).
  • Post-Processing and Architecture-Invariant: The method operates after the DGNN has been trained, making it a post-processing technique. Crucially, it doesn't alter the architecture of the original DGNN, making it general and applicable to various DGNN models.

Datasets

The authors evaluated their method on six real-world datasets commonly used for dynamic link prediction:

  • Wikipedia
  • UCI
  • Reddit
  • MOOC
  • LastFM
  • Enron

These datasets represent different domains, including social networks and interaction data. The paper does not introduce new benchmarks but uses established datasets to demonstrate the effectiveness of their approach on existing DGNN models.

Key Insights and Ideas

  • The "Right to Forget" in Dynamic Graphs is Hard: Unlearning in dynamic graphs is significantly more complex than in static graphs due to the temporal dependencies and the interconnectedness of nodes and edges over time. Simply removing data points can have cascading effects.
  • Gradient Transformation is a Powerful Proxy for Retraining: The core insight is that a learned transformation of gradients can effectively approximate the outcome of retraining a DGNN from scratch, but at a fraction of the computational cost.
  • Balancing Competing Objectives is Crucial: The proposed loss function highlights the inherent trade-offs in unlearning. It's not just about forgetting; it's about forgetting without significantly degrading performance on the remaining data or future predictions.
  • Post-Processing is Key for Practicality: The ability to unlearn from already deployed models without altering their architecture is a major practical advantage, making the method readily applicable in real-world scenarios.
  • Future Unlearning is Feasible: The method shows promise for handling future unlearning requests efficiently, as it can leverage previously learned transformations.

Key Results

The Gradient Transformation method demonstrated strong performance across multiple DGNN backbones (DyGFormer, GraphMixer, CAWN) and datasets:

  • Effectiveness: The unlearned models showed performance comparable to or even better than retraining from scratch, with minimal drops in accuracy on remaining data. For example, on test data (∆AUC(Ste)), their method often outperformed baselines.
  • Efficiency: The method achieved significant speedups compared to retraining. For instance, speedups of up to 7.23x were observed during initial evaluations, and up to 32.59x for future unlearning requests.
  • Generalization: The method proved effective across different DGNN architectures, including Transformer-based (DyGFormer), MLP-based (GraphMixer), and random walk-based (CAWN) models.
  • Avoiding Overfitting: The proposed loss function effectively mitigated overfitting to the unlearning data, a common pitfall for simpler unlearning methods.

Limitations and Future Work

  • Resource Bottleneck for Extremely Large Models: While significantly more efficient than retraining, the Gradient Transformation method's resource requirements might still become a bottleneck for exceptionally large DGNN models in the future.
  • Causal Relationships and Interplay: The authors suggest future work should delve deeper into understanding the causal relationships between events from an unlearning perspective and the intricate interplay between remaining and unlearned data.
  • Handling Complex Unlearning Scenarios: While effective for edge-based unlearning, exploring unlearning requests involving node features or more complex data manipulations could be a future direction.

Summary updated

Abstract

Dynamic graph neural networks (DGNNs) have emerged and been widely deployed in various web applications (e.g., Reddit) to serve users (e.g., personalized content delivery) due to their remarkable ability to learn from complex and dynamic user interaction data. Despite benefiting from high-quality services, users have raised privacy concerns, such as misuse of personal data (e.g., dynamic user-user/item interaction) for model training, requiring DGNNs to ''forget'' their data to meet AI governance laws (e.g., the ''right to be forgotten" in GDPR). However, current static graph unlearning studies cannot $\textit{unlearn dynamic graph elements}$ and exhibit limitations such as the model-specific design or reliance on pre-processing, which disenable their practicability in dynamic graph unlearning. To this end, we study the dynamic graph unlearning for the first time and propose an $\textit{effective}$, $\textit{efficient}$, $\textit{general}$, and $\textit{post-processing}$ method to implement DGNN unlearning. Specifically, we first formulate dynamic graph unlearning in the context of continuous-time dynamic graphs, and then propose a method called Gradient Transformation that directly maps the unlearning request to the desired parameter update. Comprehensive evaluations on six real-world datasets and state-of-the-art DGNN backbones demonstrate its effectiveness (e.g., limited drop or obvious improvement in utility) and efficiency (e.g., 7.23$\times$ speed-up) advantages. Additionally, our method has the potential to handle future unlearning requests with significant performance gains (e.g., 32.59$\times$ speed-up).
BibTeX
@inproceedings{zhang2025dynamic,
  author = {He Zhang and Bang Wu and Xiangwen Yang and Xingliang YUAN and Xiaoning Liu and Xun Yi},
  title = {{Dynamic Graph Unlearning: A General and Efficient Post-Processing Method via Gradient Transformation}},
  booktitle = {The Web Conference},
  year = {2025},
  doi = {10.1145/3696410.3714911},
}
Figure