本文目录导读：
这是一个非常经典且重要的图表示学习（Graph Embedding）算法。
我们会从核心思想、算法步骤、数学原理以及优缺点几个方面详细讲解。
核心思想：用“句子”来理解“网络”
DeepWalk 的核心思想非常巧妙：将图（网络）中的节点类比为自然语言中的单词，将随机游走生成的节点序列类比为句子。
在自然语言处理（NLP）中，Word2Vec 算法可以从大量的文本语料中学习到每个单词的向量表示,并且语义相近的词在向量空间中的距离也近。
DeepWalk 借鉴了这一思路：
- 节点（Node） $\leftrightarrow$ 单词（Word）
- 随机游走路径（Random Walk Sequence） $\leftrightarrow$ 句子（Sentence）
- 图（Graph） $\leftrightarrow$ 语料库（Corpus）
通过这种方式，DeepWalk 将图的结构信息转化为 Word2Vec 模型可以处理的数据形式。
算法步骤 (三个主要阶段)
DeepWalk 的算法流程可以概括为以下三步：
生成随机游走序列
这是最关键的一步，对于图中的每一个节点，我们都会以它为起点,进行多次固定长度的随机游走。
- 输入： 图 $G = (V, E)$，$V$ 是节点集合，$E$ 是边集合。
- 过程： 假设我们在节点 $v_i$，随机选择一个邻居 $v_j$，移动到 $v_j$，然后从 $v_j$ 再次随机选择一个邻居（可能是 $v_i$，也可能不是），如此重复 $\omega$ 次（$\omega$ 是游走长度）。
- 输出： 一系列节点序列 ${v_1, v2, ..., v\omega}$。
为什么用随机游走？
- 局部与全局信息：短游走捕捉局部邻域结构,多次游走覆盖全局拓扑。
- 并行化：可以从不同的起点同时进行多次游走,计算效率高。
- 灵活性：适用于无权图和有权图（例如在有权图中，可以依据边的权重决定邻居的选择概率）。
将序列输入 SkipGram 模型
将生成的随机游走序列输送给 Word2Vec 中的 SkipGram 模型。
- 目标： 给定一个中心节点（中心词），预测其上下文窗口（大小设为 $k$）内的相邻节点（上下文词）。
- 例如，窗口大小为 $2$，序列为 $[v_3, v_1, \mathbf{v_2}, v_5, v_4]$，中心节点 $v_2$ 的上下文就是 $v_1, v_3, v_5, v_4$。
- 模型优化： 最大化在给定中心节点 $v_i$ 的情况下，出现其上下文节点 $v_j$ 的概率 $P(v_j | v_i)$。
学习节点向量表示
通过训练 SkipGram 模型,模型的隐藏层权重就会成为每个节点的向量表示。
- 输出： 一个 $|V| \times d$ 的矩阵 $\Phi$，$d$ 是向量的维度（超参数）。
- 最终结果： 对于每个节点 $v_i$，我们得到一个 $d$ 维的稠密向量 $\Phi(v_i)$。
数学与公式 (简要)
DeepWalk 的损失函数（目标）可以表示为：
最大化整个语料库（所有随机游走序列）的对数似然函数：
$$ \max{\Phi} \sum{v \in V} \sum_{u \in N(v)} \log P(u | \Phi(v)) $$
- $\Phi(v)$ 是节点 $v$ 的嵌入向量（我们要学习的参数）。
- $N(v)$ 是节点 $v$ 的上下文节点集合（即随机游走序列中，在 $v$ 前后各 $k$ 个窗口内的节点）。
如何计算 $P(u | \Phi(v))$？
SkipGram 模型通常使用 Softmax 函数：
$$ P(u | \Phi(v)) = \frac{e^{\Phi(u) \cdot \Phi(v)}}{\sum_{w \in V} e^{\Phi(w) \cdot \Phi(v)}} $$
由于分母需要计算所有节点与中心节点的点积，计算量非常大（$O(|V|)$），实际应用中通常使用 Hierarchical Softmax（层级Softmax，利用霍夫曼树）或 Negative Sampling（负采样）来加速训练。
优缺点分析
优点
- 无监督学习：不需要任何节点标签,仅依赖图的结构信息。
- 可扩展性强：随机游走可以轻松并行化，适用于大规模图（如社交网络、网页链接图）。
- 简单有效：算法思路清晰，实现简单（直接调用
networkx+gensim即可完成）。 - 局部与全局：能够同时捕捉图的局部邻域信息和全局社区结构。
缺点
- 仅利用结构信息：无法利用节点的属性特征（如用户年龄、商品价格、文本内容等）。
- 同质性偏好：倾向于让结构上相近（属于同一社区或紧密相连）的节点具有相似的表示，对于结构等价（相距较远但拥有相似功能，如两个不同城市的“警察局”）的节点表现一般。
- 无法处理动态图：如果图结构发生变化（节点或边增删）,需要重新运行整个算法。
- 无权重敏感性：标准的 DeepWalk 在处理有权图时，仅仅将权重作为随机游走的概率依据,而不是直接学习权重的语义影响。
代码实现 (Python 伪代码)
import networkx as nx
from gensim.models import Word2Vec
import random
class DeepWalk:
def __init__(self, graph, walk_length, num_walks, embedding_size=128, window_size=10):
self.graph = graph
self.walk_length = walk_length
self.num_walks = num_walks
self.embedding_size = embedding_size
self.window_size = window_size
self.model = None
def random_walk(self, start_node):
"""生成一条以start_node为起点的随机游走序列"""
walk = [start_node]
for _ in range(self.walk_length - 1):
current_node = walk[-1]
neighbors = list(self.graph.neighbors(current_node))
if not neighbors:
break
next_node = random.choice(neighbors) # 随机选择邻居
walk.append(next_node)
return [str(node) for node in walk] # 转换为字符串以符合Word2Vec输入
def generate_corpus(self):
"""生成所有随机游走序列（语料库）"""
walks = []
nodes = list(self.graph.nodes())
for _ in range(self.num_walks):
random.shuffle(nodes) # 打乱节点顺序以减少偏差
for node in nodes:
walks.append(self.random_walk(node))
return walks
def train(self):
"""使用Word2Vec训练节点嵌入"""
corpus = self.generate_corpus()
# 使用Gensim的Word2Vec
self.model = Word2Vec(
sentences=corpus,
vector_size=self.embedding_size,
window=self.window_size,
min_count=0,
sg=1, # Skip-Gram
workers=4
)
print("DeepWalk训练完成！")
return self.model
def get_embedding(self, node):
"""获取节点的向量表示"""
return self.model.wv[str(node)]
# 示例用法
if __name__ == "__main__":
# 创建一个简单的图
G = nx.karate_club_graph() # 空手道俱乐部图
dw = DeepWalk(G, walk_length=20, num_walks=10)
model = dw.train()
# 获取节点0的嵌入向量
embedding = dw.get_embedding(0)
print("节点0的嵌入向量维度:", len(embedding))
print("节点0的嵌入向量(前10维):", embedding[:10])
- 一句话总结：DeepWalk 通过随机游走将图结构转化为“句子”，再利用 Word2Vec 学习节点的向量表示。
- 应用场景：社交网络分析、推荐系统（用户-物品图）、节点分类、链接预测、网络可视化。
- 后续发展：DeepWalk 开创了图嵌入的先河，其后的 Node2Vec 通过引入广度优先（BFS）和深度优先（DFS）的偏好参数，改进了随机游走策略，再后来的 GCN (图卷积网络) 和 GAT (图注意力网络) 则是引入了深度学习神经网络的方法,进一步提升了性能和表达能力。
