A Survey of Graph Unlearning

Anwar Said, Ngoc N. Tran, Yuying Zhao, Tyler Derr, Mudassir Shabbir, Waseem Abbas, Xenofon Koutsoukos

This survey paper by Anwar Said and colleagues provides the first systematic review of Graph Unlearning (GU)—a burgeoning field at the intersection of privacy, security, and graph machine learning. As AI systems increasingly rely on interconnected data (like social networks or financial transactions), the ability to "forget" specific information has become a legal and ethical necessity.

TL;DR

Graph unlearning is the process of removing sensitive data traces from trained Graph Neural Networks (GNNs) without retraining from scratch. This survey establishes a comprehensive taxonomy of "exact" and "approximate" unlearning methods, addressing the unique challenge of how information propagates through graph structures via message passing.

What Problem Does This Paper Address?

In the era of the "right to be forgotten" (mandated by regulations like GDPR and CCPA), users have the right to request their data be removed from AI models. While this is relatively straightforward for independent data points (like rows in a spreadsheet), it is incredibly complex for graphs.

In a GNN, a single node’s information is aggregated into its neighbors' embeddings, which then propagate to their neighbors, and so on. Deleting a node isn't just about removing a vertex; it’s about erasing its "echo" from the entire network. The naive solution—retraining the model from scratch every time a user leaves—is computationally prohibitive for large-scale systems like social networks or recommendation engines.

Methods

The authors categorize graph unlearning into two primary paradigms, as detailed in their taxonomy (see Figure 3):

  1. Exact Graph Unlearning: These methods aim to produce a model identical to one retrained from scratch.
  2. SISA-based (Sharded, Isolated, Sliced, and Aggregated): The graph is partitioned into independent "shards." When a removal request arrives, only the affected shard is retrained, significantly saving time.
  3. Parameter-based: For specific models (like linear GNNs), researchers have developed closed-form mathematical solutions to update weights directly without full retraining.
  4. Approximate Graph Unlearning: These methods are faster but provide a model that is "close enough" to a retrained one, often backed by theoretical privacy guarantees like $(\epsilon, \delta)$-unlearning.
  5. Influence Functions: These estimate how a specific training point affected the model's parameters and apply a "reverse" update to cancel that influence.
  6. Knowledge Distillation: A "teacher" model (the original) helps a "student" model learn to retain useful knowledge while intentionally "forgetting" the target data.

The framework handles various types of requests, including the removal of nodes, edges, specific features, or even entire subgraphs, as illustrated in the general framework below:

The graph unlearning framework illustrates various removal scenarios (node, edge, feature, or graph) and the goal of matching a retrained-from-scratch model.

Datasets

As a survey paper, this work does not introduce a new dataset but provides a comprehensive overview of the benchmarks used in the field. These include:

  • Social Networks: For testing privacy in user relationships.
  • Recommendation Systems: Utilizing user-item bipartite graphs (e.g., RecEraser benchmarks).
  • Biological/Chemical Networks: For molecular property prediction and toxicity identification.
  • Knowledge Graphs: Where schema-based unlearning is critical.

Key Insights and Ideas

  • The Message Passing Curse: The authors emphasize that the very mechanism that makes GNNs powerful—iterative information propagation—is the primary obstacle to unlearning. A single removed node can influence distant nodes through multiple hops.
  • Unlearning as a Defense: GU isn't just for privacy; it's a vital tool for adversarial robustness. If a graph is "poisoned" by malicious data, unlearning allows the system to surgically remove the attack's influence without losing the utility of the benign data.
  • Universal vs. Specialized: Most current research focuses on one type of unlearning (e.g., just edges). The authors argue for "Universal Graph Unlearning" approaches that can handle any request type within a single framework.

Key Results

  • Efficiency Gains: SISA-style methods can reduce the time required to handle a deletion request by orders of magnitude compared to full retraining.
  • Verification: The paper identifies Membership Inference Attacks (MIA) as the most effective way to evaluate unlearning completeness—if an attacker can't tell if a node was ever in the training set, the unlearning was successful.
  • Taxonomy of Methods: The paper provides a detailed comparison of over 30 recent algorithms, noting their venue, code availability, and the specific types of unlearning they support (see Figure 3).
A concise overview and categorization of existing graph unlearning methods.

Limitations and Future Work

  • Non-Convexity: Most approximate methods rely on convex optimization assumptions. Real-world GNNs are highly non-convex, meaning current theoretical guarantees often fall short in practice.
  • Complex Graph Types: There is a significant research gap in unlearning for temporal graphs (where relationships change over time) and directed graphs.
  • Foundation Models: As we move toward massive Graph Foundation Models and Retrieval-Augmented Generation (RAG), unlearning must scale to billions of parameters.
  • Multi-User Ethics: The authors raise a fascinating point: if User A interacts with User B, and User A wants to be forgotten, does User B have a right to "remember" that interaction? Balancing these conflicting rights is an open challenge.

Summary updated

Abstract

Graph unlearning emerges as a crucial advancement in the pursuit of responsible AI, providing the means to remove sensitive data traces from trained models, thereby upholding the \textit{right to be forgotten}. It is evident that graph machine learning exhibits sensitivity to data privacy and adversarial attacks, necessitating the application of graph unlearning techniques to address these concerns effectively. In this comprehensive survey paper, we present the first systematic review of graph unlearning approaches, encompassing a diverse array of methodologies and offering a detailed taxonomy and up-to-date literature overview to facilitate the understanding of researchers new to this field. To ensure clarity, we provide lucid explanations of the fundamental concepts and evaluation measures used in graph unlearning, catering to a broader audience with varying levels of expertise. Delving into potential applications, we explore the versatility of graph unlearning across various domains, including but not limited to social networks, adversarial settings, recommender systems, and resource-constrained environments like the Internet of Things, illustrating its potential impact in safeguarding data privacy and enhancing AI systems' robustness. Finally, we shed light on promising research directions, encouraging further progress and innovation within the domain of graph unlearning. By laying a solid foundation and fostering continued progress, this survey seeks to inspire researchers to further advance the field of graph unlearning, thereby instilling confidence in the ethical growth of AI systems and reinforcing the responsible application of machine learning techniques in various domains.
BibTeX
@misc{said2023survey,
  author = {Anwar Said and Ngoc N. Tran and Yuying Zhao and Tyler Derr and Mudassir Shabbir and Waseem Abbas and Xenofon Koutsoukos},
  title = {{A Survey of Graph Unlearning}},
  year = {2023},
  eprint = {2310.02164},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2310.02164},
}
Figure