NODE2VEC理论到复现-阿里云开发者社区

开发者社区> 大数据> 正文
登录阅读全文

NODE2VEC理论到复现

简介: NODE2VEC
参考知乎:node2vec
原文链接:node2vec: Scalable Feature Learning for Networks
复现代码见:Colab

Introduction

复杂网络主要有两种任务,一网络节点的分类,通俗点说就是将网络中的节点进行聚类,我们关心的是哪些节点具有类似的属性,就将其分到同一个类别中。二是链接预测,就是预测网络中哪些顶点有潜在的关联。
前面的DeepWalk借鉴了词嵌入模型skip-gram的思想,node2vec也是如此,最重要的不同就是在游走的方式上有了改进,在得到序列后的处理方式和DeepWalk是一致的。下面主要探讨的就是这样的序列是怎样得到的,又是怎么有利于网络嵌入的。

模型

目标函数

原文中介绍了对于优化目标函数的推导,和skipgram中的思想是类似的,首先要尽可能使得节点与周围邻居节点同时出现的概率尽可能大,也就是最大化下函数(其中表示从节点映射到嵌入向量,表示的邻居节点):

同时假设观察一个邻居节点的概率独立于观察其他邻居节点的概率,这样就有:

综合起来所有节点后,优化的目标函数就为:

这和skipgram中介绍的有很大的相似性,且的计算量太大,故也是采用负采样的方法,这也是为什么说这篇论文也借鉴了skipgram的思想。其创新点主要在下面要讲的游走方式上。这样创新的游走方式能够捕捉到网络连接的多样性。

游走方式

在学习了前面的LINE模型后,会有这样一种感觉,图中的节点信息主要蕴含两种,一种是同质性信息,一种是结构相似性的信息。第一种很好理解,就是聚集在一个社群之中的节点之间有着相似的特征,因此在向量表示中也就更加贴近,而第二种就好像下图中的u节点和s6节点,都是各自社群的中心,理应具有某种程度上的相似的向量表示信息。
image.png
图的游走方式有两种,深度优先DFS广度优先BFS,学习得到的向量表示也就更能蕴含节点的同质性结构相似性特征,这其实也和LINE中的一阶二阶相似性有异曲同工的感觉。BFS倾向于在初始节点的周围游走,可以反映出一个节点的邻居的微观特性;而DFS一般会跑的离初始节点越来越远,可以反映出一个节点邻居的宏观特性。具体为什么这样两种游走方式可以得到这样的效果可以参考
node2vec添加了p和q两个参数,来控制游走的方式。
image.pngimage.png
具体来说,如图所示,当前节点是v,是由t节点走来,并在每条与v直接相连的边上定义了往四个方向的跳转概率(也即右边的公式)。
对于参数p

  • 如果 也即 ,那么采样会尽量不往回走,对应上图的情况,就是下一个节点不太可能是上一个访问的节点t,而应当是其他的x123节点。
  • 如果 也即 ,那么采样会更倾向于返回上一个节点,这样就会一直在起始点周围某些节点来回转来转去。

对于参数q

  • 如果 也即 ,也就是说在x1和x23之间选择更倾向于选择x1,x1所代表的时节点t周围的节点,也就是说游走会倾向于在起始点周围的节点之间跑,可以反映出一个节点的BFS特性。
  • 如果 也即 ,也就是说在x1和x23之间选择更倾向于选择x23,那么游走会倾向于往远处跑,反映出DFS特性

当p=1,q=1时,游走方式就等同于DeepWalk中的随机游走。

代码复现

node2vec论文源码中主要包含了main.py和node2vec.py,下图是对整个架构的概括:
伪代码
image.png
LearnFeatures需要传入图G,每个节点向量表示的维度d,每个节点要生成r条walk,每条walk长度为l,窗口大小k(类似于word2vec中的上下文窗口大小),参数p和q。
根据图G(节点,边,权重)和参数p,q生成一个Π,Π中存的是图中每个节点以及对应的下一节点概率,将该信息加在原图G上,形成一个新图G'。
接下来,迭代r此,并调用node2vecWalk对每个节点生成一个长度为l的walk(形成walk时要借助G'来决定怎么找到下一个节点),形成的r×|V|个walk整合成一个walks序列,将其输入到类似于w2v中,输出一个矩阵,即我们需要的矩阵。
node2vecWalk,需要输入带有G'信息的图,需要生成walk的节点u,需要生成的walk的长度l。
walk的list第一个是u,接下来迭代l词,每次迭代都先将walk的最后一个元素作为当前节点curr,再得到当前节点curr的周围节点以及对应的概率信息,得到最大的一个概率对应的下一个节点,将节点添加到walk并进行下一次迭代。
具体的复现:
(参考Github

复现效果

micro-F1

image.png(文中图,最上面的是node2vec)
使用0.9的数据集BlogCatalog得到的Micro-F1=0.4009

可视化

使用数据量较小的wiki数据集可视化效果:(代码见:Colab
image.png
已经可以看到部分颜色的点有明显的聚集现象。(可视化以及micro-F1的方法在deepwalk中已经介绍)

其他问题

如果是带权图:
需要采用alias_table的方法,在采样节点的时候,需要采用此方法来既考虑到边权的影响,又不至于耗费太大内存,这部分在前面学习LINE的时候已经有所说明。别名采样。应用到这里的时候,则需要先对所有的边进行一轮别名采样,将采样完成后的图再输入到模型中,此时输入的图应当视为无权无向图。

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
大数据
使用钉钉扫一扫加入圈子
+ 订阅

大数据计算实践乐园,近距离学习前沿技术

其他文章
最新文章
相关文章