2022最新图嵌入模型综述

图分析用于深入挖掘图数据的内在特征,然而图作为非欧几里德数据,传统的数据分析方法普遍存在较高的计算量和空间开销。图嵌入是一种解决图分析问题的有效方法,其将原始图数据转换到低维空间并保留关键信息,从而提升节点分类、链接预测、节点聚类等下游任务的性能。与以往的研究不同,同时对静态图和动态图嵌入文献进行全面回顾,我们提出一种静态图嵌入和动态图嵌入通用分类方法, 即基于矩阵分解的图嵌入、基于随机游走的图嵌入、基于自编码器的图嵌入、基于图神经网络（GNN）的图嵌入和基于其他方法的图嵌入。其次,对静态图和动态图方法的理论相关性进行分析,对模型核心策略、下游任务和数据集进行全面总结。最后,提出了四个图嵌入的潜在研究方向。

http://fcst.ceaj.org/CN/10.3778/j.issn.1673-9418.2104020

图是复杂系统中常用的信息载体,可以表示现实中许多复杂关系,如社交网络[1]、犯罪网络[2]、交通网络[3]等。图结构作为一种非欧几里德数据,很难直接应用卷积神经网络（convolutional neural network,CNN）[4]和循环神经网络（recurrent neural network,RNN）[5]等深度学习方法[6]。为了构造用于图数据挖掘的特征表示,图嵌入将节点映射到低维空间,生成保留原始图中某些重要信息的低维向量。目前,图嵌入不仅在节点分类[7]、链接预测[8]、节点聚类[9]、可视化[10]等复杂网络上的机器学习任务中获得成功,还广泛用于社交影响力建模[11]、内容推荐[12]等现实任务。

早期的图嵌入算法主要用于数据降维,通过邻域关系构建相似度图,将节点嵌入低维向量空间,并保持相连节点向量的相似性。这类方法通常时间复杂度高,很难扩展到大型图上。近年来,图嵌入算法转向扩展性强的方法。例如,矩阵分解方法[13]使用邻接矩阵的近似分解作为嵌入;随机游走法[14]将游走序列输入到Skip-Gram[15]生成嵌入。这些方法利用图的稀疏性降低了时间复杂度。当前,很多综述[16,17,18,19,20,21]对图嵌入方法进行了归纳与总结,但存在两大局限：一是部分综述仅涉及传统方法介绍,许多新模型没有纳入研究;二是这些综述只关注静态图嵌入或动态图嵌入,忽略了二者之间的关联性。

本文对图嵌入方法进行全面系统性综述,有以下三方面的贡献：（1）提出一种新的图嵌入分类法,同时对静态图和动态图方法进行分类;（2）对现有模型进行系统性分析,为理解现有方法提供新视角;（3）提出了四个图嵌入的潜在研究方向。