基于特征分类的链路预测方法综述

Review of Link Prediction Methods Based on Feature Classification

复杂网络链路预测作为网络科学研究中一个重要的研究方向,受到了越来越多来自各个学科领域专家的关注,它可以利用现有的网络信息,如节点和边缘的特征,来预测未来可能形成的关系、网络中缺失的信息以及新的或正在消失的信息,识别虚假交互,评估网络演化机制,进行网络重构等。当前链路预测的文献主要来自工程学、计算机科学与物理学的专家,它们各自为政,缺少合作,结合多学科进行链路预测的综述论文少之又少。因此,文中从计算机科学和物理学的视角全面回顾、分析和讨论基于特征分类的链路预测算法的研究进展,介绍了该领域专家们提出的多种特征提取技术,首次把分层的思想引入链路预测算法分类中,将分类模型分为3层,即元数据层、特征分类层和特征抽取层。该分类模型包括“2个大块7个方面”,即把常用的链路预测算法分为2个大块(特征提取方法和特征学习方法)和7个方面(基于相似性的方法、基于似然分析的方法、基于概率模型的方法、矩阵分解方法、基于随机游走的方法、基于神经网络的方法和基于自定义损失函数的方法)。该分类方法覆盖了各学科中许多经典的和最新的链路预测技术,包括当前最流行的图神经网络链路预测技术GNN(Graph Neural Network),GCN(Graph Convolutional Network),RNN(Recurrent Neural Network)和RL(Reinforcement Learning)。文中研究了这些算法的模型复杂性和预测性能的差异,并对当前链路预测技术未来所面临的挑战进行了讨论。

As an important research direction of network science research,link prediction of complex network has been more and more attention from experts from various disciplines,and it can make use of existing network information,such as the features of the nodes and edges,to predict possible future relationships,missing information in the network,and new or disappearing information,identify the false interactions,evaluate network evolution mechanism and conduct network reconfiguration,etc.Current articles on link prediction mainly come from the expert in engineering,computer science and physics.They are independent and lack cooperation,and there are few review articles combining multidisciplinary link prediction.The goal of this article is from the perspective of computer science and physics comprehensive to review,analyze,and discusse the research progress of link prediction algorithm based on feature classification,introduces a variety of feature extraction techniques in this field.This paper firstly introduces the idea of layering into the classification of link prediction algorithm,which divides the classification model into three layers,the metadata layer,features classification layer and feature extraction layer.The classification model includes two parts and seven aspects,that is,the prediction algorithm is divided into two parts,features extraction method and features learning method.The seven aspects are the similarity based methods,probabilistic methods,likelihood based methods,matrix factorization based method,random walk based method,neural network based method and custom loss function based method.This classification method covers many classical and latest link prediction techniques in various disciplines,including GNN,GCN,RNN and RL,which are the most popular link prediction techniques in graph neural networks.The differences of these algorithms in model complexity and prediction performance are studied,and the challenges of current link prediction technology in the future are discussed.