Graph Unlearning

Abstract

Machine unlearning is a process of removing the impact of some training data from the machine learning (ML) models upon receiving removal requests. While straightforward and legitimate, retraining the ML model from scratch incurs a high computational overhead. To address this issue, a number of approximate algorithms have been proposed in the domain of image and text data, among which SISA is the state-of-the-art solution. It randomly partitions the training set into multiple shards and trains a constituent model for each shard. However, directly applying SISA to the graph data can severely damage the graph structural information, and thereby the resulting ML model utility. In this paper, we propose GraphEraser, a novel machine unlearning framework tailored to graph data. Its contributions include two novel graph partition algorithms and a learning-based aggregation method. We conduct extensive experiments on five real-world graph datasets to illustrate the unlearning efficiency and model utility of GraphEraser. It achieves 2.06$\times$ (small dataset) to 35.94$\times$ (large dataset) unlearning time improvement. On the other hand, GraphEraser achieves up to $62.5\%$ higher F1 score and our proposed learning-based aggregation method achieves up to $112\%$ higher F1 score.\footnote{Our code is available at \url{https://github.com/MinChen00/Graph-Unlearning}.}

arXiv commentTo Appear in 2022 ACM SIGSAC Conference on Computer and Communications Security, November 7-11, 2022. Please cite our CCS version

References in corpus (7)

• Community structure in social and biological networks
• Modularity and community structure in networks
• Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networks
• The performance of modularity maximization in practical contexts
• DeepInf: Social Influence Prediction with Deep Learning
• Multiway spectral community detection in networks
• Approximate Data Deletion from Machine Learning Models

Cited by in corpus (11)

• Machine Unlearning: Solutions and Challenges
• A Comprehensive Survey on Trustworthy Graph Neural Networks: Privacy, Robustness, Fairness, and Explainability
• GIF: A General Graph Unlearning Strategy via Influence Function
• Recommendation Unlearning via Influence Function
• ERASER: Machine Unlearning in MLaaS via an Inference Serving-Aware Approach
• On the Effectiveness of Unlearning in Session-Based Recommendation
• Dynamic Graph Unlearning: A General and Efficient Post-Processing Method via Gradient Transformation
• Moderator: Moderating Text-to-Image Diffusion Models through Fine-grained Context-based Policies
• Pre-training for Recommendation Unlearning
• Unlearning Inversion Attacks for Graph Neural Networks
• Faults and Pitfalls in Implementing the Right to be Forgotten