  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
SISA 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 SISA to the graph data can severely damage the graph
structural information, and thereby the resulting ML model utility. In this
paper, we propose GraphEraser, 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 GraphEraser. It achieves 2.06$\times$ (small dataset) to
35.94$\times$ (large dataset) unlearning time improvement. On the other hand,
GraphEraser achieves up to $62.5\%$ higher F1 score and our proposed
learning-based aggregation method achieves up to $112\%$ higher F1
score.\footnote{Our code is available at
\url{https://github.com/MinChen00/Graph-Unlearning}.}
