图嵌入算法研究进展

刘华玲，张国祥，马俊

（上海对外经贸大学统计与信息学院，上海 201600）

0 引 言

现实世界如同一个完整的复杂系统，每时每刻展示着各主体间的联系与交互，而由节点与连边构成的图网络可以有效储存和表示世界各实体间的属性标签及交互信息，自然契合现实世界的系统特点。因此，利用图来研究和表示现实世界中的系统性问题具有合理性和可行性[1]。随着社会的发展与演化，在多种场景中已形成客观的真实网络，如交通网络、社交网络、通信网络和生物遗传网络等，这些均以图数据的形式表示与存储。

近年来，图数据呈现海量、异构、动态、非线性且高维发展的态势，机器学习模型的非线性对数据维度的选择具有较高的要求，面对日趋复杂的信息网络，能否进行有效合理的嵌入表达成为学术界未来研 究 的 重 点[2]。 图 嵌 入（graph embedding，也 称network embedding）是解决如何将现实世界的信息抽象表征为可输入算法模型的向量或张量的一种技术方法[3]，是一种将图数据（高维稀疏的矩阵）映射为低维稠密向量的过程，研究要解决的是找到一种合理的图嵌入方法，将复杂的高维数据表示为低维向量集[4]。此类向量集可供下游的机器学习模型使用，进而解决如社区发现、推荐系统[5-6]、连接预测[7-8]、节点分类或聚类等实际应用问题。

本文的主要贡献：从基于降维方法的图嵌入[1]、矩阵分解的图嵌入[6]、网络拓扑结构信息的图嵌入、神经网络的图嵌入、生成式对抗网络的图嵌入以及超图网络的图嵌入对该领域前沿算法的基本原理及核心思想进行了梳理和分类研究，结合近年来学术界、工业界的前沿研究，对图嵌入的实际应用进行了归纳，给出了图嵌入算法的性能评价指标和常用测评数据集，并对图嵌入算法的发展进行了总结和展望。

1 图嵌入算法的基本定义及原理

1.1 基本定义

1.2 原 理

图嵌入算法是一种将图数据映射为低维稠密向量集的过程，其中作为输入的图数据属于高维稀疏的抽象空间，经映射后，图数据中节点或连边等信息将在低维稠密的空间中嵌入表示[7]，故通过图嵌入，将海量的高维、异构、动态且复杂的图数据[3]处理为可高效输入机器学习算法的嵌入向量或向量集。根据输出粒度的不同，图嵌入的输出结果包括节点嵌入、连边嵌入、混合嵌入和全图嵌入四类，嵌入后的向量或向量集仍带有图的拓扑结构、连边关系、权重和子图等属性信息。此类向量集主要应用于节点分类、节点聚类、链接预测、图重构、图信息可视化、社区发现和推荐系统等，如图1所示。

图1 图嵌入原理Fig.1 Graph embedding principle

2 模型与算法

早期，图数据量小、结构常规且维度较低，往往将图嵌入作为一种降维技术。首先将基于邻域的一组n个D维节点构建为一个相似图，然后将图的节点嵌入至d（d≪D）维向量空间，使相互链接的节点彼此更靠近，如拉普拉斯特征图和局部线性嵌入（locally linear embedding，LLE）[1]，主要用于解决可伸缩性，其时间复杂度为O（|V|2）[8]。

2010年后，图嵌入研究转向可扩展的技术领域，以迎合并较好地利用实际网络数据的稀疏性。文献[1]运用邻接矩阵的近似分解，提出了大规模信息网络嵌入方法（large-scale information network embedding，LINE）[1]，尝试通过保留一阶和二阶邻近度，扩展LINE，通过通用的奇异值分解（singular value decomposition，SVD）处理相似度矩阵，从而保留其高阶邻近度[6]。结构化深度网络嵌入（structural deep network embedding，SDNE）通过自动编码器嵌入节点并捕获其高度非线性的依存关系[9]。此类可伸缩方法的时间复杂度为O（|V|2）。

近年来，随着大数据、云计算、物联网等新兴技术的不断发展，海量数据的产生和利用场景的不断变化，学术及工业界针对不同的数据应用场景提出了不同的图嵌入算法与模型，共分六类：（1）基于降维方法的图嵌入；（2）基于矩阵分解的图嵌入；（3）基于网络拓扑结构信息的图嵌入；（4）基于神经网络的图嵌入；（5）基于生成式对抗网络的图嵌入；（6）基于超图网络的图嵌入。见表1。

表1 嵌入模型概况Table 1 Embedded model overview

2.1 基于降维方法的图嵌入算法

经典的图嵌入算法是将高维稀疏的图数据的维数降至低维稠密空间进行表示，降维后仍需保留原始数据的属性，通常可分为线性和非线性2种[10]。

2.1.1 线性降维方法

最具代表性的线性降维方法——主成分分析（principal component analysis，PCA）[11]是一种使用较广的无监督降维方法，即用原始数据中方差较大的主成分代表原始数据的重要结构信息，方差较小的代表噪声，因此，经PCA计算后的低维表示最大化了原始数据的差异[12]。通过求解特征值w，得到线性变换矩阵W∈RD×d，以提取最大方差的权重向量，降维结果中各主成分呈正交关系，可通过分解矩阵协方差的特征求解[13]。

文献[14]提出的线性判别分析（linear discriminant analysis，LDA）是一种有监督的降维方法，数据集中的每个样本均为有类别的输出，且假设数据集中每个类别均呈高斯分布，然后通过使数据的类间分布和类内分布间的比值最大化，求得线性投影矩阵W∈RD×d。而多维缩放（multidimensional scaling，MDS）[15]模型是一种在低维空间展示“距离”数据结构的流行学习方法，保留了数据的空间距离，得到相异性矩阵D，在尽可能保留数据相异性的前提下生成低维向量表示[16]。

2.1.2 非线性降维方法

非线性降维（nonlinear dimensionality redection，NLDR）[17]方法可用于流行学习，自动学习数据的非线性结构，文献[18]提出的等距特征映射（isometric feature mapping，Isomap）也称等度量映射，能精确保留所有特征向量间的距离，可应用于降维、可视化等领域。

LLE[1]作为流行学习中经典的非线性降维方法，可使降维后的数据集较好地保留原始数据的流行结构和局部特征向量间的线性结构；内核法（kernel methods）[19]是一种与Isomap、LLE相当的非线性降维方法，可用于仅需计算数据对间内积的场合，其优点是使原始空间中线性不可分的数据在新的高维空间中分离，其中内核PCA法通常用于多项式或高斯内核的非线性降维。

2.2 基于矩阵分解的图嵌入算法

基于矩阵分解的图嵌入算法常以矩阵的形式表示图的属性（如节点的成对相似性），并进行矩阵分解得到节点的嵌入式表达[1]。其中拉普拉斯特征图法[20]通过最小化成本函数Y，确保在流形上彼此接近的点映射至低维空间后仍相互接近。为控制映射后的误差，对相似映射后距离变远的节点以更大惩罚。

节点邻近矩阵分解法[21]则通过最小化目标函数min|W-YYTc|，并利用矩阵分解计算低维空间中的节点邻近度，其中，W为节点间的邻近矩阵，Y为节点的嵌入，Yc为上下文节点的嵌入。此外，HSCA[22]模型是对TADW模型的改进，基于skipgram和hierarchical softmax学习分布式单词表示，HSCA的目标函数式为

其中，第1项，使TADW的矩阵分解误差最小化；第2项，对W和H施加低级约束，并用参数λ进行协调；最后的正则化项，强制网络中邻近点间的结构同质化。该方法将使连接的节点在网络表示中彼此更接近。

基于DeepWalk改进的算法，其概率模型和目标函数普遍难以解释如何保留图的高阶相似性。为解决此类问题，文献[23]提出了GraRep模型，通过邻接矩阵相乘k次得到第k阶过度矩阵Ak，定义过度概率，并由skip-gram模型和负采样方法定义损失函数，使嵌入结果保留了嵌入空间中图的高阶相似性。而HOPE[6]模型在计算高阶相似性时保留了非对称传递性，非对称传递性指有向图之间特定的相关性。文献[6]对几种高阶近似性的计算方法，如卡兹指数法[24]、基于 PageRank的方法、共同邻居法和Adamic-Adar法进行了实验，其中节点i的嵌入表达Vi可通过分解邻近矩阵S求得，再用SVD方法等选取前K个特征值，对矩阵S进行分解。

2.3 基于网络拓扑结构信息的图嵌入算法

较著名的图嵌入算法为 DeepWalk[25]，借鉴自然语言处理中重要的词嵌入算法word2vec，通过随机游走将图嵌入转化为词嵌入问题。从每个节点出发若干次，用均匀采样方式选择当前节点的邻接节点，并作为下一步的节点进行随机游走，当游走路径达到规定长度时，停止本次游走，然后将这些节点序列作为训练样本输入skip-gram模型进行训练，得到节点的嵌入表达。因此，可将DeepWalk视为一种连接序列嵌入和图嵌入的过渡方法，其目标是最大化随机游走序列S中顶点对的平均对数概率，使具有相似邻域（具有较大的二阶相似度）的节点共享相似的嵌入。其目标函数为

文献[26-28]证明了DeepWalk算法相当于矩阵分解M=WT×H，M∈ R|V|×|V|中的每个Mij表示顶点Vi在固定步数内可到达顶点Vj的平均概率的对数，W∈Rk×|V|为顶点的嵌入表示，但H∈Rk×|V|中的信息很少被用于经典的DeepWalk模型。

DeepWalk采用深度优先采样（depth-first sampling，DFS）策略，即从源节点开始以距离递增的方式依次采样产生节点序列，其得到的节点序列具有同质性，即以距离作为节点间相似性的度量。与DFS策略相反，广度优先采样（breadth-first sampling，BFS）策略是从源节点开始，探索当前深度所有邻居节点的结构性，用节点在网络中的位置和结构表示相似性。斯坦福大学在DeepWalk基础上推出了 node2vec[30]。node2vec通过调整随机游走权重，在同质性和结构性间进行权衡，其中提出的概率模型，通过设立节点间的跳转概率控制对BFS和DFS的倾向性。图2显示的为node2vec算法从节点t跳转至节点v后下一步以节点v为起点继续跳转的概率。

图2 Node2vec算法节点跳转原理Fig.2 Node2vec algorithm node jump principle

从节点v跳转至下一节点x的概率为

其中，ωvx为边Vx的权重，

dtx为节点t到节点x的距离，返回参数p和进出参数q共同控制随机游走的倾向性，其中，p越小，随机游走回节点t的可能性越大，即算法更注重表达网络的同质性；q越小，随机游走到远方节点的可能性越大，即更注重表达网络的结构性。反之，当前节点更可能在附近节点游走，同时node2vec所体现的网络的同质性和结构性在推荐系统中可得到直观解释。

LINE[1]是一种基于邻域相似假设的算法，与DeepWalk使用DFS构造邻域不同，LINE可看作是一种用广度优先搜索（breath first search，BFS）构造邻域算法。在现实世界网络中，相互联系的节点通常表现为较相似或向量距离接近，LINE算法将其定义为一阶近邻，用于描述相邻顶点之间的局部相似度；二阶近邻则用2个节点间的共同邻居度量，描述节点与邻域的关系。LINE算法分别对所有具有一阶近邻关系和二阶近邻关系的节点对进行概率建模，通过最小化其概率分布和经验分布的KL散度，得到2个嵌入；由不同目标函数训练的2个嵌入向量连接每个顶点，可更好地表示输入图。LINE通过捕捉网络中的一阶近邻关系和二阶近邻关系，更完整地描述网络，其适用于有向图、无向图、有权图和无权图。

GraphSAGE[1]是一种利用顶点属性信息高效产生未知顶点向量进行嵌入的一种归纳式（inductive）学习框架。通过学习对邻居顶点进行聚合表示的函数产生目标顶点的嵌入向量，其运行流程可分为顶点采样、信息聚合和向量表达3个步骤，该模型训练的聚合函数可将本地邻域的特征（如文本属性、节点特征）整合后传递给目标节点Vi，并更新节点Vi的隐藏状态，此方法可利用节点的邻域信息补充损失的局部结构信息，提升表示向量的准确性。

2.4 基于神经网络的图嵌入算法

2010年后，RNNs和CNNs等神经网络模型快速发展，并试图将其推广应用于图模型。首先将CNN模型作为基础算法，或采用专为欧几里得空间设计的原始CNN模型，通过格式化输入的图模型，以适应原始CNN模型的输入要求，或将深度神经网络模型泛化为非欧几里得图。

其中，SDNE[26]模型和 node2vec[29]是同时期两项并列的工作，均发表于2016年的KDD会议论文集，可看作是LINE的扩展，首次将深度学习应用于网络表示学习。SDNE中的相似度定义与LINE相同，使用自动编码器结构同时优化一阶和二阶相似度，而LINE模型则分别进行优化，学习得到的向量表示能保留局部和全局结构，并对稀疏网络具有鲁棒性，结构如图3所示。

图3 SDNE模型结构Fig.3 SDNE model structure

GCN模型[27]可对任意大小和形状的图进行端到端学习，用卷积算子并采取迭代聚合方法对节点的邻近节点进行嵌入表示，该方法已广泛用于图结构化数据的半监督学习。由于GCN模型通常只有2个卷积层，因此无法很好地解释其工作原理。

研究表明，GCN模型是拉普拉斯平滑的一种特殊形式[30-31]，模型效果良好，若使用2个以上卷积层，将导致过度平滑，令节点的特征相似，分离困难。

带有连边信息的增强图嵌入（enhanced graph embedding with side information，EGES）[32]模型于2018年由阿里巴巴推出，其基本思想是在嵌入过程中引入带权重的补充信息，解决冷启动问题。该模型是为解决推荐问题而推出的一款基于DeepWalk算法的改进模型，面向推荐系统找回阶段，其核心任务是计算物品间的相似度。文献[32]根据用户历史行为构建物品图，然后用DeepWalk学习每个物品的嵌入表示，即基图嵌入（base graph embedding，BGE），同时为解决少量或无交互行为物品的准确表示问题，提出了使用连边信息增强其学习表示过程，并针对不同连边的贡献度，提出了一种用于学习带有连边信息的嵌入表示的加权机制。EGES并无复杂的理论创新，但给出了能融合多种嵌入表示的算法，解决了因某类信息缺失出现冷启动的问题，是一种实用性较强的图嵌入算法。

2.5 基于生成式对抗网络的图嵌入算法

生成式对抗网络（generative adversarial network，GAN）[33]是一种非监督学习算法，通过 2 个神经网络之间相互对抗的方式进行学习。自2014年GAN问世以来，其在计算机视觉等领域广受关注，在其他领域的应用研究相对较少，2019年后，逐渐将GAN思想应用于图嵌入表达。其中，文献[31]将图嵌入学习分为生成式（generative）和判别式（discriminative）2种，并提出GraphGAN模型，该模型包含判别器D(v，vc；θD)和生成器G(v∣vc；θG)，借鉴GAN中常见的对抗机制，即生成器G尽可能地逼近ptrue(v∣vc)，找到与vc的相邻节点极相似的节点，以欺骗判别器D；反之，判别器D则会检测给定的节点v是由生成器生成的还是vc的真实邻近节点。故GraphGAN模型的核心是目标函数：

GraphGAN[30]模型，为实现图中所有节点的嵌入，对每个节点做抽样正样本和生成负样本操作，但这在现实大型网络中难以实现。文献[31]提出的NetRA模型可解决当抽样较稀疏时图嵌入过拟合的问题，通过引入GAN模型的正则项，使编码器提取到更有用的信息。模型框架如图4所示，包括自动编码器、GAN和图嵌入三部分，其中，文献[31]用LSTM[34]作为编码器，在对GAN训练时需将正负样本间的差异反馈给编码器，帮助编码器提取更有效的信息以区分伪样本，避免编码器出现过拟合[35]。图嵌入部分通过保留节点与节点间的连边信息获得局部的连接关系，NetRA模型并不只有一个GAN结构，而是将GAN当作正则项的一部分嵌入模型得到节点的表征，这为GAN模型的应用提供了不同思路[36]。

图4 NetRA模型框架Fig.4 NetRA model framework

2.6 基于超图（hyper-graph）网络的图嵌入算法

近年来，随着社交网络图嵌入应用的激增，简单的图网络已不足以表示真实网络中的复杂信息，真实网络中节点间的关系远较顶点到顶点的连边关系复杂，与传统的图网络不同，超图网络中边的度可能大于2，且所有相关节点通过超边连接形成超节点，一个超图可用尺寸为|V|×|E|的入射矩阵H表示[37]。对每对超级节点均通过共享的事件顶点建立连接。因此，超图可更好地表示网络图中的社区结构，超边的这些特性使得超图更具挑战性，表2为图与超图的特性对比。超图的嵌入表示学习是近年来的研究热点，其为社会网络建模提供了有力的工具，由于超图算法可用于许多其他方式难以实现的嵌入应用场景，且超图可看作是简单图的一种变体，只要对传统图的嵌入算法稍加修改便可将其应用于超图嵌入[38-39]。

表2 图与超图的特性对比Table 2 Comparison of characteristics between graphs and hyper-graphs

受GCN中图卷积的启发，HGNN[38]将光谱卷积应用于超图，通过半监督的节点分类任务训练网络，可在卷积层的输出中获得节点表示，模型结构体系如图5所示，超图卷积由超图Laplacian[40]衍生而来，其为正半定性矩阵，特征值为相应的频率，每层的频谱卷积为

其中，X为每层的隐藏嵌入，Dv和De为对角矩阵，输出分别为顶点和超边的度。

图5 图和超图图示[38]Fig.5 Illustrations of graphs and hyper-graphs

2.7 图嵌入算法对比分析

图嵌入算法的特征分析见表3。经典的降维方法已被广泛用于图嵌入算法，其原理较简单且容易理解，但大多模型无法表示高阶相似度。基于网络拓扑结构信息的算法不是对整图进行嵌入表示，而是对每个节点的邻居信息进行采样，此类算法可以捕获节点间的远距离关系，但嵌入后的网络表示无法完全保留原始图的全部结构信息。

表3 图嵌入算法特性分析Table 3 Characteristic analysis of graph embedding algorithms

基于矩阵分解的图嵌入算法，根据节点间成对相似度的统计信息进行图嵌入，为捕获全局结构，一些算法考虑了全局节点的邻近性，能细粒度地捕获1～k阶节点的相似度信息，其性能优于基于随机游走的深度学习算法，因随机游走算法仅使用局部采样窗口，易损失图的全局结构信息，但由于邻接矩阵的构造及特征分解计算和存储复杂性更高，故此类图嵌入算法并不适合大规模的图数据场景，且算法可扩展性较差。此外，LLE算法、图拉普拉斯特征图法仅保留了图的一阶相似度，在保持图的二阶甚至更高阶相似度方面存在不足，易丢失原始图的部分结构信息。

深度学习在不同的图嵌入算法中均表现良好，能从复杂的图结构中自动识别有用的表示。例如，基于随机游走的深度学习（如DeepWalk、node2vec等）可通过图上的采样路径自动利用邻域结构；无随机游走的深度学习可对同构图（如GCN、GraphSAGE）中的可变尺寸子图结构进行建模，作为有用的表示。同时，基于深度学习的图嵌入算法能捕获网络中节点间的高阶非线性关系。传统线性降维算法无法保持图的非线性结构，基于深度神经网络的图嵌入算法主要对节点表示间的非线性进行建模，能捕获网络结构和属性中的非线性关系，并通过PPMI矩阵，避免大量无效节点的嵌入。其局限性为由于深度学习框架主要是基于神经网络结构搭建的，在模型参数优化上严重依赖现代GPU的性能，且模型处理难，解释性差，此外，适用BP神经网络训练模型参数的时间复杂度较高。大型图嵌入算法（如LGCL、GPNN）可处理大规模图数据，适合嵌入包含数千甚至百万个节点的社交网络，但仍存在限制。首先，时间复杂度很高；其次，从本质上看图都是动态的，例如学术数据库中的社交网络图和引文图均在不断变化中，且图的结构复杂性随时间的推移不断增加，故该类方法通常只适用于静态图；最后，要求对原始输入数据进行预处理，故需要适用性强的可扩展性嵌入技术。

基于生成式对抗网络的图嵌入算法，在一个统一的模型中，利用图结构、节点属性等图结构信息进行嵌入学习，由于基于某些分布假设的观测建模难以证明其合理性，且需要大量训练数据用以拟合，故此类算法对小规模图数据的嵌入效果不佳。

基于超图网络的图嵌入算法功能强大，可用于复杂、动态的图数据网络，但实施困难，尽管可用其他途径替代图嵌入，但大多数算法尚处于“证明概念”的研究阶段，未得到广泛使用。内核法可将图映射为单个向量，所得向量适用于执行整图层面的应用任务（如图分类），由于只需枚举图中所包含的子图结构，因此较深度网络模型更有效，但因在图嵌入过程中会产生冗余的子图结构，令嵌入表示维度呈几何级数增加。

3 图嵌入算法的应用

因图嵌入算法可在时间与空间上有效解决图数据的向量表示问题，所以图嵌入算法将有利于后续图数据分析。根据图嵌入算法的输入特征，将图嵌入算法的应用分为三类：与节点相关的应用、与连边相关的应用和与整图相关的应用。

3.1 与节点相关的应用

3.1.1 节点分类

节点分类已被广泛应用于社区发现[41]、欺诈识别[42]和推荐系统[43-45]等任务，通过在标记节点嵌入的结合上用分类器进行训练实现，如M-NMF[44]、SDNE、HNE[45]等使用SVM分类器，DeepWalk、GraRep等用逻辑回归作为分类模型，GCN则设计了一个统一框架共同优化图嵌入和节点分类的效果，学习每个节点分类的特定表示。

经综合平衡分析后，各试验因素的最优组合确定为A3B1C2，即吸孔直径按位，种箱相对于滚筒的角度为0°，输送带的速度为0.03m/s。此时空穴率为9.26%，单粒率为68.52%，重播率为22.22%。

3.1.2 节点聚类

节点聚类，即将图中相似的节点分为一组，以获得彼此相似的不同节点分组，其作为一种无监督算法可用于节点标签不可用的情景。现有的模型如M-NMF、GraRep、HNE、DNGR[46]等均将K-means作为聚类算法，文献[47-48]同时采用优化聚类和图嵌入，以学习特定聚类的节点表示。节点聚类已被广泛应用于社区发现、欺诈识别、推荐系统和隐私保护[49]等任务。

3.2 与连边相关的应用

3.2.1 连接预测

图嵌入可帮助推断原始的图结构[50]。通常，原始的图结构并不完整，图嵌入后的低维向量则有望保留不同级别的网络邻近度（如DeepWalk、LINE）以及不同尺度的结构相似度（如GCN、struc2vec），因此，嵌入后的向量将对有关网络结构信息进行编码，以预测不完整图中的丢失链接。已有文献对图嵌入驱动连接预测大多基于同构图，涉及异构图连接预测的图嵌入工作处理与解释很困难。其中大型图嵌入算法（如LGCL和GPNN）可处理大规模的图数据。

3.2.2 三元组预测

三元组分类在知识图谱中有特定应用，如文献[51-53]均基于三元组的预测完成知识图谱的相关任务，判断未知三元组〈h；r；t〉的分类是否正确，即预测h与t之间的关系是否为r。

3.3 与图相关的应用

3.3.1 图分类

图分类是将类别标签分配给整幅图，当图作为一个数据单位时，此应用将变得十分重要，例如文献[51]，每幅图表示一种化合物，大多情况下，全图嵌入往往用于计算整图级别的相似度[49]。近年来，已出现为相似性图[54]匹配节点嵌入，用每幅图表示一组节点嵌入向量，进而比较基于组节点的2幅嵌入图。文献[54]将图分解为一组子结构，然后将每个子结构嵌入为向量表示，进而通过子结构间的相似性比较图的相似性。

3.3.2 图重构

图重构与连接预测具有相似性，但二者应用目的不同，评价标准也有差异。图重构，旨在重构和修正图数据中已存在的连边，在实验中，将图中所有节点作为训练集，将移除连边后的节点作为测试集，利用预测结果对原始图中节点对的连边进行重构和修正；连接预测，旨在预测图中未知或可能存在的连边，从而补充节点对间的连边。

3.3.3 图拓扑信息可视化

图拓扑信息通常是在低维空间进行的可视化表达，所有节点均可作为2D向量嵌入，如在2D空间中，用不同颜色绘制的向量表示节点类别，图嵌入也可用于降维，可视化图的拓扑信息（如PCA和t-SNE[55]），DeepWalk 通过可视化 Zachary′s空手道俱乐部网络，说明嵌入方法的优点，LINE可视化DBLP网络，表明LINE能将同一领域的作者聚在一起。将SDNE应用于20-Newsgroup文档相似性网络，并基于主题对文档进行聚类。

4 实验数据集及评价指标

4.1 实验数据集

根据不同的应用领域选取相应的实验数据集和评价指标，常用的五类数据集为：（1）社交网络，（2）合成网络，（3）语言网络，（4）协作网络，（5）生物网络，共计10个数据集，如表4所示。

表4 数据集概况Table 4 Data set overview

4.2 评价指标

5 总结与展望

对近年来图嵌入领域的研究进行了全面梳理，首先，对图嵌入进行了定义并介绍了其基本原理，分析了基于降维方法的、基于矩阵分解的、基于网络拓扑结构信息的、基于神经网络的、基于生成式对抗网络的和基于超图网络的六类图嵌入算法的原理、创新点和嵌入效果等，系统梳理了图嵌入算法的发展历程，对比分析了各算法的优劣，介绍了图嵌入算法的主要应用领域，并根据应用领域与顶点、连边和整图的关系将图嵌入算法分为三类，还介绍了常用数据集及对应的评价指标。

虽然图嵌入算法在处理高维稀疏数据、计算效率和嵌入效果上已有大幅提升，但面对不断发展和变化的数据及应用要求，图嵌入算法仍需进一步发展和创新。

5.1 动态图嵌入

动态图嵌入将是图嵌入算法未来发展的重要方向。在现实世界中，图数据是动态的，如微博的社交圈、DBLP中的引文图等每时每刻都在动态变化中，图的结构（节点、连边）信息亦呈动态变化状态。一方面，图结构随时间不断变化，新的节点或连边不断出现，老的节点或连边可能消失；另一方面，可通过不断变化的信息描述节点或连边。已有文献主要集中于静态图的嵌入研究，对动态图的嵌入研究很少。与静态图嵌入算法不同，动态图嵌入算法需具更强的伸缩性和增量性，以便有效处理图的动态变化，而现有的大多数嵌入算法不符合此要求，且动态图嵌入算法存在效率低下等问题，因此，如何对动态图有效进行图嵌入将是未来重要的研究方向之一[56]。

5.2 图嵌入的可扩展性

随着社交网络规模的快速增长，其节点和连边数以亿计，针对更大规模和更高多样性的图网络，如何有效、准确地嵌入海量图数据是面临的一大挑战。尽管深度神经网络模型具有最为先进的功能，但依靠现代GPU查找最佳参数的效率较低，需要建立更合适的模型，一种可能是用前馈机器学习处理无BP的图网络，另一种是研究更优的图粗化或分区方法对数据进行预处理。

5.3 图嵌入的可解释性

最新的图嵌入算法大多为用BP神经网络训练并确定参数的CNNs模型，训练复杂度较高，其中Quickprop用于降低训练复杂度，由于用BP神经网络迭代训练模型耗时较长且对硬件的要求较高，最近，出现了有关神经网络模型的可解释性研究[54，56]，文献[54]采用基于FFdata的方法对当前层的网络参数进行基于单词通过的前一层输出的数据统计，试图用可解释的前馈设计解释CNNs模型，所得结论说明将前馈机器学习方法应用于图嵌入算法是有效的，因此，可解释性的设计可代替高级神经网络的体系结构，进而为当前图嵌入相关任务的研究提供启发。