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

Summary

This paper proposes SCGU, a subgraph-based certified graph unlearning method for machine learning-as-a-service settings, where service providers lack training data and can modify model parameters directly. The method defines an influenced subgraph tied to the unlearning target, localizes gradient and Hessian computations to that subgraph, and uses an indicator called L-CODEC to select the most important parameters. Experiments across multiple datasets and GNN architectures report SCGU at least 4 times faster than retraining, with parameters 3%-5% closer to the retrained model.