node2vec： Scalable Feature Learning for Networks

1. node2vec介绍

node2vec是一种用于学习网络中节点连续特征表示的算法框架，是一种在玩网络中可扩展的半监督特征学习学习算法，学习了节点特征的低维空间的映射，该映射最大程度地保留了节点的网络邻域，定义了网络邻域的灵活概念，并设计了一种有偏的随机游走程序，该程序可以有效地探索各种邻域。

node2vec学习节点的特征表示遵循两个原则：

1. 来自相同网络社区的节点的特征应该相似
2. 在网络中扮演相似角色的节点的特征应该相似

2. 相关工作

2.1 特征学习框架

网络中的特征学习可以看做是一个最大可能性优化问题。

给定一个图 $G=(V,E)$，$f: V\rightarrow\mathbb{R}^d$ 是从节点到特征表示的映射函数，它是通过下游的预测任务来学习的一个 $|V|\times d$ 的矩阵。对于每个源节点 $u\in V$，$N_S(u)\subset V$ 是源节点通过邻域策略 $S$ 采样的得到的邻域节点。

我们寻求优化以下目标函数，该函数最大化源节点 $u$ 特征表示 $f(u)$ 的网络邻域 $N_S(u)$ 的对数概率:

$$\max_f\sum_{u\in V}\log Pr(N_S(u)|f(u))\tag{1}$$

为了便于处理，做出如下两个假设：

1. 条件独立性：假设观察到邻域节点的可能性独立于观察任何其他邻域节点：

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

1. 特征空间对称：源节点和邻域节点在特征空间中彼此对称。因此，我们将每个源-邻节点对的条件似然概率建模为由其特征的点乘参数化的softmax单元：

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

根据上面两个假设，公式 (1) 可以简化为：

$$\max_f\sum_{u\in v}\bigg [-\log Z_u+\sum_{n_i\in N_S(u)}f(n_i)\cdot f(u)\bigg]\tag{2}$$

其中，$Z_u=\sum_{v\in V}\exp(f(u)\cdot f(v))$，由于该公式对于大规模的网络运算量太大，因此采用负采样来逼近它。

2.2 经典的搜索策略

我们将对源节点的邻域进行采样的问题视为局部搜索的一种形式。下图展示了一个简单图，其中给定一个源节点 $u$，目的是采样出它的邻域节点 $N_S(u)$，为了公平比较不同的采样策略，将 $N_S(u)$ 的采样大小设为 $k$。

2.2.1 广度优先采样策略（BFS）

BFS采样的邻域节点 $N_S(u)$ 是节点 $u$ 的直接邻居，如 $k=3$ 时，BFS采样节点 $s_1, s_2, s_3$。它可以准确地刻画局部邻域，仅通过观察每个节点的邻近区域就可以推断出基于网络角色的结构等效性。在BFS中，采样邻域中的节点往往会重复很多次，它减少了表征1-hop节点相对于源节点的分布时的差异。但是，对于任何给定的k，都只探究该图的很小一部分。

2.2.2 深度优先采样策略（DFS）

邻域 $N_S(u)$ 由在距源节点越来越远的节点顺序采样组成。 如上图，DFS采样 $s_4,s_5,s_6$。在DFS中，采样的节点可以更准确地反映邻域的宏观视图，这对于基于同构性推断社区至关重要。 但是，DFS的问题在于，不仅要推断网络中存在哪些节点到节点依赖关系，而且要表征这些依赖关系的确切性质，这一点很重要。 鉴于我们在样本数量上有一个限制，并且要探索的邻域很大，所以很难做到这一点。 其次，移动到更大的深度会导致复杂的依赖性，因为采样的节点可能离源头很远，并且代表性可能降低。

2.3 偏随机游走（BRW）

基于以上观察，我们设计了一种灵活的邻域采样策略，该策略使我们能够在BFS和DFS之间进行平衡。

2.2.3.1 随机游走（Random Walk）

对于给定的源节点 $u$，模拟一个长度为 $l$ 的随机游走。让 $c_i$ 代表随机游走的的第 $i$ 个节点，$c_0=u$，节点 $c_i$ 有以下公式生成：

$$P(c_i=x|c_{i-1}=v)= \begin{cases} \frac{\pi_{vx}}{Z}, & \mathbf{if}(v,x)\in E\\ 0, &\mathbf{otherwise} \end{cases}$$

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

2.2.3.2 搜索偏差 $\alpha$

偏随机游走的最简单方法是基于静态边缘权重 $w_{vx}$ 采样下一个节点，即 $\pi_{vx} = w_{vx}$。（如果未加权图 $w_{vx} =1$）。但是，这不允许我们考虑网络结构并指导我们探索不同类型的网络邻域。此外，与BFS和DFS分别是分别适合结构对等和同构的极端采样范式不同，偏随机游走结合了这两种极端的采样方式，并且这也满足现实世界的情况。

本文定义了带参数 $p$ 和 $q$ 的二阶随机游走来知道采样。假设当前节点 $u$ 刚经过边 $(t, v)$，并且现在需要根据边 $(v, x)$ 的转移概率 $\pi_{vx}$ 来决定下一步往哪走。令未归一化的转移概率为 $\pi_{vx}=\alpha_{pq}(t,x)\cdot w_{vx}$,

$$\alpha_{pq}(t,x)=\begin{cases} \frac{1}{p},& \mathbf{if}\ d_{tx}=0\\ 1, &\mathbf{if}\ d_{tx}=1\\ \frac{1}{q},&\mathbf{if}\ d_{tx}=2 \end{cases}$$

其中，$d_{tx}$ 代表节点 $t$ 和 $x$ 之间的最短路径，$d_{tx}$ 必须在 $\{0,1,2\}$ 中，两个参数就足够进行采样了。参数 $p$ 和 $q$ 控制探索和离开邻域的速度。

参数 $p$ 控制访问已访问过的直接邻居的可能性，当 $p>\max(q,1)$ 设为较大的值时，保证在接下来的两步中只有很小的可能访问已访问过的节点（除了节点没有其它邻居）。这种策略鼓励在采样时，适当探索并且避免2-hop冗余。如果 $p<\min(q, 1)$ 很小，那么将会在源节点 $u$ 的局部游走。

参数 $q$ 允许搜索向内和向外的不同节点。如果 $q>1$，那么随机游走会偏向节点 $t$。在我们的样本包含一个小的局部性内的节点的意义上，这样的行走可获取相对于行走中的起始节点的基础图的局部视图，并近似 BFS 行为。如果 $q<1$，则步行更倾向于访问距离节点 $t$ 更远的节点。 这种行为反映了DFS，DFS鼓励向外探索。

2.4 node2vec算法

在每一步的随机游走过程中，由于初始节点 $u$ 的选择，都存在一个隐式偏差。由于学习所有节点的表示，因此通过模拟从节点 $u$ 开始的固定长度为 $l$ 的 $r$ 个随机游走来抵消此偏差。在每一步，都是基于转移概率 $\pi_{vx}$ 采样。可以预先计算二阶马尔可夫链的转移概率 $\pi_{vx}$，因此可以使用别名采样在O（1）时间内高效地完成节点的采样，同时模拟随机游走。 依次执行node2vec的三个阶段，即计算转移概率的预处理，随机游走模拟和使用SGD的优化。 每个阶段均可并行化并异步执行，从而有助于node2vec的总体可伸缩性。