cispa_all_3615.pdf (977.98 kB)

Graph Unlearning

Download (977.98 kB)
conference contribution
posted on 2023-11-29, 18:20 authored by Min ChenMin Chen, Zhikun Zhang, Tianhao Wang, Michael BackesMichael Backes, Mathias Humbert, Yang ZhangYang Zhang
The right to be forgotten states that a data subject has the right to erase their data from an entity storing it. In the context of machine learning (ML), it requires the ML model provider to remove the data subject's data from the training set used to build the ML model, a process known as machine unlearning. While straightforward and legitimate, retraining the ML model from scratch upon receiving unlearning requests incurs a high computational overhead when the training set is large. To address this issue, a number of approximate algorithms have been proposed in the domain of image and text data, among which SISA (Sharded, Isolated, Sliced, and Aggregated) 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. We observe that GraphEraser achieves 2.06$\times$ (small dataset) to 35.94$\times$ (large dataset) unlearning time improvement compared to retraining from scratch. On the other hand, GraphEraser achieves up to $62.5\%$ higher F1 score than that of random partitioning. In addition, our proposed learning-based aggregation method achieves up to $112\%$ higher F1 score than that of the majority vote aggregation.


Preferred Citation

Min Chen, Zhikun Zhang, Tianhao Wang, Michael Backes, Mathias Humbert and Yang Zhang. Graph Unlearning. In: ACM Conference on Computer and Communications Security (CCS). 2022.

Primary Research Area

  • Trustworthy Information Processing

Name of Conference

ACM Conference on Computer and Communications Security (CCS)

Legacy Posted Date


Open Access Type

  • Green


@inproceedings{cispa_all_3615, title = "Graph Unlearning", author = "Chen, Min and Zhang, Zhikun and Wang, Tianhao and Backes, Michael and Humbert, Mathias and Zhang, Yang", booktitle="{ACM Conference on Computer and Communications Security (CCS)}", year="2022", }

Usage metrics


    No categories selected


    Ref. manager