Node2Vec：灵活有偏游走的图嵌入方法

图嵌入与Node2Vec概览

图数据存在于社交网络、推荐系统、知识图谱等众多真实场景中。将图中的节点表示为低维稠密向量是连接图结构与下游机器学习任务的关键桥梁。Node2Vec 是一种经典且广泛使用的图嵌入方法，它通过灵活的有偏随机游走来捕获节点的局部与全局结构信息，最终生成高质量嵌入向量。

本教程将带你从原理到实践，全面掌握 Node2Vec 的核心思想、游走策略、算法流程以及关键技术细节。

为什么需要图嵌入

图上的机器学习任务（节点分类、链接预测、社区发现等）通常不能直接使用邻接矩阵作为输入，因为：

• 邻接矩阵极度稀疏、维度高；
• 无法表达节点间的非线性关系；
• 缺乏对高阶邻域信息的直接编码。

图嵌入的目标是将每个节点映射到一个低维连续向量空间，使得在原始图中结构或属性相似的节点在向量空间中彼此接近。Node2Vec 利用随机游走序列作为图的采样策略，将图结构转化为线性序列，然后借用自然语言处理中的词向量模型（Skip‑gram）进行训练。

核心思想：有偏随机游走

Node2Vec 通过引入两个参数 p 和 q 来控制游走行为，使其在深度优先搜索（DFS）与广度优先搜索（BFS）之间平滑插值。这种设计能够同时捕获节点的同质性和结构等价性。

• 同质性（Homophily）：高度相连且属于同一社区的节点应有相似的嵌入。
• 结构等价性（Structural Equivalence）：在网络中扮演相似结构角色的节点（如枢纽节点、边缘节点）应有相似的嵌入，即使它们相距甚远。

游走策略详解

假设我们刚完成从节点 t 游走到节点 v 的一步，现在需要决定下一个访问节点 x。Node2Vec 定义了一个二阶马尔可夫转移概率，它不仅与当前节点 v 有关，还与前一个节点 t 有关。

转移概率定义

对于边 (v, x)，未被归一化的转移概率为：

α(t,x) * w(v,x)

其中 w(v,x) 是边权重（无权图则为1），α 由以下规则决定：

• 如果 t == x（返回上一节点）：α = 1/p
• 如果 t 与 x 之间存在边（即 x 是 t 的邻居，但 x 不是前一节点 t）：α = 1
• 如果 t 与 x 之间无边（即 x 不是 t 的邻居，且 x 不是 t）：α = 1/q

用距离来定义：记 d_tx 表示节点 t 与 x 的最短路径距离（在本步情景下只能是：0 表示返回 t 自身，1 表示 x 为 t 的邻居，2 表示 x 既不是 t 也不是 t 的邻居）。那么 α 可写为：

α = 1/p   , if d_tx = 0
α = 1     , if d_tx = 1
α = 1/q   , if d_tx = 2

最终转移概率为归一化后的值：P(v→x) = α(t,x) * w(v,x) / Z，其中 Z 为归一化常数。

参数作用直观理解

• p（返回参数）：控制游走折返的概率。

  • 小 p（<1）：游走更倾向于返回上一节点，这会使游走在局部区域来回采样，突出微观邻域结构，近似 BFS 行为。
  • 大 p（>1）：游走尽量不重复访问，推动探索更远区域。

• q（进出参数）：控制游走倾向于向内还是向外探索。

  • 小 q（<1）：游走更倾向于访问远离起始节点 t 的节点（向内探索较少，向外探索较多），体现 DFS 特性，适合捕获结构等价性。
  • 大 q（>1）：游走更倾向于在靠近节点 t 的局部邻域内移动，近似 BFS，适合捕获同质性。

通过调整 p 和 q，你可以针对特定任务学习出最适配的嵌入。

算法流程

Node2Vec 的完整流程分为三个阶段：

1. 预处理：计算转移概率

根据边权重和设定的 p、q 值，为图中每个节点预先计算出每条出边的转移概率。对于无权图，直接计算 α 并做归一化即可；有权图需乘以权重后再归一化。最终形成二阶马尔可夫链的转移概率表，这一步能使后续游走采样的复杂度降低为 O(1)。

2. 生成随机游走序列

从每个节点开始，执行固定长度 l 的随机游走，每个节点重复 r 次游走，产生大量序列。序列中的每个节点相当于一个“单词”。常用的默认设置：l=80，r=10。为了加速，通常会使用**别名采样（Alias Sampling）**让每一步采样可以在 O(1) 时间内完成。

3. 使用 Skip‑gram 训练嵌入

将游走序列视为来自某种“图语言”的句子，使用带负采样的 Skip‑gram 模型最大化序列中上下文节点出现的对数概率。对于每一个节点对（中心词，上下文词），优化目标为：

最大化 Σ (log σ(v_context · v_center) + Σ 负样本 log σ(-v_neg · v_center))

训练完毕后，每个节点得到一个 d 维实数向量（通常 d=128）。

关键实现细节

二阶马尔可夫状态

常规的随机游走只依赖当前节点，Node2Vec 的转移概率依赖 (t, v) 这一对。为了避免每个 (t,v) 对都存一套转移概率导致存储膨胀，实际实现中仅在游走过程中根据起源 t 动态调整 α，而基础权重是从当前节点 v 的邻居表中获取，因此不需要显式存储所有二阶转移矩阵。

别名采样加速

为每个节点的邻居构建别名表（Alias Table），在 O(1) 时间内完成按概率抽样。构建时间与节点的度成正比，总体构建复杂度为 O(m)（m 为边数）。这对大规模图至关重要。

归一化与损失

Skip‑gram 模型通常使用负采样近似 softmax，负采样数 k 一般取 5~20。学习率通常采用线性衰减，并使用随机梯度下降。

超参数调节指南

通常需要配合验证集（如下游分类任务）进行网格搜索。经验范围：p, q ∈ {0.25, 0.5, 1, 2, 4}。

与其他嵌入方法的对比

Node2Vec 的优势在于它为同质性和结构等价性学习提供了可解释且灵活的控制手段，是一种直推式（transductive）嵌入方法，适用于静态图。

实际使用示例（伪代码）

# 加载图 (networkx 图对象)
import node2vec

# 预计算转移概率并生成游走
graph = node2vec.Graph(nx_G, is_directed=False, p=0.5, q=2)
graph.preprocess_transition_probs()
walks = graph.simulate_walks(num_walks=10, walk_length=80)

# 训练 Skip‑gram
from gensim.models import Word2Vec
model = Word2Vec(walks, vector_size=128, window=10, min_count=0, sg=1, workers=8, epochs=1)
embeddings = model.wv

# 获取节点嵌入
vector = embeddings['node_id']

常见问题与注意事项

问：有向图怎么处理？
Node2Vec 自然支持有向图，只需在计算转移概率时只考虑出边，游走序列会遵循有向边方向。此时 d_tx 的计算也要根据有向距离。

问：如何处理节点特征？
原生 Node2Vec 是纯结构嵌入，不利用节点特征。如需融合特征，可后期拼接或使用如 GCN 等方法。

问：大规模图太慢怎么办？

• 使用较小的 r 和 l；
• 采用多线程并行游走生成；
• 使用优化过的库如 pecanpy（其应用了快速别名采样和并行化）；
• 对超大图可先做图分区采样。

问：嵌入结果如何评估？
下游任务评估：节点分类（F1）、链接预测（AUC）、可视化（t‑SNE 投影观察）。对于无标签场景，可以计算嵌入向量的内积与原图的相似性相关性。

总结

Node2Vec 通过引入可调参数 p 和 q，将 BFS 与 DFS 模式统一在同一个随机游走框架内，让嵌入学习能够灵活适配不同的结构语义需求。其核心流程清晰、实现高效，至今仍是图嵌入领域的基线方法之一。掌握 Node2Vec，你将拥有一件剖析图结构信息的强有力工具。