计算机科学

计算机科学 ›› 2026, Vol. 53 ›› Issue (7): 272-279.doi: 10.11896/jsjkx.250900118

• 数据库 & 大数据 & 数据科学 • 上一篇    下一篇

基于变分图自编码器的无监督动态图变化点检测算法

王嘉骏1, 焦鹏飞1,2, 张新勋1, 李天鹏3, 高梦州1   

  1. 1 杭州电子科技大学网络空间安全学院 杭州 310018
    2 浙江大学区块链与数据安全全国重点实验室 杭州 310027
    3 天津大学智能与计算机学部 天津 300072
  • 收稿日期:2025-09-18 修回日期:2026-01-03 出版日期:2026-07-15 发布日期:2026-07-10
  • 通讯作者: 焦鹏飞(pjiao@hdu.edu.cn)
  • 作者简介:(251270008@hdu.edu.cn)
  • 基金资助:
    浙江省科技计划(2025C01023);浙江省自然科学基金(LMS25F030011);国家自然科学基金(62372146);浙江省全省敏感数据安全保护与保密治理重点实验室基金(2024E10048)

Unsupervised Dynamic Graph Change Point Detection Method Based on Variational Graph Auto-encoder

WANG Jiajun1, JIAO Pengfei1,2, ZHANG Xinxun1, LI Tianpeng3, GAO Mengzhou1   

  1. 1 School of Cyberspace Security,Hangzhou Dianzi University,Hangzhou 310018,China
    2 State Key Laboratory of Blockchain and Data Security,Zhejiang University,Hangzhou 310027,China
    3 College of Intelligence and Computing,Tianjin University,Tianjin 300072,China
  • Received:2025-09-18 Revised:2026-01-03 Published:2026-07-15 Online:2026-07-10
  • About author:WANG Jiajun,born in 2002,master.His main research interests include change point detection and network alignment.
    JIAO Pengfei,born in 1990,Ph.D,professor,is a member of CCF(No.27894M).His main research interest is complex network analysis and its applications.
  • Supported by:
    Zhejiang Provincial Science and Technology Plan(2025C01023),Zhejiang Provincial Natural Science Foundation(LMS25F030011),National Natural Science Foundation of China(62372146) and Zhejiang Provincial Key Laboratory for Sensitive Data Security Protetion and Cnofidentiality Management(2024E10048).

PDF (PC)

13

摘要： 在动态图中检测或识别与事件相关的变化点变得愈加重要,因为网络结构的变化可能与网络系统功能的变化相关。然而,很多的变化点检测技术不能有效提取节点特征。因此,提出了一种基于变分图自编码器的无监督动态图变化点检测模型(VGRCPD)。该模型在结合了变分自编码器和递归神经网络的同时,引入了自注意力机制,用以计算历史时刻的先验分布。在得到图嵌入之后,将快照分割到不相交的簇中并按照时间顺序进行排列。最后,结合了簇的信息的时间序列自然指示了潜在的变化点。实验结果表明,所提出的方法在多个真实和合成数据集上的变化点检测任务中均取得了优异的性能,证明了其在动态图分析中的有效性和潜力。

关键词: 变化点检测, 图神经网络, 动态图, 社群检测, 图变分自编码器

Abstract: Detecting or identifying event-related change points in dynamic networks is becoming increasingly important,as structural variations in the network may correspond to changes in system functionality.However,many existing change point detection techniques fail to effectively capture node features.To address this limitation,this paper proposes an unsupervised dynamic graph change point detection model based on a Variational Graph Autoencoder(VGRCPD).The model integrates Variational Graph Autoencoders with recurrent neural networks and introduces a self-attention mechanism to compute the prior distribution from historical time steps.After obtaining graph embeddings,network snapshots are clustered into disjoint groups and arranged in temporal order.The resulting time series of cluster labels naturally indicates potential change points.Experimental results on multiple real-world and synthetic datasets demonstrate that the proposed method achieves superior performance,validating its effectiveness and potential in dynamic graph analysis.

Key words: Change point detection, Graph neural networks, Dynamic graphs, Community detection, Graph variational autoen-coder

中图分类号: 

  • TP181
[1]NEWMAN M E J,PARK J.Why Social Networks are Different From Other Types of Networks[J].Physical Review E,2003,68(3):036122.
[2]JIANGX H,SHEN Y H,LI Z J,et al.A Survey on Social Knowledge Graphs[J].Chinese Journal of Computers,2023,46(2):304-330.
[3]HEMER J.A Snapshoton Crowdfunding[R].Ar-Beitspapiere Unternehmen Und Region,2011.
[4]SILVA-ROCHA R,DE LORENZO V.Mining Logic Gates in Prokaryotic Transcriptional Regulation Networks[J].Febs Letters,2008,582(8):1237-1244.
[5]ZHAO X B,LIAN D F.Traffic Flow Prediction Based on Dy-namic Graph Convolution and Hypergraph Learning[J/OL].Computer Science,1-11 [2025-12-31].https://link.cnki.net/urlid/50.1075.Tp.20250902.0916.002.
[6]ROSSETTI G,CAZABET R.Community Discovery in Dynamic Networks:A Survey[J].ACM Computing Surveys,2018,51(2):1-37.
[7]BARROSC D T,MENDONÇA M R F,VIEIRA A B,et al.A Survey on Embedding Dynamic Graphs[J].ACM Computing Surveys,2021,55(1):1-37.
[8]WANG C,ZHU H.Wrongdoing Monitor:A Graph-Based Be-havioral Anomaly Detection In Cyber Security[J].IEEE Transactions on Information Forensics and Security,2022,17:2703-2718.
[9]BAUR C,WIESTLER B,ALBARQOUNI S,et al.Deep Au-toencoding Models for Unsupervised Anomaly Segmentation in Brain Mr Images[C]//International Miccai Brainlesion Workshop.Cham:Springer,2018:161-169.
[10]AHMED M,MAHMOOD A N,ISLAM M R.A Survey of Anomaly Detection Techniques in Financial Domain[J].Future Generation Computer Systems,2016,55:278-288.
[11]LI W,MAHADEVAN V,VASCONCELOS N.Anomaly Detection and Localization in Crowded Scenes[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2013,36(1):18-32.
[12]XIAO J S,GUO H W,XIE H G,et al.Probabilistic Memory Auto-Encoding Network for Abnormal Behavior Detection in Surveillance Videos[J].Ruan Jian Xue Bao/Journal of Software,2023,34(9):4362-4377.
[13]ZHU T,LI P,YU L,et al.Change Point Detection in Dynamic Networks Based on Community Identification[J].IEEE Tran-sactions on Network Science and Engineering,2020,7(3):2067-2077.
[14]PEEL L,CLAUSET A.Detecting Change Points in the Large-Scale Structure of Evolving Networks[C]//Proceedings of the AAAI Conference on Artificial Intelligence.2015.
[15]HUANG S,HITTI Y,RABUSSEAU G,et al.Laplacian Change Point Detection for Dynamic Graphs[C]//Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining.2020:349-358.
[16]EKLEO A,EBERLE W.Anomaly Detection in Dynamic Graphs:A Comprehensive Survey[J].ACM Transactions on Knowledge Discovery from Data,2024,18(8):1-44.
[17]LIU T,ZHANG C,LAM K M,et al.Decouple and Resolve:Transformer-Based Models for Online Anomaly Detection from Weakly Labeled Videos[J].IEEE Transactions on Information Forensics and Security,2022,18:15-28.
[18]HAGHIGHI V,SOLTANI B,MAHMOOD A,et al.Gcn-Based Multi-Task Representation Learning for Anomaly Detection in Attributed Networks[J].arXiv:2207.03688,2022.
[19]ZHOU Y,GAO S,GUO D,et al.A Survey of Change Point Detection in Dynamic Graphs[J].IEEE Transactions on Know-ledge and Data Engineering,2025,37(3):1030-1048.
[20]WANG Y,CHAKRABARTI A,SIVAKOFF D,et al.FastChange Point Detection On Dynamic Social Networks[J].ar-Xiv:1705.07325,2017.
[21]MILLER H,MOKRYN O.Size Agnostic Change Point Detection Framework for Evolving Networks[J].PLoS One,2020,15(4):E0231035.
[22]JIAO P,LI T,XIE Y,et al.Generative Evolutionary Anomaly Detection in Dynamic Networks[J].IEEE Transactions on Knowledge and Data Engineering,2021,35(12):12234-12248.
[23]KOUTRA D,SHAH N,VOGELSTEIN J T,et al.Deltacon:Principled Massive-Graph Similarity Function with Attribution[J].ACM Transactions on Knowledge Discovery from Data,2016,10(3):1-43.
[24]YU W,CHENG W,AGGARWAL C C,et al.Netwalk:A Flexible Deep Embedding Approach for Anomaly Detection in Dynamic Networks[C]//Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mi-ning.2018:2672-2681.
[25]BAI Y,DING H,BIAN S,et al.Simgnn:A Neural Network Approach to Fast Graph Similarity Computation[C]//Proceedings of the Twelfth ACM International Conference on Web Search and Data Mining.2019:384-392.
[26]ZHANG X,JIAO P,GAO M,et al.Vggm:Variational Graph Gaussian Mixture Model for Unsupervised Change Point Detection in Dynamic Networks[J].IEEE Transactions on Information Forensics and Security,2024,19:4272-4284.
[27]KIPFT N,WELLING M.Variational Graph Auto-Encoders[J].arXiv:1611.07308,2016.
[28]YANG M,ZHOU M,KALANDER M,et al.Discrete-Time Temporal Network Embedding Via Implicit Hierarchical Learning in Hyperbolic Space[C]//Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining.2021:1975-1985.
[29]YOU J,YING R,REN X,et al.Graphrnn:Generating Realistic Graphs with Deep Auto-Regressive Models[C]//International Conference on Machine Learning.PMLR,2018:5708-5717.
[30]YANG M S,LAI C Y,LIN C Y.A Robust Em Clustering Algorithm for Gaussian Mixture Models[J].Pattern Recognition,2012,45(11):3950-3961.
[31]PENTLAND A,EAGLE N,LAZER D.Inferring Social Net-work Structure Using Mobile Phone Data[J].Proceedings of the National Academy of Sciences,2009,106(36):15274-15278.
[32]BENSTONG J,HARTGRAVES A L.Enron:What Happenedand What We Can Learn From It[J].Journal of Accounting and Public Policy,2002,21(2):105-127.
[33]GLEDITSCHK S.Expanded Trade and Gdp Data[J].Journal of Conflict Resolution,2002,46(5):712-724.
[34]HULOVATYY Y,MILENKOVIĆ T.Scout:Simultaneous Time Segmentation and Community Detection in Dynamic Networks[J].Scientific Reports,2016,6(1):37557.
[35]HUANG S,COULOMBE S,HITTI Y,et al.Laplacian Change Point Detection for Single and Multi-View Dynamic Graphs[J].ACM Transactions on Knowledge Discovery from Data,2024,18(3):1-32.
[36]XIE Y,WANG W,SHAO M,et al.Multi-View Change Point Detection in Dynamic Networks[J].Information Sciences,2023,629:344-357.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
地址：重庆市两江新区洪湖西路18号    邮编：401121  
电话：023-63500828（编辑部） 023-67039612（会议/专题） 023-67039623（财务/发票）
E-mail：jsjkx12@163.com
本系统由北京玛格泰克科技发展有限公司设计开发