DeepWalk算法详解

图嵌入与网络表示学习的开创性方法

什么是DeepWalk算法？

DeepWalk是一种用于图（Graph）数据表示学习的算法，由Bryan Perozzi等人在2014年提出。它将网络中的节点表示为低维向量，从而保留图的结构信息，便于后续的机器学习任务，如节点分类、链接预测和社区发现。

其核心思想是将图中的随机游走序列类比为自然语言处理中的“句子”，然后使用类似word2vec的技术来学习节点的向量表示。

算法原理

DeepWalk借鉴了NLP中词嵌入（word embedding）的思想，特别是Skip-gram模型，将图结构学习问题转化为语言模型问题。

核心类比

节点 ≈ 词语：图中的每个节点被视为语料库中的一个“词”。
随机游走序列 ≈ 句子：通过从节点出发进行随机游走生成的节点序列被视为“句子”。
图结构 ≈ 语义：频繁共现的节点在向量空间中距离更近，反映了图的局部结构。

算法步骤

生成随机游走序列：对图中每个节点作为起点，进行多次固定长度的随机游走，生成节点序列。
构建语料库：将所有随机游走序列收集起来，形成训练语料。
应用Skip-gram模型：使用word2vec中的Skip-gram模型，以节点为“词”，学习每个节点的向量表示。

输入：图 G = (V, E)，向量维度 d，游走次数 r，游走长度 l，窗口大小 w
输出：每个节点的 d 维向量表示

for each 节点 v ∈ V:
    for i = 1 to r:
        执行一次从 v 开始的长度为 l 的随机游走，得到序列 W_vi
        将 W_vi 添加到语料库 ω
使用 Skip-gram 模型训练 ω，得到节点向量表示

应用场景

社交网络分析：用户兴趣建模、社区发现、好友推荐。
推荐系统：基于用户-物品交互图进行个性化推荐。
知识图谱：实体和关系的向量化表示，用于链接预测。
生物信息学：蛋白质相互作用网络分析。

优势与局限

优点

无需节点的属性信息，仅依赖图结构。
能够捕捉图的局部和全局结构特征。
生成的向量可用于多种下游任务。

局限性

随机游走可能无法充分探索图的全局结构。
对图的稀疏性敏感。
相比后续算法（如node2vec），灵活性较低。

与相关算法的比较

DeepWalk是图嵌入领域的开创性工作，后续出现了许多改进算法：

node2vec：通过有偏随机游走，平衡了深度优先（DFS）和广度优先（BFS）探索，更灵活地捕捉网络特征。
LINE：直接优化一阶和二阶相似性，适用于大规模图。
GCN (图卷积网络)：基于神经网络的端到端图学习方法。

尽管有更新的算法，DeepWalk因其简洁性和有效性，仍然是理解图嵌入的重要起点。