SUGPT: Efficient Graph Unsummarization for the Right to Be Forgotten
- 24 February 2026
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Knowledge and Data Engineering
- Vol. 38 (5) , 3182-3195
Abstract
Graph data has become increasingly important in the AI and Big Data era. However, graph data analysis raises privacy concerns since it often originates from individual users. As a privacy regulation, the right to be forgotten has been established to allow users to erase their data hosted by a third party. When users request to delete their information from the original graph, the deletion must be synchronized to analysis results, like graph statistics or pre-trained AI models. In existing works, much effort has been made to fulfill the right to be forgotten for complicated graph learning models. In this work, we aim at a fundamental query — graph summarization, which serves as a building block for many graph analysis tasks. Since in summarization, when data removal requests are received, re-summarizing the graph from scratch can be costly, we present a novel approach to graph summarization regarding potential deletion requests. Inspired by machine unlearning, we define this problem as graph unsummarization which has three goals: efficiency, forgetting quality, and utility. Towards these goals, we propose SUGPT, a graph summarization and unsummarization method based on matrix partition and trie. The essence of SUGPT is to identify similarities between vertices by embedding matrix partitions into a trie structure, to accelerate summary updating upon deletion requests. We prove the forgetting quality of SUGPT theoretically and our extensive experiments demonstrate that SUGPT balances well in efficiency and utility in graph analysis.Keywords
Funding Information
- National Natural Science Foundation of China (62372122)
- National Natural Science Foundation of China (62372130)
- Research Grants Council (15224124)
- Research Grants Council (15208825)
- Research Grants Council (C2003-23Y)
- Hong Kong, SAR, China
This publication has 30 references indexed in Scilit:
- Structure-Preference Enabled Graph Embedding Generation Under Differential Privacy2025
- AdvSGM: Differentially Private Graph Learning via Adversarial Skip-Gram Model2025
- Eternal Sunshine of the Spotless Net: Selective Forgetting in Deep Networks2020
- Fast and Accurate Graph Stream Summarization2019
- From Louvain to Leiden: guaranteeing well-connected communitiesScientific Reports, 2019
- Query-friendly compression of graph streams2016
- Set-based approximate approach for lossless graph summarizationComputing, 2015
- Interestingness-Driven Diffusion Process Summarization in Dynamic Networks2014
- Fast unfolding of communities in large networksJournal of Statistical Mechanics: Theory and Experiment, 2008
- A generalization of the trie data structureMathematical Structures in Computer Science, 1995