【Graph Embedding】node2vec的原理、核心算法及其应用

大家好，欢迎来到IT知识分享网。

不同于基于DFS邻域的DeepWalk和基于BFS邻域的LINE。node2vec是一种综合考虑DFS邻域和BFS邻域的graph embedding方法，可以看作是deepwalk的一种扩展，是结合了DFS和BFS随机游走的deepwalk。

node2vec的同质性和同构性

（1）网络的同构性是指距离近的节点的Embedding的结果应相似，如下图的$u和s_1$；

如何使Graph Embedding的结果能够表达网络的“结构性”？让随机游走的过程更倾向于BFS（广度优先遍历）。因为在执行BFS的过程中，相当于对周边节点进行扫描，当前节点是“局部中心节点”还是边缘节点，其生成的序列包含的节点的数量和顺序必然是不同的。从而让最终的Embedding抓取到更多结构性信息。

（2）网络的“同质性”指结构上相近的节点Embedding的结果应该相似，如下图中的$u和s_6$。

如何使Graph Embedding的结果能够表达网络的“同质性“？需要让随机游走的过程更倾向于DFS，因为DFS更有可能通过多次跳转，游走到远方的节点上，但无论怎样，DFS的游走更大概率会在一个大的集团内部进行，这就使得一个集团或者社区内部的节点的Embedding更为相似，从而更多地表达网络的“同质性”。

在DeepWalk中，使用DFS随机游走在图中进行节点采样，使用Word2Vec在采样的序列学习图中节点的向量表示，无法灵活地捕捉这两种关系。

node2vec的改进的基本想法就是，通过节点间的跳转概率让Embedding 的结果兼顾同质性和结构性（上图中的蓝色箭头和红色箭头）。

node2vec在推荐系统中的思考

同质性相同的物品很可能是同品类、同属性，或者经常被一同购买的商品，而结构性相同的物品则是各品类的爆款、各品类的最佳凑单商品等拥有类似趋势或者结构性属性的商品。毫无疑问，二者在推荐系统中都是非常重要的特征表达。由于node2vec的这种灵活性，以及发掘不同图特征的能力，甚至可以把不同node2vec生成的偏向“结构性”的Embedding结果和偏向“同质性”的Embedding结果共同输入后续的深度学习网络，以保留物品的不同图特征信息。

node2vec的基本思想

模型

给定网络图$G(V,E)$，node2vec 的目标是学习映射 $f:\mathbf{V}\to {\mathbb{R}}^d$ ，该映射将每个顶点$v$映射到低维空间表达 $\overrightarrow{{\mathbf{w}}_u}$，该低维空间表达用于下游任务。这里图 $G$可以是有向图也可以是无向图，可以是无权图也可以是带权图。

对于每个节点$u\in V$， 定义$N_S(u)\subset V$作为通过邻域采样策略$S$生成节点$u$的网络邻域。类似 SkipGram，node2vec的优化目标是：给定顶点 $u$ ，在低维空间中最大化其邻居$$N_S(u)\subset V$$ 的对数似然函数。即:
$$\underset{f}{\max }\sum _{u\in V}logPr(N_S(u)|f(u)).\text{\hspace{1em}(1)}$$

为了使优化问题易于处理，论文做了两个标准假设:

（1）条件独立性假设。给定源顶点，邻域节点出现的概率相互独立:
$$Pr(N_S(u)|f(u))=\prod _{n_i\in N_S(u)}Pr(n_i|f(u))$$
（2）特征空间对称性假设。在特征空间中，源节点与邻节点之间存在对称效应。也就是说作为源节点和作为邻节点时候共享同样的embedding向量(回想LINE定义的二阶相似度，一个顶点作为源节点和邻节点时是用不同的embedding向量表示)因此，node2vec将每个源邻节点对的条件似然建模为一个softmax单元，并由它们的特征点积进行参数化:
$$Pr(n_i|f(u))=\frac{exp(f(n_i).f(u))}{{\sum }_{v\in V}exp(f(v).f(u))}.$$
根据假设（1）（2），式(1)中的目标简化为:
$$\underset{f}{\max }\sum _{u\in V}[-log{Z}_u+\sum _{n_i\in N_S(u)}f(n_i).f(u)].\text{\hspace{1em}(2)}$$
其中，$Z_u={\sum }_{v\in V}exp(f(u).f(v))$是归一化因子，计算代价高，所以采用负采样技术优化。

采样策略

采样策略的目标是：让Embedding 的结果兼顾同质性和结构性。node2vec 设计了一种灵活的邻居采样策略，该策略使得我们能够平滑的在 BFS 和 DFS 之间采样。

如下图所示为node2vec算法从节点$t$跳转到节点$v$，在从节点$v$跳转到周围各点的跳转概率。

假设从某顶点出发开始随机游走，第$i-1$步走到当前顶点$v$，要探索第$i$步的顶点$x$，其跳转概率为：
$$P(c_i=x|c_{i-1}=v)=\{\begin{array}{ll}\frac{{\pi }_{vx}}{Z}& if(v,x)\in E\\ 0& otherwise\end{array}$$
其中，$E$是图中边的集合，$(v,x)$表示顶点和$v,x$之间的边，${\pi }_{vx}$ 表示从节点$v$跳转到下一个节点$x$的概率，$Z$是归一化常数。

随机游走的最简单的一个方式是，令${\pi }_{vx}=w_{vx}$，$Z$ 是权重之和。按照这个转移概率进行随机游走，但是无法控制BFS和DFS的倾向性。

node2vec用两个参数$p和q$定义了一个二阶随机游走，以控制随机游走的策略。

所谓的二阶随机游走，意思是说下一步去哪，不仅跟当前顶点的转移概率有关，还跟上一步顶点相关。

假设当前随机游走经过边$(t,x)$到达顶点$v$，现在要决定从节点$v$跳转到下一个节点$x$，需要依据边$(v,x)$上的跳转概率${\pi }_{vx}$ 。即：
$${\pi }_{vx}={\alpha }_{pq}(t,x)\cdot w_{vx}$$
其中，$w_{vx}$是顶点$v和x$之间的边权；${\alpha }_{pq}(t,x)$是修正系数，修正系数定义如下：
$${\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$之间的最短路径距离。注意，$d_{tx}$必须是{0, 1, 2}中的一个。当$d_{tx}=0$表示又回到顶点$t$；当$d_{tx}=1$,表示$x和t$直接相连；其他情况$d_{tx}=2$。参数$p和q$共同控制着随机游走的倾向性。

（1）返回参数(return parameter)：p，控制了重新访问上一步已访问顶点的概率

• 一个较大的值$p>max(q,1)$使得接下来访问的顶点 $x$ 不大可能是上一步已访问的顶点 $t$ （除非顶点 $v$ 除了 $t$之外再也没有其它邻居）。
• 一个较小的值$p<max(q,1)$ 将使得接下来访问的顶点 $x$很可能是上一步已访问的顶点$t$。这种策略使得随机游走序列尽可能地留在源点$u$的局部区域。node2vec就更注重表达网络的结构性。

（2）内外参数（In-out parameter）：q，控制了探索的方向是向内搜索还是向外搜索。

• 如果$q>1$则$x$倾向于向$t$靠拢，这种策略将采样局限在一个很小的范围，从而获得网络的一个局部视图，类似于 BFS 的行为。
• 如果$q<1$则$x$倾向于远离$t$，这种策略将鼓励采样向外拓展，从而获得网络的一个宏观视图，类似于 DFS 的行为，node2vec就更加注重表达网络的同质性。

但是这种策略和BFS、DFS 本质上是不同的：我们的策略采样的结点与源点的距离并不是严格相等的（BFS）、也不是严格递增的 （DFS ）。另外我们的策略易于预处理，且采样效率很高。

在论文中试验部分，作者对$p和q$的设置一般是2的指数，比如$\frac{1}{2},\frac{1}{2},1,2,4$。

学习算法

node2vec经过采样得到序列，剩下的步骤于deepwalk基本一样。用word2vec去学习顶点的embedding向量

Node2Vec 算法主要包含两个过程：Learn Feature 过程、node2vecWalk 过程。细节如下：

应用

代码来源：GraphEmbedding

使用教程：

将项目clone到本地，依次执行：

python setup.py install cd examples python deepwalk_wiki.py 

接口：

G=nx.read_edgelist('../data/wiki/Wiki_edgelist.txt', create_using = nx.DiGraph(), nodetype = None, data = [('weight', int)])#read graph model = Node2Vec(G, walk_length = 10, num_walks = 80,p = 0.25, q = 4, workers = 1)#init model model.train(window_size = 5, iter = 3)# train model embeddings = model.get_embeddings()# get embedding vectors 

参考：

node2vec: Scalable feature learning for

深度学习推荐系统中各类流行的Embedding方法（下）

Node2Vec

【Graph Embedding】node2vec：算法原理，实现和应用