Node2Vec算法介绍

article/2025/11/6 20:44:14

大家好，我是Linzhuo，今天又来给大家分享graph embedding的相关知识啦。
在上一篇文章中，我们介绍了graph embedding的经典方法：Deepwalk，其通过随机游走(Random walk)的方式将Graph embedding与Word embedding的方法(word2vec)联系起来。在这一篇文章中，我们将介绍Deepwalk的改进方法：
Node2Vec。

本文约含1K字，阅读时长约4分钟。主要分为以下部分：

Node2Vec 介绍
Node2Vec 流程

Node2Vec 介绍

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

图1 示例图结构。

Node2Vec 流程

首先，我们设定 $G = (V, E)$ 作为我们的图，其中 $V$ 为图的节点， $E$ 为图的边。对于任意一个节点 $\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$ 的值，来权衡graph embedding表达的结果的倾向性。