Graph Embedding——(3)Node2vec理论

Node2vec理论

1)介绍

前面介绍过基于DFS邻域的DeepWalk和基于BFS邻域的LINE。

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

2)优化目标

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

node2vec优化的目标是给定每个顶点条件下，令其近邻顶点（如何定义近邻顶点很重要）出现的概率最大。即：
$$\underset{f}{\max }\sum _{u\in V}\log Pr(N_S(u)|f(u))$$
为了将上述最优化问题可解，文章提出两个假设：

• 条件独立性假设

  假设给定源顶点下，其近邻顶点出现的概率与近邻集合中其余顶点无关。

$$Pr(N_S(u)|f(u))=\prod _{n_i\in N_S(u)}Pr(n_i|f(u))$$

• 特征空间对称性假设

  这里是说一个顶点作为源顶点和作为近邻顶点的时候共享同一套embedding向量。(对比LINE中的2阶相似度，一个顶点作为源点和近邻点的时候是拥有不同的embedding向量的)

  在这个假设下，上述条件概率公式可表示为:

$$Pr(n_i|f(u))=\frac{exp(f(n_i)\cdot f(u))}{{\sum }_{v\in V}exp((f(v)\cdot f(u)))}$$

根据以上两个假设条件，最终的目标函数表示为:
$$\underset{f}{\max }\sum _{u\in V}[-|N_S(u)|\log Z_u+\sum _{n_i\in N_S(u)}f(n_i)\cdot f(u)]$$
其中，$Z_u={\sum }_{v\in V}exp(f(n_i)\cdot f(u))$。由于归一化因子$Z_u$的计算代价高，所以采用负采样技术优化。

3)顶点序列采样策略

node2vec引入两个超参数$p$ 和 $q$来控制随机游走的策略，假设现在游走序列从$t$走到$v$，这时候需要算出三个系数，分别作为控制下一步走向方向的偏置$\alpha$
$${\alpha }_{pq(t,x)}=\{\begin{array}{ll}\frac{1}{p}& if{d}_{tx}=0\\ 1& if{d}_{tx}=1\\ \frac{1}{q}& if{d}_{tx}=2\end{array}$$
其中，$d_{tx}$代表$t$结点到下一步结点$x$的最短路，最多为2。

• 当$d_{tx}=0$时，表示下一步游走是回到上一步的结点；

• 当$d_{tx}=1$时，表示下一步游走跳向$t$的另外一个邻居结点；

• 当$d_{tx}=2$时，表示下一步游走向更远的结点移动。

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

• 对于$p$

  参数$p$控制重复访问刚刚访问过的顶点的概率。 注意到$p$仅作用于$d_{tx}=0$的情况，而$d_{tx}=0$表示顶点 $x$就是访问当前顶点$v$之前刚刚访问过的顶点。 那么若$p$ 较高，则访问刚刚访问过的顶点的概率会变低，反之变高。

• 对于$q$

  参数$q$控制的是游走向更远方向的概率，也就是激进探索系数。如果$q$较大，那么游走策略则更偏向于广度优先策略，若$1$较小，则偏向于深度优先策略。

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

给定当前顶点 $v$，给定当前顶点$x$ 的概率为：
$$P(c_i=x|c_{i-1}=v)=\{\begin{array}{ll}\frac{{\pi }_{vx}}{Z}& if(v,x)\in E\\ 0& ifotherwise\end{array}$$
${\pi }_{vx}$是顶点 $v$和顶点 $x$之间的未归一化转移概率，${\pi }_{vx}={\alpha }_{pq}(t,x)\cdot w_{vx}$，$w_{vx}$是顶点 $v$和顶点 $x$之间的权重，$Z$是归一化常数。

Graph Embedding——(1)DeepWalk理论
Graph Embedding——(2)LINE理论
Graph Embedding——(4)Struc2vec理论
Graph Embedding——(5)SDNE理论
Graph Embedding常见类型的理论详解