DeepWalk：随机游走图嵌入

可视化演示

核心思路

旅行博主的每一篇游记，其实都在无意中记录了一张“关系的快照”：谁和谁总被写在同一页里。DeepWalk 的思路也极其简单——图嵌入的目标，就是把图中每个节点映射到一个低维稠密的向量空间，让原本“靠边连着”的关系，变成“靠距离算着”的关系。一切都是无监督的：我们不需要告诉机器“这些节点该分成几类”，只需要丢给它一批随机游走生成的序列即可。

为什么能做到？因为 DeepWalk 借用了自然语言处理中的 Zipf 定律直觉：在随机游走生成的序列里，节点出现的频率分布和自然语言中单词的频率分布非常相似。既然 Word2Vec 能通过“单词的上下文”学习词向量，DeepWalk 当然也可以用“节点的上下文”学习节点向量。这相当于把图“翻译”成了一门语言，而随机游走序列就是语言中的句子。

最终，DeepWalk 输出的每一个节点向量，都携带了它的“社交名片”——谁和它常出现在一起，谁与它气质相似，都编码在这串数字里。节点分类、链路预测、可视化，都能在这份向量上轻松展开。

回到旅行博主的比喻：她每去一座新城，不会画一张包含几千个路口的超大地图（那太占背包空间），而是只在日记本上记几个关键的“坐标感”——附近有谁、常去哪里、和谁同行。这些精炼的记录，就是节点的“低维向量”。

节点表示学习

在 DeepWalk 出现之前，图节点最朴素的身份标识是 one-hot 编码：假设图里有 1 万个节点，每个节点就是一个长度 1 万的向量，其中只有自己的位置是 1，其他全是 0。这就像给每个路口发了一块只写着自己名字的巨大门牌号——信息量极少，却占满整面墙。而 DeepWalk 采用嵌入向量的思路，让每个节点变成一个蕴含“社交含义”的稠密短向量。

怎么学习这样的向量？核心在“语义由邻居塑造”。旅行博主写游记时，同一个地点总与相似的邻居相伴出现；在 DeepWalk 中，一个节点的向量，是由它周围频繁共现的节点共同“塑造”出来的。两个节点如果有相似“朋友圈”，它们的向量就会被训练得靠近。

维度选择则是一门平衡的艺术：维度太小，向量装不下复杂的关系结构；维度太大，不仅计算量大，还会引入噪音。实践中，DeepWalk 论文给出 64 到 128 维作为常用的稳妥区间，就像博主不会背一整本电话本（1 万维），也不必只记一个地标名（1 维），而是记几十条关键关系。

最终，这些向量组成了嵌入矩阵——相当于一本“城市人物志”，每个街区（节点）都在其中占一行，记录着它与其他街区的关联密码。下游任务只需要查表即可获得任意节点的表示，非常高效。

随机游走采样

旅行博主不会按航线图走，她随机跳上公交，到站随机换乘——这种“无目的”行走，就是 随机游走采样。DeepWalk 从每个节点出发，按均匀概率随机选择当前节点的一个邻居作为下一站，重复 t 次，得到一条长度为 t 的节点序列。把这条序列看作一个句子，节点就是句子里的单词。

转移概率是随机游走的引擎。站在当前节点 $v_i$，选择邻居 $v_j$ 的概率是：

为了覆盖全图，DeepWalk 通常对每个节点执行 γ 次随机游走（论文中常取 $\gamma = 10$，游走长度 $t = 40$）。这些序列合在一起，就构成了训练 Skip-gram 模型的“语料库”。游走参数很重要：长度太短，序列捕捉不到远距离结构；次数太少，稀有节点无法被充分采样。

博主游走得越多，日记越丰富，对城市的理解越全面。随机游走同理：序列越多越有代表性。这份由游走产生的“语料库”，就是训练节点向量的全部素材。

Skip-gram模型

有了“游记语料”，DeepWalk 用 Skip-gram 模型 学习节点向量。Skip-gram 的任务是：给定序列中的一个中心节点 $v_i$，预测它周围窗口 $w$ 内的上下文节点。这就像博主翻到日记某一页，看到“街角咖啡店”，就能猜到前后页写的可能是邻桌的常客。模型希望最大化：

具体地，给定中心节点 $v_i$，上下文节点 $v_k$ 出现的概率由 softmax 定义：

直接计算 softmax 需要对全图所有节点求和，代价太高。DeepWalk 引入层次 Softmax：把所有节点组织成一棵二叉树，把归一化分母的求和变成沿树路径的若干次二分类。这样计算复杂度从 $O(|V|)$ 降到 $O(\log |V|)$。

博主不需要记住全城几万人才能判断“谁和咖啡店老板熟”，只需沿着“街区—街道—门店”的树状结构逐层对号入座。层次 Softmax 就是这个对号入座的过程。训练完成后，矩阵 $\Phi$ 的每一行就是图节点的最终向量。

参数与窗口影响

参数选择直接决定嵌入质量，最关键的当属窗口大小 w。窗口小（如 w=2）时，模型只关注直接邻居，向量强调局部结构；窗口大（如 w=10）时，模型能看到更远的上下文，向量能捕获社区结构。这就像博主写日记：如果只记录“我在 A 地遇到 B ”，A 和 B 的关联最紧；如果记录“我这一天从 A 兜转到 B 再到 C 又偶遇 D ”，A 和 D 之间也能产生间接关联。

嵌入维度 $d$ 也是核心参数：$d$ 太小，表达能力不足，相似节点挤作一团；$d$ 太大，容易引入噪音且训练变慢。经验上，64~128 维是性价比最高的区间。游走参数方面，游走长度 $t$ 和每人游走次数 $\gamma$ 共同决定语料规模，规模越大、覆盖越全，但计算成本也越高。

调参策略通常是“先定游走参数再调窗口”：固定 $\gamma=10, t=40$，在验证集上网格搜索 $w$ 和 $d$。如果任务侧重邻居预测，用小窗口；如果任务侧重社区发现，用大窗口。每一组参数都是一次新的“游记风格”，直接影响下游任务表现。

调参时，可以把窗口想象成博主的“视野半径”：视野窄，只看到眼前的人；视野宽，能发现整条街的社交圈子。DeepWalk 不给标准答案，只提供旋钮——你要根据业务场景决定博主该戴哪副眼镜。

应用与对比

DeepWalk 常被拿来与谱方法（如 Laplacian 特征映射）对比。谱方法通过学习拉普拉斯矩阵的底部特征向量来降维，理论上很优美，但需要矩阵分解，复杂度高，且新节点加入时必须整体重算。DeepWalk 用随机游走 + Skip-gram 绕开了全局矩阵分解，近似等价于对图的归一化拉普拉斯矩阵做因式分解，但支持在线学习和增量更新——有新闻节点加入时，只需对它生成序列、增量训练，不必重跑全图。

在应用上，DeepWalk 最典型的两个场景是节点分类和链接预测。节点分类：先对一部分节点打标签（如“垃圾账号”），用 DeepWalk 学到的向量做特征，训练一个分类器，再预测未标记节点。链接预测：把两个节点的向量拼接或做内积，作为“这两个人是否将成为好友”的特征。在社交网络中，DeepWalk 已被验证能在少量标注下达到高准确率。

回到博主的类比：谱方法像一个必须把全城地图扫描进电脑才能规划路线的“全局规划师”；DeepWalk 则是一个边走边写的“实地记者”——来一个新景点，只需补写一篇游记即可更新整本攻略，效率高且适合动态变化的社交网络。

AI 应用场景

Python 演示

import randomimport networkx as nxfrom gensim.models import Word2Vecfrom sklearn.decomposition import PCAimport matplotlib.pyplot as plt class DeepWalkSampler:    def __init__(self, graph, walk_length=10, num_walks=5):        self.g = graph        self.walk_length = walk_length        self.num_walks = num_walks     def generate_walks(self):        walks = []        nodes = list(self.g.nodes())        for _ in range(self.num_walks):            random.shuffle(nodes)            for node in nodes:                walk = [node]                for __ in range(self.walk_length - 1):                    neighbors = list(self.g.neighbors(walk[-1]))                    if not neighbors:                        break                    walk.append(random.choice(neighbors))                walks.append([str(n) for n in walk])        return walks  def train_deepwalk_graph(G, window=5, dim=64, walk_length=10, num_walks=5):    sampler = DeepWalkSampler(G, walk_length, num_walks)    corpus = sampler.generate_walks()    model = Word2Vec(corpus, vector_size=dim, window=window,                     min_count=0, sg=1, workers=2, epochs=5)    return model  def plot_embeddings(model, G, title):    labels = list(G.nodes())    vectors = [model.wv[str(n)] for n in labels]    low = PCA(n_components=2).fit_transform(vectors)    color_map = nx.get_node_attributes(G, "community")    colors = [color_map.get(n, "gray") for n in labels]    plt.figure(figsize=(6, 5))    plt.scatter(low[:, 0], low[:, 1], c=colors, cmap="viridis", s=60)    plt.title(title)    plt.show()  def main():    G = nx.karate_club_graph()    comm = {n: G.nodes[n]["club"] for n in G.nodes()}    nx.set_node_attributes(G, comm, "community")     model_small = train_deepwalk_graph(G, window=2, dim=32)    plot_embeddings(model_small, G, "DeepWalk small window w=2")     model_large = train_deepwalk_graph(G, window=10, dim=64)    plot_embeddings(model_large, G, "DeepWalk large window w=10")  if __name__ == "__main__":    main()

1. DeepWalkSampler.generate_walks对每个节点执行多次随机游走，产生节点序列，相当于“写游记”
2. random.choice(neighbors)从邻居中随机挑选下一站，这是随机游走的核心转移规则
3. Word2Vec(corpus, sg=1, ...)用 Skip-gram 模式在序列语料上训练节点向量，把节点当“单词”
4. window=2` 与 `window=10两组窗口对比，小窗口抓局部关系、大窗口抓社区结构
5. PCA(n_components=2)把高维嵌入降到二维，直观检查节点聚类效果

常见误区

面试题