什么是DeepWalk

DeepWalk 是一种创新性的图嵌入（Graph Embedding）‍算法，最早由斯坦福大学的 Bryan Perozzi 等人于 2014 年提出。它的核心思想是将图结构（如社交网络、知识图谱）转化为类似自然语言文本的序列，并利用深度学习中的语言模型（SkipGram）来学习每个节点的低维向量表示。

以下是对 DeepWalk 的详细介绍：

1. 基本原理与灵感来源

DeepWalk 的核心灵感来源于 Word2Vec（一种将词语转化为向量的技术）。其核心逻辑是将图视为一门语言：

• 图中的节点 = 文本中的词语（Words）‍
• 随机游走生成的路径 = 文本中的句子（Sentences）‍
• SkipGram（Word2Vec）模型 = 学习这些词语的上下文关系

DeepWalk 通过模拟一个人在图中随机行走（Random Walk），记录下行走的路径序列。随后，它使用 SkipGram 模型（通常是 Word2Vec 的实现）来预测路径中节点的上下文，从而学习到每个节点的向量表示。

2. 算法流程

DeepWalk 的工作流程主要包括两个阶段：

a. 随机游走（Random Walk）‍

• 参数设置：用户需要设定游走的长度（Walk Length）和每个节点的游走次数（Number of Walks）。
• 过程：从图中每个节点出发，随机选择其相邻的节点进行移动，记录下路径序列（例如 A → B → C → D）。

b. SkipGram 训练

• 视作句子：将上述路径序列视作 Word2Vec 中的“句子”。
• 上下文窗口：为每个节点设定一个上下文窗口（Context Window），如窗口大小为 2，则节点 B 的上下文为 A 和 C。
• 目标：最大化在同一游走序列中出现的节点对的相似性，使得在图中结构相似或关系紧密的节点在向量空间中也接近。

3. 主要优势

DeepWalk 作为一种早期的图嵌入方法，具有以下显著优势：

• 无监督学习：不依赖任何标签数据，只需要图的拓扑结构即可进行学习。
• 可扩展性强：该算法是在线学习（Online Learning）的，能够处理大规模的图数据，且天然支持并行计算。
• 捕捉局部结构：通过随机游走，DeepWalk 能够有效捕捉图中的社区结构和局部特征。
• 语言模型优势：利用了 NLP 领域成熟的技术（如负采样、层次 Softmax），在多标签分类任务中表现优异，特别是在标签稀疏的情况下。

4. 局限性

尽管 DeepWalk 贡献巨大，但它也存在一些局限性：

• 随机性不足：随机游走是均匀选择邻居，这在某些情况下可能生成的路径缺乏多样性，无法区分结构相似但身份不同的节点。
• 忽略节点属性：DeepWalk 只考虑了节点之间的连接关系（Topology），未直接利用节点本身的属性信息（如节点的标签或特征）。
• 有向图与权重图：原始的 DeepWalk 主要针对无向无权图，对于有向图或带权重的图结构处理不够自然。

5. 典型应用场景

DeepWalk 学到的节点向量可以直接用于许多机器学习任务：

• 节点分类：如社交网络中预测用户的兴趣爱好。
• 链接预测：如推荐系统中预测用户可能感兴趣的商品或电影。
• 社区检测：通过聚类算法发现图中的潜在社区结构。
• 异常检测：识别图中结构异常或行为异常的节点。

6. 发展与演变

DeepWalk 为后续图嵌入算法奠定了基础，衍生出了许多改进版本，如：

• Node2Vec：引入了偏置随机游走（Biased Random Walk），能够更灵活地平衡“广度优先搜索”和“深度优先搜索”策略。
• DeepWalk 在推荐系统中的应用：利用用户和物品构建异构图，通过 DeepWalk 学习用户/物品嵌入，提升推荐效果。

综上所述，DeepWalk 是一种将“语言模型”巧妙引入“图分析”的开创性工作，它通过将图结构序列化并利用深度学习进行特征学习，为图数据的机器学习应用提供了一种高效且易于实现的解决方案。