[Graph Embedding] node2vec

在前面两篇文章中，我们分别介绍了DeepWalk 和 LINE，其中DeepWalk使用随机游走来扩展节点的领域。本文的node2vec的中心思想和DeepWalk很相似，作者对随机游走进行改写，使得通过改写的随机游走进行节点领域的遍历时，可以同时反应dfs（深度优先采样）和bfs（广度优先采样）的特性。
 

Introduction

关于DeepWalk之前的算法（应该已经是慢慢无人问津了）我们就暂且不讨论了。作者对于DeepWalk和LINE这两个算法的评价是：它们都提出了有效的图表示学习算法，但是它们对网络邻域的概念的理解都比较僵硬死板，导致这些方法对网络特有的连接模式不敏感。具体来说，网络中的节点可以基于community的概念进行组织，也可以基于structural role的概念进行组织。而现实世界中的网络通常都是表示出这2种等价关系的混合，作者提出的node2vec算法就可以灵活的兼顾这2种对于网络节点之间进行组织的想法。

如上图所示，节点u和节点s1属于同一个紧密相连的community（社区），同时节点u和节点s6在2个不同的社区中扮演着相同的中心节点的角色（structural role）。

因此，node2vec算法学习到的特征表示向量想要做到：

• 同一个community中的节点更加的相似
• 拥有类似的结构特征（structural role）的节点更加的相似

node2vec算法原理

1. 目标函数

图的定义为 G = ( V , E ) G = (V,E) G=(V,E)，其中V为节点集合，E为边集合。定义 f : V → R d f : V\rightarrow R^d f:V→Rd 为从节点到特征表示向量的映射函数， f f f 相当于一个大小为 ∣ V ∣ × d |V| \times d ∣V∣×d 的矩阵，这就是算法所求。对任何一个源节点 u ∈ V u \in V u∈V，我们定义 N S ( u ) ⊂ V N_S(u) \subset V NS​(u)⊂V作为节点 u 通过改写的随机游走策略S生成的网络领域。

优化目标为：
m a x f   ∑ u   ∈   V l o g   P r ( N S ( u ) ∣ f ( u ) ) (1) \underset{f}{max} \ \displaystyle \sum_{u \ \in\ V}{log\ P_r(N_S(u)| f(u))} \tag1 fmax​ u ∈ V∑​log Pr​(NS​(u)∣f(u))(1)
为了让这个目标函数更加易于处理，引入了2个假设：

1. 条件独立性（Conditionalindependence）：对一个节点u进行改写的随机游走策略S获得节点的网络领域 N S ( u ) N_S(u) NS​(u)，定义其中每一个节点被采样到的概率与其他节点被采样到的概率是相互独立的。即节点u采样到 N S ( u ) N_S(u) NS​(u)的概率是节点u分别采样到 N S ( u ) N_S(u) NS​(u)中每一个节点的概率的乘积，表示如下：
   P r ( N s ( u ) ∣ f ( u ) ) = ∏ n i ∈ N S ( u ) P r ( n i ∣ f ( u ) ) P_r(N_s(u)| f(u)) = \prod_{n_i \in N_S(u)}{P_r(n_i|f(u))} Pr​(Ns​(u)∣f(u))=ni​∈NS​(u)∏​Pr​(ni​∣f(u))

2. 特征空间中的对称性（Symmetry in feature space）：在特征空间中，源节点和领域中的节点相互的影响是对称的。就是说节点u作为源节点和作为领域中的节点时，它的feature represensation（ f ( u ) f(u) f(u)）是一样的；这里可以对比LINE算法中，节点作为源节点和领域中的节点时，表示向量是不一样的。上述条件概率就可以改写为：
   P r ( n i ∣ f ( u ) ) = e x p ( f ( n i ) ⋅ f ( u ) ) ∑ v   ∈   V e x p ( f ( v ) ⋅ f ( u ) ) P_r(n_i|f(u)) = {exp(f(n_i)\cdot f(u))\over \displaystyle \sum_{v \ \in\ V}{exp(f(v) \cdot f(u))}} Pr​(ni​∣f(u))=v ∈ V∑​exp(f(v)⋅f(u))exp(f(ni​)⋅f(u))​

基于上面的假设，公式（1）可以简化为：
m a x f   ∑ u   ∈   V [ − l o g Z u + ∑ n i ∈ N S ( u ) f ( n i ) ⋅ f ( u ) ] (2) \underset{f}{max} \ \displaystyle \sum_{u \ \in\ V} {[-logZ_u + \displaystyle \sum_{n_i\in N_S(u)}{f(n_i) \cdot f(u)}]} \tag2 fmax​ u ∈ V∑​[−logZu​+ni​∈NS​(u)∑​f(ni​)⋅f(u)](2)
其中 Z u = ∑ u ∈ V e x p ( f ( u ) ⋅ f ( v ) ) Z_u = \displaystyle \sum_{u \in V}{exp(f(u) \cdot f(v))} Zu​=u∈V∑​exp(f(u)⋅f(v))， Z u Z_u Zu​的计算非常费时，所以作者采用负采样的方法来优化该部分。

对公式（2）采用SGD（随机梯度下降）进行优化，所求得 f f f 就是我们将节点映射为表示向量的函数。然后就可以将节点或边的表示向量喂给下游的分类器，进行节点预测、边预测等任务。

2. 节点序列采样策略

在普通的Random Walk中， 令 c i c_i ci​ 表示一个节点序列中的第i个节点，则节点 c i c_i ci​ 服从下面的分布：

其中 π v x \pi_{vx} πvx​是从节点v到节点x的非归一化前的转移概率，Z是归一化常数。

作者基于深度优先采样和广度优先采样的思想，对上面的传统的Random Walk进行了改进，node2vec引入了2个参数p和q。如上图所示，我们假设当前节点刚从节点t 经过边(t, v) 到达节点v。

我们令上面传统Random Walk式中的未归一化前的转移概率 π v x = α p q ( t , x ) ⋅ w v x \pi_{vx} = \alpha_{pq}(t,x)\cdot w_{vx} πvx​=αpq​(t,x)⋅wvx​ ,其中

上式中的 d t x d_{tx} dtx​ 表示从节点t到节点x的最短路径长度。我们将上面的 α p q ( t , x ) \alpha_{pq}(t,x) αpq​(t,x) 带入回传统的Random Walk式中，就得到了顶点到他的邻居节点的转移概率。

3. 参数解析

上面 α p q ( t , x ) \alpha_{pq}(t,x) αpq​(t,x) 中的参数p和q的意义如下：

• Return parameter（p），参数p控制在一个采样序列中，对于已经访问到的节点进行重采样的概率，如果我们参数p的值很大的时候，则一个节点不太会重新采样一个刚刚采样到的节点；如果参数p的值比较小的时候，则相反。

• In-out parameter（q），参数q控制着采样序列是采样到多为community内的节点还是community以外的节点。

  我们令 q > 1 q > 1 q>1，则采样节点会倾向跑到与节点t在同一个community中的节点，类似于BFS（广度优先搜索）。

  我们令 q < 1 q < 1 q<1，则采样节点会倾向于跑出t所在的community，类似于DFS（深度优先搜索）。

4. 伪代码

上面是作者提供的node2vec的伪代码，这里不多加赘述。值得一提的是，节点到它的邻居节点的转移概率 π v x \pi_{vx} πvx​已经被提前算好了。因此与LINE中一样，作者采用alias table method，采样一个节点的时间复杂度仅为O(1)。

论文原文：node2vec: Scalable Feature Learning for Networks