Graph Embedding Techniques, Applications, and Performance: A Survey（图嵌入技术、应用及性能）

原文https://arxiv.org/pdf/1705.02801.pdf

定义

1.图
2.一阶相似性
3.二阶相似性

嵌入方法的分类

1.因子分解方法（3.3）
2.随机漫步技术（3.4）
3.深度学习（3.5）
4.其他杂项战略（3.6）

图嵌入的研究内容及其进化

1.2000s.为一组基于邻域的n个D维点建立一个相似度图，然后把图的节点嵌入到d维向量空间中，其中d<<D.这种嵌入的观点能保证相连的节点在向量空间中靠近彼此（Eg.拉普拉斯特征映射算法;局部线性嵌入）
该算法时间复杂度

2.2010.利用真实世界的稀疏性得到可拓展的图嵌入技术。(Eg. Graph Factorization使用邻接矩阵的近似因子分解作为嵌入；LINE拓展了上述方法并尝试保留了一阶相似性以及二阶相似性，HOPE延伸了LINE尝试通过常规的奇异值分解（SVD）来分解相似度矩阵而非邻接矩阵去保留更高阶的距离;SDNE使用了高度非线性的依赖)
新的可拓展的方法的时间复杂度为O(|E|)

图嵌入方法的分类

将图嵌入方法分为广义的三个类别

1.基于矩阵分解

基于因数分解的算法表示节点之间的连接构成了矩阵，再对该矩阵进行因式分解以获得嵌入。该矩阵被用于表示包括节点邻接矩阵，拉普拉斯矩阵，节点跃迁概率矩阵，以及Katz相似度矩阵。分解代表性矩阵的方法根据矩阵类型的不同而变化。
半正定矩阵（如拉普拉斯矩阵）可以应用特征值分解
非结构化矩阵 -》 可以应用梯度下降法在线性时间内获得嵌入。

(1)局部线性嵌入LLE
假设每个节点在潜入空间内都是其邻节点的结合，将约束最优化问题简化成特征值问题，得到系数矩阵中最底的d+1个特征向量，并丢弃最小特征值所对应的特征向量。

(2)拉普拉斯特征映射算法
Laplacian Eigenmaps
保证当Wij的权值较高所对应的俩个节点在嵌入空间的距离较近。
找到第d小的正则化的拉普拉斯矩阵特征值所对应的特征向量。

(3)柯西图嵌入Cauchy Graph Embedding
对于嵌入中的距离使用二次罚函数。作者根据节点之间的距离的相对强调的不同（相似度/不相似度），提出了几种不同的变体，包括高斯函数、指数函数和线性嵌入。

(4)结构保存嵌入SPE
拉普拉斯特征映射方法的继承。目标是重建输入图。嵌入被保存为一个半正定核矩阵K和一个连接算法。为了处理图中的噪声，需要增加一个松弛变量。

(5)图分解GF
图分解是首个能够在O(|E|)的时间复杂度内获得嵌入的方法。GF分解了图的邻接矩阵，最小化了损失函数。

(6)GraRep
以 定义了节点跃迁可能性 并通过最小化保存了k阶相似性。缺点是可伸缩性。

(7)HOPE
HOPE通过最小化.其中S是相似度矩阵.作者基于多种相似度度量方法做了实验。相似度这使得HOPE能够使用通用的奇异值分解（SVD）来获得嵌入。

(8)额外变体
为了给高维数据降维，还有许多可以执行图嵌入的方法。如主成分分析PCA,线性判别分析LDA,多维拓展MDS,本地属性保存LPP.和内核特征映射。
还有许多最新的方法关注联合学习网络结构以及网络中可用的额外节点属性信息。

2.基于随机漫步

随机漫步已经被用来近似于图中的许多属性，包括节点中心和相似度。当一个人只能部分地观察这个图形，或者这个图形太大而不能全部测量时，它们就特别有用。在图中使用随机漫步的方法来获得节点表示：DeepWalk和node2vec是两个例子。

(1)DeepWalk
DeepWalk通过最大化观察最后k个节点的概率，以及在以vi为中心的随机漫步中的下k个节点，保持了节点之间的高阶相似性。

(2)node2vec
与DeepWalk相同，node2vec通过最大限度地增加固定长度随机漫步中后续节点发生的概率，保持节点间的高距离。他们之间最关键区别是node2vec采用的是双随机漫步，它提供了在广度优先（BFS）和深度优先（DFS）图搜索之间的交易，因此产生了比DeepWalk更优质、更有信息的嵌入。

(3)网络的分层表示学习HARP
DeepWalk和node2vec为模型训练随机初始化节点嵌入。由于它们的目标函数是非凸的，所以这样的初始化可以被卡在局部的最优值中。
通过更好的权重初始化，哈普引入了一种改进解决方案和避免局部优化的策略。为了达到这个目的，通过使用图形粗化来聚合前一层层次的节点，HARP创建了节点的层次结构。然后，它生成最粗图的嵌入，并根据已学习的嵌入来初始化精确图（在层次结构中的一个）的节点嵌入。它通过层次结构传播这种嵌入，以获得原始图的嵌入。因此，HARP可以与诸如DeepWalk和node2vec等随机漫步的方法结合使用，从而获得更好的优化功能解决方案。

(4)Walklets
DeepWalk和node2vec通过生成多个随机漫步，含蓄地保留了节点之间的高阶近距离，由于其随机特性，在不同的距离上连接节点。另一方面，像GF和HOPE这样的基于因子分解的方法可以通过在目标函数中对节点进行建模来显式地保存节点之间的距离。walklet将这种显式建模与随机漫步的理念结合在一起。该模型通过跳过图中的一些节点来修改在DeepWalk中使用的随机漫步策略。这是为多个跳跃长度执行的，类似于在GraRep中分解Ak，而产生的随机漫步集用于训练类似于DeepWalk的模型。

(5)额外变体
最近提出的上述方法有几种不同的变体。类似于基于因子分解增加图结构中的节点属性的方法、Gen向量、鉴别深度随机漫步（DDRW）、三方深网络表示（TriDNR）和扩展随机漫步，共同学习网络结构和节点属性。

3.基于深度学习的方法

对深度学习的不断增长的研究已经导致了大量基于神经网络的方法应用于图表。深度自动编码器由于其在数据中建模非线性结构的能力而被用于维度的减少。最近，SDNE，DNGR利用这种深度自动编码器的能力生成了一个嵌入模型，可以在图中捕捉非线性。

(1)构造深度网络嵌入SDNE
王等人提出要使用深度自动编码器来保存网络的第一和第二阶相似性。他们通过共同优化这两个距离来实现这一目标。该方法使用高度非线性的函数来获得嵌入。该模型由两个部分组成：无人监督和监督。前者由一个自动编码器组成，它的目标是为一个可以重建其社区的节点找到一个嵌入。后者基于Laplacian特征映射，当相似的顶点在嵌入空间中相互映射时，它会施加一个惩罚。

(2)用于学习图形表示的深层神经网络DNGR
DNGR将随机冲浪与深度自动编码器结合在一起。该模型由3个组成部分组成：随机冲浪、正点互信息（PPMI）计算和堆叠去噪的自动编码器。在输入图上使用随机冲浪模型来产生概率共发生矩阵，类似于HOPE中的相似矩阵。矩阵被转换成一个PPMI矩阵，并将其输入到一个堆叠的去噪的自动编码器中，以获得嵌入。输入PPMI矩阵可以确保自动编码器模型能够捕获更高阶的接近度。此外，使用堆叠去噪的自动编码器，在图中存在噪声的情况下，支持模型的健壮性，以及捕获诸如链接预测和节点分类等任务所需的底层结构。

(3)图卷积网络
对于大型稀疏图而言，SDNE、DNGR的效果是昂贵且不理想的。图形卷积网络（GCNs）31通过在图上定义一个卷积运算符来解决这个问题。该模型迭代地聚集了一个节点的邻居的嵌入，并在以前的迭代中使用了获得的嵌入和嵌入的功能来获得新的嵌入。聚集局部邻居的聚合使其具有可伸缩性，并且多次迭代允许学习嵌入一个节点来描述全局邻居。

(4)变分图像自动编码器VGAE
该模型应用一个卷积网络编码器和一个内置产品解码器。它的输入是邻接矩阵并且依赖GCN去学习节点之间的高阶依赖。们的经验表明，与非概率自动编码器相比，使用变分自动编码可以提高性能。

4.其他方法

1.LINE
LINE明确定义了两个函数，分别为第一和二阶相似性，并最小化了两者的组合。一阶近似的函数类似于图分解（GF），因为它们都是为了保持邻接矩阵和内嵌的点积。不同之处在于，GF可以通过直接最小化两者的差来做到这一点。相反，LINE定义了每一对顶点的两个联合概率分布，一个是使用了一个矩阵，另一个使用了嵌入。然后，LINE最小化了这两个分布的kullback-Leibler（KL）散度。相似的定义了二阶相似性的分布和目标函数。

讨论

应用

1.网络压缩
费德等人 介绍了网络压缩的概念（a.k.a。图简化）。 对于图G，他们定义了具有较少边数的压缩G. 目标是更有效地存储网络并更快地运行图形分析算法。 他们通过将原始图划分为二分派并用树替换它们来获得压缩图，从而减少了边数。 多年来，许多研究人员使用基于聚合的方法来压缩图形。 这一系列工作的主要思想是利用图的链接结构来对节点和边进行分组。 Navlakha等人使用信息论中的最小描述长度(MDL)将图形总结为图形汇总和边缘校正。
与这些表示类似，图形嵌入也可以解释为图形的摘要。 王等人和Ou等人通过从嵌入和重建误差评估重建原始图来明确地测试该假设。 它们表明每个节点的低维表示（大约100s）足以重建高精度的图形。

2.可视化
可视化图形的应用可以追溯到1736年，当欧拉用它来解决“Konigsberger Bruckenproblem”时。 近年来，图形可视化已经在软件工程，电路，生物学和社会学中得到应用。 Battista等人 和Eades等人调查了一系列用于绘制图形的方法，并为此目的定义了美学标准。 赫尔曼等人 概括这一点并从信息可视化角度查看它。他们研究和比较用于绘制图形的各种传统布局，包括基于树，3D和双曲线的布局.
由于嵌入表示向量空间中的图形，因此可以应用主成分分析（PCA）和t分布随机邻域嵌入（t-SNE）等维数减少技术来对图形进行可视化。作者 DeepWalk 通过可视化Zachary的空手道俱乐部网络，展示了他们嵌入方法的优点。 LINE 的作者将DBLP合作网络可视化，并表明LINE能够将作者聚集在同一领域。 SDNE的作者将其应用于20-Newsgroup文档相似性网络，以获得基于主题的文档集群。

3.聚类分析
图聚类（也就是说，网络分区）可以是两种类型：（a）基于结构，（b）基于属性的聚类。 前者可以进一步分为两类，即基于社区和结构上等同的聚类。
基于结构的方法旨在找到具有大量簇内边缘和较少簇间边缘的密集子图。 相反，结构等价聚类旨在识别具有相似作用的节点（如桥梁和异常值）。 基于属性的方法除了观察到的链接外，还利用节点标签来聚类节.White 等人在嵌入上使用k-means来聚类节点并可视化在Wordnet和NCAA数据集上获得的聚类，以验证所获得的聚类具有直观的解释。 最近的嵌入方法没有明确地评估它们在这个任务上的模型，因此它是图嵌入社区中一个很有前景的研究领域。

4.链路预测
指预测未来可能在不断发展的网络中出现的缺失交互或链路的任务。在社交网络中，可以用于推荐可能的好友关系，达到更好的用户体验。 Liben Nowell等人，Lu等人和哈桑等人调查该领域的最新进展并将算法分类为（a）基于相似性（局部和全局）（b）基于最大可能性和（c）基于概率的方法。
嵌入可以明确或隐含的捕获网络固有动态，使得应用程序可以链路预测。经验证，在生物网络和社交网络等数据集上，使用嵌入预测的链接比上述传统的基于相似性的链接预测方法更准确。

5.节点分类
指通过已标记的节点和网络中的链接来推断缺少的标签。
通常在网络中，标记一小部分节点。在社交网络中，标签可以表示兴趣，信仰或人口统计。在语言网络中，文档可以用主题或关键词标记，而生物学网络中的实体的标签可以基于功能。由于各种因素，对于大部分节点，标签可能是未知的。例如，在社交网络中，由于隐私问题，许多用户不提供他们的人口统计信息。可以使用标记的节点和网络中的链接来推断缺少的标签。预测这些缺失标签的任务也称为节点分类。 Bhagat等人调查文献中用于此任务的方法。他们将方法分为两类，即基于特征提取和基于随机游走。基于特征的模型基于其邻域和局部网络统计为节点生成特征，然后应用Logistic回归和朴素贝叶斯等分类器来预测标签。基于随机游走的模型通过随机游走传播标签。
嵌入可以被解释为基于网络结构自动提取节点的特征，因此属于第一类。近期关于语言、社会，生物，和协作方面的工作证明了图嵌入可以高精度的预测丢失的标签。

实验设置

系统：Ubuntu 14.04.4 LT .该系统具有32个内核，128 GB RAM和2.6 GHz的时钟速度。

用于基于深度网络的模型的GPU：Nvidia Tesla K40C。

数据集：一个合成数据集和6个真实数据集
(1)SYN-SBM
(2)空手道网络
(3)BlogCatalog网站上列出的博主的社交关系网络
(4)Youtube
(5)HEP-TH 1993。1-2003.4期间高能物理理论论文写作网络
(6)PPI人类蛋白质之间的生物相互作用网络

评估指标：
评估嵌入方法在图形重建和链接预测中的性能的指标：精度k（Pr @ k）和均值平均精度（MAP）。
评估节点分类指标：micro-F1和macro-F1。
指标定义如下：
Pr @ k:指是前k个预测中正确预测的比率。
MAP:估计每个节点的精度，并计算所有节点的平均值
macro-F1:在多标签分类任务中，定义为所有标签的平均F1值
F1值是精确率和召回率的调和均值，即F1=2PR/(P+R)，相当于精确率和召回率的综合评价指标）。精确率（Precision）为TP/(TP+FP)，即为在预测为坏人的人中，预测正确（实际为坏人）的人占比。召回率（Recall）为TP/(TP+FN)，即为在实际为坏人的人中，预测正确（预测为坏人）的人占比。]
micro-F1:micro-F1通过计算总真阳性，假阴性和误差来全局计算F1，给每个实例赋予相同的权重。

实验及分析

在本节中，我们将评估和比较上述任务中的嵌入方法。 对于每个任务，我们显示嵌入维度的数量对性能的影响，并比较方法的超参数灵敏度。 此外，我们将嵌入技术的性能与不同超参数的各种任务相关联，以测试可以在所有任务上表现良好的“全好”嵌入的概念。

图重建

期望以低维的表征进行图嵌入来精确的重构图。
图2展示了通过128维所获得的重建精度。
经过图的重建， 我们观察到虽然方法的性能依赖于数据集，但是保持高阶邻近性的嵌入方法通常优于其他方法。 拉普拉斯特征图在SBM上的良好性能可归因于数据集中缺乏更高阶的结构。 我们还观察到SDNE在所有数据集上始终表现良好。 这可以归因于它从网络中学习复杂结构的能力。 node2vec学习的嵌入具有低重建精度。 这可能是由于高度非线性维度减少，产生非线性流形。 但是，HOPE可以学习线性嵌入但保留更高阶的接近度，可以很好地重建图形而无需任何其他参数。
维度的影响：图3显示了维度对于重建误差的影响。 除了几个例外，随着维度数量的增加，MAP值也会增加。这是直观的，因为更多的维度能够存储更多信息。 我们还观察到SDNE能够以高精度将图形嵌入16维向量空间中，尽管需要解码器参数来获得这样的精度。

可视化

由于嵌入是图中节点的低维向量表示，因此它允许我们可视化节点以理解网络拓扑。 由于不同的嵌入方法保留了网络中不同的结构，它们对节点可视化的能力和解释更加困难。
-- 对于SBM，我们将学习方法的128维嵌入，并输入到t-SNE(t-SNE是目前来说效果最好的数据降维与可视化方法)，来将维度降低到2并在2维空间中可视化节点。可视化结果如图4所示。
-- 我们可视化空手道图（见图5）来说明嵌入方法保留的属性。 LLE和LE（（a）和（f））尝试将具有高簇内边缘的图和群集节点的社区结构保持在一起。
GF（（b））非常密切地嵌入社区，并使叶节点远离其他节点。在（d）中，我们观察到HOPE嵌入节点16和21，其原始图中的Katz相似性非常低（0.0006），相距最远（考虑点积相似性）。 node2vec和SDNE（（c）和（e））保留了节点的社区结构和结构属性的混合。节点32和33，它们都是高度集中并且在它们的社区中心，嵌入在一起并且远离低度节点。此外，它们更接近属于其社区的节点。 SDNE嵌入节点0，节点0作为社区之间的桥梁，远离其他节点。请注意，与其他方法不同，它并不意味着节点0与其余节点断开连接。这里的含义是SDNE将节点0识别为单独类型的节点，并将其与编码器和解码器中其他节点的连接编码。深度自动编码器识别网络中重要节点的能力尚未研究，但鉴于此观察，我们认为这一点方向可能是有希望的。

链路预测

为了测试不同嵌入方法在此任务上的性能，对于每个数据集，我们随机隐藏20％的网络边缘。我们使用剩余的80％边缘学习嵌入，并预测在学习嵌入的训练数据中未观察到的最可能的边缘。node2vec实现了在BlogCatalog上的良好性能，但在其他数据集上表现不佳。 HOPE在所有数据集上都取得了良好的性能，这意味着保留更高阶的邻近性有助于预测未观察到的链路。同样，SDNE优于其他方法，但PPI除外，随着嵌入维数增加到8以上，性能会急剧下降。
图7说明了嵌入维度对链路预测的影响。有两个发现。1.在PPI和BlogCatalog中，与图形重建性能不同，随着维数的增加，性能没有提高。 这可能是因为有了更多参数，模型会在观察到的链路上过度拟合，无法预测未观察到的链路。2.在相同的数据集上，方法的相对性能也取决于嵌入维度。

节点分类

使用网络拓扑预测节点标签在网络分析中广泛流行，并且具有各种应用，包括文档分类和兴趣预测。良好的网络嵌入应该保留了网络结构，因此对节点分类很有用。我们通过使用生成的嵌入作为节点特征对节点进行分类来比较嵌入方法对此任务的有效性。对于每个数据集，我们随机抽取10％到90％的节点作为训练数据，并评估其余节点的性能。
图8显示了实验结果，可以看到node2vec在节点分类上优于其他方法。

超参数灵敏性

（超参数：根据经典的机器学习文献，可以将模型看作假设，而参数是根据特定的数据集对假设进行的具体调整。模型超参数是模型外部的配置，其值不能从数据估计得到。应用于估计模型参数的过程中。通常由实践者直接指定，通常可以使用启发式方法来设置，通常根据给定的预测建模问题而调整。）
超参数灵敏度：参数设置对于嵌入方法性能的影响程度。
-嵌入方法相对于超参数有多健壮？
-最佳超参数是否依赖于嵌入的下游任务？
-有关超参数的性能差异对数据集提供了哪些见解？
（1）图因子分解GF
图因子分解的目标函数包含具有系数的权重正则化项。该系数控制着嵌入的普遍性。低正则化系数有利于更好的重建，但可能过度拟合观察到的图导致预测性能差。 另一方面，高正规化可能代表数据不足，因此在所有任务上表现不佳。图10展示了链路预测和节点分类的性能随着正则化系数的增加，先达到峰值，然后下降。且该性能变化是相当大的。因此应该根据给定数据集仔细调整系数。
（2）HOPE
HOPE是对节点之间的相似性矩阵进行分解以获得嵌入，因此 超参数依赖于获得相似度矩阵的方法。我们使用了Katz指数用于此目的。评估衰减因子（β）的影响，可以将其解释为性能的高阶接近系数。图形结构影响该参数的最佳值。
对于具有紧密编织社区的结构良好的图形，高的β值将错误地在嵌入空间中更近地分配不同的节点。相反，对于具有弱社区结构的图，捕获更高阶距离是很重要的，β的高值可以产生更好的嵌入。
（3）SDNE
SDNE使用耦合深度自动编码器嵌入图形。 它利用一个参数来控制目标函数中观察到的和未观察到的链接重建的权重。高参数值将集中于重建观察到的链接而忽略不存在未观察到的链接。 此参数可能至关重要，因为较低的值可能会阻碍预测隐藏链接。 图12显示了我们的分析结果。
（4）node2vec.
node2vec在图上执行偏向随机遍历，并将通常一起出现在其中的节点嵌入到嵌入空间中。在该方法的各种超参数中（包括行走长度，上下文大小和偏差权重），我们分析偏差权重对性能的影响，并采用剩余超参数的常用值[29]，即上下文大小node2vec具有两个偏置权重：（a）inout参数（q），它控制随机游走远离传入节点的可能性（更高的值有利于更近的节点），以及（b）返回参数（p），它衡量返回概率（较低的值有利于返回）。较低的q值将有助于捕获节点之间更长的距离，并旨在保持结构等效性。
在节点分类中（图13c），我们观察到低q值有助于实现更高的准确度，这表明需要捕获结构等价来准确地嵌入图的结构。相反，高q值有利于链接预测（图13b）
针对链路预测的任务对图14中的SBM进行了类似的观察，还注意到，由于图形具有强大的社区结构，因此SBM中q的最佳值要高得多。

图嵌入的Python库

我们发布了一个开源Python库，GEM（图形嵌入方法，https：//github.com/palash1992/GEM），它为这里介绍的所有方法的实现及其评估指标提供了统一的接口。 该库支持加权和未加权图形。 GEM的分层设计和模块化实现应该有助于用户在新数据集上测试已实现的方法，并作为平台轻松开发新方法。
GEM（https://github.com/palash1992/GEM）提供了局部线性嵌入[26]，拉普拉斯特征映射[25]，图分解[21]，HOPE [24]，SDNE [23]和node2vec [29]的实现。 对于node2vec，我们使用作者[95]提供的C ++实现并生成Python接口。 此外，GEM还提供了一个界面，用于评估上述四个任务中的学习嵌入。 该接口非常灵活，支持多种边缘重建指标，包括余弦相似度，欧氏距离和基于解码器（基于自动编码器的模型）。 对于多标记节点分类，库使用one-rest-rest逻辑回归分类器并支持使用其他ad hoc分类器。

结论与展望

对图嵌入技术的回顾涵盖了三大类方法：基于分解，基于随机游走和基于深度学习。我们研究了通过各种嵌入方法保留的结构和属性，并描述了图嵌入技术以及每种方法所面临的挑战。我们报告了嵌入的各种应用及其各自的评估指标。我们使用几个公开可用的真实网络对这些应用程序的调查方法进行了实证评估，并比较了它们的优缺点。最后，我们提出了一个开源Python库，名为GEM，我们开发了实施的调查嵌入方法和评估任务，包括图形重建，链接预测，节点分类和可视化。我们认为图嵌入领域有三个有前景的研究方向：（1）探索非线性模型，（2）研究网络演化，（3）生成具有现实世界特征的合成网络。如调查所示，一般的非线性模型（例如基于深度学习）在捕获图的固有动态方面表现出很大的希望。它们能够近似任意函数，最好地解释网络边缘，这可能导致网络的高度压缩表示。这种方法的一个缺点是可解释性有限。进一步研究侧重于解释这些模型所学的嵌入可能非常有成效。利用嵌入技术研究图形演化是一个需要进一步探索的新研究领域。最近的工作跟随了这一思路，并说明了嵌入如何用于动态图。生成具有真实世界特征的合成网络一直是一个受欢迎的研究领域，主要是为了便于模拟。实图的低维矢量表示可以帮助理解它们的结构，因此可用于生成具有真实世界特征的合成图。使用生成模型学习嵌入可以在这方面帮助我们。