KDD 2016 | node2vec：可扩展的网络特征学习模型

论文标题｜ node2vec：Scalable Feature Learning for Networks
论文来源｜ KDD 2016
论文链接｜ node2vec: Scalable Feature Learning for Networks
源码链接｜ https://github.com/aditya-grover/node2vec

TL; DR

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

Model/Algorithm

优化目标

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

node2vec 优化的目标是给定每个顶点条件下，令其近邻顶点（如何定义近邻顶点很重要）出现的概率最大。公式如下所示：

$\max _{f} \sum_{u \in V} \log \operatorname{Pr}\left(N_{S}(u) | f(u)\right)$

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

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

$\operatorname{Pr}\left(N_{S}(u) | f(u)\right)=\prod_{n_{i} \in N_{S}(u)} \operatorname{Pr}\left(n_{i} | f(u)\right)$

特征空间对称性假设：指一个顶点作为源顶点和作为近邻顶点的时候共享同一套 embedding 向量。（对比 LINE 中的 2 阶相似度，一个顶点作为源点和近邻点的时候是拥有不同的 embedding 向量的）在这个假设下，上述条件概率公式可表示为

$\operatorname{Pr}\left(n_{i} | f(u)\right)=\frac{\exp \left(f\left(n_{i}\right) \cdot f(u)\right)}{\sum_{v \in V} \exp (f(v) \cdot f(u))}$

根据以上两个假设条件，最终的目标函数表示为

$\max _{f} \sum_{u \in V}\left[-\log Z_{u}+\sum_{n_{i} \in N_{S}(u)} f\left(n_{i}\right) \cdot f(u)\right]$

由于归一化因子 $Z_{u}=\sum_{v \in V} \exp (f(u) \cdot f(v))$ 的计算代价高，所以采用负采样技术优化。

顶点序列采样策略

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

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

$P\left(c_{i}=x | c_{i-1}=v\right)=\left\{\begin{array}{ll}{\frac{\pi_{v x}}{z}} & {\text { if }(v, x) \in E} \\ {0} & {\text { otherwise }}\end{array}\right.$

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

计算转移概率 $\pi_{v x}$ 最简单的想法就是基于 $w_{vx}$ ，但是这种想法没有考虑到网络的结构特性来研究不同类型的网络邻居节点。基于 BFS 和 DFS 的游走策略适用于不同的 structural equivalence and homophily。

因此，node2vec 引入两个超参数 $p$ 和 $q$ 来控制随机游走的策略，同时考虑到了 BFS 和 DFS 游走策略。假设当前随机游走经过边 $(t,v)$ 到达顶点 $v$ 。设 $\pi_{v x}=\alpha_{p q}(t, x) \cdot w_{v x}$ ， $w_{vx}$ 是顶点 $v$ 和 $x$ 之间的边权，

$\alpha_{p q}(t, x)=\left\{\begin{array}{ll}{\frac{1}{p}} & {\text { if } d_{t x}=0} \\ {1} & {\text { if } d_{t x}=1} \\ {\frac{1}{q}} & {\text { if } d_{t x}=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)。