基于节点影响力的图遗忘学习近似最差遗忘集构造算法

doi:10.11896/jsjkx.250700094

Abstract

Abstract: GNNs have attracted significant attention due to their wide-ranging applications in fields such as social networks and recommendation systems.Motivated by intensified demands for data removal,including the right to be forgotten,data-ownership safeguards,and the expiration of data-use permissions,research on unlearning has accelerated,particularly in graph unlearning,deep unlearning,and unlearning in large language models.However,most existing studies simulate forgetting by randomly removing data,which fails to provide the strongest guarantee for data owners’ right to be forgotten and neglects the construction of extreme scenarios required to comprehensively evaluate different unlearning algorithms.To address these issues,this paper proposes a worst-case forgetting set construction algorithm based on node influence in graph data,aiming to approximately construct an optimal set of nodes to be forgotten for graph unlearning.This algorithm ranks the influence of training sample nodes by combining each node’s training loss and structural centrality,thereby identifying the most influential and hardest-to-forget nodes.It then selects the forgetting set by jointly considering each node’s impact on model performance and its importance.Experiments on different GNN models,graph datasets,and unlearning algorithms show that the proposed algorithm enables graph unlearning methods to more effectively reduce model performance.And it achieves up to a 15% greater reduction in performance compared to random forgetting strategies.At the same time,the approach significantly accentuates performance differences among various graph unlearning algorithms across multiple metrics,facilitating more effective multi-dimensional evaluation of these unlearning algorithms.

Key words: Graph neural network, Machine unlearning, Privacy protection, Worst-case forget set, Node influence

CLC Number:

TP309.2

ZHAO Zhengbiao, LU Hanyu, DING Hongfa. Node-influence Based Construction Algorithm of Approximate Worst-case Forgetting Set for Graph Unlearning[J].Computer Science, 2026, 53(3): 64-77.

References

[1]SUN H N,LI X K,WU Z G,et al.Breaking the entanglement of homophily and heterophily in semi-supervised node classification[C]//Proceedings of the 40th IEEE International Conference on Data Engineering(ICDE 2024).IEEE,2024:2379-2392.
[2]DEFFERRARD M,BRESSON X,VANDERGHEYNST P.Convolutional neural networks on graphs with fast localized spectral filtering[C]//Proceedings of the 30th Conference on Neural Information Processing Systems(NIPS 2016).Red Hook,NY:Curran Associates Inc.,2016:3844-3852.
[3]LUO Y K,SHI L,WU X M,et al.Classic GNNs are strong baselines:reassessing GNNs for node classification[C]//Proceedings of the 37th Conference on Neural Information Processing Systems(NeurIPS 2024).Red Hook,NY:Curran Associates Inc.,2024:97650-97669.
[4]ZHU C Z,WANG X,ZHENG Q.A graph convolutional net-work framework based on element separation and global attention[J].Journal of Computer Research and Development,2024,61(8):2008-2019.
[5]ZOU H Q,SHI B Z,SONG L Y,et al.A survey on complex spatio-temporal data mining methods based on graph neural networks[J].Journal of Software,2025,36(4):1811-1843.
[6]XIAO G Q,LI X Q,CHEN Y D,et al.A survey of large-scale graph neural network research[J].Chinese Journal of Computers,2024,47(1):148-171.
[7]LIN J J,YE Z L,ZHAO H X,et al.A survey on hypergraph neural networks[J].Journal of Computer Research and Deve-lopment,2024,61(2):362-384.
[8]ZHANG H F,ZHANG F,WANG H,et al.A novel privacy-preserving graph convolutional network via secure matrix multiplication[J].Information Sciences,2023,657:119897.
[9]WANG Z X,CHEN T S,REN J,et al.Deep reasoning withknowledge graph for social relationship understanding[C]//Proceedings of the 27th International Joint Conference on Artificial Intelligence(IJCAI 2018).International Joint Conferences on Artificial Intelligence Organization,2018:1021-1028.
[10]CAI X H,HUANG C,XIA L H,et al.LightGCL:Simple yet effective graph contrastive learning for recommendation[C]//Proceedings of the 11th International Conference on Learning Representations(ICLR 2023).New Orleans,LA:OpenReview.net,2023:1-15.
[11]HE X N,DENG K,WANG X,et al.LightGCN:simplifying and powering graph convolution network for recommendation[C]//Proceedings of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval(SIGIR 2020).New York:ACM,2020:639-648.
[12]JIN W.Graph mining with graph neural networks[C]//Proceedings of the 14th ACM International Conference on Web Search and Data Mining(WSDM 2021).New York:ACM,2021:1119-1120.
[13]LIU Z Y,JIANG Y,SHEN J Y,et al.A survey on federated unlearning:Challenges,Methods,and future directions[J].ACM Computing Surveys,2025,57(1):2.
[14]WANG C L,HUAI M,WANG D.Inductive graph unlearning[C]//Proceedings of the 32nd USENIX Security Symposium(USENIX Security 2023).Boston,MA:USENIX Association,2023:3205-3222.
[15]CHENG J L,DASOULAS G,HE H,et al.GNNDelete:A general unlearning strategy for graph neural networks[C]//Proceedings of the 11th International Conference on Learning Representations(ICLR 2023).New Orleans,LA:OpenReview.net,2023:1-23.
[16]LI X K,ZHAO Y L,WU Z Y,et al.Towards effective and general graph unlearning via mutual evolution[C]//Proceedings of the 38th AAAI Conference on Artificial Intelligence(AAAI 2024).Association for the Advancement of Artificial Intelligence,2024:13682-13690.
[17]WU J C,YANG Y,QIAN Y C,et al.GIF:A general graph unlearning strategy via influence function[C]//Proceedings of the ACM Web Conference 2023(WWW 2023).ACM,2023:651-661.
[18]FAN C C,LIU J Q,HERO A O,et al.Challenging forgets:Unveiling the worst-case forget sets in machine unlearning[C]//Proceedings of the 18th European Conference on Computer Vision(ECCV 2024).Berlin:Springer,2024:278-297.
[19]WEI J Q,JIANG D,ZHANG C.On efficient single-source personalized PageRank computation in Online Social Networks[J].IEEE Transactions on Knowledge and Data Engineering,2025,37(6):3598-3612.
[20]MCCALLUM A,NIGAM K,RENNIE J,et al.Automating the construction of internet portals with machine learning[J].Information Retrieval,2000,3(2):127-163.
[21]SHCHUR O,MUMME M,BOJCHEVSKI A,et al.Pitfalls of graph neural network evaluation[J].CoRR:abs/1811.05868,2018.
[22]HU W,FEY M,ZITNIK M,et al.Open Graph Benchmark:Datasets for Machine Learning on Graphs[C]//Proceedings of the 34th Conference on Neural Information Processing Systems(NeurIPS 2020).Red Hook,NY:Curran Associates Inc.,2020:22118-22133.
[23]CHEN M,ZHANG Z K,WANG T H,et al.Graph unlearning[C]//Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security(CCS 2022).New York:ACM,2022:499-513.
[24]LI X,FAN B,WU Z,et al.Toward scalable graph unlearning:A node influence maximization based approach[J].CoRR:abs/2501.11823,2025.
[25]DONG Y S,ZHANG B C,LEI Z Y,et al.IDEA:A flexible framework of certified unlearning for graph neural networks[C]//Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining(KDD 2024).New York:ACM,2024:621-630.
[26]TAN J J,SUN F,QIU R C,et al.Unlink to unlearn:Simplifying edge unlearning in GNNs[C]//Proceedings of the ACM Web Conference 2024(WWW 2024).New York:ACM,2024:489-492.
[27]SINHA Y,MANDAL M,KANKANHALLI M S.Distill to delete:Unlearning in graph networks with knowledge distillation[J].CoRR:abs/2309.16173,2023.
[28]WU K,SHEN J,NING Y,et al.Certified edge unlearning forgraph neural networks[C]//Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining(KDD 2023).ACM,2023:2606-2617.
[29]ZHANG T,GAO Y H,ZHAO J,et al.Efficient exact and approximate betweenness centrality computation for temporal graphs[C]//Proceedings of the ACM Web Conference 2024(WWW 2024).New York:ACM,2024:2395-2406.
[30]IACOBUCCI D,MCBRIDE R,POPOVICH D L,et al.Confidence intervals for assessing sizes of social network centralities[J].Social Networking,2018,7(4):220-242.
[31]TANG J K,MUSOLESI M,MASCOLO C,et al.Analysing information flows and key mediators through temporal centrality metrics[C]//Proceedings of the 3rd Workshop on Social Network Systems(SNS 2010).New York:ACM,2010:3.
[32]LI A,CORNELIUS S P,LIU Y Y,et al.The fundamental advantages of temporal networks[J].Science,2017,358(6366):1042-1046.
[33]ROZENSHTEIN P,GIONIS A.Temporal pagerank[C]//Machine Learning and Knowledge Discovery in Databases.Cham:Springer,2016:674-689.
[34]YU E,FU Y,ZHOU J,et al.Predicting critical nodes in temporal networks by dynamic graph convolutional networks[J].Applied Sciences,2023,13(12):7272.
[35]YING Z,BOURGEOIS D,YOU J,et al.GNNExplainer:Generating explanations for graph neural networks[C]//Proceedings of the 33rd Conference on Neural Information Processing Systems(NeurIPS 2019).Curran Associates Inc.,2019:9240-9251.
[36]DUVAL A,MALLIAROS F D.GraphSVX:Shapley value explanations for graph neural networks[C]//Proceedings of the European Conference on Machine Learning and Knowledge Discovery in Databases(ECML PKDD 2021).Cham:Springer,2021:302-318.
[37]BALDASSARRE F,AZIZPOUR H.Explainability techniquesfor graph convolutional networks[C]//Proceedings of the International Conference on Machine Learning,Workshop on Learning and Reasoning with Graph-Structured Representations(ICML 2019),New York:ACM,2019.
[38]YUAN H,YU H Y,WANG J,et al.On explainability of graph neural networks via subgraph explorations[C]//Proceedings of the 38th International Conference on Machine Learning(ICML 2021),New York:PMLR,2021:12241-12252.
[39]AKKAS S,AZAD A.GNNShap:scalable and accurate GNN explanation using shapley values[C]//Proceedings of the ACM Web Conference 2024(WWW 2024).New York,:ACM,2024:827-838.
[40]LI X,SHEN Q L,WANG H N,et al.LoReUn:Data itself implicitly provides cues to improve machine unlearning[C]//Proceedings of the 38th Conference on Neural Information Processing Systems(NeurIPS 2025).NeurIPS,2025:1.
[41]ZHAO K,KURMANJI M,BARBULESCU G O,et al.What makes unlearning hard and what to do about it[C]//Procee-dings of the 37th Conference on Neural Information Processing Systems(NeurIPS 2024).Red Hook,NY:Curran Associates Inc.,2024:12293-12333.
[42]XU K,HU W,LESKOVEC J,et al.How powerful are graph neural networks?[C]//Proceedings of the 7th International Conference on Learning Representations(ICLR 2019).New Orleans,LA:OpenReview.net,2019:9104-9121.
[43]TONEVA M,SORDONI A,COMBES R T D,et al.An empirical study of example forgetting during deep neural network Learning[C]//Proceedings of the 7th International Conference on Learning Representations(ICLR 2019).New Orleans,LA:OpenReview.net,2019:1768-1786.
[44]KOH P W,LIANG P.Understanding black-box predictions via influence functions[C]//Proceedings of the 34th International Conference on Machine Learning.JMLR.org,2017:1885-1894.
[45]MARIANI M S,MEDO M,ZHANG Y C.Ranking nodes in growing networks:When PageRank fails[J].Scientific Reports,2015,5(1):16181.
[46]KLICPERA J,BOJCHEVSKI A,GÜNNEMANN S.Predictthen propagate:Graph neural networks meet personalized PageRank[C]//Proceedings of the 7th International Conference on Learning Representations(ICLR 2019).New Orleans,LA:OpenReview.net,2019:2667-2682.
[47]XU H,ZHU T Q,ZHANG L F,et al.Machine unlearning:A survey[J].ACM Computing Surveys,2024,56(1):1-36.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

Comments

Recommended 0

No Suggested Reading articles found!

Node-influence Based Construction Algorithm of Approximate Worst-case Forgetting Set for Graph Unlearning

PDF (PC)

Abstract

Cite this article

share this article

References

Related Articles 15

Metrics

Comments

Recommended 0

[1]	WU Jiahao, PENG Li, YANG Jielong. Partial Domain Adaptation Based on Machine Unlearning [J]. Computer Science, 2026, 53(3): 173-180.
[2]	WANG Jinghong, LI Pengchao, WANG Xizhao, ZHANG Zili. Dual-channel Graph Neural Network Based on KAN [J]. Computer Science, 2026, 53(3): 188-196.
[3]	DING Yan, DING Hongfa, YU Muran, JIANG Heling. Survey of Backdoor Attacks and Defenses on Graph Neural Network [J]. Computer Science, 2026, 53(3): 1-22.
[4]	LI Chengyu, HUANG Ke, ZHANG Ruiheng , CHEN Wei. Heterogeneous Graph Attention Network-based Approach for Smart Contract Vulnerability Detection [J]. Computer Science, 2026, 53(2): 423-430.
[5]	ZHAI Jie, CHEN Lexuan, PANG Zhiyu. Survey on Graph Neural Network-based Methods for Academic Performance Prediction [J]. Computer Science, 2026, 53(2): 16-30.
[6]	YANG Ming, HE Chaobo, YANG Jiaqi. Direction-aware Siamese Network for Knowledge Concept Prerequisite Relation Prediction [J]. Computer Science, 2026, 53(2): 39-47.
[7]	WANG Xinyu, SONG Xiaomin, ZHENG Huiming, PENG Dezhong, CHEN Jie. Contrastive Learning-based Masked Graph Autoencoder [J]. Computer Science, 2026, 53(2): 145-151.
[8]	LIU Hongjian, ZOU Danping, LI Ping. Pedestrian Trajectory Prediction Method Based on Graph Attention Interaction [J]. Computer Science, 2026, 53(1): 97-103.
[9]	LI Yaru, WANG Qianqian, CHE Chao, ZHU Deheng. Graph-based Compound-Protein Interaction Prediction with Drug Substructures and Protein 3D Information [J]. Computer Science, 2025, 52(9): 71-79.
[10]	WU Hanyu, LIU Tianci, JIAO Tuocheng, CHE Chao. DHMP:Dynamic Hypergraph-enhanced Medication-aware Model for Temporal Health EventPrediction [J]. Computer Science, 2025, 52(9): 88-95.
[11]	SU Shiyu, YU Jiong, LI Shu, JIU Shicheng. Cross-domain Graph Anomaly Detection Via Dual Classification and Reconstruction [J]. Computer Science, 2025, 52(8): 374-384.
[12]	FENG Yimeng, FENG Yan, XIE Sijiang, ZHANG Qing. Proxy-based Bidirectional Coin Mixing Mechanism of Blockchain [J]. Computer Science, 2025, 52(8): 385-392.
[13]	DAI Xiangguang, HE Chenglong, GUAN Mingyu, ZHANG Wei, ZHOU Yang, LIU Jianfeng, LYU Qingguo. State-decomposition Distributed Dual Averaging Algorithm for Privacy Online ConstrainedOptimization over Directed Networks [J]. Computer Science, 2025, 52(8): 411-420.
[14]	TANG Boyuan, LI Qi. Review on Application of Spatial-Temporal Graph Neural Network in PM_2.5 ConcentrationForecasting [J]. Computer Science, 2025, 52(8): 71-85.
[15]	GUO Husheng, ZHANG Xufei, SUN Yujie, WANG Wenjian. Continuously Evolution Streaming Graph Neural Network [J]. Computer Science, 2025, 52(8): 118-126.