首页 › ML › Node2vec

Node2vec

2020-04-12发布在 ML

1,851 0 0

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

Node2vec算法原理

优化目标

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

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采用的是一种有偏的随机游走。

给定当前顶点，访问下一个顶点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}$ 是顶点和顶点之间的未归一化转移概率， $Z$ 是归一化常数。

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

$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}$ 为顶点 $t$ 和顶点 $x$ 之间的最短路径距离。

下面讨论超参数 $p$ 和 $q$ 对游走策略的影响

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