概述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如果 xt (返回前一步)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)⎩⎨⎧p11q1如果xt(返回前一步)如果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 走向每个邻居的未归一化概率假设 p0.5, q2走向B即返回上一步概率 1/p 1/0.5 2走向DD 是 B 的邻居吗B 的邻居是 A, C, ED 不是 B 的邻居所以属于 DFS 类概率 1/q 1/2 0.5走向FF 也不是 B 的邻居概率 0.5归一化后从 E 走到 B 的概率为 2/(20.50.5)0.667走到 D 或 F 各为 0.167。这种高概率回到 B的设定符合 BFS 搜索强调局部紧密性。如果设置 p2, q0.5则走向 B 的概率为 1/(122)0.2走向 D 或 F 各为 0.4此时游走更倾向于探索远处节点DFS。随机游走序列生成重复上述过程生成长度固定的随机游走序列例如长度10序列p0.5, q2B → E → B → C → F → E → D → A → B → E偏 BFS绕小圈子序列p2, q0.5B → E → F → C → B → A → D → E → F → C偏 DFS探索远区域基于特定的概率对每个节点A, B, C, D, E, F都重复上述过程每个节点进行多次游走例如 γ10 次每次游走长度固定例如 l10。最终得到例如 60 条序列6节点×10次这些序列就是“大量序列”。二维向量推导假设嵌入维度 d2最终得到各节点的二维向量如参考中给出的表格。这个二维向量是通过Skip-gram 模型Word2Vec 的一种训练得到的并非通过简单的数学公式直接推导而是一个神经网络优化过程。下面列出其核心步骤和数学原理步骤 1构建训练样本中心-上下文对对于每一条随机游走序列设定窗口大小 w例如 w2。以序列[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)∈DlogP(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′i1kEv)∑n∼Pn[logσ(−vu⋅vn′)] \log \sigma(\mathbf{v}u \cdot \mathbf{v}{i1}^{k} \mathbb{E}v) \sum{n \sim P_n} \left[ \log \sigma(-\mathbf{v}_u \cdot \mathbf{v}_n) \right]logσ(vu⋅v′i1kEv)∑n∼Pn[logσ(−vu⋅vn′)]其中 (σ(x)1/(1e−x)\sigma(x) 1/(1e^{-x})σ(x)1/(1e−x))(k) 是负样本个数(P_n) 是噪声分布通常为节点度数的 3/4 次方。步骤 4梯度下降训练通过反向传播对每个节点的向量中心向量和上下文向量求梯度并更新。训练完成后通常取每个节点的中心向量 (vu\mathbf{v}_uvu) 作为该节点的最终嵌入向量。对于 d2 的情况训练结束后每个节点得到一个 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 相同学习每个节点的嵌入向量。假设嵌入维度 d2经过训练后得到各节点的二维向量节点p0.5, q2 (BFS)p2, q0.5 (DFS)A(0.8, 0.2)(0.4, 0.6)B(0.9, 0.1)(0.5, 0.5)C(0.8, 0.3)(0.6, 0.4)D(0.1, 0.9)(0.3, 0.7)E(0.2, 0.8)(0.4, 0.6)F(0.1, 0.7)(0.5, 0.5)在 BFS 设置下A, B, C左半部分的向量聚在一起D, E, F右半部分聚在一起体现了结构性同一边界角色。在 DFS 设置下B和E桥接节点向量相似说明其同质性它们都处于图的中心位置。同质性与结构性的权衡应用社交网络同质性更重要朋友的朋友也是朋友用低 qDFS。引文网络论文的主题或引用模式更关键BFS用低 p。电商推荐用户购买序列同质性和商品分类结构性兼顾需调整 p 和 q。Node2Vec 的优点与局限优点局限通过 p、q 可灵活适应不同图特征需要人工调整 p 和 q无自动选择保留了 DeepWalk 高效性仅能处理静态图不支持动态更新在节点分类、链接预测任务中表现优异不考虑节点属性/标签信息总结Node2Vec 的核心贡献是提出了一种有偏的二阶随机游走通过调节 p 和 q 在同质性和结构性之间找到最佳平衡。从而学习到更富有表现力的节点嵌入。它扩展了 DeepWalk成为图嵌入领域的一个经典里程碑。
