GIF: A General Graph Unlearning Strategy via Influence Function

Abstract

With the greater emphasis on privacy and security in our society, the problem of graph unlearning -- revoking the influence of specific data on the trained GNN model, is drawing increasing attention. However, ranging from machine unlearning to recently emerged graph unlearning methods, existing efforts either resort to retraining paradigm, or perform approximate erasure that fails to consider the inter-dependency between connected neighbors or imposes constraints on GNN structure, therefore hard to achieve satisfying performance-complexity trade-offs. In this work, we explore the influence function tailored for graph unlearning, so as to improve the unlearning efficacy and efficiency for graph unlearning. We first present a unified problem formulation of diverse graph unlearning tasks \wrt node, edge, and feature. Then, we recognize the crux to the inability of traditional influence function for graph unlearning, and devise Graph Influence Function (GIF), a model-agnostic unlearning method that can efficiently and accurately estimate parameter changes in response to a $\epsilon$-mass perturbation in deleted data. The idea is to supplement the objective of the traditional influence function with an additional loss term of the influenced neighbors due to the structural dependency. Further deductions on the closed-form solution of parameter changes provide a better understanding of the unlearning mechanism. We conduct extensive experiments on four representative GNN models and three benchmark datasets to justify the superiority of GIF for diverse graph unlearning tasks in terms of unlearning efficacy, model utility, and unlearning efficiency. Our implementations are available at \url{https://github.com/wujcan/GIF-torch/}.

arXiv commentAccepted by WWW 2023

References in corpus (18)

• Neural Graph Collaborative Filtering
• Graph Convolutional Neural Networks for Web-Scale Recommender Systems
• Self-supervised Graph Learning for Recommendation
• Understanding Black-box Predictions via Influence Functions
• Simplifying Graph Convolutional Networks
• Graph Convolutional Matrix Completion
• Representation Learning on Graphs with Jumping Knowledge Networks
• LightGCN: Simplifying and Powering Graph Convolution Network for Recommendation
• Graph Unlearning
• Poison Ink: Robust and Invisible Backdoor Attack
• Discovering Invariant Rationales for Graph Neural Networks
• Descent-to-Delete: Gradient-Based Methods for Machine Unlearning
• Approximate Data Deletion from Machine Learning Models
• Coded Machine Unlearning
• Let Invariant Rationale Discovery Inspire Graph Contrastive Learning
• Incorporating Bias-aware Margins into Contrastive Loss for Collaborative Filtering
• Certified Graph Unlearning
• Characterizing the Influence of Graph Elements

Cited by in corpus (7)

• Machine Unlearning: Solutions and Challenges
• A Comprehensive Survey on Trustworthy Graph Neural Networks: Privacy, Robustness, Fairness, and Explainability
• On the Effectiveness of Sampled Softmax Loss for Item Recommendation
• Recommendation Unlearning via Influence Function
• On the Effectiveness of Unlearning in Session-Based Recommendation
• Pre-training for Recommendation Unlearning
• Unlearning Inversion Attacks for Graph Neural Networks