LINE

ryluo 2020-06-30 20:59:30

解决的问题

在LINE之前的很多Graph Embedding的算法无法直接应用于现实生活中存在的超大规模的节点的Embedding。LINE算法可以用来处理任何类型的信息网络数据,包括有向的、无向的,甚至是加权的图数据。


创新点分析:

  1. 提出了一种新的目标函数,使用节点的一阶近近似和二阶近似保持了网络的局部和全局结构
  2. 提出了一种边采样算法,用来解决在该问题中随机梯度下降不稳定的问题。


算法细节:

与DeepWalk的区别:

DeepWalk更关注的是节点之间更高阶相似度。

LINE更关注的是节点之间一阶和二阶的相似度。


image-20200701153408241

一阶近似

如果两个节点$v_i,v_j$有直连边连接,那么边的权重$W_{i,j}$就是这两个节点的形似度。如果两个节点没有直连的边,那么这两个节点的相似度为0。

定义节点$v_i,v_j$的联合概率分布,$u_i$是节点$v_i$的向量表示

上述的概率分布实质上是两个向量的内积然后将内积带入到sigmoid函数中得到一个概率分布,而$v_i,v_j$的经验概率分布定义为$\hat{p_1} = \frac{w_{ij}}{W}$,其中$W=\sum_{(i,j)\in E}w_{ij}$,为了保持一阶相似性,优化的目标函数为:

也即,为了保持一阶相似性就应该最小化两个概率分布函数,可以使用KL散度来度量两个分布的距离,所以一阶相似度的优化函数可以表示为:

但是一阶相似性只能用于有向图,下面的二阶相似度可以可以用于有向图和无向图


二阶近似

令$p_u=(w_{u,1},…w_{u,|V|})$表示的是定点u与所有其他节点的一阶相似度,则节点u与v的二阶相似度由$p_u,p_v$表示,如果u与v不存在相同的邻居节点,那么这两个节点的二阶相似度为0。(本质上就是看两个节点的邻居节点是否存在交集,若不存在交集,那么相似度为0,否则通过两个节点的交集去计算两个节点的二阶相似度)

在计算节点之间二阶相似度的时候每个节点都有两个向量表示,分别是该节点本身的向量表示和以该节点为上下文时的向量表示,分别用$u_i$和$u_i^{‘}$表示,对于任何一个有向边$(i,j)$,在节点$v_i$已知的条件下生成$v_j$的条件概率为:

其中$|V|$表示的是节点$v_i$所有的上下文向量。为了保持二阶相似性,与保持一阶相似性一样使用两个分布的KL散度来表示目标函数,

其中$\lambda_i$表示的是$v_i$的重要程度,可以通过节点的度或者PageRank得到,其中$\hat{p_2}(\cdot|v_i)$定义为$\hat{p_2}(v_j|v_i)=\frac{w_{i,j}}{d_i}$其中$w_{i,j}$表示的是边$(i,j)$的权重,$d_i$表示的是节点$i$的出度,对于带权图,$d_i=\sum_{k\in N(I)}W_{ik}$,可以形象的理解为,对于无权图节点的二阶经验概率表示的是边的算术平均,而有权图表示的是边的加权平均。将上述中的$\lambda_i=d_i$并使用KL散度可以得到二阶相似度的目标函数为:

模型优化

negativa sampling

通过$p_2(v_j|v_i)=\frac{exp(u_j^T\cdot u_i)}{\sum_{k=1}^{|V|}exp(u_k^T\cdot u_i)}$可以看出,在计算$p_2$时需要遍历所有的节点,这个计算代价是非常大的,所以这里采用负采样的方法来优化该函数,优化的函数如下:

其中$\delta(x) = (1 + exp(-x))$是sigmoid函数。上述公式中的第一项是对当前边$(i,j)$的建模,第二项表示的是负采样的边,K表示的是边的数量,并且$P_n(v) \propto d_v^{3/4}$,其中$d_v$表示的节点的出度。

eage sampling

对$p_2$求导可得:

这个式子中的$w_{ij}$如果方差比较大,那么模型在优化的时候梯度下降就会非常的不稳定。而$w_{ij}$在实际的应用中很多情况下都是不稳定的,比如次的共现,有些词之间出现的非常多,但是有些词之间出现的次数就非常少,所以此时出现多的权重就会非常大而出现少的权重会非常的小。在这种情况下,模型收敛是比较困难的,因为学习率的设置比较困难。作者为了解决这个问题提出了边采样。

当边之间都是平等的没有权重的说法,那么就不会出现上述的问题,作者提出了,使用边的权重对边进行采样,采样得到的边的权重是一样的,这样问题就转化成了如何通过权重来进行采样,文中使用的采样方法是Alias算法,该采样算法是一种时间复杂度为O(1)的离散时间抽样算法。

Alias采样方法可以参考:

https://blog.csdn.net/haolexiao/article/details/65157026

https://zhuanlan.zhihu.com/p/54867139