《LINE:Large-scale Information Network Embedding》 ---论文笔记

LINE模型是微软唐建老师提出的一个模型发表在了WWW‘15上,LINE模型适用于大规模信息网络嵌入(Large-scale Information Network Embedding),对模型的类别(有向图、无向图、是否带权等)不作限制,论文同时提出了一种解决经典SGD限制的边缘采样算法,可以完成更有效的推理计算。

1、Introduction

论文简介比较长,首先指出了对于大规模网络,现有的一些网络表示学习算法需要复杂的计算量,而最近有关大规模网络的一些方法要么使用间接的方式降低计算复杂度,要么缺少明确的目标函数(DeepWlk)。然后提出本文的模型:LINE,模型定义了两种相似性关系,包括一阶相似性(the first-order proximity)二阶相似性(the second-order proximity)。一阶相似性定义为网络中的节点连接关系(局部特征),二阶相似性作为一阶相似性的补充,定义为不直接相连的节点的共同邻居节点(全局特征)。

上图中,因为节点6和节点7直接相连,而且连接边的权重值很大(线很粗),所以节点6和节点7之间存在很强的一阶相似性,它们在嵌入空间中的表示应该很接近。节点5和节点6之间虽然没有直接连接,但是由于它们有很多更同的邻居节点(阴影),所以节点5和节点6之间存在二阶相似性,它们在嵌入空间中的表示也应该很接近。

因为网络节点之间的权重不同,边上的权重值通常有很大的方差,所以传统的SGD算法会导致梯度爆炸。论文提出了一种边采样的方法来解决该问题,根据边权重的概率分布进行边采样,然后使用采样到的边进行参数更新。

2、LINE
2.1、一阶相似性(First-order Proximity)

一阶相似性定义为:图中两个相连节点$(u,v)$的连接边上的权重$w_{uv}$,如果节点之间没有连接,一阶相似性为0。一阶相似性是网络中局部点对的相似度,在真实网路中,有连接的节点很少,因此只用一阶相似性刻画网络结构是不完善的。

对于每条无向边$(i,j)$,节点$v_i$和节点$v_j$之间的联合概率分布定义为:

经验概率分布可以定义为:$\widehat{p}_(i,j)=\frac{w_{ij}}{W}$,其中$\vec{u_i}\in{R^d}$是节点$v_i$的低维度特征向量表示,$W=\sum_{(i,j)\in{E}}{w_{ij}}$。

为保持其一阶相似性,一种直接的方法是最小化目标函数$O_1=d(\widehat{p}_1(\cdot,\cdot),p_1(\cdot,\cdot))$,其中$d(\cdot,\cdot)$表示两种分布间的距离,论文通过最小化两种分布的KL散度(KL-divergence)来计算它们之间的距离。代入计算,目标函数化简为:

一阶相似性只适用于无向图,通过优化目标函数学习每个节点的特征表示。

2.2、二阶相似性(Second -order Proximity)

二阶相似性是指一对顶点对之间的相似性和它们邻居网络结构之间的相似性是相似的。从数学的角度定义,$p_u=(w_{u,1},……,w_{u,|V|})$表示节点$u$与其他所有节点的一阶相似性,节点$u$和节点$v$之间的二阶相似性定义为$p_u$和$p_v $之间的相似性。如果没有一个节点同时和节点$u$和节点$v$连接,那么它们之间的二阶相似性为0。

二阶相似性既适用于有向图,也适用于无向图,其假设共享许多邻居节点的节点是相似的,每个节点充当两个角色:一个是其本身,一个是其它节点的上下文,定义两个向量:$\vec{u_i}$表示$v_i$作为节点时候的特征表示,$\vec{u_i}’$表示$v_i$作为上下文时候的特征表示。对于每一条有向边$(i,j)$,由节点$v_i$生成上下文$v_j$的概率为:

其中,$|V|$表示节点或上下文的数量,对于每一个节点$v_i$,公式(3)定义了一个条件分布 $p_2(\cdot|v_i)$。同样为了保持其二阶相似性,条件概率分布应该尽可能的与经验分布$\widehat{p}_2(v_j|v_i)=\frac{w_{ij}}{d_i}$接近,通过最小化两者的最小KL散度$O_2=d(\widehat{p}_2(\cdot,\cdot),p_2(\cdot,\cdot))$,优化目标函数:

通过学习$\{\vec{u_i}\}_{i=1…|V|}$和$\{\vec{u_i}’\}_{i=1…|V|}$最下化目标函数,并用于节点的特征表示。

2.3、模型优化

由于目标函数(6)的优化过程非常复杂,因此论文在优化时使用负采样的方法(negative sampling)[1],为每条边定义以下的目标函数:

目标函数使用异步随机梯度下降方法优化,每一步采样小批量的边,然后更新模型参数,如果一条边$(i,j)$被采样到,那么节点$i$的embedding向量$\vec{u_i}$的计算公式如下:

可以看到,计算过程中需要乘以边的权重,这就带来了一个问题:网络中边的权重有很大的方差时,会导致梯度爆炸。因此边采样也需要优化,从初始边采样,然后将其作为二进制边,采样概率和初始边的权重成正比。

3、Experiment

论文在一个语言网络、两个社交网络和两个引用网络上进行实验验证,对比实验包括GF、DeepWalk、LINE-SGD、LINE和LINE(1st+2nnd)几种模型。实验结果不再叙述,详情可以参考论文。

4、Conclusion

论文提出了一个网路嵌入模型LINE,能够用于处理大规模网络,其目标函数既保留了一阶相似性又保留了二阶相似性,同时还提出了一种边采样方法,解决了在带权重边上SGD的限制问题。

5、Summary

个人认为,这边论文的主要亮点有两个:首先,定义出了一阶相似性和二阶相似性,并分别设计了不同的目标函数。其次,论文提出的边采样方法在不影响效率的前提下,解决了带权重边上的随机梯度下降的限制问题。

References

[1] T. Mikolov, I. Sutskever, K. Chen, G. S. Corrado, and J. Dean. Distributed representations of words and phrases and their compositionality. In Advances in Neural Information Processing Systems, pages 3111–3119, 2013

[2] Tang J, Qu M, Wang M, et al. Line: Large-scale information network embedding[C]//Proceedings of the 24th International Conference on World Wide Web. International World Wide Web Conferences Steering Committee, 2015: 1067-1077.

写的还不错?那就来个红包吧!
0%