在现实世界的各种场景中,图处处可见。社交网络是在人与人构建连接的图,生物学家使用图描述蛋白质分子的交互,通信网络本身就以图的形式存在。在文本挖掘中还会使用词共现图进行分析。毫无疑问,在图数据上探索机器学习受到越来越多的关注。人们试图通过以此预测社交网络中的新朋友或是发现蛋白质分子新的性质与功能。然而,无论数学家还是统计学家都无法直接在图上进行计算的,如何将图数据处理成可直接应用于机器学习的数据是一项极大的挑战。在这样的背景下,图嵌入方法被提出。
什么是图嵌入?
图嵌入是将属性图转换为一个向量(图)或者一组向量(顶点)。好的嵌入应该尽可能的捕获图拓扑结构、顶点之间的关系以及其他一些关于图/子图/顶点的信息。尽可能多的捕获相关属性会产生更好的嵌入,对下游任务会很有帮助。一般来说,我们可以将图嵌入大致分为两类:
接下来,我们会分别介绍实现这两种嵌入的方法。顶点嵌入:DeepWalk、node2vec、SDNE方法;图嵌入:graph2vec。
为什么必须图嵌入?
图是一种信息丰富且易于理解的数据结构,在机器学习中必须对图进行嵌入的原因如下:
挑战
嵌入方法需要满足很多要求。在这里我向大家介绍进行嵌入时面临的三种主要挑战:
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主要可分为三个步骤:
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包括三步:
由于图嵌入是通过子图实现,因此具有相似子图和结构的图的嵌入表示更为接近。
其他嵌入方法
本文介绍了常用的四种图嵌入方法。然而当前图嵌入非常火热,其他很多嵌入方法也被提出。这里我简单列出其他一些未介绍的方法,有兴趣的同学可以去做更深入的了解:
参考资料
[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