图表示学习Graph Embedding综述

最近在学习Embedding相关的知识的时候看到了一篇关于图嵌入的综述，觉得写的不错便把文章中的一部分翻译了出来。因自身水平有限，文中难免存在一些纰漏，欢迎发现的知友在评论区中指正。

目录

一、图嵌入概述

二、图嵌入的挑战

三、图嵌入的方法

一、图嵌入概述

图，如社交网络、单词共存网络和通信网络，广泛地存在于各种现实应用中。通过对它们的分析，我们可以深入了解社会结构、语言和不同的交流模式，因此图一直是学界研究的热点。图分析任务可以大致抽象为以下四类: ( a )节点分类，( b )链接预测，( c )聚类，以及( d )可视化。其中，节点分类旨在基于其他标记的节点和网络拓扑来确定节点的标签(也称为顶点)。链路预测是指预测缺失链路或未来可能出现的链路的任务。聚类用于发现相似节点的子集，并将它们分组在一起；最后，可视化有助于深入了解网络结构。

真实的图（网络）往往是高维、难以处理的，20世纪初，研究人员发明了图形嵌入算法，作为降维技术的一部分。他们首先根据实际问题构造一个D维空间中的图，然后将图的节点嵌入到d（d<<D）维向量空间中。嵌入的思想是在向量空间中保持连接的节点彼此靠近。拉普拉斯特征映射（Laplacian Eigenmaps）和局部线性嵌入（Locally Linear Embedding ，LLE）是基于这一原理的算法的例子。然而，可伸缩性是这种方法的一个主要问题，它的时间复杂度是O (| V| 2)。

img

自2010年以来，关于图嵌入的研究已经转移到解决网络稀疏性的可伸缩图嵌入技术上。例如，图分解（Graph Factorization）使用邻接矩阵的近似分解作为嵌入。LINE扩展了这种方法，并试图保持一阶和二阶近似。HOPE通过使用广义奇异值分解( SVD )分解相似性矩阵而不是邻接矩阵来扩展LINE以试图保持高阶邻近性。SDNE 使用自动编码器嵌入图形节点并捕捉高度非线性的依赖关系。这些新的可扩展方法的时间复杂度为0 ( | E | )。

二、图嵌入的挑战

如前所述，图嵌入的目标是发现高维图的低维向量表示，而获取图中每个节点的向量表示是十分困难的，并且具有几个挑战，这些挑战一直在推动本领域的研究：

• 属性选择：节点的“良好”向量表示应保留图的结构和单个节点之间的连接。第一个挑战是选择嵌入应该保留的图形属性。考虑到图中所定义的距离度量和属性过多，这种选择可能很困难，性能可能取决于实际的应用场景。
• 可扩展性：大多数真实网络都很大，包含大量节点和边。嵌入方法应具有可扩展性，能够处理大型图。定义一个可扩展的模型具有挑战性，尤其是当该模型旨在保持网络的全局属性时。
• 嵌入的维数：实际嵌入时很难找到表示的最佳维数。例如，较高的维数可能会提高重建精度，但具有较高的时间和空间复杂性。较低的维度虽然时间、空间复杂度低，但无疑会损失很多图中原有的信息。

三、图嵌入的方法

在过去的十年里，在图形嵌入领域已经有了大量的研究，重点是设计新的嵌入算法。发展到现在，大体上可以将这些嵌入方法分为三大类：( 1 )基于因子分解的方法，( 2 )基于随机游走的方法，以及( 3 )基于深度学习的方法。在下文中我将简要解释每一个类别的特征与每一类别代表性算法的原理。

img

1.预备知识与符号定义

2.基于因子分解的方法

3、基于随机游走的方法

3.1. DeepWalk

DeepWalk方法受到word2vec的启发，首先选择某一特定点为起始点，做随机游走得到点的序列，然后将这个得到的序列视为句子，用word2vec来学习，得到该点的表示向量。DeepWalk通过随机游走去可以获图中点的局部上下文信息，因此学到的表示向量反映的是该点在图中的局部结构，两个点在图中共有的邻近点（或者高阶邻近点）越多，则对应的两个向量之间的距离就越短。

img

3.2. node2vec

与DeepWalk相似，node2vec通过最大化随机游走得到的序列中的节点出现的概率来保持节点之间的高阶邻近性。与DeepWalk的最大区别在于，node2vec采用有偏随机游走，在广度优先（bfs）和深度优先（dfs）图搜索之间进行权衡，从而产生比DeepWalk更高质量和更多信息量的嵌入。

4、基于深度学习的方法

4.1. Structural deep network embedding (SDNE)

SDNE建议使用深度自动编码器来保持一阶和二阶网络邻近度。它通过联合优化这两个近似值来实现这一点。该方法利用高度非线性函数来获得嵌入。模型由两部分组成：无监督和监督。前者包括一个自动编码器，目的是寻找一个可以重构其邻域的节点的嵌入。后者基于拉普拉斯特征映射，当相似顶点在嵌入空间中彼此映射得很远时，该特征映射会受到惩罚。

img

4.2. Deep neural networks for learning graph representations (DNGR)

DNGR结合了随机游走和深度自动编码器。该模型由3部分组成：随机游走、正点互信息（PPMI）计算和叠加去噪自编码器。在输入图上使用随机游走模型生成概率共现矩阵，类似于HOPE中的相似矩阵。将该矩阵转化为PPMI矩阵，输入到叠加去噪自动编码器中得到嵌入。输入PPMI矩阵保证了自动编码器模型能够捕获更高阶的近似度。此外，使用叠加去噪自动编码器有助于模型在图中存在噪声时的鲁棒性，以及捕获任务（如链路预测和节点分类）所需的底层结构。

4.3. Graph convolutional networks (GCN)

上面讨论的基于深度神经网络的方法，即SDNE和DNGR，以每个节点的全局邻域（一行DNGR的PPMI和SDNE的邻接矩阵）作为输入。对于大型稀疏图来说，这可能是一种计算代价很高且不适用的方法。图卷积网络（GCN）通过在图上定义卷积算子来解决这个问题。该模型迭代地聚合了节点的邻域嵌入，并使用在前一次迭代中获得的嵌入及其嵌入的函数来获得新的嵌入。仅局部邻域的聚合嵌入使其具有可扩展性，并且多次迭代允许学习嵌入一个节点来描述全局邻域。最近几篇论文提出了利用图上的卷积来获得半监督嵌入的方法，这种方法可以通过为每个节点定义唯一的标签来获得无监督嵌入。这些方法在卷积滤波器的构造上各不相同，卷积滤波器可大致分为空间滤波器和谱滤波器。空间滤波器直接作用于原始图和邻接矩阵，而谱滤波器作用于拉普拉斯图的谱。

4.4. Variational graph auto-encoders (VGAE)

VGAE采用了图形卷积网络（GCN）编码器和内积译码器。输入是邻接矩阵，它们依赖于GCN来学习节点之间的高阶依赖关系。他们的经验表明，与非概率自编码器相比，使用变分自编码器可以提高性能。

5、其他

LINE

LINE适用于任意类型的信息网络：无向、有向和无权、有权。该方法优化了精心设计的目标函数，能够保留局部和全局网络结构。此外，LINE中还提出了边缘采样算法，解决了经典随机梯度下降的局限性，提高了算法的有效性和效率。具体来说，LINE明确定义了两个函数，分别用于一阶和二阶近似，并最小化了这两个函数的组合。一阶邻近函数与图分解（GF）相似，都是为了保持嵌入的邻接矩阵和点积接近。区别在于GF通过直接最小化两者的差异来实现这一点。相反，LINE为每对顶点定义了两个联合概率分布，一个使用邻接矩阵，另一个使用嵌入。然后，LINE最小化了这两个分布的Kullback–Leibler（KL）散度。这两个分布和目标函数如下：

参考文献 [1] Goyal P , Ferrara E . Graph Embedding Techniques, Applications, and Performance: A Survey[J]. Knowledge-Based Systems, 2017.

[2] Roweis, S. T . Nonlinear Dimensionality Reduction by Locally Linear Embedding[J]. Science, 2000, 290(5500):2323-2326.

[3] Perozzi B , Al-Rfou R , Skiena S . DeepWalk: Online Learning of Social Representations[J]. 2014.

[4] Grover A , Leskovec J . node2vec: Scalable Feature Learning for Networks[J]. Kdd, 2016.

[5] Wang D , Cui P , Zhu W . Structural Deep Network Embedding[C]// the 22nd ACM SIGKDD International Conference. ACM, 2016.

[6] Tang J , Qu M , Wang M , et al. LINE: Large-scale information network embedding[J]. 24th International Conference on World Wide Web, WWW 2015.