基于随机投影和主成分分析的网络嵌入后处理算法  

Post-processing Network Embedding Algorithm with Random Projection and Principal Component Analysis

作　　者：胡昕彤 沙朝锋[1] 刘艳君 HU Xin-tong;SHA Chao-feng;LIU Yan-jun(School of Computer Science,Fudan University,Shanghai 200433,China)

机构地区：[1]复旦大学计算机科学技术学院,上海200433

出　　处：《计算机科学》2021年第5期124-129,共6页Computer Science

基　　金：国家重点研发计划(2018YFB0904503)。

摘　　要：网络嵌入作为网络表示学习,近年来受到了研究人员的广泛关注。目前,已有许多基于网络结构学习网络中结点的低维向量表示的模型,如DeepWalk等,并且这些模型在结点分类和链接预测等任务中取得了良好的效果。然而,随着网络规模的增大,多个网络嵌入算法存在计算瓶颈问题。为缓解该问题,可采用诸如随机投影这类无需学习的方法,但这样可能会丢失网络结构的关键信息,致使算法性能下降。为此,文中提出了一种网络嵌入的后处理算法PPNE(Post-Processing Network Embedding),该算法结合了随机投影以及主成分分析,有效地保留了网络结构的关键信息,保持了网络结构的高阶近似性。将所提算法与其他网络嵌入算法在3个公共数据集上针对结点分类和链接预测任务进行实验对比,以验证其有效性。实验结果表明,PPNE算法在运行速度和预测性能方面相比其他算法有较大的提升,尤其是该算法在保证良好任务效果的同时,运行速度比其他基于学习的算法提升了至少两个数量级。Network embedding as network representation learning has received a lot of attention from researchers in recent years.A number of models based on low-dimensional vector representation of nodes in network structure learning networks,such as DeepWalk,have been developed with good results in tasks such as node classification and link prediction.However,with the network size increases,there are computational bottlenecks with multiple network embedding algorithms.To mitigate this problem,no-learning methods such as random projection can be used,but critical information about the network structure may be lost,resulting in degraded algorithm performance.In this paper,a post-processing algorithm for network embedding(PPNE)is proposed,which uses random projection as well as principal component analysis to effectively retain key information and maintain a higher order approximation of the network structure.Experiments are conducted on three public datasets for node classification and link prediction tasks,while the performance of the PPNE algorithm is verified against other network embedding algorithms.The experimental results show that the PPNE algorithm has a large improvement over other algorithms in terms of both perfor-mance and running time,and the algorithm has a speed improvement of at least two orders of magnitude over other learning-based algorithms while ensuring good task performance.

关 键 词：随机投影 主成分分析 网络嵌入 结点分类 链接预测 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]