DeepWalk是一种图节点表示学习算法，由Bryan Perozzi、Rami Al-Rfou和Steven Skiena于2014年提出，发表于第20届ACM SIGKDD知识发现与数据挖掘会议。它把网络中截断随机游走产生的节点序列视作自然语言中的句子，再借助词向量模型中的Skip-Gram方法学习每个节点的低维连续向量表示[1]。这一做法首次把神经网络方法引入图表示学习，其思路被后续大量节点嵌入与图神经网络方法沿用和扩展[2]。
定义
DeepWalk是一种无监督的图表示学习算法，输入一张图，输出图中每个节点的一个低维稠密向量，使得在原图中邻域结构相近的节点在向量空间中彼此靠近[3]。它属于随机游走类的浅层网络嵌入方法，学到的向量可以直接交给分类、聚类等统计模型使用[4]。与谱聚类等早期方法相比，这类方法不要求把整张图一次性载入计算，因此更容易扩展到大规模网络[2]。
算法把从某个节点出发的一段截断随机游走序列当成一个句子，把序列中的节点当成句子里的词，从而把图上的表示学习转化为序列上的表示学习问题。它学习到的表示只由节点的邻域结构决定，并不依赖节点的标签或属性[5]。
原理
算法的第一步是对图做随机游走采样。对每个节点各采样若干条长度固定的游走路径，路径上的每一步都按照转移概率从当前节点跳向其邻居，归一化邻接矩阵 $\tilde{A} = D^{-1}A$ 刻画了这种一跳的转移概率[6]。由于游走可以同时从不同节点独立开始，采样过程天然适合并行，也便于只处理图的局部而不必遍历全图。
第二步是在采样得到的节点序列上使用Skip-Gram模型。设定窗口大小为 $t$，模型以中心节点 $v_i$ 的向量为目标，去预测窗口内出现的上下文节点，其目标是最大化条件概率的对数和 [\max_{\Phi} \sum_{i} \sum_{-t \le j \le t, j \ne i} \log \Pr(v_{j} \mid \Phi(v_{i}))]，其中 $\Phi(v_i)$ 表示节点 $v_i$ 的向量表示[7]。在条件独立的假设下，上下文节点的联合概率被拆成各个上下文节点概率的乘积，再通过一层神经网络配合层次Softmax或负采样来计算和优化[7]。
从优化目标的另一面看，等价于让在随机游走中经常共同出现的节点在嵌入空间里更接近。训练时一边提高中心节点与其上下文节点之间的相似度，一边降低它与从负采样分布中抽取的随机节点之间的相似度[8]。有研究证明，这种学习过程实际上相当于对由邻接矩阵各次幂构成的矩阵进行分解，因而模型也隐式地利用了图的高阶拓扑信息[2]。
完整的算法流程可以概括如下：初始化节点向量矩阵；为便于层次Softmax，先根据节点集合构建一棵二叉树；然后重复若干轮，每轮先随机打乱节点顺序，再对每个节点采样一条随机游走序列，并调用Skip-Gram更新参数[9]。
flowchart LR
A[输入图 G(V, E)] --> B[从每个节点采样截断随机游走]
B --> C[得到节点序列语料]
C --> D[Skip-Gram 滑动窗口取上下文]
D --> E[层次 Softmax / 负采样 优化]
E --> F[每个节点的 d 维向量表示]
发展历程
相关工作发表于2014年。论文《DeepWalk: Online Learning of Social Representations》收录于2014年8月24日至27日举行的第20届ACM SIGKDD知识发现与数据挖掘会议论文集，页码为701至710[10]。作者Bryan Perozzi、Rami Al-Rfou与Steven Skiena在文中提出用截断随机游走获取的局部信息来学习节点的隐含表示，并在BlogCatalog、Flickr和YouTube等社交网络的多标签分类任务上进行了验证[11]。
作者随后公开了算法的开源实现，支持邻接表、边表和Matlab矩阵等多种输入格式，代码以Python写成，依赖numpy与scipy[12]。开发方表示，新版实现基于较新版本的词向量库，若要完全复现论文结果需要安装较老版本的依赖[12]。
DeepWalk提出的随机游走加神经网络的范式被后来者延续。2016年出现的node2vec在其基础上改用带偏置的随机游走，通过返回参数和进出参数在广度优先与深度优先式的探索之间进行权衡[3]。同年提出的LINE也把浅层神经网络引入图表示学习，两者共同超越了基于谱聚类的传统方法[2]。此后GraRep直接沿用DeepWalk的矩阵分解形式，按阶数分别建模并拼接各阶表示；TADW则把分解框架扩展为可同时使用节点文本信息的模型[2]。
在时间复杂度上，各类综述给出的结论一致：DeepWalk的运行开销与节点数和嵌入维度成正比，被记为 $O(N \cdot d)$ 量级。
应用
最直接的用途是节点分类，尤其是网络中只有少部分节点带有标签的多标签分类场景。原文在BlogCatalog等数据集上表明，DeepWalk学到的向量在标注信息缺失的情况下仍能取得优于部分基线方法的F1分数[11]。开源实现中给出的多标签评测脚本也显示，随着已标注节点比例从10%提高到90%，Micro-F1与Macro-F1两项指标随之上升[12]。
学到的向量还可以支撑链接预测，即判断两个节点之间是否可能存在连边。相关综述把DeepWalk列为网络生物学中用于链接预测任务的图表示学习技术之一[8]。
在无监督分析方面，节点向量可用于聚类、社区发现和可视化。由于嵌入空间中位置相近的节点通常具有相似的邻域结构，把向量投影到二维平面上能够得到与社区划分大致对应的分布[3]。
工业场景中，浅层图表示学习方法被广泛用于推荐系统，为大规模或异质图上的用户与物品生成向量特征[2]。此外，这一范式还被视为知识图谱嵌入与自然语言处理中图方法的重要来源之一。
局限
最常被指出的问题是它属于直推式方法，只能给出训练时图中已有节点的向量。一旦图中新增节点或整张图发生变化，就需要重新运行算法来获得全部节点的表示，因此难以直接应用于节点不断变化的动态图[13]。后来的GraphSAGE等方法采用邻居聚合的归纳式思路，使模型能够为训练阶段未见过的新节点生成表示[14]。
参数规模是另一项约束。由于每个节点都对应一份独立参数、节点之间不共享参数，参数总量随节点数线性增长，在大规模图上占用较多空间，也使计算效率受限[15]。有分析指出，该算法的时间复杂度与节点数和嵌入维度成正比。
算法只使用图的结构信息，不能直接利用节点的文本、图像或元数据等属性，对带属性图的支持不足[15]。相比之下，图卷积网络可以把节点特征沿边传播，从而同时利用连边与节点自身特征[5]。
随机游走策略本身也有代价。在超大规模图上，纯随机的采样式游走可能使部分节点很少被访问、表示质量偏弱，并可能丢失一些关键语义信息[16]。同时，该方法没有考虑网络随时间演化的特性，也无法利用边权，在有向图和带权图的处理上存在限制[17]。
参见
参考资料
- Google at KDD’17: Graph Mining and Beyond [引用日期2026-10-14]
- springer.com 上的网页 [引用日期2026-10-14]
- Lecture 3: Node Embeddings [引用日期2026-10-14]
- Random Walk Based Method - Chapters and Articles [引用日期2026-10-14]
- 11. Simple Graph Convolution [引用日期2026-10-14]
- arxiv.org 上的网页 [引用日期2026-10-14]
- arxiv.org 上的网页 [引用日期2026-10-14]
- references [引用日期2026-10-14]
- DeepWalk: Online Learning of Social Representations 1 [引用日期2026-10-14]
- acm.org 上的网页 [引用日期2026-10-14]
- zbmath.org 上的网页 [引用日期2026-10-14]
- deepwalk [引用日期2026-10-14]
- 问换能型GraphSAGE和归纳型GCN的模型体系结构有什么不同？EN [引用日期2026-10-14]
- arxiv.org 上的网页 [引用日期2026-10-14]
- Inductive Representation Learning in Large Attributed Graphs [引用日期2026-10-14]
- springer.com 上的网页 [引用日期2026-10-14]
- s40747-024-01352-z [引用日期2026-10-14]