  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.
