论文标题: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之间有很高的二阶相似性:
举例
大规模图embedding学习的优化问题很具有挑战性,直接应用随机梯度下降法是有问题的,这是因为在很多图中边是加权的,而且权重具有很高的方差。比如一个词共现网络中,权重数值从1到几十万不等,这些权重在优化时都要与梯度相乘,这就造成了梯度爆炸。为了解决这个问题,我们提出了一种边采样(edge-sampling)方法,根据边的权重作为概率来采样,这样就可以将加权图当做binary的图来处理。
二、问题定义
- 信息网络
三、方法
LINE具有以下三个特点:
①能够保留节点之间的一阶相似性和二阶相似性;
②能够处理大规模图;
③能够处理任意类型边的图。
- 模型
- LINE与一阶相似性
- LINE与二阶相似性
对于有向图和无向图,都存在二阶相似性。给定一个网络,不失一般性,我们可以认为它是有向图(无向图也可以认为两个相反方向相同权重有向图的合并)。二阶相似性假设共享很多连接的节点是相似的。在这种假设下,每个节点被看做其他节点的“上下文”,如果两个节点具有相同的上下文分布的话,它们就应该是相似的。因此,每个节点扮演两种角色:
①节点本身;
②其他节点的上下文。
- 一阶与二阶相似性的结合
在本文中采用的结合一阶与二阶相似性训练结果的方法是首先单独按照上面一阶与二阶相似性的方法进行训练,然后将得到的对应的词向量拼接起来。本文没有提出联合训练的方法。
- 模型的优化
Alias table method:【数学】时间复杂度O(1)的离散采样算法—— Alias method/别名采样方法
- 讨论
该部分讨论了LINE模型的几个实际问题。
- 低度节点
四、实验
- 数据集
在语言网络、社交网络、引用网络上进行实验,这些数据集覆盖了各种类型的网络:
数据集
- 结果
在各个数据集上的实验结果如下:
word analogy on Wikipedia data
page classification on Wikipedia data set
multi-label classification on the Flickr network
multi-label classification on the Youtube network
multi-label classification on DBLP(AuthorCitation) network
multi-label classification on DBLP(PaperCitation) network
- 可视化
可视化
- 网络稀疏性
应对稀疏网络结构:
网络稀疏性
- 参数敏感性
超参数的影响:
参数敏感性
- 并行化
多线程训练的影响:
多线程加速