SUGPT: Efficient Graph Unsummarization for the Right to Be Forgotten

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.