图嵌入方法介绍

在现实世界的各种场景中，图处处可见。社交网络是在人与人构建连接的图，生物学家使用图描述蛋白质分子的交互，通信网络本身就以图的形式存在。在文本挖掘中还会使用词共现图进行分析。毫无疑问，在图数据上探索机器学习受到越来越多的关注。人们试图通过以此预测社交网络中的新朋友或是发现蛋白质分子新的性质与功能。然而，无论数学家还是统计学家都无法直接在图上进行计算的，如何将图数据处理成可直接应用于机器学习的数据是一项极大的挑战。在这样的背景下，图嵌入方法被提出。

什么是图嵌入？

图嵌入是将属性图转换为一个向量（图)或者一组向量（顶点)。好的嵌入应该尽可能的捕获图拓扑结构、顶点之间的关系以及其他一些关于图/子图/顶点的信息。尽可能多的捕获相关属性会产生更好的嵌入，对下游任务会很有帮助。一般来说，我们可以将图嵌入大致分为两类：

• 顶点嵌入：将图中的每一个顶点向量化表示。当我们想在节点层次上进行可视化或预测任务的时候就会做顶点嵌入，比如说在2维平面上可视化顶点或者基于顶点之间的相似度预测顶点之间是否连接。
• 图嵌入：将整个图表示成一个向量。当我们对整个图做预测任务或是与其他图比较，又或者可视化整张图，例如比较分子结构时， 我们就进行图嵌入。

接下来，我们会分别介绍实现这两种嵌入的方法。顶点嵌入：DeepWalk、node2vec、SDNE方法；图嵌入：graph2vec。

为什么必须图嵌入？

图是一种信息丰富且易于理解的数据结构，在机器学习中必须对图进行嵌入的原因如下：

• 直接在图上进行机器学习是很困难的。图由边和节点组成， 数学、统计学和机器学习方法只能部分处理图数据，而在向量空间可以更充分的利用图数据。
• 嵌入是压缩表示。邻接矩阵描述图中顶点的连接关系，大小为|V| x |V|，其中V为顶点个数。在邻接矩阵中，非零值表示对应行和列的两个节点之间有边。然而对节点数众多的图来说，使用邻接矩阵对图进行描述是不现实的。想象一下有1M节点的图，其邻接矩阵大小会是1M x 1M。基于嵌入的矩阵通过低维向量表示节点，可以避免这种情况。
• 相对于在图上比较属性，在嵌入空间中处理向量更加方便快捷。

挑战

嵌入方法需要满足很多要求。在这里我向大家介绍进行嵌入时面临的三种主要挑战：

• 确保嵌入表示能够很好的描述图的属性，主要包括图的拓扑结构、顶点连接、顶点周围节点等。嵌入表示的好坏对后续预测或可视化任务的结果有很大的影响。
• 嵌入速度应该与图的大小无关。通常图都是非常大的，比如社交网络就有超过数百万人的顶点。好的嵌入方法应该能高效处理这样的大图。
• 嵌入维度也是非常关键的问题。更大的维度会保存更多的信息，同时也会花费更多的时间与存储空间。实验者应该根据自己的需求选取恰当的嵌入维度。在论文中，作者们一般会将嵌入维度设置为128或256，对多数任务来说这个维度就差不多了。另外你还需要知道，word2vec中作者做得是300维的嵌入。

Word2vec

在介绍图嵌入之前，我们有必要了解Word2vec和Skip-gram神经网络，这是理解图嵌入的基础。如果你还想更深入的了解这些方法，可以查看这篇教程（http://mccormickml.com/2016/04/19/word2vec-tutorial-the-skip-gram-model/）。

Word2vec是将单词转化为嵌入向量的方法。相似的词应具有相似的嵌入。Word2vec使用只有一个隐藏层的skip-gram神经网络进行训练。训练的目标是预测句子中当前词的相邻词。由于这样的任务只会在训练阶段出现，skip-gram的上下文单词预测也被称为伪任务。网络的输入为一个单词，通过优化最大化该单词在句子中相邻单词的概率。下图显示了这一任务，其中标有绿色的是输入单词，通过网络预测其前后各两个词。通过这样的训练，具有相似含义的两个词很可能具有相似的邻域词，于是得到相似的嵌入表示。

注：绿色标记的单词是网络的输入，通过skip-gram优化使其相邻单词的概率最大化。在上图中，我们考虑所选单词前后各两个单词的出现概率。

如下图所示，skip-gram神经网络由输入层、一个隐藏层和输出层组成。输入层输入当前词的one-hot编码（one-hot编码是长度为字典数量的向量，其中除当前词位置为1外其余位均为0）；隐藏层没有激活函数，该层输出表示单词的嵌入；输出层通过softmax分类器输出邻域词的预测概率。想要了解更多详细信息可以看我之前的教程（http://mccormickml.com/2016/04/19/word2vec-tutorial-the-skip-gram-model/）。

Skip-gram神经网络

接下来，我将介绍四种图嵌入方法，包括三种节点嵌入方法、一种整个图嵌入方法。这些方法是在word2vec的思想上进行了一些有趣的尝试。

顶点嵌入方法

这一部分我会介绍三种节点嵌入的方法，这三种方法在实践中经常被使用，而且通常会产生最好的效果。在深入探讨之前，你需要知道，节点嵌入的方法可以分为三大类：分解，随机游走和深度学习。

DeepWalk通过随机游走的方式生成顶点嵌入。随机游走就是从一个顶点出发，随机移动到它的一个邻居节点，将该节点作为新的当前节点，如此循环执行若干步，得到一条游走路径。

DeepWalk主要可分为三个步骤：

• 采样：通过随机游走对图形进行采样。每个顶点只需要随机游走若干次就可以。原始论文中作者表明，从每个顶点执行32到64次随机游走就基本足够了，此外还特别说明，一般每个顶点随机游走四十次效果最好。
• 训练skip-gram：可以将随机游走得到顶点路径类比为word2vec中的句子。skip-gram将随机游走的一个顶点的one-hot向量作为输入，并最大化其相邻节点的预测概率。训练中通常预测20个邻居节点-左侧10个节点，右侧10个节点。
• 计算嵌入：网络隐藏层的输出即为顶点嵌入。DeepWalk对图中的所有顶点计算嵌入。

DeepWalk图示

由于DeepWalk采用随机游走策略，无法很好地保留节点的局部信息。Node2vec可以解决这个问题。

Node2vec是对DeepWalk的改进，虽然也是基于随机游走但却不同于完全随机，它多了两个参数P和Q。参数Q确定随机游走时选择新顶点的可能性，而参数P确定随机游走时返回之前顶点的可能性。参数P使随机游走更多的关注顶点领域的信息（也就是倾向广度优先搜索），参数Q则选择更深更远的信息发现（也就是倾向深度优先搜索）。因此，node2vec可以获取邻域信息和更复杂的依存信息。

上图显示了Node2vec中随机行走的概率。假设前一步是从红色节点游走到绿色节点，那么此时返回红色节点的概率为1 / P，到达未与先前红色节点连接的节点的概率为1 / Q，到达红色节点邻居的概率为1。

其余步骤于DeepWalk基本相同。

结构深层网络嵌入（SDNE）完全不同于前两种方法，它并不是基于随机游走。之所以介绍这种方法是因为它在不同任务上的表现都非常稳定。

SDNE在嵌入中同时保留一阶和二阶相似度。一阶接近相似度是由边链接节点间的局部成对相似性，表征本地网络结构。如果网络中的两个节点间有边，则它们是相似的，例如当一篇论文引用另一篇论文时，意味着它们涉及相似的主题。二阶相似度表示节点邻域结构的相似性，它捕获全局网络结构。如果两个节点共享许多邻居，它们往往是相似的。

作者介绍了一种自动编码器神经网络-如下图所示，该网络由两部分组成，左右的自动编码器均接收节点的邻接向量，并进行训练以重建节点邻接。这些自动编码器被称为vanilla自动编码器，能够学习二阶相似度。某点与当前节点存在边那么对应邻接向量（邻接矩阵的一行）位置为正。

该网络结构中左右两部分之间的连接是受监督的部分。它计算左侧嵌入和右侧嵌入间的距离，并将其统计到网络的公共损失中。将所有相互连接的节点对分别作为左右自动编码器的输入，通过尽可能减小损失保持一阶相似度。

在该结构中，网络的总损失=左自动编码器的损失+右自动编码器的损失+中间连接的损失。

图嵌入方法

最后介绍一种对整个图嵌入的方法，也就是通过一个向量表示整个图。我只介绍graph2vec这一种方法，因为据我所知，这是最好的图嵌入方法。

Graph2vec借鉴doc2vec（https://medium.com/scaleabout/a-gentle-introduction-to-doc2vec-db3e8c0cce5e）的思想使用skip-gram网络进行训练。doc2vector获取文档的ID作为输入，经过训练使文档中每个随机预测的单词概率最大化。

Graph2vec包括三步：

• 采样并重新标记图中的所有子图。子图是出现在所选节点周围的一组节点，通常来说来说，这些节点距离所选节点不会太远。
• 训练skip-gram模型。图与文档十分相似，文档是单词组成的集合，图则是子图构成的集合。于是，可以通过最大化输入图子图的概率的方法对skip-gram进行训练。最终， 可以得到输入图的one-hot向量表示。
• 训练完成后，只需提供图的ID就可以得到该图的one-hot向量， 隐藏层就是嵌入结果。

由于图嵌入是通过子图实现，因此具有相似子图和结构的图的嵌入表示更为接近。

其他嵌入方法

本文介绍了常用的四种图嵌入方法。然而当前图嵌入非常火热，其他很多嵌入方法也被提出。这里我简单列出其他一些未介绍的方法，有兴趣的同学可以去做更深入的了解：

• 顶点嵌入：LLE, Laplacian Eigenmaps, Graph Factorization, GraRep, HOPE, DNGR, GCN, LINE
• 图嵌入: Patchy-san, sub2vec (embed subgraphs), WL kernel andDeep WL kernels

参考资料

[1] C. Manning, R. Socher, Lecture 2 | Word Vector Representations: word2vec (2017), YouTube.

[2] B. Perozzi, R. Al-Rfou, S. Skiena, DeepWalk: Online Learning of Social Representations (2014), arXiv:1403.6652.

[3] C. McCormick. Word2Vec Tutorial — The Skip-Gram Model (2016), http://mccormickml.com.

[4] T. Mikolov, K. Chen, G. Corrado, J. Dean, Efficient Estimation of Word Representations in Vector Space (2013), arXiv:1301.3781.

[5] A. Narayanan, M. Chandramohan, R. Venkatesan, L. Chen, Y. Liu, S. Jaiswal, graph2vec: Learning Distributed Representations of Graphs (2017),arXiv:1707.05005.

[6] P. Goyal, E. Ferrara, Graph Embedding Techniques, Applications, and Performance: A Survey (2018), Knowledge-Based Systems.

[7] D. Wang, P. Cui, W. Zhu, Structural Deep Network Embedding (2016), Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining.

[8] A. Grover, J. Leskovec, node2vec: Scalable Feature Learning for Networks (2016), Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining.

via https://towardsdatascience.com/graph-embeddings-the-summary-cc6075aba007