《node2vec:Scable Feature Learning for Network》—论文笔记

node2vec是16年KDD的一个工作,论文提出了一种学习网络节点的特征表示的算法框架。论文定义了一个网络节点邻居的灵活概念,并设计了一个带偏置的随机游走过程来获得不同邻居节点。论文的亮点主要在:采用深度优先搜索(DFS)宽度优先搜索(BFS)两种策略,随机游走生成节点的邻居节点集合。

1、Feature Learning Framework

论文将网络的特征学习看作是最大化似然估计的优化问题,定义网络$G=(V,E)$,映射函数$f:V \to {R^d}$表示将节点映射到d维度的特征表示中,其实$f$就是大小为$|V|\times{d}$的矩阵。对于源节点$u$,定义$N_S(u)\subset{V}$表示通过采样策略S采样得到的邻居节点集合。论文同样也是酱Skip-gram模型扩展到网络表示学习中,优化下面的目标函数:

为了让目标函数更容易训练,论文做了两个假设:

  • 条件独立假设,观察到邻居节点的可能性独立于观察给定源节点特征表示的任何其他邻居节点,也就有如下公式:

  • 特征空间的对称性,源节点和邻居节点之间的相互影响是对称的。于是有如下定义:

综合上面的(1)(2)(3)式,得到最终的目标函数:

其中,$Z_u=\sum_{u\in{V}}{\exp(f(u)\cdot{f(v)})}$,但当处理大的网络时候,$Z_u$的计算量非常大,所以论文采用负采样(negative sample)进行近似计算。

1.1、Search Strategies

论文把对接点邻居的采样看作一种局部搜索,分别利用深度优先和宽度优先搜索,构造源节点的邻居节点集合,集合的大小固定。

  • 宽度优先采样(BFS)

    与源节点u直接相连接的节点,例如上图中的$s_1,s_2,s_3$。

  • 深度优先采样(DFS)

    搜索与源节点距离递增的节点序列,如上图中的$s_4,s_5,s_6$。

1.2、node2vec

定义随机游走的开始节点为$c_0=u$,游走路径长度为$l$,路径中第i个节点的生成服从下面的分布:

其中,$\pi_{vx}$是节点$v$和节点$x$之间的未归一化的转移概率,$Z$是归一化常数。

假设随机游走刚刚经过了边$(t,v)$,游走的当前节点是v,游走策略需要判断下一节点x的选择,因此论文将$\pi_{vx}$定义为$\pi_{vx}=\alpha_{pq}(t,x)\cdot{w_{vx}}$,其中,$\alpha_{pq}$表示搜索偏置,参数p和q用于指导随机游走下一节点的选择,具体定义为:

其中,$d_{tx}$表示节点t到节点x的最短距离,等于0时表示,下一节点x回跳到上一节点t;等于1表示下一节点x和上一节点t直接相连;等于2表示,下一节点x与上一节点t必须经由一个节点才能连接。【当前节点是v】

论文给出了程序的伪代码,算法分为三步:首先预处理计算转移概率,然后随机游走得到游走路径,最后使用SGD优化目标函数。

2、Summary

论文算是对DeepWalk工作的一个延伸,对随机游走序列的生成方式进行了扩展。论文引入两个参数p和q控制游走序列的跳转概率,基于深度优先搜索宽度优先搜索进行随机游走,生成游走序列。

写的还不错?那就来个红包吧!
0%