Graph Unlearning for MLaaS: Towards Flexible Privacy Adjustment via Influenced Subgraph

Graph unlearning methods focus on removing specific information from graph neural networks (GNNs) to protect privacy. Existing graph unlearning methods often assume that all training data can be accessed. However, in machine learning as a service (MLaaS) scenarios, data owners, model developers, and service providers are responsible for providing data, training models, and deploying models, respectively. Service providers typically cannot have access to training data. Thus, graph unlearning can only be performed by model developers. In this paper, we introduce an innovative subgraph-based certified graph un learning (SCGU) method for MLaaS scenarios, enabling service providers to directly modify model parameters to achieve graph unlearning while minimizing privacy exposure. Specifically, we first define the influenced subgraph, which is only closely related to the unlearning target. Based on the influence function principle and the message-passing mechanism of GNNs, we then localize the computation of the gradient difference to the influenced subgraph. Moreover, by introducing an indicator, L-CODEC, to evaluate each parameter's importance to the unlearning target and to select the most important subset, we compute only the Hessian matrix of these parameters via finite differences, thereby efficiently localizing all parameter-estimation computation within the influenced subgraph. Once an unlearning request is received, the service provider only requires the influenced subgraph to calculate relevant variables, thereby directly modifying the model parameters to achieve graph unlearning. We evaluate the model utility, unlearning efficiency, and efficacy of our SCGU across multiple datasets (i.e., Cora, Citeseer, Pubmed, Coauthor-CS, and Coauthor-Physics) and GNN-based architectures (i.e., GCN, GIN, GAT, and SGC). The running efficiency experiments indicate that our SCGU is at least 4 times faster than retraining-based methods. The experimental results on SGC demonstrate that our SCGU achieves a closer parameter approximation to the retrained model, reducing the distance to it by 3%-5% compared to baseline methods. In addition, our SCGU outperforms other baseline methods, except for retraining, across most scenarios in terms of model utility and unlearning efficacy.