Node2Vec 算法 主页                                            博客   留言 

在上一篇文章中,我们介绍了graph embedding的经典方法:Deepwalk,其通过随机游走(Random walk)的方式将Graph embedding与Word embedding的方法(word2vec)联系起来。在这一篇文章中,我们将介绍Deepwalk的改进方法: Node2Vec。

Node2Vec 介绍

相比于Deepwalk 中图的随机游走策略,Node2Vec通过调整随机游走的概率,使得graph embedding的结果在“同质性”和“结构性”中进行权衡。我们用图1来说明:其中“同质性”指的是相邻的网络节点中,embedding表达应该相似,例如us1节点。而“结构性”指的是结构相似的网络节点中需要具有相似的embedding表达,例如us6节点。为了表达图网络的结构性,我们应该采用BFS (Breadth First Search,宽度优先搜索) 的方法来进行采样。这是因为BFS可以扫描局部的结构。同时为了表达图结构的同质性,我们采用DFS (Depth First Search,深度优先搜索) 的方法来进行扫描。通过调整随机游走的概率,其扫描过程可以在BFS和DFS之间进行权衡,我们下面将详细讲述。

图1 示例图结构。

Node2Vec 流程

首先,我们设定$G = (V, E)$ 作为我们的图,其中$V$为图的节点,$E$ 为图的边。对于任意一个节点$u \in V$,我们模拟一个长度为$l$的随机游走。我们设定$c_i$为随机游走的第$i$个节点,以$c_0=u$ 作为起始点,其中第$i$个节点$c_i$通过下列概率分布产生:

\[P(c_i=x | c_{i-1}=v) = \left\{ \begin{aligned} &\frac{\pi_{vx}}{Z} \quad if (v,x) \in E \\ &0 \quad otherwise \end{aligned} \right.\]

其中$\pi_{vx}$为是节点$v$和节点$x$的非归一化转移概率,Z为归一化常数。

最简单的方法是将$\pi_{vx}$直接设为相连边的权重,即$\pi_{vx}=w_{vx}$。这种方式与我们上次讲述的Deepwalk方法相同。然而这种方法不能充分考虑到图结构的同质性和结构性。因此,我们通过设定$\pi_{vx}=\alpha_{pq}(t,x)w_{vx}$来调整节点之间的转移概率,其中:

\[\alpha_{pq}(t,x)= \left\{ \begin{aligned} &\frac{1}{p} \quad if \ d_{t,x} = 0 \\ &1 \quad if \ d_{t,x} = 1 \\ &\frac{1}{q} \quad if \ d_{t,x} = 2 \\ \end{aligned} \right.\]

我们在图2中进行说明:其中$t$ 为节点$v$的上一个节点,$d_{t,x}$表示节点$t$与节点$x$的最短距离,例如如果两个节点直接相连,那么$d_{tx}=1$。如果两个节点为相同的节点,$d_{tx}=0$。如果两个节点不相连,则$d_{tx}=2$。参数$p$ 为返回参数,$p$越小,节点返回$t$的概率越高,图的遍历越倾向于BFS,越趋向于表示图的结构性。参数$q$则被称为进出参数,$q$越小,遍历到远处节点的概率越高,图的遍历越倾向于DFS,同时越趋向于表示图的同质性。我们可以通过设置$p,q$的值,来权衡embedding表达的结果。

图2 节点之间的转移概率。

总的来说,Node2vec的流程如下:

  1. 获取用户与物品的交互序列。

  2. 依据生成的交互序列,生成对应的物品关系图。

  3. 使用改进的随机游走的方法(BFS和DFS的混合)产生物品序列。

  4. 将生成的序列通过word2vec模型进行embedding。

由于Node2Vec embedding中表达结果的多样性,我们甚至可以把不同倾向表达结果的embedding拼接起来,得到更丰富的embedding特征。

参考资料

[1]: https://zhuanlan.zhihu.com/p/64200072

[2]:node2vec: Scalable Feature Learning for Networks