Towards Effective and General Graph Unlearning via Mutual Evolution
Xunkai Li Yulin Zhao Zhengyu Wu Wentao Zhang Rong-Hua Li Guoren Wang
With the rapid advancement of AI applications, the growing needs for data
privacy and model robustness have highlighted the importance of machine
unlearning, especially in thriving graph-based scenarios. However, most
existing graph unlearning strategies primarily rely on well-designed
architectures or manual process, rendering them less user-friendly and posing
challenges in terms of deployment efficiency. Furthermore, striking a balance
between unlearning performance and framework generalization is also a pivotal
concern. To address the above issues, we propose \underline{\textbf{M}}utual
\underline{\textbf{E}}volution \underline{\textbf{G}}raph
\underline{\textbf{U}}nlearning (MEGU), a new mutual evolution paradigm that
simultaneously evolves the predictive and unlearning capacities of graph
unlearning. By incorporating aforementioned two components, MEGU ensures
complementary optimization in a unified training framework that aligns with the
prediction and unlearning requirements. Extensive experiments on 9 graph
benchmark datasets demonstrate the superior performance of MEGU in addressing
unlearning requirements at the feature, node, and edge levels. Specifically,
MEGU achieves average performance improvements of 2.7\%, 2.5\%, and 3.2\%
across these three levels of unlearning tasks when compared to state-of-the-art
baselines. Furthermore, MEGU exhibits satisfactory training efficiency,
reducing time and space overhead by an average of 159.8x and 9.6x,
respectively, in comparison to retraining GNN from scratch.