LINE 算法 主页                                            博客   留言 

我们已经介绍了Deepwalk方法和Node2Vec方法。接下来,我们将介绍一种应用在大型网络中的Embedding技术:LINE。该方法将first-order相似性和second-order相似性结合,来获取更丰富的图表示结果。我们接下来将详细说明。

First-order 与 Second-order

我们以图1为例举例说明first-order 与 second-order。其中线的粗细代表着权重的大小,我们可以看到,由于节点6与节点7直接相连,且有着较大的权值,因此它们的first-order相似性较高。同时,虽然节点5与节点6没有直接相连,但它们的有着共同的邻接节点,因此它们的embedding理应有着相近的距离。因此这就是我们说的second-order相似性。

图1 first-order 与 second-order的说明。

First-order相似性定义

First-order是针对每个无向边进行建模,首先,我们给出节点转移的概率分布

\[p_1(v_i,v_j)=\frac{1}{1+exp(-u_i^T.u_j)}\]

其中$u_i$和 $u_j$分别为节点$i$ 和节点$j$的embedding向量表示,同时我们依据边的权值,也可得经验分布

\[p_1'(i,j) = \frac{w_{ij}}{W} \\ W = \sum_{i,j\in E} w_{ij}\]

其中$W$为图中边的权值之和。为了保证first-order的相似性,我们需要将经验分布​与概率分布保持相似,因此我们使用KL散度来衡量两种分布的相似性。我们去掉常数项后,得到的损失函数如下:

\[L_1 = -\sum_{(i,j)\in E} w_{ij}log(p_1(v_i,v_j))\]

因此只要最小化$L_1$,我们即可保证图中节点embedding的First-order相似性。

Second-order相似性定义

second-order既适用有向图也适用于无向图。我们首先定义节点转移的概率分布:

\[p_2(v_j|v_i) = \frac{exp(u_j^{'T}.u_i)}{\sum_{k=1}^{|V|} exp(u_k^{'T}.u_i)}\]

其中$u_i$为节点$i$的embedding向量,$u’_j$为节点$j$的上下文向量。$|V|$为图中的节点总数或者上下文节点的数量。

同时我们给出second-order 的经验分布定义:

\[p'_2(v_j||v_i) = \frac{w_{ij}}{d_i}\\ d_i = \sum_{k\in N(i)}w_{ik}\]

其中$d_i$为节点$i$的出度,$N(i)$为节点$i$的邻近节点。为了保证second-order的相似性,我们需要将经验分布概率分布保持相似,因此我们使用KL散度来衡量两种分布的相似性。在去掉常数项和进行一系列近似后,我们得到的损失函数如下:

\[L_2 = -\sum_{(i,j)\in E}w_{ij}log(p_2(v_j||v_i))\]

在论文中,作者分别训练了first-order相似性和second-order相似性的模型,然后将两种模型的表示结合起来。

LINE实现细节

由于目标损失函数$L2$中的softmax需要遍历所有节点,在大型的图结构中,需要耗费较多的计算资源。 因此,同word2vec算法,我们用负采样来对训练速度进行优化,对于边$(i,j)$,我们的损失函数为:

\[log\ \sigma(u'^{T}_{j}.u_i) + \sum_{i=1}^{K}E_{v_n \sim P_n(v)}[log \ \sigma(-u'^T_n . u_i)]\]

其中$P_n(v)$(采样概率)与节点v的$d_v^{3/4}$ 成正比。由于参数的稀疏性,我们采用异步随机梯度下降的方法进行参数更新(ASGD)。其中参数的更新过程中,梯度与边的权值相关。在实际应用过程中,边的权值方差较大,因此很难找到一个合适的学习率,来保证每个边的参数更新不会出现梯度消失或者梯度爆炸。论文中采用的方法为:将每个边的采样概率与权值成正比,并将采样过后的原始边视为权值为1的二元边。其中对于加权采样问题,作者采用了Alias算法。

如果图中有新加入的顶点$i$,且该顶点与其他的顶点有相连,我们只需要固定其他顶点的参数,专注于优化下列两个损失函数之一即可:

\[-\sum_{j\in N(i)} w_{ij}log(p_1(v_i,v_j)) ,or-\sum_{j\in N(i)}w_{ij}log(p_2(v_j||v_i))\]

总结

总的来说,LINE同时考虑到了节点之间的first-order和second-order相似性,并可适用于各种类型的网络和大型网络。但一些顶点由于其邻接点少,导致embedding向量的学习不充分,对高阶信息的利用不足,因此,这也是接下来的改进方向。

参考资料

[1]: https://zhuanlan.zhihu.com/p/56478167

[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.

[3]:https://mp.weixin.qq.com/s/4_dOPQonYrJDlMQw-XOwxQ