A Survey of Graph Unlearning

Basic Information

• Paper ID: 2310.02164
• Title: A Survey of Graph Unlearning
• Authors: Anwar Said, Ngoc N. Tran, Yuying Zhao, Tyler Derr, Mudassir Shabbir, Waseem Abbas, Xenofon Koutsoukos
• Classification: cs.LG (Machine Learning)
• Publication Date: arXiv October 2023 (Latest version October 14, 2025)
• Paper Link: https://arxiv.org/abs/2310.02164

Abstract

Graph machine unlearning, as a critical technology in the development of responsible AI, provides a means to remove traces of sensitive data from trained models, thereby upholding the "right to be forgotten." Given the sensitivity of graph machine learning to data privacy and adversarial attacks, the application of graph unlearning techniques to effectively address these issues has become particularly necessary. This survey paper provides the first systematic review of graph unlearning methods, covering diverse methodologies and providing a detailed taxonomy and comprehensive literature overview, facilitating research for newcomers to the field. To ensure clarity, the paper provides clear explanations of fundamental concepts and evaluation metrics in graph unlearning, targeting a broad audience with varying levels of expertise.

Research Background and Motivation

Problem Background

1. Privacy Protection Requirements: With the implementation of data privacy regulations (such as GDPR and CCPA), individuals have the right to request deletion of their data from machine learning models
2. Complexity of Graph Data: The interconnectedness of nodes and edges in graph-structured data makes simple data deletion difficult, as information propagates to remote nodes through message-passing mechanisms
3. Adversarial Attack Defense: The need to remove maliciously injected data from models to maintain system integrity
4. Inadequacy of Existing Methods: Traditional machine unlearning methods cannot be directly applied to graph-structured data

Research Significance

• Legal Compliance: Meeting requirements of data protection regulations
• Privacy Protection: Safeguarding personal sensitive information from model leakage
• Security Defense: Resisting adversarial attacks such as data poisoning
• Ethical AI: Promoting the development of responsible AI systems

Existing Limitations

• Lack of systematic survey of graph unlearning methods
• The interconnected nature of graph data makes complete unlearning complex
• Difficult trade-offs between efficiency and completeness
• Absence of unified evaluation standards

Core Contributions

1. First Systematic Survey: Provides the first comprehensive systematic review of the graph unlearning field
2. Detailed Taxonomy: Categorizes graph unlearning methods into two major classes: Exact Unlearning and Approximate Unlearning
3. Comprehensive Application Analysis: Explores applications of graph unlearning in multiple domains including social networks, recommendation systems, and medical networks
4. Evaluation Framework: Provides methods for assessing unlearning completeness, efficiency, and model utility
5. Future Directions: Identifies multiple promising research directions

Methodology Details

Task Definition

Basic Concepts

• Graph Definition: G = (V, E, X, Xe), where V is the node set, E is the edge set, X is the node feature matrix, and Xe is the edge feature matrix
• Unlearning Set: S ⊆ D, representing the subset of data to be unlearned
• Objective: Update model parameters θ such that the effect is equivalent to retraining on D\S

(ε, δ)-Unlearning Definition

For a fixed dataset D, unlearning set S, and randomized learning algorithm A, an unlearning algorithm U is (ε, δ)-unlearning if and only if for all R ⊆ R:

Pr[A(D \ S) ∈ R] ≤ e^ε Pr[U(A(D), S, D) ∈ R] + δ
Pr[U(A(D), S, D) ∈ R] ≤ e^ε Pr[A(D \ S) ∈ R] + δ

Graph Unlearning Type Classification

1. Transductive Unlearning

• Node Unlearning: Removing specific nodes and all their connections
• Edge Unlearning: Removing specific edges while preserving nodes
• Node Feature Unlearning: Removing specific features of nodes

2. Inductive Unlearning

• Inductive Node Unlearning: Removing node sets from multiple graphs
• Inductive Edge Unlearning: Removing edge sets from multiple graphs
• Graph-Level Unlearning: Removing entire graph instances

Technical Framework

Exact Unlearning Methods

1. SISA Framework: Partitions training data, requiring retraining only of affected partitions
2. Parameter Retraining: Stores historical parameters and retrains from the point where deleted data first appeared
3. Closed-Form Solutions: Such as GraphEditor, which transforms GNN training into analytically solvable problems

Approximate Unlearning Methods

1. Methods in Convex Settings:
   • Utilizing Hessian matrices for parameter updates
   • Influence function estimation of data impact
   • Providing theoretical guarantees
2. Methods in Non-Convex Settings:
   • Influence function-based edge unlearning (CEU)
   • Hierarchical deletion operations (GNNDelete)
   • Knowledge distillation methods (GUKD, D2DGN)

Experimental Setup

Evaluation Dimensions

1. Unlearning Completeness

• Membership Inference Attacks: Evaluating whether unlearned data can still be detected
• Prediction Divergence: Comparing output differences between unlearned and retrained models
• Parameter Divergence: Comparing Euclidean distances between model parameters

2. Unlearning Efficiency

• Time Complexity: Most methods have complexity linear in the number of layers and quadratic in feature dimension
• Empirical Runtime: Actual time required for unlearning operations

3. Model Utility

• Downstream Task Performance: F1 score, accuracy, AUROC, etc.
• Benchmark Comparison: Typically compared against performance from retraining from scratch

Datasets

The methods discussed in the paper are evaluated on diverse graph datasets:

• Social network data
• Citation networks
• Molecular graph data
• Recommendation system data

Experimental Results

Main Findings

Exact vs. Approximate Methods

• Exact Methods: Provide perfect unlearning guarantees but incur large computational overhead
• Approximate Methods: Achieve balance between efficiency and unlearning quality

Performance Trade-offs

• Fundamental trade-off exists between unlearning completeness and computational efficiency
• Graph interconnectedness causes local unlearning to affect global performance
• Different unlearning types (node/edge/feature) exhibit different complexity levels

Method Comparison

According to the summary in Table II:

• SISA-class methods demonstrate superior performance in exactness
• Influence function methods are more efficient in approximate unlearning
• Knowledge distillation methods show advantages in preserving model utility

Application Effectiveness

• Recommendation Systems: Methods like RecEraser effectively handle user-item interaction unlearning
• Social Networks: GraphEraser achieves efficient unlearning through graph partitioning
• Adversarial Defense: Unlearning methods effectively remove maliciously injected data

Related Work

Traditional Machine Unlearning

• Primarily focuses on independent and identically distributed data
• Cannot be directly applied to graph-structured data
• Lacks consideration of dependencies between data points

Graph Machine Learning

• Node classification, link prediction, graph classification tasks
• Message-passing mechanisms complicate information propagation
• Requires specialized unlearning techniques

Privacy Protection

• Applications of differential privacy on graph data
• Integration of federated learning with graph neural networks
• Membership inference attacks and defenses

Conclusions and Discussion

Main Conclusions

1. Graph unlearning is a critical technology for responsible AI
2. Exact and approximate methods each have advantages; selection should depend on application requirements
3. Evaluation standards require further refinement and standardization
4. Cross-domain applications demonstrate tremendous potential

Limitations

1. Evaluation Standard Controversies: Existing evaluation methods have reliability issues
2. Non-Convex Setting Challenges: Most practical GNN models are non-convex, making theoretical guarantees difficult
3. Scalability Constraints: Unlearning efficiency on large-scale graphs requires further improvement
4. Complex Graph Structures: Insufficient support for directed graphs, temporal graphs, and other complex structures

Future Directions

1. Technical Development

• Approximate Unlearning in Non-Convex Settings: Developing unlearning methods applicable to complex GNN models
• Universal Graph Unlearning Framework: Unified methods supporting multiple unlearning types
• Complex Graph Structure Support: Extension to directed graphs, temporal graphs, and knowledge graphs

2. Application Expansion

• Foundation Model Unlearning: Adapting to unlearning requirements of large-scale graph foundation models
• Multi-User Interactions: Addressing ethical issues in unlearning user-interaction data
• Edge Computing Environments: Efficient unlearning in resource-constrained environments

3. Theoretical Refinement

• Certified Removal Methods: Providing stronger theoretical guarantees
• Evaluation Standardization: Establishing reliable frameworks for unlearning assessment
• Privacy Quantification: More precise methods for quantifying privacy leakage

In-Depth Evaluation

Strengths

1. Pioneering Work: The first systematic survey in the graph unlearning field
2. Comprehensiveness: Covers multiple dimensions including methods, applications, and evaluation
3. Practicality: Provides a clear technical roadmap for researchers and practitioners
4. Forward-Looking: Identifies multiple valuable future research directions
5. Standardization: Establishes fundamental concepts and classification frameworks for the field

Weaknesses

1. Limited Empirical Analysis: As a survey paper, lacks new experimental validation
2. Method Depth: Technical details of certain complex methods could be described more thoroughly
3. Missing Benchmarks: Lacks unified benchmark tests and comparison standards
4. Theoretical Analysis: Theoretical complexity analysis of different methods could be more detailed

Impact

1. Academic Value: Establishes theoretical foundations for the emerging graph unlearning field
2. Practical Guidance: Provides method selection guidelines for industrial applications
3. Research Promotion: Expected to stimulate more related research work
4. Standard Establishment: Contributes to establishing evaluation and comparison standards in the field

Applicable Scenarios

1. Privacy-Sensitive Applications: Domains such as healthcare and finance requiring strict privacy protection
2. Large-Scale Graph Systems: Internet applications such as social networks and recommendation systems
3. Adversarial Environments: Security-critical systems requiring resistance to data poisoning attacks
4. Compliance Requirements: Systems requiring compliance with data protection regulations such as GDPR

References

The paper cites 113 related references, covering important works in machine unlearning, graph neural networks, privacy protection, and other related domains, providing readers with comprehensive literature foundation.

Overall Assessment: This is a high-quality survey paper that systematically reviews the research status of graph unlearning, an emerging field, and establishes important foundations for its development. The paper is well-organized, comprehensive in content, and holds significant importance for advancing responsible AI development.