DeepWalk：图嵌入表示学习

可视化演示

展示DeepWalk将图节点映射到低维向量的完整流程：随机游走采样节点序列、SkipGram训练学习节点共现关系、嵌入空间可视化及与node2vec对比，交互切换四种模式。

图嵌入思想

想象你手里那张家喻户晓的游乐园地图。过山车与跳楼机之间有一条小路，旋转木马旁紧挨着摩天轮。每一个游乐项目是图上的一个节点，每一条路是一条边。对运营总监来说，地图是直观的；但计算机拿到这张图时，看到的不过是“哪个点和哪个点相连”。要让机器学习模型替我们做决策，得先把这些点变成它熟悉的语言——一串数字。

图嵌入的目标，正是给每个节点生成一张“数字画像”。画像不需要人工设计，而是自动从图结构中学出来。传统做法是维护一张 N×N 的邻接矩阵，N 是节点总数。可真实的社交网络动辄上亿用户，邻接矩阵会稀疏到让人绝望，而且独热式的行向量完全看不出两个节点之间的相似性。DeepWalk 换了个思路：借用词向量的思想，把“图”当成“文章”，把“节点”当成“词”，把节点之间的连接关系当成“语境”，让模型自己把这些语境压缩成低维向量。

在数学上，一张图可以写成一个极简的二元组：

嵌入的本质，是找到一个映射函数：

回到游乐园的场景：一旦每个项目都有了“数字画像”，计算机就能用它们之间的坐标距离来回答“过山车和哪个项目最像”这样的问题。而 DeepWalk 学到画像的方式，正是让路线记录员先去遛弯。

随机游走采样

园区请来一批“路线记录员”，他们的任务很简单：从任意一个项目出发，随机选一条路走到下一个项目，再随机走，直到走满规定步数。每走完一圈，记录员手里就多了一张纸条，上面写着一串项目编号，比如“过山车 → 大摆锤 → 鬼屋 → 摩天轮”。这张纸条，就是图领域常说的“游走序列”。

这些纸条有什么用？回想自然语言处理里的一个朴素规律：一句话里经常挨在一起出现的词，意思往往相近。比如“过山车”和“大摆锤”总被游客连着提起，说明它们很可能都属于“刺激项目”。把这一规律搬到图上：一条游走序列就是“一句话”，序列中前后脚出现的节点，就是“相邻的词”。DeepWalk 用海量这样的“句子”作为训练语料，把图结构里的邻居关系，转化为语言模型能消化的共现关系。

具体采样时，有四个关键控制：第一是游走长度（walk length），决定每张纸条最多记几个项目；第二是游走数量（num walks），决定从每个项目出发要派几批记录员；第三是邻域关系保持，路径上相邻或共现的节点，会被视为语义相近；第四是生成方式，每一步都从当前节点的邻居中等概率随机挑选下一个项目。转移概率写作：

记录员们的纸条收得越多，“句子”越丰富，后面训练出的画像就越精准。接下来，我们要把这一堆纸条喂给教练，让他提炼规律。

SkipGram训练

现在你手上有了成千上万张游玩路线纸条。一位聪明的教练接过纸条，开始帮每个项目刻画性格。他的原则是：如果一个项目频繁出现在另一个项目的“前后文”里，那它们就很有缘分。比如“鬼屋”总出现在“3D 影院”相邻的位置，教练就推测这两个项目气质接近。

在 DeepWalk 中，这位教练就是 SkipGram 模型。它会用一个可滑动的窗口，在每张纸条上从前往后扫。窗口正中间的项目是“中心词”，窗口内其他项目是“上下文”。模型的任务是：看到中心项目，预测窗口内那些上下文项目出现的概率。如果预测得准，说明中心项目的向量确实浓缩了它的“朋友圈”信息。

训练目标是最小化如下所示的错误：

为了计算方便，SkipGram 假设窗口内各上下文项目互不影响，于是联合概率可以拆成每个上下文分别相乘：

教练利用层次 Softmax 做加速，把原本要遍历全部节点计算概率的做法，改成沿着霍夫曼树走一条路径，复杂度从 O(|V|) 降到 O(log|V|)。训练结束后，每个项目都有了自己的向量，接下来就轮到这些画像登场了。

节点向量学习

训练完成后的画面，就像是所有游乐项目都被贴上了一张“气质雷达图”。过山车、跳楼机、大摆锤的画像挤在一处，暗示它们是“刺激三兄弟”；旋转木马、摩天轮、小飞象的画像依偎在一起，属于“亲子温柔区”。画家并没有告诉模型“过山车是刺激的”，但模型从路线的共现规律中，自己悟出了这些隐藏维度。

这些画像有几个特点：第一是低维稠密，每个节点只有几十到几百个连续数值，不像独热编码那样上亿维且几乎全是 0；第二是语义可算，向量之间的夹角、距离可以直接反映节点之间的“亲近程度”；第三是即插即用，下游任务只需把向量当作特征，就能接入分类器、聚类算法或排序模型。

最常用的度量方式是余弦相似度，它只看两个向量的方向是否一致：

有了可比较的向量，乐园区块规划、游客动线优化都不再是拍脑袋。而 DeepWalk 的改进版 Node2Vec，则想让记录员们遛弯时更有主见一些。

与Node2Vec对比

DeepWalk 的记录员是完全“脸盲”的——站在路口时，不管前面是回头路、近邻还是远方，他都一视同仁。但现实中，不同的规划目标需要不同的探索风格：想摸清一个片区的项目构成，最好在小范围内反复逛；想了解整个园区的宏观格局，最好多往远处走。Node2Vec 就是给记录员加装了两个“口味开关”。

这两个开关是参数 p 和 q。p 控制“回退”的吸引力：p 越小，记录员越容易走回刚刚离开的项目；q 控制“远探”的吸引力：q 越小，记录员越喜欢往离上一步很远的节点跑。当 q 较大时，游走近似广度优先搜索（BFS），重点捕捉局部社区结构；当 q 较小时，游走近似深度优先搜索（DFS），重点捕捉全局功能相似性。这一调整只改变了采样策略，训练仍然用 SkipGram。

从转移概率看，Node2Vec 在上一步节点 t 和当前节点 v 的约束下，给候选邻居 x 分配不同的权重：

当 p=q=1 时，三个权重全部等于 1，游走重新变成完全随机，Node2Vec 就退化为 DeepWalk。所以两者不是两个割裂的算法，而是“基础版”与“可调版”的关系。

可扩展性设计

如果游乐园规模扩大到千万级项目，地图还能不能靠人工一块块画出来？显然不行。DeepWalk 之所以在工业界受欢迎，恰恰因为它对大图非常友好，几乎不做“重活”。

首先，DeepWalk 从不显式构造 N×N 邻接矩阵，随机游走只访问局部邻居，天然避免全图展开。其次，每个记录员的遛弯路线互不依赖，可以分派给多个线程甚至多台机器并行处理，最后汇总成语料即可。再次，训练阶段使用层次 Softmax，用二叉树结构替代全量归一化，省掉了对千万个节点逐一计算概率的巨大开销。总体复杂度可以写成：

正因为复杂度可控，DeepWalk 才能处理千万级节点的社交网络或交易网络。有了这批“路线记录员”和高效训练管线，图向量才能真正落地到业务场景。

应用场景展望

当每个节点都拥有了向量画像，游乐园和互联网的各种“聪明功能”就可以上线了。运营方最关心的三件事：给新项目自动分类、预测该在哪两个项目之间修路、找到园区里隐藏的“主题片区”——分别对应图学习中的节点分类、链路预测和社区发现。

节点分类很简单：把节点向量当作特征，训练一个逻辑回归或小分类器，就能自动判断“刺激型 / 亲子型 / 观赏型”。链路预测则依赖向量之间的亲和度，两个节点向量点积越大，越可能在未来产生连接。社区发现更直接：对向量做 K-Means 或 DBSCAN 聚类，每一簇就是一个潜在的“圈子”。

链路预测的数学形式通常写成：

回顾整个游乐园：记录员遛弯得到路线，教练从路线中学出画像，画像再服务于分类、预测和聚类。DeepWalk 作为这一切的起点，它的价值并不在于模型多复杂，而在于用最简单的随机游走加 SkipGram，为图数据打开了一条通往机器学习世界的大路。

AI 应用场景

Python 演示

"""DeepWalk 图嵌入最小演示"""import randomimport numpy as np try:    import networkx as nxexcept ImportError:    raise SystemExit("请先安装 networkx: pip install networkx") try:    from gensim.models import Word2Vecexcept ImportError:    raise SystemExit("请先安装 gensim: pip install gensim")  def random_walk(graph, start, walk_length):    walk = [start]    for _ in range(walk_length - 1):        neighbors = list(graph.neighbors(walk[-1]))        if not neighbors:            break        walk.append(random.choice(neighbors))    return walk  def build_corpus(graph, num_walks, walk_length):    sentences = []    nodes = list(graph.nodes())    for _ in range(num_walks):        random.shuffle(nodes)        for node in nodes:            sentences.append([str(x) for x in random_walk(graph, node, walk_length)])    return sentences  def deepwalk_embed(graph, dim=16, num_walks=10, walk_length=20, window=5):    sentences = build_corpus(graph, num_walks, walk_length)    model = Word2Vec(        sentences=sentences,        vector_size=dim,        window=window,        min_count=0,        sg=1,        hs=1,        workers=4,        seed=42,    )    return {node: model.wv[str(node)] for node in graph.nodes()}  def main():    graph = nx.Graph()    graph.add_edges_from([        (0, 1), (1, 2), (2, 3), (3, 0),   # 刺激系小团体        (4, 5), (5, 6), (6, 7), (7, 4),   # 亲子系小团体        (2, 4),                            # 连接两个团体的路    ])    embeddings = deepwalk_embed(graph, dim=8, num_walks=5, walk_length=10)    v0, v4 = embeddings[0], embeddings[4]    v6, v7 = embeddings[6], embeddings[7]    cos04 = float(np.dot(v0, v4) / (np.linalg.norm(v0) * np.linalg.norm(v4)))    cos67 = float(np.dot(v6, v7) / (np.linalg.norm(v6) * np.linalg.norm(v7)))    print("节点0 与 节点4 的余弦相似度:", round(cos04, 4))    print("节点6 与 节点7 的余弦相似度:", round(cos67, 4))  if __name__ == "__main__":    main()

1. random_walk(graph, node, walk_length)实现核心采样：从当前节点随机选择邻居，逐步生成一条游走序列。
2. sentences.append([str(x) for x in random_walk(graph, node, walk_length)])把一次游走转换成一串节点编号组成的“句子”，加入语料库。
3. random.shuffle(nodes)每轮遍历前打乱节点顺序，让不同起点都有机会作为开头，语料更均衡。
4. model = Word2Vec(...)使用 Gensim 的 Word2Vec 完成 SkipGram 训练。
5. sg=1, hs=1指定 SkipGram 模型和层次 Softmax，与 DeepWalk 论文的技术路线一致。
6. return {node: model.wv[str(node)] for node in graph.nodes()}把训练好的向量按节点导出，方便下游任务直接取用。

常见误区

面试题