Graph Unlearning

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

Research output: Working paper / PreprintPreprintAcademic

2 Downloads (Pure)

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}.}
Original languageEnglish
PublisherarXiv
Pages1-22
Number of pages22
ISBN (Electronic)9781450394505
DOIs
Publication statusPublished - 16 Sept 2021

Publication series

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

Bibliographical note

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

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

    Keywords

    • cs.LG
    • cs.AI
    • cs.CR
    • stat.ML

    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., 2022, CCS '22: Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security. ACM, p. 499-513 15 p. (Proceedings of the ACM Conference on Computer and Communications Security).

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

    Cite this