Graph Unlearning

Machine unlearning is a process of removing the impact of some training data from the machine learning (ML) models upon receiving removal requests. While straightforward and legitimate, retraining the ML model from scratch incurs a high computational overhead. To address this issue, a number of approximate algorithms have been proposed in the domain of image and text data, among which is the state-of-the-art solution. It randomly partitions the training set into multiple shards and trains a constituent model for each shard. However, directly applying to the graph data can severely damage the graph structural information, and thereby the resulting ML model utility. In this paper, we propose, a novel machine unlearning framework tailored to graph data. Its contributions include two novel graph partition algorithms and a learning-based aggregation method. We conduct extensive experiments on five real-world graph datasets to illustrate the unlearning efficiency and model utility of. It achieves 2.06$ $ (small dataset) to 35.94$ $ (large dataset) unlearning time improvement. On the other hand, achieves up to $62.5\