Node2Vec采样

wen IT资讯 2026-07-01 19

本文目录导读：

Node2Vec采样

Node2Vec 是一种用于图（网络）中节点表示学习（Node Embedding）的算法，它基于 Word2Vec 的思想，但其核心创新点在于如何生成节点的“上下文序列”。

Node2Vec 通过一种有偏的随机游走（Biased Random Walk） 在图上采样节点序列，然后将这些序列输入到 Skip-Gram 模型中进行训练。

下面从核心概念、采样流程和参数深度解析三个方面来回答你。

Node2Vec 采样的核心目标

Word2Vec 处理的是文本序列（如 我 -> 爱 -> 自然语言处理），而 Node2Vec 处理的是图，为了让 Word2Vec 能处理图，我们需要将图转换为一系列“句子”，即节点序列。

Node2Vec 使用了一种 二阶有偏随机游走，它引入了两个关键参数：返回参数 ( p ) 和 进出参数 ( q )。

假设我们从上一步节点 ( t ) 走到了当前节点 ( v ) ，现在需要决定下一步走到哪个邻居节点 ( x )。

核心采样逻辑（The Random Walk Strategy）：

定义邻居： 从当前节点 ( v ) 出发，所有与 ( v ) 相连的节点（包括上一步的 ( t )）都是候选。
引入偏置： 通常的随机游走是等概率选择邻居，但 Node2Vec 根据 ( p ) 和 ( q ) 对每条边赋予不同的转移概率。
计算转移概率： 设 ( \pi_{vx} ) 是从节点 ( v ) 走到节点 ( x ) 的转移概率（未归一化）。

[ \pi{vx} = \alpha{pq}(t, x) \cdot w_{vx} ]
- ( w_{vx} ) 是边 ( (v, x) ) 的权重（如果是无权图，则为 1）。
- ( \alpha{pq}(t, x) ) 是一个寻路偏置函数，它取决于上一步节点 ( t ) 和候选节点 ( x ) 之间的最短距离（距离 ( d{tx} ) 只能是 0, 1, 或 2）：
[ \alpha{pq}(t, x) = \begin{cases} \frac{1}{p} & \text{if } d{tx} = 0 \quad \text{(即 } x = t \text{，返回上一步)} \ 1 & \text{if } d{tx} = 1 \quad \text{(即 } x \text{ 是 } t \text{ 和 } v \text{ 的共同邻居，BFS行为)} \ \frac{1}{q} & \text{if } d{tx} = 2 \quad \text{(即 } x \text{ 离 } t \text{ 较远，DFS行为)} \end{cases} ]

图解说明： 假设刚才从 t 走到了 v，现在在 v 处，需要决定下一步走向 x1, x2, x3 的哪个（还是走回 t）。

t ——> v
v 的邻居：t, x1, x2, x3
d_{tx} (t 到 x 的最短距离)：
- 走回 t：距离 = 0 (\rightarrow) 偏置 = ( 1/p )
- 走到 x1（t和v的共同邻居）：距离 = 1 (\rightarrow) 偏置 = 1
- 走到 x2（与t不相邻）：距离 = 2 (\rightarrow) 偏置 = ( 1/q )
- 走到 x3（与t不相邻）：距离 = 2 (\rightarrow) 偏置 = ( 1/q )

Node2Vec 的强大之处在于通过调整 ( p ) 和 ( q )，可以控制采样的风格是更接近 BFS 还是 DFS,从而捕捉不同的网络结构特征。

控制回到上一个节点的概率。
高 ( p ) 值（如 p > 1）： 偏向于避免走回头路，这会使游走更倾向于探索新节点，与 BFS 类似，保持游走在当前节点的局部范围内（探索“同质性/社区结构”）。
低 ( p ) 值（如 p < 1）： 偏向于返回上一步，这会使游走在局部附近来回跳跃，卡在局部社区内，采样出的序列非常接近 BFS，能很好地捕捉结构等价性（Structural Equivalence）。

控制向外探索还是向内保守。
高 ( q ) 值（如 q > 1）： 偏向于访问离上一步节点 ( t ) 较近的节点（d_{tx}=1 的节点），这类似于 BFS，游走局限在 ( t ) 和 ( v ) 的附近，采样出的序列能捕捉节点的局部邻域特征（社区感）。
低 ( q ) 值（如 q < 1）： 偏向于访问离上一步节点 ( t ) 较远的节点（d_{tx}=2 的节点），这类似于 DFS，游走会大胆地走向更远的节点，采样出的序列能捕捉节点的宏观结构角色（Hub 节点、桥接节点）。

参数组合	采样风格	捕获的特征	适用场景
p 小, q 大	偏向 BFS 和局部探索	同质性/社区	社区发现、聚类、推荐系统（用户兴趣社群）
p 大, q 小	偏向 DFS 和宏观探索	结构等价性/角色	异常检测、节点分类（如判断节点是核心还是边缘）、链路预测

假设有一个小图： A — B — C D — E — F

初始化游走： 随机选择一个起始节点，B，长度为 L（5）。
第一步： 当前在 B，它的邻居是 A, C, E。
- 因为没有上一步节点，所以这一步是无偏的（等概率选择），假设选中了 C。
- 序列变为：[B, C]
第二步： 当前在 C，上一步是 B，候选邻居：B（距离 0），F（距离 2）。
- 设置 ( p=0.5, q=2 )：
  - 回到 B：概率 (\propto 1/0.5 = 2)
  - 走到 F：概率 (\propto 1/2 = 0.5)
- 归一化后，回到 B 的概率远大于走向 F，所以大概率会回到 B。
- 序列变为：[B, C, B]
第三步： 当前在 B，上一步是 C，邻居：A, C, E。
- ( p=0.5, q=2 )：
  - 回到 C（距离 0）：概率 (\propto 1/0.5 = 2)
  - 走到 A（距离 2）：概率 (\propto 1/2 = 0.5)
  - 走到 E（距离 2）：概率 (\propto 1/2 = 0.5)
- 大概率会回到 C，游走会在 B 和 C 之间不断往返（BFS风格，探索局部）。
重复直到序列长度达到 L。
重复 r 次（每个节点开始游走若干次），生成大量序列。

得到的所有节点序列（相当于“句子”），就作为训练数据，喂给 Skip-Gram 模型（Word2Vec）进行训练。

经过训练，图中的每个节点就对应一个稠密向量，即 Node Embedding。

Node2Vec 的采样本质上是：

希望你通过这个回答，对 Node2Vec 的采样机制有了更清晰的理解。