专栏首页AI研习社图嵌入方法介绍

图嵌入方法介绍

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

什么是图嵌入?

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

  • 顶点嵌入:将图中的每一个顶点向量化表示。当我们想在节点层次上进行可视化或预测任务的时候就会做顶点嵌入,比如说在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

本文分享自微信公众号 - AI研习社(okweiwu),作者:雷锋字幕组编译

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-11-27

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 多图演示高效的神经架构搜索

    设计不同类型的神经网络诸如图像分类和自然语言理解通常需要大量的网络架构工程及专业知识。神经架构搜索(NAS)可使这些手工设计过程自动化。学界对NAS的研究兴趣与...

    AI研习社
  • 学界 | 一位冉冉上升的青年理论计算机科学家:陈立杰斩获 ACM STOC 最佳学生论文

    AI 科技评论按:前不久我们刚刚介绍了出自清华姚班并获得 2019 年斯隆研究奖的华裔学者鬲融,近日我们又获悉另一位姚班天才少年陈立杰获得 ACM STOC 2...

    AI研习社
  • 动态 | Facebook 开源高速大规模图嵌入工具 PBG

    AI 科技评论按:如何有效处理大规模图像,对于推动人工智能研究与应用的发展而言至关重要。这也是为何 Facebook AI 选择创建并开源 PyTorch-Bi...

    AI研习社
  • Context-Aware Network Embedding for Relation Modeling

    论文:http://www.aclweb.org/anthology/P17-1158

    超然
  • Jeff Dean强推:可视化Bert网络,发掘其中的语言、语法树与几何学

    这篇文章是为了补充解释论文,大致呈现了主要的结论。请参阅论文以获得完整的参考文献和更多信息

    代码医生工作室
  • 如何可视化BERT?你需要先理解神经网络的语言、树和几何性质

    语言的结构是离散的,而神经网络则基于连续数据运作:高维空间中的向量。成功的语言处理网络必须要能将语言的符号信息转译为某种几何表征——但是这种表征该是怎样的形式呢...

    机器之心
  • Jeff Dean强推:可视化Bert网络,发掘其中的语言、语法树与几何学

    本文是论文(Visualizing and Measuring the Geometry of BERT)的系列笔记的第一部分。这篇论文由Andy Coenen...

    大数据文摘
  • 【干货】Entity Embeddings : 利用深度学习训练结构化数据的实体嵌入

    【导读】本文是数据科学家Rutger Ruizendaal撰写的一篇技术博客,文章提出深度学习在非结构数据中有不错的表现,当前通过实体嵌入也可以使之在结构化数据...

    WZEARW
  • CoNLL 2018 | 最佳论文揭晓:词嵌入获得的信息远比我们想象中的要多得多

    昨日,CoNLL 公布了最佳论文,由来自西班牙巴斯克大学 IXA NLP 组的 Mikel Artetxe 等人获得。该论文展示了词嵌入模型能够捕获不同层面的信...

    机器之心
  • 每周学点大数据 | No.31拓扑排序

    No.31期 拓扑排序 Mr. 王:很好,你还记得这个问题。接下来我们来讨论另一种磁盘中的大数据算法策略,叫作时间前向处理方法。在这种策略中,我会讲解求解最...

    灯塔大数据

扫码关注云+社区

领取腾讯云代金券