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

2021-12-06 本文已影响0人酷酷的群

论文标题：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的图来处理。

二、问题定义

信息网络

一个网络用 $G=(V,E)$ 来表示。 $E$ 中的每条边 $e=(u,v)$ 都绑定一个权重 $w_{uv}> 0$ 。如果 $G$ 是无向图，那么有 $(u,v)\equiv (v,u)$ 以及 $w_{uv}\equiv w_{vu}$ ；如果 $G$ 是有向图，那么有 $(u,v)\not\equiv (v,u)$ 以及 $w_{uv}\not\equiv w_{vu}$ 。边的权重既可以是binary的也可以是加权的，在本文中不讨论权重为负值的情况。

一阶相似性

对于每条边 $(u,v)$ ， $w_{uv}$ 表明了节点 $u$ 和 $v$ 之间的一阶相似性。如果 $u$ 和 $v$ 之间没有，那么它们的一阶相似性为0。

二阶相似性

节点 $u$ 和 $v$ 之间的二阶相似性是它们之间邻居网络结构的相似性。具体的，用 $p_{u}=\left (w_{u,1},\cdots ,w_{u,|V|}\right )$ 表示 $u$ 和所有节点的一阶相似性。 $u$ 和 $v$ 之间的二阶相似性取决于 $p_{u}$ 和 $p_{v}$ 的相似性，如果没有节点同时与 $u$ 和 $v$ 相连，那么 $u$ 和 $v$ 之间的二阶相似性为0。

大规模信息网络embedding

大规模信息网络embedding的目的是学习一个函数 $f$ 将每个节点 $v\in V$ 映射到低维空间 $\mathbb{R}^{d}$ ： $f_{G}:V\rightarrow \mathbb{R}^{d}$ ，这里 $d\ll |V|$ 。

三、方法

LINE具有以下三个特点：
①能够保留节点之间的一阶相似性和二阶相似性；
②能够处理大规模图；
③能够处理任意类型边的图。

模型

LINE与一阶相似性

对于每个无向边 $(i,j)$ ，定义一个节点 $v_i$ 与 $v_j$ 之间的联合分布如下：

$p_{1}(v_{i},v_{j})=\frac{1}{1+exp(-\vec{u}_{i}^{T}\cdot \vec{u}_{j}^{T})}$

$\vec{u}_{i}\in \mathbb{R}^{d}$ 是节点 $v_i$ 对应的低维向量表示。上式定义了一个 $V\times V$ 空间上的概率分布 $p_{1}(\cdot ,\cdot )$ ，它的经验概率可以定义为 $\hat{p}_{1}(i,j)=\frac {w_{ij}}{W}$ ，这里 $W=\sum _{(i,j)\in E}w_{ij}$ 。LINE的目标是要让概率分布 $p_{1}(\cdot ,\cdot )$ 与权重的经验分布 $\hat{p}_{1}(\cdot ,\cdot )$ 接近。具体的方式是要让两个分布之间的距离越小越好，目标函数表示为：

$O_{1}=d(\hat{p}_{1}(\cdot ,\cdot ),p_{1}(\cdot ,\cdot ))$

$d(\cdot ,\cdot )$ 代表两个分布的距离。这里我们选择KL散度作为这个举例，那么目标函数就变为：

$O_{1}=-\sum _{(i,j)\in E}w_{ij}\: log\: p_{1}(v_{i},v_{j})$

通过找到能够使目标函数最小的 $\left \{\vec{u}_{i}\right \}_{i=1..|V|}$ ，可以在 $d$ 维空间上得到每个节点的表示。注意一阶相似性只对无向图有这个概念，而有向图节点之间不存在一阶相似性。

LINE与二阶相似性

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

对此我们引入两个向量 $\vec{u}_{i}$ 和 $\vec{u}_{i}^{'}$ ， $\vec{u}_{i}$ 是节点 $v_i$ 的表示， $\vec{u}_{i}^{'}$ 是节点 $v_i$ 被当做其他节点上下文时的表示。对于每个有向边 $(i,j)$ ，我们首先定义上下文 $v_j$ 关于节点 $v_i$ 的条件概率：

$p_{2}(v_{j}|v_{i})=\frac{exp(\vec{u}_{j}^{'T}\cdot \vec{u}_{i})}{\sum_{k=1}^{|V|}exp(\vec{u}_{k}^{'T}\cdot \vec{u}_{i})}$

上式定义了一个在所有节点上关于 $v_{i}$ 的条件概率分布 $p_{2}(\cdot |v_{i})$ 。类似的，我们也需要让这个分布与它的经验分布 $\hat{p}_{2}(\cdot |v_{i})$ 尽可能地接近，那么就有目标函数：

$O_{2}=\sum_{i\in V}\lambda _{i}d(\hat{p}_{2}(\cdot |v_{i}),p_{2}(\cdot |v_{i}))$

网络中的节点可能具有不同的重要性，因而每个节点对于损失的贡献不应该是一样的，于是我们引入了 $\lambda _{i}$ 来作为节点 $i$ 的重要性，可以通过节点的度来度量或者使用一些算法比如PageRank。经验分布 $\hat{p}_{2}(\cdot |v_{i})$ 被定义为 $\hat{p}_{2}(v_{j}|v_{i})=\frac{w_{ij}}{d_{i}}$ ， $d_i$ 是节点 $v_i$ 的出度。在本文中设置 $\lambda _{i}=d_{i}$ 。同样使用KL散度来度量分布之间的距离，那么损失函数就成为：

$O_{2}=-\sum _{(i,j)\in E}w_{ij}\: log\: p_{2}(v_{j}|v_{i})$

通过学习 $\left \{\vec{u}_{i}\right \}_{i=1..|V|}$ 和 $\left \{\vec{u}_{i}^{'}\right \}_{i=1..|V|}$ 来最小化这个目标函数，可以在 $d$ 维空间上得到每个节点的表示。

一阶与二阶相似性的结合

在本文中采用的结合一阶与二阶相似性训练结果的方法是首先单独按照上面一阶与二阶相似性的方法进行训练，然后将得到的对应的词向量拼接起来。本文没有提出联合训练的方法。

模型的优化

在上面有关二阶相似性的训练过程中采用了softmax函数来计算 $p_{2}(\cdot |v_{i})$ ，这个过程需要计算分母上的配分函数，由于需要对所有节点进行加和，显然这个过程在计算上是昂贵的。因此采用负采样的方法，也就是从一个噪声分布中为每条边 $(i,j)$ 采样多个负样本，具体的，每条边的损失函数变为：

$log\: \sigma (\vec{u}_{j}^{'T}\cdot \vec{u}_{i})+\sum_{n=1}^{K}E_{v_{n}\sim P_{n}(v)}[log\: \sigma (-\vec{u}_{n}^{'T}\cdot \vec{u}_{i})]$

这里 $\sigma$ 代表sigmoid函数， $K$ 是负样本的数量。上面式子中第一项建模图中可观测的边，第二项建模从噪声分布 $P_{n}(v)$ 中采样出来的负样本。这里的噪声分布中节点 $v$ 的概率 $P_{n}(v)$ 正比于 $d_v$ 的 $3/4$ 次方（这是负采样原论文中的做法），即 $P_{n}(v)\propto d_{v}^{3/4}$ ，也就是说 $v$ 的出度越高，越容易被采样称为负样本。负采样是语言模型中的技术，在这里不做赘述。

对于概率 $p_{1}(\cdot ,\cdot )$ 的计算，如果有 $u_{ik}=\infty ,for\: i=1,\cdots ,|V|\: and\: k=1,\cdots ,d$ ，那么可以轻易使损失函数 $O_1$ 最小，为了避免这种情况，也可以采用上述负采样的策略，只需要将 $\vec{u}_{j}^{'T}$ 这部分替换成 $\vec{u}_{j}^{T}$ ：

$log\: \sigma (\vec{u}_{j}^{T}\cdot \vec{u}_{i})+\sum_{n=1}^{K}E_{v_{n}\sim P_{n}(v)}[log\: \sigma (-\vec{u}_{n}^{T}\cdot \vec{u}_{i})]$

使用异步随机梯度下降（ASGD）来优化上面的目标函数。在每个step，ASGD采样一个mini batch的边并且更新模型的参数。以 $O_2$ 为例，如果一个边 $(i,j)$ 被采样到，那么目标函数 $O_2$ 对节点 $i$ 的embedding向量 $\vec{u}_{i}$ 的梯度（随机实际不会用到这个式子进行更新）为：

$\frac {\partial O_{2}}{\partial \vec{u}_{i}}=w_{ij}\cdot \frac {\partial log\: p_{2}(v_{j}|v_{i})}{\partial \vec{u}_{i}}$

这里面临的一个问题是如果边的权重具有很高的方差（比如词共现网络中有的边权值很大，有的很小），那么学习率的选择就会很困难。为此，本文提出了一种边采样的方法。可以根据边的权重对边进行采样，权重越高的边越有可能被采样出来到mini batch中。不过这样的复杂度为 $O(|E|)$ ，因此本文采用别名表（alias table）采样方法，这样只需要 $O(1)$ 的复杂度。

Alias table method：【数学】时间复杂度O(1)的离散采样算法—— Alias method/别名采样方法

讨论

该部分讨论了LINE模型的几个实际问题。

低度节点

具有很低的度的节点往往很难学习它的表示，尤其是二阶相似性十分依赖上下文节点的数量。一个直观的方法是为这些节点添加更多高阶邻域的节点，也就是邻域的邻域。在本文中我们只采用二阶邻域。节点 $i$ 和他的二阶邻域 $j$ 的权重为：

$w_{ij}=\sum _{k\in N(i)}w_{ik}\frac{w_{kj}}{d_{k}}$

在实际使用时只需要添加 $\left \{j\right \}$ 中与 $i$ 有最大相似性 $w_{ij}$ 的一个子集就好。

新节点

对于一个新到来的节点 $i$ ，如果我们知道它与现有节点的连接关系，那么我们就可以获得它的经验分布 $\hat{p}_{1}(\cdot ,v_{i})$ 和 $\hat{p}_{2}(\cdot |v_{i})$ ，然后固定现有节点的embedding，按照以下目标函数更新新节点的embedding：