Node2Vec

概述

Node2Vec 是2016 年由斯坦福大学提出的一种图嵌入算法。

它在 DeepWalk 的基础上引入了一个有偏的随机游走策略，通过两个超参数p（返回参数）和q（进出参数）来控制游走偏向广度优先搜索（BFS）还是深度优先搜索（DFS）。

从而在**同质性（homophily）和结构性（structural equivalence）**之间灵活权衡。

同质性：相邻近的节点（如同一社区）有相似的嵌入，由 DFS 偏好实现。

结构性：具有相似角色或功能的节点（如不同社区中的“枢纽”节点）有相似的嵌入，由 BFS 偏好实现。

这种权衡使得 Node2Vec 能同时适用于两种类型的数据，成为图嵌入领域的经典基准方法。

Node2Vec 的核心：有偏随机游走

在 DeepWalk 中，随机游走以均匀概率从当前节点的邻居中选取下一个节点。

而 Node2Vec 则定义了非均匀转移概率，使得游走可以选择“回到上一个节点”（BFS-like）或“探索更远的节点”（DFS-like）。

设当前节点为 vv，上一步是从节点 tt 走到 vv 的。那么从 vv 走到其邻居 xx 的未归一化概率为：

αpq(x)={1p如果 x=t (返回前一步)1如果 x 是 t 的其他邻居 (BFS)1q如果 x 不是 t 的邻居 (DFS) \alpha_{pq}(x) = \begin{cases} \frac{1}{p} & \text{如果 } x = t \text{ (返回前一步)} \\ 1 & \text{如果 } x \text{ 是 } t \text{ 的其他邻居 (BFS)} \\ \frac{1}{q} & \text{如果 } x \text{ 不是 } t \text{ 的邻居 (DFS)} \end{cases}αpq​(x)=⎩⎨⎧​p1​1q1​​如果x=t(返回前一步)如果x是t的其他邻居(BFS)如果x不是t的邻居(DFS)​

详细示例

考虑下面的加权图（节点之间的边表示连接强度，但这里用无权图演示）：

A -- B -- C | | | D -- E -- F

• 节点集合：A, B, C, D, E, F
• 边：A-B, B-C, A-D, B-E, C-F, D-E, E-F

首次游走

设定开始节点为B。初始游走：B → E（从 B 的邻居 {A, C, E} 中随机选到 E）。

第二步：计算转移概率

当前节点v = E，上一步节点t = B。E 的邻居：B, D, F。

我们计算从 E 走向每个邻居的未归一化概率（假设 p=0.5, q=2）：

• 走向B（即返回上一步）：概率 = 1/p = 1/0.5 = 2
• 走向D（D 是 B 的邻居吗？B 的邻居是 A, C, E，D 不是 B 的邻居，所以属于 DFS 类）：概率 = 1/q = 1/2 = 0.5
• 走向F（F 也不是 B 的邻居）：概率 = 0.5

归一化后，从 E 走到 B 的概率为 2/(2+0.5+0.5)=0.667，走到 D 或 F 各为 0.167。

这种高概率回到 B的设定符合 BFS 搜索，强调局部紧密性。

如果设置 p=2, q=0.5，则走向 B 的概率为 1/(1+2+2)=0.2，走向 D 或 F 各为 0.4，此时游走更倾向于探索远处节点（DFS）。

随机游走序列生成

重复上述过程，生成长度固定的随机游走序列（例如长度=10）：

• 序列（p=0.5, q=2）：B → E → B → C → F → E → D → A → B → E（偏 BFS，绕小圈子）
• 序列（p=2, q=0.5）：B → E → F → C → B → A → D → E → F → C（偏 DFS，探索远区域）

基于特定的概率，对每个节点（A, B, C, D, E, F）都重复上述过程，每个节点进行多次游走（例如 γ=10 次），每次游走长度固定（例如 l=10）。

最终得到例如 60 条序列（6节点×10次），这些序列就是“大量序列”。

二维向量推导

假设嵌入维度 d=2，最终得到各节点的二维向量（如参考中给出的表格）。

这个二维向量是通过Skip-gram 模型（Word2Vec 的一种）训练得到的，并非通过简单的数学公式直接推导，而是一个神经网络优化过程。

下面列出其核心步骤和数学原理：

步骤 1：构建训练样本（中心-上下文对）

对于每一条随机游走序列，设定窗口大小 w（例如 w=2）。以序列[B, E, B, C, F, E, D, A, B, E]为例。

• 中心节点 B（位置1）：上下文节点为 E（位置2）→ 样本 (B, E)
• 中心节点 E（位置2）：上下文节点为 B（位置1）和 B（位置3）→ 样本 (E, B), (E, B)
• 中心节点 B（位置3）：上下文节点为 E（位置2）和 C（位置4）→ 样本 (B, E), (B, C)
• ……

所有序列生成大量这样的 (中心节点, 上下文节点) 对。

步骤 2：定义 Skip-gram 模型

每个节点对应两个向量（训练时使用）：

• 中心节点向量：(vu∈Rd\mathbf{v}_u \in \mathbb{R}^dvu​∈Rd)
• 上下文节点向量：(vu′∈Rd\mathbf{v}'_u \in \mathbb{R}^dvu′​∈Rd)

对于一对 (中心节点 u, 上下文节点 v)，模型希望最大化给定 u 出现 v 的概率。该概率通常用 softmax 定义
P(v∣u)=exp⁡(vu⋅v′v)∑n∈Vexp⁡(vu⋅vn′) P(v | u) = \frac{\exp(\mathbf{v}_u \cdot \mathbf{v}'v)}{\sum{n \in V} \exp(\mathbf{v}_u \cdot \mathbf{v}'_n)}P(v∣u)=∑n∈Vexp(vu​⋅vn′​)exp(vu​⋅v′v)​

其中 (V) 是所有节点集合。

步骤 3：优化目标（最大化对数似然）

对于所有训练样本，目标函数为：
max⁡∑(u,v)∈Dlog⁡P(v∣u) \max \sum_{(u,v) \in D} \log P(v | u)max(u,v)∈D∑​logP(v∣u)

其中 (D) 是所有 (中心, 上下文) 对的集合。

直接计算 softmax 分母（对所有节点求和）在大图上不可行，因此实际使用 负采样（Negative Sampling） 来近似:

log⁡σ(vu⋅v′i=1kEv)+∑n∼Pn[log⁡σ(−vu⋅vn′)] \log \sigma(\mathbf{v}u \cdot \mathbf{v}'{i=1}^{k} \mathbb{E}v) + \sum{n \sim P_n} \left[ \log \sigma(-\mathbf{v}_u \cdot \mathbf{v}'_n) \right]logσ(vu⋅v′i=1kEv)+∑n∼Pn​[logσ(−vu​⋅vn′​)]

其中 (σ(x)=1/(1+e−x)\sigma(x) = 1/(1+e^{-x})σ(x)=1/(1+e−x))，(k) 是负样本个数，(P_n) 是噪声分布（通常为节点度数的 3/4 次方）。

步骤 4：梯度下降训练

通过反向传播，对每个节点的向量（中心向量和上下文向量）求梯度，并更新。

训练完成后，通常取每个节点的中心向量 (vu\mathbf{v}_uvu​) 作为该节点的最终嵌入向量。

对于 d=2 的情况，训练结束后每个节点得到一个 2 维向量，例如参考中给出的：

• A: (0.8, 0.2)
• B: (0.9, 0.1)
• C: (0.8, 0.3)
• D: (0.1, 0.9)
• E: (0.2, 0.8)
• F: (0.1, 0.7)

这些向量是训练收敛后的结果，没有显式解析表达式，而是通过优化算法学习到的。

训练嵌入

将生成的大量序列（每个节点重复多次，设定游走次数）输入 Skip-gram 模型（与 Word2Vec 相同），学习每个节点的嵌入向量。

假设嵌入维度 d=2，经过训练后得到各节点的二维向量：

在 BFS 设置下，A, B, C（左半部分）的向量聚在一起，D, E, F（右半部分）聚在一起，体现了结构性（同一边界角色）。

在 DFS 设置下，B和E（桥接节点）向量相似，说明其同质性（它们都处于图的中心位置）。

同质性与结构性的权衡应用

• 社交网络：同质性更重要（朋友的朋友也是朋友），用低 q（DFS）。
• 引文网络：论文的主题或引用模式更关键（BFS），用低 p。
• 电商推荐：用户购买序列（同质性）和商品分类（结构性）兼顾，需调整 p 和 q。

Node2Vec 的优点与局限

总结

Node2Vec 的核心贡献是提出了一种有偏的二阶随机游走，通过调节 p 和 q 在同质性和结构性之间找到最佳平衡。

从而学习到更富有表现力的节点嵌入。它扩展了 DeepWalk，成为图嵌入领域的一个经典里程碑。