计算机科学与探索 ›› 2022, Vol. 16 ›› Issue (10): 2365-2376.DOI: 10.3778/j.issn.1673-9418.2101055
收稿日期:
2021-01-15
修回日期:
2021-03-16
出版日期:
2022-10-01
发布日期:
2021-03-25
通讯作者:
+ E-mail: zhao_jieyu@nbu.edu.cn作者简介:
唐晨(1995—),男,安徽合肥人,硕士研究生,主要研究方向为图神经网络、模式识别等。基金资助:
TANG Chen, ZHAO Jieyu+(), YE Xulun, ZHENG Yang, YU Shushi
Received:
2021-01-15
Revised:
2021-03-16
Online:
2022-10-01
Published:
2021-03-25
About author:
TANG Chen, born in 1995, M.S. candidate. His research interests include graph neural networks, pattern recognition, etc.Supported by:
摘要:
在现实世界中,任何复杂的关系都可以表示成图的形式,例如通信网络、生物网络、推荐系统等。链接预测是图领域的重要研究课题,但目前大部分的链接预测模型仅针对静态图,忽视了图在时域上的演化规律以及全局特征在演化过程中的重要性。为此,提出了一种动态图的链接预测模型。首先,为了获得高质量的全局特征,模型采用对抗训练的方式优化全局特征和高阶局部特征的互信息损失,然后利用基于宽平稳随机过程的感知模型,通过约束全局特征在时间维度上的均值和自相关函数值,以此保证全局特征在时域上的平稳性,再利用长短期记忆网络(LSTM)捕获动态图的演化规律,最后利用对抗网络优化预测值和真实值的损失。在USCB、SBM、AS数据集上的实验结果显示,本模型在动态图的链接预测任务上具有较好的表现,它不仅显著地提高了AUC值,还降低了MSE值。同时,消融实验的结果也表明,局部特征对全局特征的提取有促进作用,而且全局特征的质量和平稳性对网络链接预测有重要作用。
中图分类号:
唐晨, 赵杰煜, 叶绪伦, 郑阳, 俞书世. 动态图的链接预测模型[J]. 计算机科学与探索, 2022, 16(10): 2365-2376.
TANG Chen, ZHAO Jieyu, YE Xulun, ZHENG Yang, YU Shushi. Link Prediction Model for Dynamic Graphs[J]. Journal of Frontiers of Computer Science and Technology, 2022, 16(10): 2365-2376.
数据集 | 节点数 | 时间序列数 |
---|---|---|
USCB | 38 | 1 000 |
SBM | 1 000 | 50 |
AS | 6 474 | 100 |
表1 数据集的具体情况
Table 1 Details of dataset
数据集 | 节点数 | 时间序列数 |
---|---|---|
USCB | 38 | 1 000 |
SBM | 1 000 | 50 |
AS | 6 474 | 100 |
配置项目 | 设置 |
---|---|
操作系统 | Windows10 64 bit |
GPU | NVIDIA GeForce RTX2080Ti |
CPU | Intel® CoreTM i5-9600K |
频率 | 3.70 GHz |
硬盘 | Samsung SSD 860 EVO 500 GB |
存储器 | 32 GB DDR4 |
编程语言及环境 | Python3.6+Pytorch1.0 |
表2 实验设置
Table 2 Experimental setup
配置项目 | 设置 |
---|---|
操作系统 | Windows10 64 bit |
GPU | NVIDIA GeForce RTX2080Ti |
CPU | Intel® CoreTM i5-9600K |
频率 | 3.70 GHz |
硬盘 | Samsung SSD 860 EVO 500 GB |
存储器 | 32 GB DDR4 |
编程语言及环境 | Python3.6+Pytorch1.0 |
Model | USCB | SBM | AS |
---|---|---|---|
GCN | 38-64 | 1 000-64 | 6 474-64 |
Discriminator1 | 64-1 | 64-1 | 64-1 |
LSTM | 64-128 | 64-128 | 64-32 |
Generator | 128-38×38 | 128-1 000×1 000 | 32-6 474×6 474 |
WSD | 64-64-10 | 64-64-10 | 64-64-10 |
Discriminator2 | 38×38-512 | 1 000×1 000-512 | 6 474×6 474-32 |
表3 模型参数设置
Table 3 Setting of model parameters
Model | USCB | SBM | AS |
---|---|---|---|
GCN | 38-64 | 1 000-64 | 6 474-64 |
Discriminator1 | 64-1 | 64-1 | 64-1 |
LSTM | 64-128 | 64-128 | 64-32 |
Generator | 128-38×38 | 128-1 000×1 000 | 32-6 474×6 474 |
WSD | 64-64-10 | 64-64-10 | 64-64-10 |
Discriminator2 | 38×38-512 | 1 000×1 000-512 | 6 474×6 474-32 |
Methods | AUC | MSE |
---|---|---|
GCN | 0.924 7 | 0.213 7 |
GCN-GRU | 0.940 4 | 0.113 8 |
EnvolveGCN-h | 0.969 9 | 0.057 5 |
EnvolveGCN-o | 0.936 5 | 0.199 8 |
GCN-GAN | 0.970 4 | 0.014 3 |
LPMDG* | 0.973 4 | 0.024 3 |
LPMDG | 0.989 5 | 0.012 6 |
表4 USCB的预测结果
Table 4 Prediction results of USCB
Methods | AUC | MSE |
---|---|---|
GCN | 0.924 7 | 0.213 7 |
GCN-GRU | 0.940 4 | 0.113 8 |
EnvolveGCN-h | 0.969 9 | 0.057 5 |
EnvolveGCN-o | 0.936 5 | 0.199 8 |
GCN-GAN | 0.970 4 | 0.014 3 |
LPMDG* | 0.973 4 | 0.024 3 |
LPMDG | 0.989 5 | 0.012 6 |
Methods | AUC | MSE |
---|---|---|
GCN | 0.670 0 | 0.167 9 |
GCN-GRU | 0.769 4 | 0.207 9 |
EnvolveGCN-h | 0.767 6 | 0.212 3 |
EnvolveGCN-o | 0.770 9 | 0.179 5 |
GCN-GAN | 0.888 6 | 0.027 9 |
LPMDG* | 0.941 8 | 0.015 6 |
LPMDG | 0.950 3 | 0.013 3 |
表5 SBM的预测结果
Table 5 Prediction results of SBM
Methods | AUC | MSE |
---|---|---|
GCN | 0.670 0 | 0.167 9 |
GCN-GRU | 0.769 4 | 0.207 9 |
EnvolveGCN-h | 0.767 6 | 0.212 3 |
EnvolveGCN-o | 0.770 9 | 0.179 5 |
GCN-GAN | 0.888 6 | 0.027 9 |
LPMDG* | 0.941 8 | 0.015 6 |
LPMDG | 0.950 3 | 0.013 3 |
Methods | AUC | MSE |
---|---|---|
GCN | 0.553 9 | 0.558 7 |
GCN-GRU | 0.793 9 | 0.206 2 |
EnvolveGCN-h | 0.904 1 | 0.014 1 |
EnvolveGCN-o | 0.921 8 | 0.013 4 |
GCN-GAN | 0.935 5 | 0.014 3 |
LPMDG* | 0.979 9 | 0.002 5 |
LPMDG | 0.985 3 | 0.002 0 |
表6 AS的预测结果
Table 6 Prediction results of AS
Methods | AUC | MSE |
---|---|---|
GCN | 0.553 9 | 0.558 7 |
GCN-GRU | 0.793 9 | 0.206 2 |
EnvolveGCN-h | 0.904 1 | 0.014 1 |
EnvolveGCN-o | 0.921 8 | 0.013 4 |
GCN-GAN | 0.935 5 | 0.014 3 |
LPMDG* | 0.979 9 | 0.002 5 |
LPMDG | 0.985 3 | 0.002 0 |
[1] |
LIBEN-NOWELL D, KLEINBERG J M. The link-predic-tion problem for social networks[J]. Journal of the American Society for Information Science and Technology, 2007, 58(7): 1019-1031.
DOI URL |
[2] | JIN D, WANG X B, HE R F, et al. Robust detection of link communities in large social networks by exploiting link se-mantics[C]// Proceedings of the 32nd AAAI Conference on Artificial Intelligence, the 30th Innovative Applications of Artificial Intelligence, and the 8th AAAI Symposium on Educational Advances in Artificial Intelligence, New Orleans, Feb 2-7, 2018. Menlo Park: AAAI, 2018: 314-321. |
[3] |
GUO L, MA J, CHEN Z, et al. Learning to recommend with social contextual information from implicit feedback[J]. Soft Computing, 2015, 19(5): 1351-1362.
DOI URL |
[4] |
SCHAFER J B, KONSTAN J A, RIEDL J. E-commerce re-commendation applications[J]. Data Mining and Knowledge Discovery, 2001, 5(1/2): 115-153.
DOI URL |
[5] |
YU H, BRAUN P, YILDIRIM M A, et al. High-quality bi-nary protein interaction map of the yeast interactome net-work[J]. Science, 2008, 322(5898): 104-110.
DOI URL |
[6] |
STANFIELD Z, COŞKUN M, KOYUTÜRK M. Drug res-ponse prediction as a link prediction problem[J]. Scientific Reports, 2017, 7(1): 1-13.
DOI URL |
[7] | HJELM R D, FEDOROV A, LAVOIE-MARCHILDON S, et al. Learning deep representations by mutual information es-timation and maximization[C]// Proceedings of the 7th Inter-national Conference on Learning Representations, New Or-leans, May 6-9, 2019: 06670-06694. |
[8] | VELICKOVIC P, FEDUS W, HAMILTON W L, et al. Deep graph infomax[C]// Proceedings of the 7th International Con-ference on Learning Representations, New Orleans, May 6-9, 2019. |
[9] | KIPF T, WELLING M. Semi-supervised classification with graph convolutional networks[C]// Proceedings of the 5th International Conference on Learning Representations, Tou-lon, Apr 24-26, 2017: 2907-2921. |
[10] |
HOCHREITER S, SCHMIDHUBER J. Long short-term me-mory[J]. Neural Computation, 1997, 9(8): 1735-1780.
DOI URL |
[11] | PEROZZI B, AL-RFOU R, SKIENA S. DeepWalk: online learning of social representations[C]// Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Dis-covery and Data Mining, New York, Aug 24-27, 2014. New York: ACM, 2014: 701-710. |
[12] | GROVER A, LESKOVEC J.node2vec: scalable feature lear-ning for networks[C]// Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Francisco, Aug 13-17, 2016. New York: ACM, 2016: 855-864. |
[13] | NGUYEN G H, LEE J B, ROSSI R A, et al. Continuous-time dynamic network embeddings[C]// Companion Proceedings of the The Web Conference 2018, Lyon, Apr 23-27, 2018. New York: ACM, 2018: 969-976. |
[14] | YU W C, 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 and Data Mining, London, Aug 19-23, 2018. New York: ACM, 2018: 2672-2681. |
[15] | AHMED N M, CHEN L. An efficient algorithm for link pre-diction in temporal uncertain social networks[J]. Informa-tion Sciences, 2016, 331: 120-136. |
[16] | LI J D, DANI H, HU X, et al. Attributed network embed-ding for learning in a dynamic environment[C]// Proceedings of the 2017 ACM Conference on Information and Knowle-dge Management, Singapore, Nov 6-10, 2017. New York: ACM, 2017: 387-396. |
[17] | ZHU D, CUI P, ZHANG Z, et al. High-order proximity pre-served embedding for dynamic networks[J]. IEEE Transac-tions on Knowledge and Data Engineering, 2018, 30(11): 2134-2144. |
[18] | MA X, SUN P, WANG Y. Graph regularized nonnegative ma-trix factorization for temporal link prediction in dynamic net-works[J]. Physica A: Statistical Mechanics and Its Applica-tions, 2018, 496: 121-136. |
[19] | SEO Y, DEFFERRARD M, VANDERGHEYNST P, et al. Struc-tured sequence modeling with graph convolutional recurrent networks[C]// LNCS 11301: Proceedings of the 25th Interna-tional Conference on Neural Information Processing, Cam-bodia, Dec 13-16, 2018. Cham: Springer, 2018: 362-373. |
[20] | DEFFERRARD M, BRESSON X, VANDERGHEYNST P. Convolutional neural networks on graphs with fast locali-zed spectral filtering[C]// Proceedings of the Annual Conference on Neural Information Processing Systems 2016, Barcelona, Dec 5-10, 2016. Red Hook: Curran Associates, 2016: 3837-3845. |
[21] |
MANESSI F, ROZZA A, MANZO M. Dynamic graph con-volutional networks[J]. Pattern Recognition, 2020, 97: 107000-107016.
DOI URL |
[22] | NARAYAN A, ROE P H O N. Learning graph dynamics using deep neural networks[J]. IFAC-PapersOnLine, 2018, 51(2): 433-438. |
[23] | PAREJA A, DOMENICONI G, CHEN J, et al. EvolveGCN: evolving graph convolutional networks for dynamic graphs[C]// Proceedings of the 34th AAAI Conference on Artifi-cial Intelligence, the 32nd Innovative Applications of Arti-ficial Intelligence Conference, the 10th AAAI Symposium on Educational Advances in Artificial Intelligence, New York, Feb 7-12, 2020. Menlo Park: AAAI, 2020: 5363-5370. |
[24] | LEI K, QIN M, BAI B, et al. GCN-GAN: a non-linear tem-poral link prediction model for weighted dynamic networks[C]// Proceedings of the 2019 IEEE Conference on Computer Communications, Paris, Apr 29-May 2, 2019. Piscataway: IEEE, 2019: 388-396. |
[25] | GOODFELLOW I, POUGET-ABADIE J, MIRZA M, et al. Generative adversarial nets[C]// Proceedings of the Annual Conference on Neural Information Processing Systems 2014, Dec 8-13, 2014. Red Hook: Curran Associates, 2014: 2672-2680. |
[26] |
LINSKER R. Self-organization in a perceptual network[J]. Computer, 1988, 21(3): 105-117.
DOI URL |
[27] | RAMACHANDRAN K N, SHERIFF I, BELDING E M, et al. Routing stability in static wireless mesh networks[C]// LNCS 4427: Proceedings of the 8th Internatinoal Conference on Passive and Active Network Measurement, Belgium, Apr 5-6, 2007. Berlin, Heidelberg: Springer, 2007: 73-82. |
[28] | GOYAL P, KAMRA N, HE X, et al. DynGEM: deep embed-ding method for dynamic graphs[J]. arXiv:1805.11273, 2018. |
[29] | LESKOVEC J, KLEINBERG J M, FALOUTSOS C. Graphs over time: densification laws, shrinking diameters and pos-sible explanations[C]// Proceedings of the 11th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Chicago, Aug 21-24, 2005. New York: ACM, 2005: 177-187. |
[1] | 夏鸿斌, 肖奕飞, 刘渊. 融合自注意力机制的长文本生成对抗网络模型[J]. 计算机科学与探索, 2022, 16(7): 1603-1610. |
[2] | 申瑞彩, 翟俊海, 侯璎真. 选择性集成学习多判别器生成对抗网络[J]. 计算机科学与探索, 2022, 16(6): 1429-1438. |
[3] | 张雁操, 赵宇海, 史岚. 融合图注意力的多特征链接预测算法[J]. 计算机科学与探索, 2022, 16(5): 1096-1106. |
[4] | 林佳伟, 王士同. 用于无监督域适应的深度对抗重构分类网络[J]. 计算机科学与探索, 2022, 16(5): 1107-1116. |
[5] | 姜艺, 胥加洁, 柳絮, 朱俊武. 边缘指导图像修复算法研究[J]. 计算机科学与探索, 2022, 16(3): 669-682. |
[6] | 李志欣, 陈圣嘉, 周韬, 马慧芳. 协同级联网络和对抗网络的目标检测[J]. 计算机科学与探索, 2022, 16(1): 217-230. |
[7] | 袁立宁, 李欣, 王晓冬, 刘钊. 图嵌入模型综述[J]. 计算机科学与探索, 2022, 16(1): 59-87. |
[8] | 马力, 邹亚莉. 嵌入自注意力机制的美学特征图像生成方法[J]. 计算机科学与探索, 2021, 15(9): 1728-1739. |
[9] | 李西明, 吴嘉润, 吴少乾. 敌手能力有限时基于生成对抗网络的保密增强[J]. 计算机科学与探索, 2021, 15(7): 1220-1226. |
[10] | 吕昊远, 俞璐, 周星宇, 邓祥. 半监督深度学习图像分类方法研究综述[J]. 计算机科学与探索, 2021, 15(6): 1038-1048. |
[11] | 王曙燕, 金航, 孙家泽. GAN图像对抗样本生成方法[J]. 计算机科学与探索, 2021, 15(4): 702-711. |
[12] | 费建伟,夏志华,余佩鹏,戴昀书. 人脸合成技术综述[J]. 计算机科学与探索, 2021, 15(11): 2025-2047. |
[13] | 舒世泰,李松,郝晓红,张丽平. 知识图谱嵌入技术研究进展[J]. 计算机科学与探索, 2021, 15(11): 2048-2062. |
[14] | 刘颖, 张艺轩, 佘建初, 王富平, 林庆帆. 人脸去遮挡新技术研究综述[J]. 计算机科学与探索, 2021, 15(10): 1773-1794. |
[15] | 马永杰, 徐小冬, 张茹, 谢艺蓉, 陈宏. 生成式对抗网络及其在图像生成中的研究进展[J]. 计算机科学与探索, 2021, 15(10): 1795-1811. |
阅读次数 | ||||||
全文 |
|
|||||
摘要 |
|
|||||