DeepWalk：图网络与NLP的巧妙融合

作者  | kaiyuan

整理  | NewBeeNLP公众号

最近这段时间一直在做图网络相关，也差不多收尾了，有空整体复盘了下，大致以下几个主题，不过没整理完全哈哈（下次一定）

顺手再安利几份资料吧 

• 斯坦福的CS224W课程
• 清华大学唐杰老师的很多分享
• 清华大学 thunlp/GNNPapers
• 一些大佬们的新书：《Graph Representation Learning》、《Deep Learning on Graphs》
• 等等

ok，回到正题，今天要介绍的这篇是『Graph Embedding』系列第一篇，十分经典

• 论文：DeepWalk: Online Learning of Social Representations ^[1]
• 代码：https://github.com/phanein/deepwalk

enjoy~

TL;DR

DeepWalk是首次将深度学习技术（无监督学习）引入到网络分析（network analysis）中的工作，它的输入是一个图，最终目标就是获得网络图中每个结点的向量表示 。毕竟万物皆可向量，得到向量之后能做的事情就非常多了。如下所示是论文中给出的Karate network例子。

先验知识

说到生成向量表示，最有名的莫过于Word2Vec了，那么是不是可以将network embedding的问题转化为熟悉的word embedding形式呢？这样我们就可以借用word2vec的思想来解决了。

转化的方式就是Random Walk ，通过这种方式将图结构表示为一个个序列，然后我们就可以把这些序列当成一个个句子，每个序列中的结点就是句子中的单词。

简单的说，DeepWalk = RandomWalk + SikpGram， 下面我们来具体介绍下两种技术。

Random Walk

随机游走，顾名思义，就是从输入图中的任意一个结点 开始，随机选取与其邻接的下一个结点，直至达到给定长度 ， 生成的序列 。在论文中，对于每一个顶点 ， 都会随机游走出   条序列。

采用随机游走有两个好处：

• 「利于并行化」：随机游走可以同时从不同的顶点开始采样，加快整个大图的处理速度；
• 「较强适应性」：可以适应网络局部的变化；

Skip Gram

word2vec的skip-gram相信大家都非常熟悉了，这里就不再赘述，放一张图。

DeepWalk

结合上面两点， deepwalk其实就是首先利用random walk来表示图结构，然后利用skip-gram模型来更新学习节点表示。算法流程如下所示：

算法有两层循环，第一层循环采样 条路径，第二层循环遍历图中的所有结点随机采样一条路径并利用skip-gram模型进行参数更新。

其中第2步构建二叉树的目的是为了方便后续 SkipGram模型的层次softmax算法。

参数更新的流程如下：

一个小结

deepwalk可以说给网络学习方向打开了一个新思路，有很多优点：

• 支持数据稀疏场景
• 支持大规模场景（并行化）

但是仍然存在许多不足：

• 游走是完全随机的，但其实是不符合真实的社交网络的；
• 未考虑有向图、带权图

本文参考资料

[1]

DeepWalk: Online Learning of Social Representations: https://arxiv.org/abs/1403.6652

- END -

说个正事哈


由于微信平台算法改版，公号内容将不再以时间排序展示，如果大家想第一时间看到我们的推送，强烈建议星标我们和给我们多点点【在看】。星标具体步骤为：
（1）点击页面最上方"AINLP"，进入公众号主页。
（2）点击右上角的小点点，在弹出页面点击“设为星标”，就可以啦。
感谢支持，比心。

欢迎加入图神经网络交流群
进群请添加AINLP小助手微信 AINLPer（id: ainlper)，备注GNN
推荐阅读
这个NLP工具，玩得根本停不下来
征稿启示| 200元稿费+5000DBC（价值20个小时GPU算力）
完结撒花！李宏毅老师深度学习与人类语言处理课程视频及课件（附下载）
从数据到模型，你可能需要1篇详实的pytorch踩坑指南
如何让Bert在finetune小数据集时更“稳”一点
模型压缩实践系列之——bert-of-theseus，一个非常亲民的bert压缩方法
文本自动摘要任务的“不完全”心得总结番外篇——submodular函数优化
Node2Vec 论文+代码笔记
模型压缩实践收尾篇——模型蒸馏以及其他一些技巧实践小结
中文命名实体识别工具（NER）哪家强？
学自然语言处理，其实更应该学好英语
斯坦福大学NLP组Python深度学习自然语言处理工具Stanza试用
关于AINLP
AINLP 是一个有趣有AI的自然语言处理社区，专注于 AI、NLP、机器学习、深度学习、推荐算法等相关技术的分享，主题包括文本摘要、智能问答、聊天机器人、机器翻译、自动生成、知识图谱、预训练模型、推荐系统、计算广告、招聘信息、求职经验分享等，欢迎关注！加技术交流群请添加AINLPer(id：ainlper)，备注工作/研究方向+加群目的。

阅读至此了，分享、点赞、在看三选一吧🙏