CoChat
Sign Up
Cited by 133Privacy-Preserving Technologies in DataAdversarial Robustness in Machine LearningAdvanced Graph Neural Networks

Graph Unlearning

Open access
Chen, Min, Zhang, Zhikun, Wang, Tianhao, Backes, Michael, Humbert, Mathias, Zhang, Yang·2022·Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security
DOI 10.1145/3548606.3559352
Open this paper in CoChat — free account

Abstract

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.06x (small dataset) to 35.94x (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. https://github.com/MinChen00/Graph-Unlearning.

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.1145/3548606.3559352

Cites

39 of 39 references verified0 citation errors · 0 not checkable

Statistics

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • Most unlearning algorithms retain intermediate parameters and make use of the original training dataset.

    “From those summaries, we can see that most unlearning algorithms retain intermediate parameters and make use of the original training dataset [30, 47].”

    From Machine Unlearning: A Survey (2024) · cites this paper as [47]

    Section 2.2 (pp. 2–3) describes unlearning methods that reuse the training data after removing the revoked sample, including retraining the affected shard. It does not say that most unlearning algorithms retain intermediate parameters or establish that most use the original training dataset. (LLM, conf=0.82)

    Experimental — accuracy not yet measured

  • Unlearning methods based on data reorganization will affect the consistency and the accuracy of the model as the unlearning process continues.

    “It is worth pointing out that unlearning methods based on data reorganization will affect the consistency and the accuracy of the model as the unlearning process continues [30, 47, 48].”

    From Machine Unlearning: A Survey (2024) · cites this paper as [47]

    Appendix F, “Robustness of GraphEraser” (p. 19), reports that model utility declined in some cases after a large proportion of nodes was unlearned, but F1 scores did not drop significantly in most settings below 10% deletion. The paper does not establish that data-reorganization-based methods generally lose accuracy as unlearning continues, or that their consistency is affected. (LLM, conf=0.86)

    Experimental — accuracy not yet measured

  • The unlearning schemes proposed in References [29, 30, 33, 47, 68, 69] are essentially based on a retraining mechanism that naturally has a verifiability property.

    “The unlearning schemes proposed in References [29, 30, 33, 47, 68, 69] are essentially based on a retraining mechanism that naturally has a verifiability property.”

    From Machine Unlearning: A Survey (2024) · cites this paper as [47]

    Section 2.2 (pp. 2–3) describes retraining as an unlearning method, and says GraphEraser removes a requested node and retrains its shard model. The cited paper does not establish the claimed verifiability property; its description of retraining as easy to enforce is not a statement that the result can be verified. (LLM, conf=0.83)

    Experimental — accuracy not yet measured

  • Deterministic unlearning schemes such as SISA or GraphEraser promise nothing about what can be learned about specific samples from the difference between a trained model and an unlearned model.

    “Deterministic unlearning schemes, such as SISA [30] or GraphEraser [47], promise nothing about what can be learned about specific samples from the difference between a trained model and an unlearned model.”

    From Machine Unlearning: A Survey (2024) · cites this paper as [47]

  • They are mostly designed to leverage the special characteristics of a particular learning process or training scheme.

    “They are mostly designed to leverage the special characteristics of a particular learning process or training scheme [24, 47, 54].”

    From Machine Unlearning: A Survey (2024) · cites this paper as [47]

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Cites

Flagged first, then by citations

Research works printed but not linked: 28

  1. [1][1] R. Andersen, F. R. K. Chung, and K. J. Lang. Local Graph Partitioning using PageRank Vectors. In IEEE Symposium on Foundations of Computer Science (FOCS) , pages 475-486. IEEE, 2006. 14 -
  2. [2][2] D. Avdiukhin, S. Pupyrev, and G. Yaroslavtsev. MultiDimensional Balanced Graph Partitioning via Projected Gradient Descent. In Proceedings of the VLDB Endowment (VLDB) , page 906-919. VLDB Endowment, 2019. 7, 14 -
  3. [3][3] A. Awadelkarim and J. Ugander. Prioritized Restreaming Algorithms for Balanced Graph Partitioning. In ACM Conference on Knowledge Discovery and Data Mining (KDD) , pages 1877-1887. ACM, 2020. 14 -
  4. [6][6] J. Brophy and D. Lowd. Machine Unlearning for Random Forests. In International Conference on Machine Learning (ICML) , pages 1092-1104. JMLR, 2021. 1 -
  5. [18][18] A. Ginart, M. Y. Guan, G. Valiant, and J. Zou. Making AI Forget You: Data Deletion in Machine Learning. In Conference on Neural Information Processing Systems (NeurIPS) , pages 3513-3526. NeurIPS, 2019. 1, 13 -
  6. [23][23] C. Guo, T. Goldstein, A. Y. Hannun, and L. van der Maaten. Certified Data Removal from Machine Learning Models. In International Conference on Machine Learning (ICML) , pages 3832-3842. JMLR, 2020. 1, 13 -
  7. [24][24] V. Gupta, C. Jung, S. Neel, A. Roth, S. SharifiMalvajerdi, and C. Waites. Adaptive Machine Unlearning. In Conference on Neural Information Processing Systems (NeurIPS) , pages 16319-16330. NeurIPS, 2021. 13 -
  8. [25][25] W. L. Hamilton, Z. Ying, and J. Leskovec. Inductive Representation Learning on Large Graphs. In Conference on Neural Information Processing Systems (NeurIPS) , pages 1025-1035. NeurIPS, 2017. 2, 4, 18 -
  9. [26][26] S. He, F. Bastani, S. Jagwani, E. Park, S. Abbar, M. Alizadeh, H. Balakrishnan, S. Chawla, S. Madden, and M. A. Sadeghi. RoadTagger: Robust Road Attribute Inference with Graph Neural Networks. In AAAI Conference on Artificial Intelligence (AAAI) , pages 1096510972. AAAI Press, 2020. 1 -
  10. [29][29] T. Kanungo, D. M. Mount, N. S. Netanyahu, C. D. Piatko, R. Silverman, and A. Y. Wu. An Efficient kMeans Clustering Algorithm: Analysis and Implementation. In IEEE Transactions on Pattern Analysis and Machine Intelligence (TPAMI) , pages 881-892. IEEE, 2002. 6 -
  11. [30][30] G. Karypis and V. Kumar. A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs. In SIAM Journal on Scientific Computing (SIAM J. Sci. Comput.) , pages 20.1.359-392. SIAM, 1998. 14 -
  12. [31][31] T. N. Kipf and M. Welling. Semi-Supervised Classification with Graph Convolutional Networks. In International Conference on Learning Representations (ICLR) , pages 23341-23362. OpenReview.net, 2017. 1, 4, 8, 18 -
  13. [33][33] H. Liu, J. Han, F. Nie, and X. Li. Balanced Clustering with Least Square Regression. In AAAI Conference on Artificial Intelligence (AAAI) , pages 2231-2237. AAAI Press, 2017. 14 -
  14. [36][36] S. Neel, A. Roth, and S. Sharifi-Malvajerdi. Descentto-Delete: Gradient-Based Methods for Machine Unlearning. In International Conference on Algorithmic Learning Theory (ICALT) , pages 931-962. PMLR, 2021. 1, 13 -
  15. [38][38] A. Pal, C. Eksombatchai, Y. Zhou, B. Zhao, C. Rosenberg, and J. Leskovec. PinnerSage: Multi-Modal User Embedding Framework for Recommendations at Pinterest. In ACM Conference on Knowledge Discovery and Data Mining (KDD) , pages 2311-2320. ACM, 2020. 1, 2 -
  16. [40][40] T. Pham, T. Tran, D. Q. Phung, and S. Venkatesh. Column Networks for Collective Classification. In AAAI Conference on Artificial Intelligence (AAAI) , pages 2485-2491. AAAI Press, 2017. 18 -
  17. [42][42] U. N. Raghavan, R. Albert, and S. Kumara. Near Linear Time Algorithm to Detect Community Structures in Large-scale Networks. In Physical Review E (Phys. Rev. E) , page 036106. APS, 2007. 2, 3, 4 -
  18. [43][43] M. Rosvall and C. T. Bergstrom. Maps of Random Walks on Complex Networks Reveal Community Structure. In Proceedings of the National Academy of Sciences (PNAS) , pages 1118-1123. National Acad Sciences, 2008. 2, 4 -
  19. [44][44] F. Scarselli, M. Gori, A. C. Tsoi, M. Hagenbuchner, and G. Monfardini. The Graph Neural Network Model. In IEEE Transactions on Neural Networks (TNN) , pages 20.1.61-80. IEEE, 2009. 18 -
  20. [52][52] L. van der Maaten and G. Hinton. Visualizing Data using t-SNE. In Journal of Machine Learning Research (JMLR) , pages 9.86.2579-2605. JMLR, 2008. 19 -
  21. [53][53] P. Velickovic, G. Cucurull, A. Casanova, A. Romero, P. Liò, and Y. Bengio. Graph Attention Networks. In International Conference on Learning Representations (ICLR) . OpenReview.net, 2018. 1, 2, 18 -
  22. [60][60] Y. Wu, E. Dobriban, and S. B. Davidson. DeltaGrad: Rapid retraining of machine learning models. In International Conference on Machine Learning (ICML) , pages 10355-10366. JMLR, 2020. 1 -
  23. [61][61] K. Xu, W. Hu, J. Leskovec, and S. Jegelka. How Powerful are Graph Neural Networks. In International Conference on Learning Representations (ICLR) . OpenReview.net, 2019. 2, 18 -
  24. [62][62] Z. Yang, W. W. Cohen, and R. Salakhutdinov. Revisiting Semi-Supervised Learning with Graph Embeddings. In International Conference on Machine Learning (ICML) , pages 40-48. JMLR, 2016. 5, 8 -
  25. [63][63] R. Ying, R. He, K. Chen, P. Eksombatchai, W. L. Hamilton, and J. Leskovec. Graph Convolutional Neural Networks for Web-Scale Recommender Systems. In ACM Conference on Knowledge Discovery and Data Mining (KDD) , pages 974-983. ACM, 2018. 1 -
  26. [64][64] H. Zeng, H. Zhou, A. Srivastava, R. Kannan, and V. K. Prasanna. GraphSAINT: Graph Sampling Based Inductive Learning Method. In International Conference on Learning Representations (ICLR) . OpenReview.net, 2020. 10 -
  27. [67][67] Z. Zhang, T. Wang, N. Li, S. He, and J. Chen. CALM: Consistent Adaptive Local Marginal for Marginal Release under Local Differential Privacy. In ACMSIGSAC Conference on Computer and Communications Security (CCS) , pages 212-229. ACM, 2018. 13 -
  28. [68][68] Z. Zhang, T. Wang, N. Li, J. Honorio, M. Backes, S. He, J. Chen, and Y. Zhang. PrivSyn: Differentially Pri- vate Data Synthesis. In USENIX Security Symposium (USENIX Security) , pages 929-946. USENIX, 2021. 13

Cited by

Sorted by citations

Related

Authors
Chen, M., Zhang, Z., Wang, T., Backes, M., Humbert, M., & Zhang, Y.
Affiliations
  • Helmholtz Center for Information Security (DE)
  • University of Virginia (US)
  • CISPA Helmholtz Center for Information Security, Saarbruecken, Germany
  • University of Lausanne (CH)
ORCID
Venue
Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security
Publisher
ACM
Published
2022-11-07
Pages
499-513
ISSN
1543-7221 (ISSN-L)
DOI
10.1145/3548606.3559352
OpenAlex
W4296562799
Cited by
133
References
39
Citations by year
2026: 32 · 2025: 51 · 2024: 29 · 2023: 19 · 2022: 2
FWCI
13.93
Type
conference paper
Language
en
Open access
Licence
Locations
  • ACM SIGSAC Conference on Computer and Communications Security (CCS) (publishedVersion)
  • SERVAL (Université de Lausanne) (publishedVersion, other-oa)
  • arXiv (Cornell University) (submittedVersion)
  • IRIS (submittedVersion)
  • VU Research Portal (submittedVersion)
  • arXiv (Cornell University)
Funders
  • Purdue University (Bilsland Dissertation Fellowship)
  • Helmholtz Association (ZT-I-OO1 4)
  • the Packard Foundation (Packard Fellowship)
  • National Science Foundation (No.1931443)
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Privacy-Preserving Technologies in Data
  • Physical Sciences › Computer Science › Artificial Intelligence › Adversarial Robustness in Machine Learning
  • Physical Sciences › Computer Science › Artificial Intelligence › Advanced Graph Neural Networks
Keywords
machine unlearning, graph partitioning, SISA, graph neural networks, model utility preservation

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review