1. 从一次组会提问说起：DeepWalk到底解决了什么问题
几年前在一次内部技术分享会上，有位做推荐系统的同事问了我一个问题：如果手上只有一张用户之间的关注关系图，没有任何用户画像、没有行为日志、没有文本标签，怎么给每个用户生成一个可以喂给下游模型的向量表示？当时我脑子里第一个蹦出来的答案就是DeepWalk。这篇发表在KDD 2014上的工作，全称是"DeepWalk: Online Learning of Social Representations"，它做的事情用一句话概括就是：把自然语言处理里Word2Vec那套思路，搬到了图结构数据上，用随机游走生成的节点序列来"造句"，再学出每个节点的嵌入向量。
这个思路在2014年的时候是相当有冲击力的。在此之前，图上的节点表示要么靠人工设计的特征（度、聚类系数、PageRank值等），要么靠矩阵分解那一套（比如拉普拉斯特征映射）。人工特征的问题是泛化差、维度爆炸、需要领域专家；矩阵分解的问题是计算复杂度高，对大规模稀疏图很不友好，而且很难做增量更新。DeepWalk的巧妙之处在于，它把图嵌入问题转化成了一个"序列学习"问题，而序列学习在NLP领域已经有非常成熟的工具链——Word2Vec。这就好比你想做一道从没做过的菜，但发现手边的食材和调料跟另一道你熟悉的菜几乎一样，那直接借用那套烹饪流程就行了。
我后来在好几个实际项目里用过DeepWalk及其变体，踩过不少坑，也总结了一些文档里不会写的经验。这篇文章我打算从原理拆解、随机游走的参数选择、Word2Vec的配置细节、工程实现中的性能优化、以及它和后续方法（Node2Vec、LINE等）的对比这几个角度，把DeepWalk彻底讲透。不管你是刚接触图嵌入的新手，还是已经用过但没深究细节的老手，应该都能从中找到一些有用的东西。
2. 随机游走为什么能等价于"图上的句子"
2.1 从Word2Vec的假设出发理解图嵌入
Word2Vec的核心假设是分布式假设：一个词的含义由它周围出现的词决定。Skip-gram模型做的事情是，给定中心词，预测它窗口内的上下文词。训练完之后，语义相近的词在向量空间里距离就近。这个假设之所以成立，是因为自然语言中词的共现模式确实反映了语义关系——"猫"和"狗"经常出现在相似的上下文里，所以它们的向量会靠近。
DeepWalk把这个逻辑迁移到图上：如果两个节点在随机游走序列中经常出现在彼此的窗口内，那它们的向量就应该靠近。随机游走序列在这里扮演的角色就是"句子"，节点就是"词"。这个类比之所以成立，是因为真实网络中的随机游走序列，其节点出现频率分布确实服从幂律分布，这和自然语言中词频的Zipf分布非常相似。作者在论文里专门做了这个对比实验，发现短随机游走中节点访问频率的分布和NLP语料中词频分布高度吻合。这不是巧合，而是因为很多真实网络（社交网络、引用网络、生物网络）本身就具有无标度特性，少数节点连接度极高，大多数节点连接度很低。
我第一次读到这个类比的时候觉得有点牵强，但后来自己在一个学术合作网络上跑了一遍随机游走，统计了节点出现频率，画出来的双对数坐标图确实是一条近似直线。这个验证过程很重要，因为它告诉你：DeepWalk不是硬套Word2Vec，而是有实证基础的。
2.2 随机游走的数学定义与转移概率
随机游走的过程很朴素：从某个节点出发，每一步以均匀概率随机选择一个邻居走过去，走固定步数或者直到走到没有邻居的节点为止。形式化地说，如果当前在节点v，那么下一步走到邻居u的概率是1/deg(v)，其中deg(v)是v的度。这个转移概率矩阵可以写成D^{-1}A，其中A是邻接矩阵，D是度矩阵。
这里有一个细节值得注意：DeepWalk用的是无偏的均匀随机游走，也就是说每个邻居被选中的概率相同。这个选择看起来很简单，但它隐含了一个假设——所有边的权重相同，或者说边的权重信息没有被利用。如果你的图是带权图，直接套用DeepWalk会丢失权重信息。我在一个带权重的交易网络里试过直接用DeepWalk，效果明显不如后来改成按权重比例采样的版本。所以如果你手头的图有边权，要么先把权重离散化成多重边，要么修改采样逻辑按权重走。
另一个细节是游走长度t的选择。论文里推荐的默认值是t=40，但这个值不是拍脑袋定的。作者做了敏感性分析，发现t在20到60之间效果比较稳定，太短了窗口内上下文不够丰富，太长了计算开销大且可能引入太多噪声。我自己的经验是，对于直径较小的图（比如社交网络，六度分隔理论下直径通常不超过10），t=30到40就够了；对于直径较大的图（比如引用网络，可能达到20以上），t可以适当加大到60甚至80。但要注意，t增大带来的收益是递减的，而计算成本是线性增长的。
2.3 窗口大小与"共现"的定义
Skip-gram的窗口大小w决定了多大的范围算作"上下文"。在NLP里，窗口通常取5到10。在DeepWalk里，论文推荐的默认值是w=5，也就是中心节点左右各5个节点算上下文。这个值同样需要根据图的特性调整。
窗口大小的本质是在定义"局部邻域"的范围。窗口太小，只能捕捉到直接邻居和二阶邻居的信息；窗口太大，会把远处不相关的节点也拉进来，引入噪声。我通常的做法是先用默认值w=5跑一版，然后观察嵌入向量的可视化效果（用t-SNE或者UMAP降维到二维），如果同类节点聚得不够紧，就适当增大窗口；如果不同类节点混在一起，就减小窗口。
还有一个容易被忽略的点：DeepWalk的窗口是对称的，也就是说节点i和节点j如果在窗口内共现，它们互相都是对方的上下文。这跟NLP里Skip-gram的标准做法一致，但在图上有时候我们可能更关心有向关系（比如关注关系中的方向性）。如果你需要保留方向信息，可以考虑用有向随机游走，或者在后处理阶段对嵌入向量做方向性的微调。
3. 用Word2Vec训练嵌入时的参数陷阱
3.1 负采样与层次Softmax的选择
Word2Vec有两种训练加速方案：层次Softmax和负采样。DeepWalk论文里用的是层次Softmax，但后来的实践中负采样用得更普遍。两者的区别在于：层次Softmax构建一棵Huffman树，把预测问题转化成一系列二分类问题，时间复杂度是O(log V)，其中V是节点数；负采样则是把多分类问题转化成二分类问题，每次只更新一小部分权重，时间复杂度是O(k)，k是负采样数量。
我推荐用负采样，原因有三个。第一，负采样的实现更简单，调参更直观，主要就是调负采样数量k。第二，对于大规模图（节点数百万级以上），层次Softmax的Huffman树构建本身就有开销，而且树的平衡性会影响训练效率。第三，负采样在实践中效果通常不差，甚至在某些图上更好。k的默认值一般是5到10，我通常从5开始试，如果嵌入质量不够就加到10或15。但k太大也会导致训练变慢，而且收益递减。
有一个坑我踩过：负采样的时候，采样分布的选择很关键。Word2Vec默认用的是均匀分布或者按词频的3/4次方采样。在图嵌入里，如果直接用均匀分布，高频节点（度大的节点）会被过度采样为负样本，导致它们的嵌入被"推"得太远。我后来改成按节点度的3/4次方采样，效果有可感知的提升。这个细节论文里没写，是我自己对比实验发现的。
3.2 学习率与迭代次数的配合
Word2Vec的学习率默认是0.025，并且会随着训练的进行线性衰减。这个设置对于NLP语料是合适的，但对于图上的随机游走序列，可能需要调整。原因是图上的"句子"数量取决于游走次数和每次游走的长度，这个数量可能比NLP语料大得多或者小得多。
我的经验是：如果游走生成的序列总长度在千万级别以下，用默认学习率0.025没问题；如果序列总长度上亿，学习率可以适当降低到0.01到0.015，否则后期震荡会比较明显。迭代次数（epochs）默认是5，对于图嵌入通常3到10都合理。太少学不充分，太多容易过拟合——虽然Word2Vec本身正则化不强，但过拟合表现为嵌入向量在训练集上区分度很好，在验证集（比如链路预测任务）上表现下降。
还有一个实用技巧：用早停（early stopping）。具体做法是留出一部分边作为验证集，每训练一个epoch就评估一次链路预测的AUC或准确率，当验证指标不再提升时就停止。这个做法在论文里没有，但在工程实践中非常有用，可以节省大量训练时间。
3.3 嵌入维度的确定
嵌入维度d是另一个关键参数。论文里默认d=128，这个值在大多数场景下是合理的起点。但维度的选择跟图的规模和复杂度有关：图越大、结构越复杂，需要的维度通常越高。我的一般原则是，d取节点数的对数级别，比如节点数在1万左右，d=64到128；节点数在100万左右，d=128到256；节点数上亿，d=256到512。
但维度不是越高越好。维度太高会导致两个问题：一是训练和存储开销大，二是嵌入向量可能变得稀疏，下游任务（比如用余弦相似度找相似节点）的效果反而下降。我做过一组对比实验，在一个10万节点的图上，d从32增加到256，链路预测的AUC先升后降，峰值在d=128附近。所以建议从128开始，根据下游任务的表现上下调整。
4. 工程实现中的性能优化与踩坑记录
4.1 随机游走的并行化策略
DeepWalk的原始实现是单线程的，对于大规模图来说速度很慢。后来社区里出现了很多并行化版本，核心思路是把节点分成若干批次，每个批次内的随机游走并行执行。但这里有一个坑：如果多个线程同时读写同一个随机数生成器，会导致结果不可复现，甚至出现数据竞争。
我的做法是给每个线程分配独立的随机数种子，种子之间保持足够大的间隔（比如用线程ID乘以一个大素数）。这样既能并行加速，又能保证结果可复现。另外，随机游走的输出序列最好先写到内存缓冲区，攒够一批再统一写入磁盘或送入Word2Vec训练，避免频繁的IO操作成为瓶颈。
还有一个优化点是游走的重启策略。DeepWalk的原始做法是每个节点都作为起点走固定步数，但这样对于度很小的节点（比如度为1的叶子节点），游走很快就会走到死胡同。我的处理方式是：如果游走过程中走到一个没有未访问邻居的节点，就随机跳回起点重新开始，或者直接终止这条序列。前者能保证序列长度一致，后者实现更简单但会导致序列长度不一。我通常选前者，因为Word2Vec对序列长度不一致虽然能处理，但长度差异太大会影响训练稳定性。
4.2 内存占用与图存储格式
图数据的存储格式对内存占用影响很大。如果用邻接矩阵存储，对于稀疏图来说浪费极大——一个100万节点的图，邻接矩阵就是10^12个元素，根本存不下。正确的做法是用邻接表，而且要用压缩稀疏行（CSR）格式，这样内存占用跟边数成正比，而不是跟节点数的平方成正比。
我在一个项目里一开始用了Python的字典套字典来存图，结果100万节点、500万边的图占了将近20GB内存。后来改成用SciPy的CSR矩阵，内存直接降到不到1GB。这个教训告诉我，图算法的工程实现里，数据结构的选择比算法本身还重要。如果你用Python做原型，建议直接用NetworkX或者SciPy；如果要上生产环境，考虑用C++或者Rust实现核心的游走部分，Python只做调度。
4.3 增量更新与动态图处理
DeepWalk的一个明显局限是它假设图是静态的。但真实场景中，图经常在变化——社交网络有新用户加入、有新关注关系产生；交易网络有新交易发生。如果每次图变了就重新训练整个嵌入，成本太高。
一个实用的折中方案是：定期（比如每天或每周）重新训练一次全量嵌入，在两次全量训练之间，对于新加入的节点，用其邻居嵌入的平均值作为初始嵌入，然后只对新节点及其局部邻域做少量迭代更新。这个做法不是DeepWalk论文里的，是我在实际系统中摸索出来的，效果还不错，能覆盖大部分增量场景。当然，如果图的变化非常剧烈，还是得全量重训。
另一个思路是用流式Word2Vec，把新的随机游走序列持续喂给模型，让嵌入缓慢演化。但这样做的问题是嵌入空间会漂移，不同时间点学出来的嵌入不可比。如果下游任务需要跨时间比较，这个方案就不合适。
5. 下游任务验证：嵌入到底好不好用
5.1 多标签节点分类的实验设计
DeepWalk论文里用的主要评估任务是多标签节点分类。具体做法是：把每个节点的嵌入向量作为特征，训练一个一对多的逻辑回归分类器，预测节点所属的标签。评估指标是Micro-F1和Macro-F1。
这个实验设计有几个细节需要注意。第一，训练集和测试集的划分必须是节点级别的，不能有重叠。第二，对于多标签问题，一个节点可以属于多个类别，所以不能用普通的单标签分类器。第三，逻辑回归的正则化强度需要调，太强了欠拟合，太弱了过拟合。我通常用交叉验证在训练集上选正则化参数。
我复现过这个实验，在CiteSeer和Cora这两个常用引用网络数据集上，DeepWalk的Micro-F1能到0.65到0.70左右，比人工特征（比如节点的度、聚类系数）高10到15个百分点。但比后来Node2Vec的最好结果低3到5个百分点。这个差距主要来自Node2Vec的有偏随机游走能更好地平衡同质性和结构性。
5.2 链路预测中的表现与陷阱
链路预测是另一个常用的评估任务：给定一对节点，预测它们之间是否应该有边。做法通常是把嵌入向量拼接或者做Hadamard积，然后训练一个二分类器。
这里有一个容易踩的坑：负样本的构造方式会极大影响评估结果。如果负样本是随机选的节点对，任务太简单，所有方法的AUC都能到0.9以上，区分度不高。正确的做法是按照一定的启发式规则构造负样本，比如选择那些在图上距离为2或3的节点对作为负样本，这样任务更有挑战性，也更能反映嵌入的质量。
我在一个合作网络数据集上做过对比：随机负样本下，DeepWalk的AUC是0.95，Node2Vec是0.96，差距很小；但换成距离为2的负样本后，DeepWalk降到0.82，Node2Vec是0.86，差距就明显了。这说明评估协议的设计比方法本身的选择有时候更重要。
5.3 嵌入可视化的正确打开方式
很多人喜欢用t-SNE把嵌入降到二维来看聚类效果，这个做法本身没问题，但有几个注意事项。第一，t-SNE的困惑度参数对可视化结果影响很大，默认的30不一定适合你的数据，建议在5到50之间多试几个值。第二，t-SNE的随机种子不同，结果可能差异很大，最好多跑几次取一个稳定的结果。第三，不要过度解读可视化的结果——二维可视化只是为了直观感受，真正的评估还是要靠定量指标。
我通常的做法是：先用t-SNE看整体分布，如果同类节点明显聚在一起，说明嵌入至少捕捉到了类别信息；然后再用定量指标（分类F1、链路预测AUC）做精确评估。两者结合，既能快速发现问题，又能给出可靠的结论。
6. DeepWalk与后续方法的对比及适用边界
6.1 Node2Vec的有偏游走改进了什么
Node2Vec是2016年提出的，核心改进是引入了两个参数p和q来控制随机游走的偏向性。p控制回退到上一个节点的概率，q控制探索新区域的概率。当p=1且q=1时，Node2Vec退化成DeepWalk。通过调节p和q，Node2Vec可以在同质性（相邻节点嵌入相近）和结构性（结构角色相似的节点嵌入相近）之间做权衡。
我在实际项目里的体会是：如果你的图是同质性的（比如社交网络，朋友的朋友大概率也是朋友），DeepWalk和Node2Vec差别不大；但如果图有明显的结构性（比如蛋白质相互作用网络，不同模块里的节点可能有相似的功能角色），Node2Vec的优势就体现出来了。不过Node2Vec的调参成本更高，p和q的组合需要网格搜索，而DeepWalk基本不需要调游走参数。
6.2 LINE、SDNE等方法的定位差异
LINE是2015年的工作，它直接优化一阶和二阶相似度，不需要随机游走。一阶相似度对应直接相连的节点，二阶相似度对应共享邻居的节点。LINE的优势是训练目标更直接，收敛更快；劣势是它只考虑了一阶和二阶邻域，对于需要更长距离依赖的任务可能不够。
SDNE是2016年的工作，用自编码器来学嵌入，同时优化一阶和二阶相似度。它的优势是能捕捉非线性结构，但训练成本高，而且自编码器的调参比Word2Vec复杂得多。
我的选型建议是：如果图规模大、需要快速出结果，DeepWalk或Node2Vec是首选；如果图规模小、对嵌入质量要求极高，可以试试SDNE；如果只需要一阶和二阶信息，LINE够用且更快。没有哪个方法绝对好，关键看你的任务需求和计算预算。
6.3 什么时候不该用DeepWalk
DeepWalk不是万能的。以下几种情况我建议考虑其他方案：第一，图是动态的且变化频繁，DeepWalk的全量重训成本太高；第二，图是异质的（有多种类型的节点和边），DeepWalk的均匀游走会混淆不同类型的信息，应该用metapath2vec这类异质图嵌入方法；第三，图有丰富的节点属性（文本、图像等），DeepWalk只用了结构信息，浪费了属性信息，应该用GraphSAGE或者GAT这类能融合属性的方法；第四，需要嵌入具有可解释性，DeepWalk学出来的向量是黑盒，很难解释每一维的含义。
我自己的经验是，DeepWalk最适合的场景是：中等规模（10万到1000万节点）、同质、静态、结构信息为主、需要快速得到基线结果的图。在这个范围内，它的性价比非常高，实现简单、训练快、效果稳定。超出这个范围，就需要考虑更专门的方法了。
7. 几个我反复用到的实操技巧
第一个技巧是关于随机游走的起点选择。DeepWalk默认每个节点都作为起点，但如果图很大，可以只从度较大的节点出发，因为度小的节点游走很快会走到死胡同，生成的序列信息量低。我通常选度排名前50%的节点作为起点，这样能覆盖大部分重要节点，同时减少无效游走。
第二个技巧是关于嵌入向量的后处理。Word2Vec学出来的向量默认没有归一化，如果下游任务用余弦相似度，最好先做L2归一化。另外，有时候对向量做中心化（减去均值）能提升聚类效果，这个操作在NLP里不常用，但在图嵌入里我试过几次，对某些数据集有正面效果。
第三个技巧是关于超参数搜索的策略。DeepWalk的主要超参数有四个：游走长度t、窗口大小w、嵌入维度d、负采样数量k。我通常按这个顺序调：先固定t=40、w=5、d=128、k=5跑一版基线，然后单独调d（因为d对下游任务影响最大），再调w，最后微调t和k。这样能用最少的实验次数找到不错的配置。
第四个技巧是关于结果的可复现性。随机游走和负采样都涉及随机数，如果不固定种子，每次跑的结果都会有差异。我的做法是在代码里显式设置Python的random种子、NumPy的种子、以及Word2Vec的种子，并且把这三个种子都记录在实验日志里。这样别人复现你的结果时，能拿到几乎一样的嵌入。
第五个技巧是关于评估的严谨性。不要只看一个指标就下结论。我通常同时看节点分类的Micro-F1和Macro-F1、链路预测的AUC和AP、以及嵌入的稳定性（多次运行的方差）。如果某个方法在一个指标上好但在另一个指标上差，就需要分析原因，而不是简单地说它好或不好。
这些技巧都是我在实际项目中一点点积累的，有些是踩坑之后才明白的，有些是对比实验发现的。DeepWalk本身不复杂，但要用好它，这些细节往往决定了最终效果的好坏。
