A Highly Efficient and Lightweight Graph Unlearning Method with Balanced Graph Partitioning and Adaptive Aggregation

Graph neural networks (GNNs), designed specifically for handling graph-structured data, have been widely applied in many domains involving such data. As public awareness of privacy grows, data privacy protection is increasingly emphasized, and related regulations are continually being introduced and refined. The right to be forgotten, closely related to data privacy protection, empowers data subjects to demand data controllers delete data pertaining to them, and machine unlearning aims to address the implementation of this right in the field of machine learning. The unique characteristics of GNNs bring challenges to the corresponding machine unlearning research, for example, traditional machine unlearning algorithms are difficult to directly transfer. Moreover, for some larger-scale graphs, methods purely based on graph partitioning struggle to achieve a good balance between sub-model performance and unlearning efficiency. To address these issues, this paper presents GraphRemover, an highly efficient and lightweight graph unlearning method based on balanced graph partitioning and adaptive aggregation. Comprising three main components-balanced graph partitioning, efficient submodel training, and adaptive submodel aggregation-GraphRemover's effectiveness is demonstrated through experiments on five da-tasets, evaluating both unlearning efficiency and model utility.