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}}是顶点vv和xx之间的边权
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之间的最短路径距离。
下面讨论超参数pp和qq对游走策略的影响
- 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运行得到可视化图像
本文系作者 @rinbn 原创发布在 噓だ。未经许可,禁止转载。