会员服务 ·

Node2Vec: 可扩展的网络特征学习

2020 年 11 月 9 日 AINLP

在阿里巴巴电商推荐之十亿级商品embedding中, 我们介绍了如何利用用户的操作序列来为每个商品学习Embedding，今天我们就详细的介绍这个图结构特征学习的算法: Node2Vec。

Node2Vec[1]有3400+的引用，是一篇非常经典的论文，发表在KDD 2016上。

问题提出

给定一个图结构，为每个节点学习embedding，使之能够借助深度学习的东风在图上的各种问题中有所提升。

作为一个图结构，直接利用监督学习的方法去进行学习是比较难的，因为这样做需要提取特征，而图结构上提取特征比较困难；即便可以，也会导致这样的方法是受限于具体任务的，无法通用。

问题建模

首先，定义G=(V,E)为一个网络，V是节点集合，E是边集合。我们的目标是学习一个函数f，使得V中的每个节点都能映射到一个d维向量上。

对于每个节点u，定义N_S(u)为这个节点的邻居节点集合。

在建模上，效仿skip-gram的操作，skip-gram是语言模型学习的一种方式，即对于一句话A B C D E，对于句子中的每个词，去预测周边的词语。

同理，对于图中的每个节点，去预测它的邻居。公式如下：

同时，做出两个假设:

节点之间相互独立，从而，预测节点集合就可以变成预测每个节点然后乘起来：

节点之间相互对称，即对于A,B的一个连接来说，A对B的作用和B对A的作用是对称的，所以，可以用一些对称函数来计算节点embedding之间的关系，这里采用的是内积，同时做了归一化:

基于这两个假设，最后的损失函数是：

其中，Z_u的计算如下:

损失函数有了，但是skip-gram是在序列上去训练的，而网络不是序列。所以为了把网络变成序列，这里采用了一些随机采样的方法对网络进行遍历。

网络遍历

说起网络遍历，大家有计算机基础的恐怕直接就能想到DFS和BFS，即深度优先搜索和宽度优先搜索。

如下图所示，红色箭头代表的是宽度优先，而蓝色则是深度优先。

但大家细想一下，如果采用BFS和DFS中的一种的话，会有什么后果？

如果是BFS，那么就会导致，有相似网络结构的节点会有相似的embedding，强调的是结构性。
如果是DFS，就会导致，互相连接的节点会有相似的embedding，强调的是连接性。

显然，连接性和结构性都是我们需要的，所以我们想要的是BFS和DFS之间的一种遍历方法。

网络遍历策略

为了得到折中的遍历方法，提出了随机游走的策略。

π_vx代表的是没有归一化的转移概率，Z是归一化常数。

为了防止一个节点被经常重复访问到，这里采用了二阶的权重策略。

对于节点x和它的上一个节点t，x要转移到的目标节点的权重π_vx由alpha来决定，如果节点是t，那么概率为1/p，如果节点到t的距离是1，那么权重就为1，如果节点到t的距离是2，那么概率为1/q。如下图所示:

这里p被称为Return Parameter，q被称为In-out Parameter。如果q>1，那么算法倾向于BFS，反之，倾向于DFS。如果p>1，那么倾向于不重复节点，反之，则倾向于返回源节点。

边的embedding

在得到的节点的embedding之后，可以通过对一条边的两个节点的embedding做操作得到边的embedding。可以采用的操作如下:

node2vec

由上面的介绍，可以得到node2vec的算法:

在上面的算法中，node2vecWalk用来得到随机序列，其中AliasSample用来计算概率并采样。

在得到序列后，使用随机梯度下降来进行学习，这个学习就类似skip-gram了。

实验

首先，在一个小数据集上做了一个可视化的实验，学习到的embedding用K-means进行了聚类，聚类后相同类别的embedding有同样的颜色。

其中上图中的上半部分，参数为p=1, q=0.5，即倾向于BFS，所以学到的类别更强调连接性。下半部分，参数为p=1, q=2，倾向于DFS，学到的类别更强调结构性。

其次，在两个任务上对生成的embedding进行了验证:

node class prediction: 预测节点属于哪一类。
edge prediction: 预测两个节点间该不该有边。

对于分类任务，结果如下，可以看到，node2vec比其他方法强很多，DeepWalk算是比较接近的。

而对于边预测来说，结果如下，可以看到node2vec和DeepWalk两个一档，比其他方法强很多；而node2vec也比DeepWalk强一些。

总结与思考

总体观感，这篇论文非常巧妙，利用了skip-gram的方式来训练embedding，提出的随机游走的策略兼容了DFS和BFS两家之长，得到的效果也很赞。

我能naively的想到的可以改进的点就是动态调整p,q参数，使用更deep的网络结构来进行学习等。

参考文献

[1]. Grover, Aditya, and Jure Leskovec. "node2vec: Scalable feature learning for networks." Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining. 2016.

由于微信平台算法改版，公号内容将不再以时间排序展示，如果大家想第一时间看到我们的推送，强烈建议星标我们和给我们多点点【在看】。星标具体步骤为：

（1）点击页面最上方"AINLP"，进入公众号主页。

（2）点击右上角的小点点，在弹出页面点击“设为星标”，就可以啦。

感谢支持，比心。

欢迎加入AINLP技术交流群

进群请添加AINLP小助手微信 AINLPer（id: ainlper)，备注NLP技术交流

推荐阅读

这个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)，备注工作/研究方向+加群目的。