LINE：不得不看的大规模信息网络嵌入

2020 年 11 月 10 日 AINLP

NewBeeNLP原创出品

作者 | kaiyuan

和DeepWalk一样，今天介绍的论文同样是做网络嵌入表示的，但还是有很大区别的。关于DeepWalk，我们已经在之前文章介绍，戳：DeepWalk：图网络与NLP的巧妙融合

论文来自2015年微软，

论文：LINE: Large-scale Information Network Embedding
链接：https://arxiv.org/abs/1503.03578
源码：https://github.com/tangjianpku/LINE

从论文标题就可以看出，文章主打大规模图网络。当时大多数的嵌入表示研究在小型图网络上表现非常不错，但是当网络规模扩展到百万、百亿级别时，就会显得不尽人意。此外，适用场景也比较有限，无法应用到有向或者带权重图中。为此，本文提出了一种新的网络向量嵌入模型LINE，以解决上述等问题。

先验知识

在我们介绍模型之前，以如下示例先来了解一下相关概念定义。

一阶相似性

一阶相似性定义为两个顶点和之间的邻近度，用该边的权重表示，如果两个顶点之间没有边，那么它们的一阶相似性为0。这个概念是用于模型刻画局部信息的。

如上图，一阶相似性的大小就可以用链接线的粗细来表示。

二阶相似性

在真实场景中，大规模图中有链接的结点相对少，因此如果只用上述一阶相似性来建模是不全面的。比如上图中的5和6结点，两者没有链接，但是拥有几乎完全相同的邻居结点，我们可以认为它们的距离应该也是近的。

二阶相似性定义为一对结点的邻居网络结构相似性。类比到NLP中就是上下文的相似性，即经典的『you shall know a word by the company it keeps』。这个概念用于模型刻画全局信息。

KL散度

KL散度是用于衡量两个概率分布相似性的指标，定义为：

表示概率分布和概率分布之间的差异，越小越接近。

LINE模型

一阶相似性的LINE模型

对于两个顶点和，它们之间的相似性可以用向量距离来表示(其中和分别表示对应的向量 )

而实际直观上两个结点的相似度是用链接强度表示，即边的权重，可以表示为，

因此我们的目标函数就是使得和尽可能地相同。论文里使用了上一节介绍的KL散度，

注意，一阶相似度仅适用于无向图。

二阶相似性的LINE模型

二阶相似性模型和word2vec类似，认为中间结点的上下文结点交集越大则越相似。对于每个节点都有两个向量表示：一个是作为中间结点时的表示，以及作为上下文结点时的表示。对于每一条边，由结点生成上下文的概率为：

啊哈！这不就是word2vec计算词向量的公式嘛！

实际直观上两个结点的二阶相似性可以表示为，

其中为边的权重，为结点的出度。最终也是通过KL散度来最小化两个概率分布的差距，

注意，二阶相似度既可用于无向图，也可用于有向图、带权图。

模型优化

二阶相似性的目标函数中，这一项的计算会涉及所有和结点相邻结点的内积，计算量很大。为此作者采用了『负采样』的方式进行优化，其中第一项为正样本的边，第二项为采样的负样本边。

然后，当模型在优化更新过程中，对结点embedding的计算如下，

很明显，当边的权重存在较大的方差时，会导致学习不稳定，无法选择一个合适的学习率。不难想到如果边的权重都相同，这个问题不就解决了。于是一个简单的做法是将权重为的边拆分成 w 条binary edge，但是如果w很大则会很费存储空间。

一种更合理的思路是对边进行采样，采样概率正比于边的权重，然后把被采样到的边认为是binary edge处理。

思考

实验部分就略过了，感兴趣的小伙伴可以自行研究~

针对实际应用，作者提出了两个思考。

『孤岛』结点

原文中为『low degree vertices』，指的是拥有较少邻居结点的结点。这样一来，就很难学习到其向量表示，作者的建议是可以考虑邻居的邻居结点，即多采样几跳结点，丰富信息表示。

『新来』结点

对于一个新来的结点，如果它和已知的结点有链接关系，那么可以来优化下面任意一个目标函数，

并且保持原有已知节点的embedding不变，更新新来节点的embdding。

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

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