TY - GEN
T1 - Certified Edge Unlearning for Graph Neural Networks
AU - Wu, Kun
AU - Shen, Jie
AU - Ning, Yue
AU - Wang, Ting
AU - Wang, Wendy Hui
N1 - Publisher Copyright:
© 2023 ACM.
PY - 2023/8/6
Y1 - 2023/8/6
N2 - 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.
AB - 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.
KW - graph neural networks
KW - graph unlearning
KW - machine learning security and privacy
UR - http://www.scopus.com/inward/record.url?scp=85171376586&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85171376586&partnerID=8YFLogxK
U2 - 10.1145/3580305.3599271
DO - 10.1145/3580305.3599271
M3 - Conference contribution
AN - SCOPUS:85171376586
T3 - Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining
SP - 2606
EP - 2617
BT - KDD 2023 - Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining
T2 - 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD 2023
Y2 - 6 August 2023 through 10 August 2023
ER -