Certified Edge Unlearning for Graph Neural Networks

Kun Wu, Jie Shen, Yue Ning, Ting Wang, Wendy Hui Wang

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

8 Scopus citations

Abstract

The emergence of evolving data privacy policies and regulations has sparked a growing interest in the concept of "machine unlearning", which involves enabling machine learning models to forget specific data instances. In this paper, we specifically focus on edge unlearning in Graph Neural Networks (GNNs), which entails training a new GNN model as if certain specified edges never existed in the original training graph. Unlike conventional unlearning scenarios where data samples are treated as independent entities, edges in graphs exhibit correlation. Failing to carefully account for this data dependency would result in the incomplete removal of the requested data from the model. While retraining the model from scratch by excluding the specific edges can eliminate their influence, this approach incurs a high computational cost. To overcome this challenge, we introduce CEU, a Certified Edge Unlearning framework. CEU expedites the unlearning process by updating the parameters of the pre-trained GNN model in a single step, ensuring that the update removes the influence of the removed edges from the model. We formally prove that CEU offers a rigorous theoretical guarantee under the assumption of convexity on the loss function. Our empirical analysis further demonstrates the effectiveness and efficiency of CEU for both linear and deep GNNs - it achieves significant speedup gains compared to retraining and existing unlearning methods while maintaining comparable model accuracy to retraining from scratch.

Original languageEnglish
Title of host publicationKDD 2023 - Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining
Pages2606-2617
Number of pages12
ISBN (Electronic)9798400701030
DOIs
StatePublished - 6 Aug 2023
Event29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD 2023 - Long Beach, United States
Duration: 6 Aug 202310 Aug 2023

Publication series

NameProceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

Conference

Conference29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD 2023
Country/TerritoryUnited States
CityLong Beach
Period6/08/2310/08/23

Keywords

  • graph neural networks
  • graph unlearning
  • machine learning security and privacy

Fingerprint

Dive into the research topics of 'Certified Edge Unlearning for Graph Neural Networks'. Together they form a unique fingerprint.

Cite this