动态图的链接预测模型

doi:10.3778/j.issn.1673-9418.2101055

计算机科学与探索 ›› 2022, Vol. 16 ›› Issue (10): 2365-2376.DOI: 10.3778/j.issn.1673-9418.2101055

动态图的链接预测模型

唐晨, 赵杰煜⁺(), 叶绪伦, 郑阳, 俞书世

宁波大学信息科学与工程学院,浙江宁波 315211

收稿日期:2021-01-15 修回日期:2021-03-16 出版日期:2022-10-01 发布日期:2021-03-25
通讯作者: + E-mail: zhao_jieyu@nbu.edu.cn
作者简介:唐晨（1995—）,男,安徽合肥人,硕士研究生,主要研究方向为图神经网络、模式识别等。
赵杰煜（1965—）,男,浙江宁波人,博士,教授,博士生导师,主要研究方向为计算智能、模式识别、人机交互等。
叶绪伦（1991—）,男,安徽安庆人,博士,讲师,主要研究方向为贝叶斯学习、凸优化等。
郑阳（1995—）,男,山东烟台人,硕士研究生,主要研究方向为三维图像处理、模式识别等。
俞书世（1996—）,女,浙江慈溪人,硕士研究生,主要研究方向为生成对抗网络、模式识别等。
基金资助:
国家自然科学基金(62071260);国家自然科学基金(62006131)

Link Prediction Model for Dynamic Graphs

TANG Chen, ZHAO Jieyu⁺(), YE Xulun, ZHENG Yang, YU Shushi

Faculty of Information Science and Engineering, Ningbo University, Ningbo, Zhejiang 315211, China

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.
ZHAO Jieyu, born in 1965, Ph.D., professor, Ph.D. supervisor. His research interests include computational intelligence, pattern recognition, human-computer interaction, etc.
YE Xulun, born in 1991, Ph.D., lecturer. His research interests include Bayesian learning, convex optimization, etc.
ZHENG Yang, born in 1995, M.S. candidate. His research interests include 3D image processing, pattern recognition, etc.
YU Shushi, born in 1996, M.S. candidate. Her research interests include generative adversarial networks, pattern recognition, etc.
Supported by:
National Natural Science Foundation of China(62071260);National Natural Science Foundation of China(62006131)

摘要/Abstract

摘要：

在现实世界中,任何复杂的关系都可以表示成图的形式,例如通信网络、生物网络、推荐系统等。链接预测是图领域的重要研究课题,但目前大部分的链接预测模型仅针对静态图,忽视了图在时域上的演化规律以及全局特征在演化过程中的重要性。为此,提出了一种动态图的链接预测模型。首先,为了获得高质量的全局特征,模型采用对抗训练的方式优化全局特征和高阶局部特征的互信息损失,然后利用基于宽平稳随机过程的感知模型,通过约束全局特征在时间维度上的均值和自相关函数值,以此保证全局特征在时域上的平稳性,再利用长短期记忆网络（LSTM）捕获动态图的演化规律,最后利用对抗网络优化预测值和真实值的损失。在USCB、SBM、AS数据集上的实验结果显示,本模型在动态图的链接预测任务上具有较好的表现,它不仅显著地提高了AUC值,还降低了MSE值。同时,消融实验的结果也表明,局部特征对全局特征的提取有促进作用,而且全局特征的质量和平稳性对网络链接预测有重要作用。

关键词: 动态图, 链接预测, 互信息, 对抗网络, 长短期记忆网络（LSTM）

Abstract:

In the real world, any complex relationships can be represented as graphs, such as communication networks, biological networks, recommendation systems, etc. Link prediction is an important research topic in the field of graphs, but most of the current link prediction models are only for static graphs, and they ignore the evolution pattern of graphs in the time domain and the importance of global features in the evolution process. To this end, this paper proposes a link prediction model for dynamic graphs. First, in order to obtain high-quality global features, the model uses adversarial training to optimize the mutual information loss of global features and higher-order local features. Then a perceptual model based on a wide smooth stochastic process is used to ensure the smoothness of the global features in the time domain by constraining the mean and autocorrelation function values of the global features in the time dimension. The evolution pattern of the dynamic graph is then captured using a long and short-term memory (LSTM) network. Finally, the loss of predicted and true values is optimized using adversarial networks. The experimental results on USCB, SBM and AS datasets show that the proposed model performs well in the link prediction task of dynamic graphs, and it not only significantly improves the AUC values, but also reduces the MSE values. Also, the results of the ablation experiments show that the local features contribute to the global feature ground extraction, and the quality and smoothness of the global features play an important role in network link prediction.

Key words: dynamic graphs, link prediction, mutual information, adversarial networks, long short-term memory networks (LSTM)

中图分类号:

TP183

唐晨, 赵杰煜, 叶绪伦, 郑阳, 俞书世. 动态图的链接预测模型[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.

图/表 13

参考文献 29

[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.

数据集	节点数	时间序列数
USCB	38	1 000
SBM	1 000	50
AS	6 474	100

数据集	节点数	时间序列数
USCB	38	1 000
SBM	1 000	50
AS	6 474	100

配置项目	设置
操作系统	Windows10 64 bit
GPU	NVIDIA GeForce RTX2080Ti
CPU	Intel^® Core^TM i5-9600K
频率	3.70 GHz
硬盘	Samsung SSD 860 EVO 500 GB
存储器	32 GB DDR4
编程语言及环境	Python3.6+Pytorch1.0

配置项目	设置
操作系统	Windows10 64 bit
GPU	NVIDIA GeForce RTX2080Ti
CPU	Intel^® Core^TM 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

动态图的链接预测模型

Link Prediction Model for Dynamic Graphs

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 13

参考文献 29

相关文章 15

编辑推荐

Metrics

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

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]	夏鸿斌, 肖奕飞, 刘渊. 融合自注意力机制的长文本生成对抗网络模型[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.