Journal of Frontiers of Computer Science and Technology ›› 2022, Vol. 16 ›› Issue (5): 1096-1106.DOI: 10.3778/j.issn.1673-9418.2012092

• Artificial Intelligence • Previous Articles     Next Articles

Multi-feature Based Link Prediction Algorithm Fusing Graph Attention

ZHANG Yancao, ZHAO Yuhai(), SHI Lan   

  1. College of Computer Science and Engineering, Northeastern University, Shenyang 110169, China
  • Received:2020-12-24 Revised:2021-03-12 Online:2022-05-01 Published:2022-05-19
  • About author:ZHANG Yancao, born in 1997, M.S. candidate. His research interests include machine learning, complex network, etc.
    ZHAO Yuhai, born in 1975, Ph.D., professor, Ph.D. supervisor, senior member of CCF. His research interests include machine learning, social network analysis, etc.
    SHI Lan, born in 1964, M.S., associate professor. Her research interests include computer architecture, network information security, etc.
  • Supported by:
    National Natural Science Foundation of China(61772124);National Key Research and Development Program of China(2018YFB1004402)

融合图注意力的多特征链接预测算法

张雁操, 赵宇海(), 史岚   

  1. 东北大学 计算机科学与工程学院,沈阳 110169
  • 通讯作者: + E-mail: zhaoyuhai@mail.neu.edu.cn
  • 作者简介:张雁操(1997—),男,安徽阜阳人,硕士研究生,主要研究方向为机器学习、复杂网络等。
    赵宇海(1975—),男,辽宁鞍山人,博士,教授,博士生导师,CCF高级会员,主要研究方向为机器学习、社交网络分析等。
    史岚(1964—),女,辽宁沈阳人,硕士,副教授,主要研究方向为计算机体系结构、网络信息安全等。
  • 基金资助:
    国家自然科学基金(61772124);国家重点研发计划(2018YFB1004402)

Abstract:

Link prediction is one of the important research directions in complex networks. Using neural networks to learn predefined heuristic features has attracted extensive attention in recent years. However, at present, this kind of method mainly uses the local subgraph of the target link to predict the link, which has strong locality. To solve this problem, based on SEAL (learning from subgraphs, embeddings and attributes for link prediction) algorithm, this paper proposes an algorithm ADNSL (learning from double-radius node labeling, node2vec and struc2vec for link prediction with attention mechanism) for link prediction using multi-feature fusing graph attention, which supports multi-type node embedding features as inputs, including local feature generation and global feature extraction. For the local feature generation module, the node features in the local subgraph are interactively fused by using the graph convolution layer. In order to make up for the feature ineffectiveness and node unbiasedness in SEAL, a bidirectional parameterless attention is proposed. The global feature extraction module uses iterative formula to generate agglomerative graph to reduce the complexity of struc2vec node embedding algorithm, and then mines interpretable structural features from a global perspective, which can effectively improve the performance of link prediction algorithm. Experiments show that ADNSL algorithm can reasonably utilize multi-type node embedding features, and its performance is obviously better than that of multiple benchmark algorithms across eight real datasets in different fields.

Key words: link prediction, node embedding, graph neural network, attention mechanism, agglomerative graph

摘要:

链接预测是复杂网络中重要的研究方向之一。利用神经网络学习预定义的启发式特征近年来受到广泛关注。但是目前此类方法主要利用目标链接的局部子图预测链接,具有较强的局部性。针对这一问题,在SEAL算法的基础上,提出了利用多特征融合图注意力进行链接预测的算法ADNSL。该模型支持多类型的节点嵌入特征作为输入,包括局部特征生成和全局特征提取两部分。对于局部特征生成模块,利用图卷积层,将局部子图中的节点特征交互融合。为了弥补SEAL中的特征无效性和节点无偏性,提出了双向无参注意力。在全局特征提取模块中,利用迭代公式生成聚合图以降低struc2vec节点嵌入算法的复杂度,进而从全局角度挖掘可解释的结构特征,可以有效提升链接预测算法性能。实验表明,ADNSL算法可以合理地利用多类型节点嵌入特征,在八个不同领域的真实数据集上的表现明显优于多个基准算法。

关键词: 链接预测, 节点嵌入, 图神经网络, 注意力机制, 聚合图

CLC Number: