赞
踩
简介
DeepWalk是由Bryan Perozzi
,Rami Al-Rfou
和Steven Skiena
在2014年提出的,它是一种基于图的无监督特征学习方法,它有趣的点是将文本处理任务中词向量的处理思想迁移到了图特征学习上,就像处理句子得到word embedding一样,通过处理由网络中节点组成的序列从而得到Node embedding,算是图特征学习的开山之作。
示例的输入是一个网络,输出是图中每个节点的二维向量,DeepWalk通过截断随即游走学习出一个网络的社会表示,从两张图的对比也可以发现,越是在网络中拓扑结构相近的点,其对应的二维向量在二维空间上的距离越近。
文章中提出,在学习一个网络的特征表示时,需要注意几个问题:
那如何得到图中节点的向量表示?
总结一下就是随机游走+语言模型
所谓随机游走(random walk),就是在网络上不断重复的随机选择游走路径,最终形成一条贯穿网络的路径,有点类似与图搜索中的深度优先遍历,但此处是随机的深度优先遍历。随机遍历有以下几点好处:
文章中提到网络中随机游走的分布规律与NLP中句子序列在语料库中出现的规律有着类似的幂律分布特征,既然网络的特征与自然语言的词特征有着十分的类似,那为什么不能借助处理自然语言处理中词向量的方法,计算网络顶点的向量表示呢?
语言模型这里不做过多的介绍,相信接触过自然语言处理的同学肯定对词向量(word embedding)不会太陌生。
算法一共分为两个部分:
1、随机游走生成器:首先随机选择一个顶点,然后执行随机游走方法,每次游走均匀的采样一个邻居节点,直到最后一个节点达到最大长度。重复N次,重复N次,可以得到N个随机游走序列。
上述算法的3-9行是该算法的核心。外围循环的循环次数 γ ,每次都会重新在某个节点(作为根节点)开始随机游走。每次迭代都会在数据中形成一个PASS,在PASS中每个节点采样一个随机游走。在每个PASS的开始,产生随机序列遍历节点。虽然不是严格的要求,但是能加快随机梯度下降的收敛速度。 在内循环中,在每个节点上进行迭代。对于每个节点 vi ,我们产生一个随机游走 |Wvi|=t ,然后用它来更新表示(Line7)。
2、更新顶点向量:将随机游走序列变成一个窗口长度为w的Skip-Gram编码序列,然后利用梯度下降进行更新权重。
word2vec有两种训练方式,cbow和skipgram,cbow是用周围的字预测中间字,而skipgram用中间字预测周围的字。为什么DeepWalk采用后者?(个人理解) 原因在于skipgram没有过分关注“顺序”这个概念,在图结构的学习中,节点周围的节点更能反映出该节点的信息,需要更注重“局部”的刻画。所以在图中,“局部”的刻画并不需要一个很强的“顺序”的限制,所以cbow通过连续的上下文去预测中间字的方式,不太适合在该场景下使用。
原论文也基于现有算法提出了优化策略,总的来说这篇论文为后续的学习网络特征提供了很好的思路。但是此篇论文也存在一些缺点,比如随机漫步可以当做是随机的深度优先遍历,深度往往增加了复杂度,而且没有考虑广度带来的周围邻居结构的影响;另一个是文中没有提出一个明确的优化目标函数,但这些并不妨碍其是一篇优秀的论文。
总结:
万物皆可embedding,DeepWalk是使用自然语言处理中的word2vec模型skipgram无监督算法去学习图中节点的局部表示,由于是无监督的算法,训练的时候不依赖下游的具体任务,因此学习到的embedding可以作为非常好的特征表示,天然的适应下游的各种任务,包括节点分类,异常检测,节点链接预测等。
最后,不仅是图模型,对于推荐系统的数据结构,也很适合用DeepWalk去解决,比如电商,用户点击商品序列就是一个天然的walk,由此可以学习到商品的embedding表示等,Airbnb在kdd上就发过类似的文章进行房源的embedding和用户的embedding,有兴趣的可以看看。DeepWalk是最基本的一个方式,后续出现了很多变种和改进,后续继续学习。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。