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

• 人工智能 • 上一篇    下一篇

动态图的链接预测模型

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

  1. 宁波大学 信息科学与工程学院,浙江 宁波 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   

  1. 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)

摘要:

在现实世界中,任何复杂的关系都可以表示成图的形式,例如通信网络、生物网络、推荐系统等。链接预测是图领域的重要研究课题,但目前大部分的链接预测模型仅针对静态图,忽视了图在时域上的演化规律以及全局特征在演化过程中的重要性。为此,提出了一种动态图的链接预测模型。首先,为了获得高质量的全局特征,模型采用对抗训练的方式优化全局特征和高阶局部特征的互信息损失,然后利用基于宽平稳随机过程的感知模型,通过约束全局特征在时间维度上的均值和自相关函数值,以此保证全局特征在时域上的平稳性,再利用长短期记忆网络(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)

中图分类号: