Graph Unlearning

Min Chen, Zhikun Zhang, Tianhao Wang, Michael Backes, Mathias Humbert, Yang Zhang

Research output: Chapter in Book / Report / Conference proceedingConference contributionAcademicpeer-review

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.06x (small dataset) to 35.94x (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. https://github.com/MinChen00/Graph-Unlearning.
Original languageEnglish
Title of host publicationCCS '22: Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security
PublisherACM
Pages499-513
Number of pages15
ISBN (Electronic)9781450394505
DOIs
Publication statusPublished - 2022

Publication series

NameProceedings of the ACM Conference on Computer and Communications Security
ISSN (Print)1543-7221

Funding

We thank all anonymous reviewers for their constructive comments. This work is partially funded by the Helmholtz Association within the project “Trustworthy Federated Data Analytics” (TFDA) (funding number ZT-I-OO1 4). Tianhao Wang did part of the work while at Purdue University and Carnegie Mellon University, and was funded by National Science Foundation (NSF) grant No.1931443, a Bilsland Dissertation Fellowship, and a Packard Fellowship.

FundersFunder number
TFDAZT-I-OO1 4
National Science Foundation1931443
Purdue University
Carnegie Mellon University
Helmholtz Association

    Fingerprint

    Dive into the research topics of 'Graph Unlearning'. Together they form a unique fingerprint.
    • Graph Unlearning

      Chen, M., Zhang, Z., Wang, T., Backes, M., Humbert, M. & Zhang, Y., 16 Sept 2021, arXiv, p. 1-22, 22 p. (Proceedings of the ACM Conference on Computer and Communications Security).

      Research output: Working paper / PreprintPreprintAcademic

      File
      2 Downloads (Pure)

    Cite this