Graph Embedding之node2vec

node2vec是Aditya Grover和Jure Leskovec提出的一种Graph Embedding方法，与传统的graph embedding方式不同，node2vec在DeepWalk的基础上引入BFS（广度优先搜索）和DFS（深度优先搜索）两种有偏的随机游走方式，以达到分别表征网络的结构对等性（structural equivalence）和同质性（homophily）的目的。与无任何指导的随机游走相比，作者通过引入Return Parameter和In-out Parameter来达到有偏游走的目的，即通过设定不同的偏置，使得整个随机游走过程在BFS和DFS之间进行游走。在正式介绍node2vec之前，我们先介绍一下网络的结构对等性和同质性。

结构对等性（structural equivalence）

结构对等性主要用于表征节点之间结构的相似性，即相同结构的顶点应该在结构对等性上的表征是相似的。通过BFS能尽可能地遍历顶点周围相邻地的顶点信息，因此BFS更适合用来表征顶点的结构对等性。通过结构对等性，我们可以发现整个图中完全不连通的两个相似结构的顶点，这点在风控反欺诈和异常检测具有非常重要的实际意义。

同质性（homophily）

而同质性表征的是相邻的顶点具有相似的同质性，这个跟Word2Vec有点类似，即经常一起出现的单词，大概率上意思具有相同的表述。因为DFS能从宏观上反应各顶点的邻域情况，因此基于DFS的网络同质性表征更多的被用来做社区发现。下图是BFS和DFS的简单示例，示例中，顶点 $\small u$ 和 $\small S_6$ 具有结构对等性，而顶点 $\small u$ 和 $\small S_4$ 更具有同质性。

Figure 1: BFS and DFS search strategies from node u (k = 3)

feature learning framework

介绍完图的同质性和结构对等性，我们再简单介绍一下作者针对图中顶点特征学习的整体框架。假设现在有一个图 $\small G=(V,E)$ ，那么我们学习的目标就是学得一个函数 $\small f:V \to \Bbb R^d$ 来表示顶点到特征表示的映射，其中 $\small d$ 是一个预先设定的超参数，表示每个顶点的特征表示的维度。那么我们最终学习的结果 $\small f$ 就是一个 $\small |V| \times d$ 的矩阵，对于每一个顶点 $\small u \in V$ ，作者定义 $\small N_s(u) \subset V$ 表示顶点 $u$ 在采样策略 $\small s$ 下的邻居顶点。然后作者通过扩展SkipGram，定义了一个最大化log-property的目标函数：
$\max_f \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))$
特征空间对称。特征空间中，两个顶点之间的影响是对阵的。
$Pr(n_i|f(u))=\frac{\exp(f(n_i) \cdot f(u))}{\sum_{v \in V} \exp(f(v) \cdot f(u))}$ 基于以上假设，前面的目标函数可以简化为
$\max_f \sum_{u\in V}[-\log Z_u + \sum_{u_i \in N_s(u)}f(u_i) \cdot f(u)]$ 对于每一个顶点，有 $Z_u=\sum_{v \in V}\exp(f(u) \cdot f(v))$

node2vec

论文作者提出了一种能在BFS和DFS中实现平滑过渡的随机游走方法，称之为node2vec，在Random Walks的基础上，为每一步Walk引入了偏执 $\alpha$ ，下图展示了node2vec的有偏随机游走的过程。

Figure 2: Illustration of the random walk procedure in node2vec. The walk just transitioned from t to v and is now evaluating its next step out of node v. Edge labels indicate search biases

如上图所示，作者定义了一个二阶游走的过程：假设目前已经从顶点 $\small t$ 游走到了顶点 $\small v$ ，此时从顶点 $\small v$ 游走到下一个顶点 $\small x$ 的转移概率为：
$\pi_{vx} = \alpha_{pq}(t,x)·w_{vx}$ 其中 $\alpha_{pq}(t,x)= \begin{cases} \frac{1}{p}, & \text{if $d_{tx}=0$} \\ 1, & \text{if $d_{tx}=1$} \\ \frac{1}{q}, & \text{if $d_{tx}=2$} \end{cases}$ 其中 $\small d_{tx}$ 表示顶点 $\small t$ 和顶点 $\small x$ 之间的最短距离，且 $\small d_{tx}$ 的取值必须为 $\small \{0，1，2\}$ 其中之一。上式中的 $\small p$ 称之为 $\small \text{Return parameter}$ ， $\small q$ 称之为 $\small \text{In-out parameter}$ ，下面我们分别对这两个参数进行介绍。

Return parameter， $\small p$

$\small p$ 控制一次游走返回上次顶点的可能性。即当一次游走从顶点 $\small t$ 走到顶点 $\small v$ ，然后再回头到顶点 $\small t$ 的概率。如果该值设置的比较大，那么一个从顶点游走回到上一个顶点的概率就越小，即该游走会越走越远，越来越偏离起点。这样就可以游走某个出发点领域还是某个出发点更深度域的目的。参数 $\small p$ 并不直接控制整个游走过程时DFS还是BFS， $\small p$ 只控制游走的区域是一直接近起点还是逐渐远离起点。

In-out parameter， $\small q$

$\small q$ 用于控制一次游走向内游走还是向外游走。当 $\small q>1$ 时随机游走偏向于接近顶点 $\small t$ 的节点，也就是说游走的区域更倾向于顶点 $t$ 的领域，也就是BFS。同样的当 $\small q>1$ 时随机游走偏向于远离顶点 $\small t$ 的节点，也就是DFS。因此参数 $\small p$ 决定了随机游走的区域，而参数 $\small q$ 决定了随机游走的方式，而两者的结合后，通过若干次有偏游走，能更全面的表征网络上顶点的结构信息和同质性。

Algorithm

node2vec算法由两个部分组成node2vecWalk和LearnFeatures。下图给出了算法的整个过程。

Algorithm 1

Case Study: Les Misérables network

作者在《悲惨世界》中的人物关系网络上，分别使用DFS和BFS两种方式进行人物网络特征的Embedding，结果如下图所示。上半部分展示了相邻的人物之间的相似性，而下半部分展示了人物关系网络结构的相似性。在实际的生产应用中，基于DFS的Graph Embedding通常用来做社区发现，用于评估邻节点之间的相似性；基于BFS的Graph Embedding通常可以用来实现相似网络结构或者相似网络行为的顶点，通常用来做推荐或者隔空的风险传播。

Figure 3: Complementary visualizations of Les Misérables coappearance network generated by node2vec with label colors reflecting homophily (top) and structural equivalence (bottom)