DeepWalk

概述DeepWalk 是一种基于随机游走的图嵌入方法它通过将图中的节点视为“单词”将随机游走生成的节点序列视为“句子”。然后利用 Word2Vec 的 Skip-gram 模型学习节点的低维稠密向量表示。核心思想图中经常一起出现的节点在短随机游走中共现在向量空间中距离更近。这使得 DeepWalk 能够捕捉图的局部结构同质性并可用于节点分类、链接预测、可视化等任务。算法流程随机游走生成从每个节点出发进行多次长度固定的随机游走生成大量节点序列。训练嵌入将节点序列输入 Skip-gram 模型以节点预测上下文节点类似 Word2Vec学习每个节点的嵌入向量。详细示例图结构定义假设我们有一个简单的社交网络图包含 6 个节点用户及边好友关系节点: A, B, C, D, E, F 边: (A-B), (A-C), (B-D), (B-E), (C-E), (D-F), (E-F)可视化A -- B -- D | | | C -- E -- F图中节点度数A:2, B:3, C:2, D:2, E:3, F:2。步骤 1生成随机游走序列设定每条游走长度 l4即序列包含 5 个节点每个节点开始游走次数 γ3。以节点 A 为例进行 3 次随机游走每次从邻居中均匀采样下一个节点游走 1A → B → D → F → E 序列[A, B, D, F, E]游走 2A → C → E → B → D序列[A, C, E, B, D]游走 3A → B → E → C → A序列[A, B, E, C, A]对其他节点同样生成序列最终获得数十个序列作为训练语料。“均匀采样”直接说明了跳转概率是均匀分布的即每个邻居被选中的概率相等。形式化定义的补充P(vi1x∣viu){1deg(u)if (u,x)∈E0otherwise P(v_{i1} x \mid v_i u) \begin{cases}\frac{1}{\text{deg}(u)} \text{if } (u, x) \in E \\0 \text{otherwise}\end{cases}P(vi1​x∣vi​u){deg(u)1​0​if(u,x)∈Eotherwise​其中 (E) 是边集(deg(u)\text{deg}(u)deg(u)) 是节点 (u) 的度数。步骤 2构建训练样本Skip-gram with 负采样设定窗口大小 w2对每个序列中的每个中心节点取其前后 2 个节点作为上下文生成中心节点, 上下文节点对。例如序列[A, B, D, F, E]中心 A上下文 B窗口内 [B, D] 但距离1只有B→ 样本 (A, B)中心 B上下文 A, D → 样本 (B, A), (B, D)中心 D上下文 B, F → (D, B), (D, F)中心 F上下文 D, E → (F, D), (F, E)中心 E上下文 F → (E, F)所有序列生成大量样本送入 Skip-gram 模型通常配合负采样加速训练。步骤 3训练获得节点嵌入设定嵌入维度 d2便于可视化用 Word2Vec 训练后每个节点得到一个 2 维向量。例如A: [0.8, 0.2] B: [0.6, 0.5] C: [0.7, 0.1] D: [0.4, 0.9] E: [0.5, 0.7] F: [0.3, 0.8]这些向量使得在图结构中邻近的节点距离更近。例如 A 与 B、C 相似因为它们直接相连B 与 D、E 接近D 与 F 接近等。步骤 4应用嵌入向量节点相似度计算用余弦相似度例如 cos_sim(A,B) 0.8 * 0.60.2 * 0.5 0.58cos_sim(A,C)0.8 * 0.70.2 * 0.10.58而 cos_sim(A,D)0.8 * 0.40.2 * 0.90.50说明 A 与 B、C 更相似。节点分类可将向量作为特征输入分类器预测节点标签如社交网络中的兴趣分类。社区发现通过聚类如 K-means发现节点分组。DeepWalk 的特点与局限优点缺点无监督不需要人工标注特随机游走无法捕捉节点之间的高阶结构差异如不同角色的节点可扩展到大规模图超参数游走长度、数量、窗口大小对结果影响较大结合了随机游走与语言模型简单高效无法利用节点属性特征信息变体与改进Node2Vec引入偏置随机游走BFS/DFS可控制探索邻居或远距离节点。LINE显式优化一阶和二阶相似度。GraphSAGE通过邻居聚合学习支持归纳学习新节点。总结DeepWalk 将图节点类比为文本中的单词用随机游走生成序列再通过 Word2Vec 学习嵌入。该方法奠定了图嵌入领域的基础至今仍是处理中等规模图的常用基准方法。其核心思想“共现即相似”被后续多种方法继承。