LINE：大规模信息网络嵌入方法

2022-06-11 160

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： LINE：大规模信息网络嵌入方法

论文标题：LINE: Large-scale Information Network Embedding

论文链接：https://arxiv.org/abs/1503.03578

论文来源：WWW 2015

一、概述

目前已有一些图embedding的方法，这些方法在小规模网络上有不错的效果，然而面对现实世界中的大规模信息网络时是无能为力的，这些网络通常包含几百万个节点和数十亿的边。举例来说，一些方法比如MDS,IsoMap以及拉普拉斯特征图法的复杂度与节点数量呈二次关系。

虽然最近的一些研究提出了一些大规模图的embedding方法，然而这些方法要么使用不是为了网络而设计的间接方法，要么缺少一个特别为图设计的目标函数。本文提出的LINE方法是一个新的大规模图embedding方法，提出了一个专门设计的目标函数，能够学习图的特性，并且提出了一个高效的优化算法，能够有效率地学习数百万节点的embedding向量。 LINE能够处理各种类型的网络，无论是有向的还是无向的，binary的还是加权的。模型优化的目标函数保留了图局部和全局的结构。

通常图的局部结构由图中可观测到的连接（也就是边）来反映，在本文中这被定义为节点之间的一阶相似性（first-order proximity）。我们观察到在现实世界的网络中，一些合理的连接可能是没有被观测到的，换句话说一阶相似性对于保持图的全局结构是不足够的。作为一阶相似性的互补，本文提出了节点之间的二阶相似性（second-order proximity），二阶相似性通过节点的共享邻居来决定，直观地来解释就是拥有共享邻居的节点是更为相似的。在许多现实的例子中可以印证这一点，比如拥有相同社交网络的两个人是很可能有共同的兴趣的，或者两个词如果经常和相同的一些词一起使用，那么这两个词的含义很可能是相似的。如下图所示，节点6,7之间有很高的一阶相似性，5,6之间有很高的二阶相似性：

QQ截图20220612095757.png

举例

大规模图embedding学习的优化问题很具有挑战性，直接应用随机梯度下降法是有问题的，这是因为在很多图中边是加权的，而且权重具有很高的方差。比如一个词共现网络中，权重数值从1到几十万不等，这些权重在优化时都要与梯度相乘，这就造成了梯度爆炸。为了解决这个问题，我们提出了一种边采样（edge-sampling）方法，根据边的权重作为概率来采样，这样就可以将加权图当做binary的图来处理。

二、问题定义

信息网络

QQ截图20220611221142.png

三、方法

LINE具有以下三个特点：

①能够保留节点之间的一阶相似性和二阶相似性；

②能够处理大规模图；

③能够处理任意类型边的图。

模型

LINE与一阶相似性

QQ截图20220611221301.png

QQ截图20220611221339.png

LINE与二阶相似性

对于有向图和无向图，都存在二阶相似性。给定一个网络，不失一般性，我们可以认为它是有向图（无向图也可以认为两个相反方向相同权重有向图的合并）。二阶相似性假设共享很多连接的节点是相似的。在这种假设下，每个节点被看做其他节点的“上下文”，如果两个节点具有相同的上下文分布的话，它们就应该是相似的。因此，每个节点扮演两种角色：

①节点本身；

②其他节点的上下文。

QQ截图20220611221547.png