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

Graph unlearning focuses on removing specific information from graph neural networks (GNNs). Existing methods often assume full access to training data, which is impractical in machine learning-as-a-service (MLaaS) scenarios, where data owners, model developers, and service providers operate separately. Since service providers typically lack access to training data, graph unlearning can only be performed by model developers. In this paper, we introduce an innovative subgraph-based certified graph unlearning (SCGU) method for MLaaS scenarios, enabling service providers to directly modify model parameters to achieve graph unlearning. Specifically, we first define the influenced subgraph, which is only closely related to the unlearning target. Based on the message-passing mechanism of GNNs, we then localize the computation of the gradient difference to the influenced subgraph. Moreover, we introduce an indicator, L-CODEC, to identify the most important parameters for unlearning and compute only their Hessian matrix via finite differences, thereby localizing all parameter estimation within the influenced subgraph. Once an unlearning request is received, the service provider only requires the influenced subgraph to compute relevant variables and then directly modifies the model parameters to achieve graph unlearning. We evaluate the model utility, unlearning efficiency, and efficacy of our SCGU across multiple datasets and GNN architectures. Experimental results show that SCGU is at least 4 times faster than retraining, achieves a parameter approximation to the retrained model that is 3%- 5% closer, and outperforms all baselines except retraining in model utility and unlearning efficacy across most scenarios.