Node2vec

node2vec是一种综合考虑DFS邻域和BFS邻域的graph embedding方法。简单来说,可以看作是eepwalk的一种扩展,可以看作是结合了DFS和BFS随机游走的deepwalk。

Node2vec算法原理

优化目标

f(u)f(u)是将顶点uu映射为embedding向量的映射函数,对于图中每个顶点uu,定义NS(u)N_S(u)为通过采样策略SS采样出的顶点uu的近邻顶点集合。

node2vec优化的目标是给定每个顶点条件下,令其近邻顶点出现的概率最大。

{\text{max}}_{\mathrm f}{\textstyle\sum_{\mathrm u\in\mathrm V}}\mathrm{logPr}({\mathrm N}_{\mathrm s}(\mathrm U)\left|\mathrm f(\mathrm u)\right.)

为了将上述最优化问题可解,文章提出两个假设:

  • 条件独立性假设
    假设给定源顶点下,其近邻顶点出现的概率与近邻集合中其余顶点无关。
    P_r(N_s(u)\left|f(u)\right.)={\textstyle\prod_{n_i\in N_s(u)}}\;P_r(n_i\vert f(u))
  • 特征空间对称性假设
    这里是说一个顶点作为源顶点和作为近邻顶点的时候共享同一套embedding向量。(对比LINE中的2阶相似度,一个顶点作为源点和近邻点的时候是拥有不同的embedding向量的)
    在这个假设下,上述条件概率公式可表示为P_r(n_i\vert f(u))=\frac{exp\;f(n_i)\cdot f(u)}{\sum_{v\in V}\;exp\;f(v)\cdot f(u)}

根据以上两个假设条件,最终的目标函数表示为max_f{\textstyle\sum_{u\in V}}\;\lbrack-\log\;Z_u+{\textstyle\sum_{n_i\in N_s(u)}}\;f(n_i)\cdot f(u)\rbrack

由于归一化因子Z_u={\textstyle\sum_{n_i\in N_s(u)}}\;exp(f(n_i)\cdot f(u))的计算代价高,所以采用负采样技术优化。

采样策略

node2vec依然采用随机游走的方式获取顶点的近邻序列,不同的是node2vec采用的是一种有偏的随机游走。

给定当前顶点v,访问下一个顶点x的概率为

P(c_i=x\left|c_{i-1}\right.=v)=\left\{\begin{array}{lc}\frac{{\mathrm\pi}_{vx}}Z&if(v,x)\in E\\0&otherwise\end{array}\right.

{\mathrm\pi}_{vx}是顶点v和顶点x之间的未归一化转移概率,是归一化常数。

node2vec引入两个超参数来控制随机游走的策略,假设当前随机游走经过边到达顶点{\mathrm\pi}_{vx}={\mathrm\alpha}_{\mathrm{pq}}(\mathrm t,\mathrm x)\cdot{\mathrm w}_{\mathrm{vx}}{\mathrm w}_{\mathrm{vx}}是顶点vvxx之间的边权

P\left(c;=x\vert c_{i-1}==v\right)=\left\{\begin{array}{l}\frac11\;\;\;if\;d_{tx}=0\\1\;\;\;\;\;if\;d_{tx}=1\\\frac19\;\;\;if\;d_{tx}=2\end{array}\right.

d_{tx}为顶点tt和顶点xx之间的最短路径距离。

下面讨论超参数ppqq对游走策略的影响

  • Return parameter,p
    参数pp控制重复访问刚刚访问过的顶点的概率。
    注意到pp仅作用于dtx=0d_{tx}=0的情况,而dtx=0d_{tx}=0表示顶点xx就是访问当前顶点vv之前刚刚访问过的顶点。
    那么若pp较高,则访问刚刚访问过的顶点的概率会变低,反之变高。
  • In-out papameter,q
    qq控制着游走是向外还是向内,若q>1,随机游走倾向于访问和tt接近的顶点(偏向BFS)。若q<1q<1,倾向于访问远离tt的顶点(偏向DFS)。

下面的图描述的是当从t访问到v时,决定下一个访问顶点时每个顶点对应的α\alpha

学习算法

采样完顶点序列后,剩下的步骤就和deepwalk一样了,用word2vec去学习顶点的embedding向量。
值得注意的是node2vecWalk中不再是随机抽取邻接点,而是按概率抽取,node2vec采用了Alias算法进行顶点采样。

 

可视化node2vec应用

使用node2vec在wiki数据集上进行节点分类任务和可视化任务。 wiki数据集包含 2,405 个网页和17,981条网页之间的链接关系,以及每个网页的所属类别。 通过简单的超参搜索,这里使用p=0.25,q=4的设置。

本例中的训练,评测和可视化的完整代码在下面的git仓库中,

https://github.com/shenweichen/GraphEmbedding

最后使用python运行得到可视化图像

本文系作者 @ 原创发布在 噓だ。未经许可,禁止转载。

喜欢()
评论 (0)
热门搜索
37 文章
3 评论
11 喜欢
Top