论文: LINE: Large-scale Information Network Embedding
源码: https://github.com/tangjianpku/LINE

TL; DR

DeepWalk首先使用DFS随机游走方法在图中进行采样，然后使用word2vec在采样的序列中学习图中顶点的低维向量表示。LINE也是一种基于邻域相似假设的方法，只不过与DeepWalk使用DFS构造邻域不同的是，LINE可以看作是一种使用BFS构造邻域的算法，包含一阶相似度和二阶相似度两种定义。LINE可以应用在有向/无向、无权/加权图中。DeepWalk仅能用于无权无向图中。

Model/Algorithm

节点相似度定义

LINE算法对图中顶点的相似度定义如下：

First-order proximity

一阶相似度用于描述图中成对顶点之间的局部相似度。例如，在社交网络中相互交友的人往往有着相似的兴趣;在万维网上相互链接的页面倾向于谈论类似的话题。形式化描述为若uu ,vv 之间存在直连边，则边权wuvw_{uv} 即为两个顶点的相似度，若不存在直连边，则1阶相似度为0。 如上图，顶点6和7之间存在直连边，且边权较大，则认为两者相似且1阶相似度较高，而5和6之间不存在直连边，则两者间1阶相似度为0。

Second-order proximity

由于有些边观察不到等原因，一阶相似度不足以保存网络结构。因此提出共享相似邻居的顶点倾向于彼此相似，即二阶相似度。 例如，在社交网络中，分享相似朋友的人倾向于有相似的兴趣，从而成为朋友; 在词语共现网络中，总是与同一组词语共同出现的词往往具有相似的含义。

优化目标函数定义

First-order proximity Note：一阶相似模型仅能用于无向图中

对于每一条无向边(i,j)(i, j) ，定义顶点viv_i 和vjv_j 之间的联合概率为：

p1(vi,vj)=11+exp⁡(−u⃗iT⋅u⃗j)p_{1}\left(v_{i}, v_{j}\right)=\frac{1}{1+\exp \left(-\vec{u}_{i}^{T} \cdot \vec{u}_{j}\right)}

其中u⃗i\vec{u}_{i}为顶点viv_i的低维向量表示。（可以视为一个内积模型用来计算两个顶点向量间的相似性）。

同时定义一个经验分布：p1^=wijW,W=∑(i,j)∈Ewij\hat{p_{1}}=\frac{w_{i j}}{W}, \quad W=\sum_{(i, j) \in E} w_{i j}。

优化目标为最小化两个分布间的距离：O1=d(p^1(⋅,⋅),p1(⋅,⋅))O_{1}=d\left(\hat{p}_{1}(\cdot, \cdot), p_{1}(\cdot, \cdot)\right)

d(⋅,⋅)d(\cdot, \cdot) 是两个分布的距离，常用的衡量两个概率分布差异的指标为KL散度，使用KL散度并忽略常数项后为

O1=−∑(i,j)∈Ewijlog⁡p1(vi,vj)O_{1}=-\sum_{(i, j) \in E} w_{i j} \log p_{1}\left(v_{i}, v_{j}\right)

Second-order proximity

对于图中每个顶点维护两个embedding向量，一个是该顶点本身的表示向量，一个是该点作为其他顶点的上下文顶点时的表示向量。

对于有向边(i,j)(i, j) ，定义给定顶点viv_i 条件下，产生上下文(邻居)顶点vjv_j 的概率为

p2(vj∣vi)=exp⁡(u⃗jT⋅u⃗i)∑k=1∣V∣exp⁡(u⃗kT⋅u⃗i)p_{2}\left(v_{j} | v_{i}\right)=\frac{\exp \left(\vec{u}_{j}^{T} \cdot \vec{u}_{i}\right)}{\sum_{k=1}^{|V|} \exp \left(\vec{u}_{k}^{T} \cdot \vec{u}_{i}\right)}

其中∣V∣|V| 为上下文顶点的个数。

同时定义经验分布为：p^2(vj∣vi)=wijdi\hat{p}_{2}\left(v_{j} | v_{i}\right)=\frac{w_{i j}}{d_{i}}
其中wijw_{ij}表示边(i,j)(i, j)的边权，did_i为顶点viv_i的出度，对于带权图，di=∑k∈N(i)wikd_i=\sum_{k\in N(i)}w_{ik}。

优化目标为最小化两个分布间的距离:O2=∑i∈Vλid(p^2(⋅∣vi),p2(⋅∣vi))O_{2}=\sum_{i \in V} \lambda_{i} d\left(\hat{p}_{2}\left(\cdot | v_{i}\right), p_{2}\left(\cdot | v_{i}\right)\right)

其中λi\lambda_{i} 为控制节点重要性的因子，可以通过顶点的度数或者PageRank等方法估计得到。

使用KL散度并设λi=di\lambda_i=d_i ，忽略常数项，最终优化函数为

O2=−∑(i,j)∈Ewijlog⁡p2(vj∣vi)O_{2}=-\sum_{(i, j) \in E} w_{i j} \log p_{2}\left(v_{j} | v_{i}\right)

结合一阶相似度和二阶相似度

采用分别训练一阶相似度模型和二阶相似度模型，然后将学习的两个向量表示连接成一个更长的向量。更适合的方法是共同训练一阶相似度和二阶相似度的目标函数，比较复杂，文章中没有实现。

模型优化

负采样 Negative sampling

由于计算二阶相似度时，softmax函数的分母计算需要遍历所有顶点，这是非常低效的，论文采用了负采样优化的技巧，目标函数变为：

log⁡σ(u⃗j′T⋅u⃗i)+∑i=1KEvn∼Pn(v)[log⁡σ(−u⃗n′T⋅u⃗i)]\log \sigma\left(\vec{u}_{j}^{\prime T} \cdot \vec{u}_{i}\right)+\sum_{i=1}^{K} E_{v_{n} \sim P_{n}(v)}\left[\log \sigma\left(-\vec{u}_{n}^{\prime T} \cdot \vec{u}_{i}\right)\right]

其中KK是负边的数量。论文中使用Pn(v)∝dv3/4P_{n}(v) \propto d_{v}^{3 / 4}，其中dvd_v是顶点vv的出度。

边采样 Edge sampling

注意到我们的目标函数在log之前还有一个权重系数wijw_{ij} ，在使用梯度下降方法优化参数时，wijw_{ij} 会直接乘在梯度上。如果图中的边权方差很大，则很难选择一个合适的学习率。若使用较大的学习率那么对于较大的边权可能会引起梯度爆炸，较小的学习率对于较小的边权则会导致梯度过小。

对于上述问题，如果所有边权相同，那么选择一个合适的学习率会变得容易。这里采用了将带权边拆分为等权边的一种方法，假如一个权重为ww 的边，则拆分后为ww 个权重为1的边。这样可以解决学习率选择的问题，但是由于边数的增长，存储的需求也会增加。

另一种方法则是从原始的带权边中进行采样，每条边被采样的概率正比于原始图中边的权重，这样既解决了学习率的问题，又没有带来过多的存储开销。

这里的采样算法使用的是Alias算法，Alias是一种O(1)O(1) 时间复杂度的离散事件抽样算法。可以参考另一篇博客关于数学理论。

FAQ

度数很低的顶点如何处理？
这样的节点的邻居数量非常少，所以很难精确地推断它的表示，特别是基于二阶相似度的方法。解决方案是通过添加更高阶的邻居扩展这些顶点的邻居，例如将节点邻居的邻居作为节点的邻居。LINE中只考虑向每个顶点添加二阶邻居，即邻居的邻居。顶点i与其二阶邻居j之间的权重被测量为：

wij=∑k∈N(i)wikwkjdkw_{i j}=\sum_{k \in N(i)} w_{i k} \frac{w_{k j}}{d_{k}}

新加入的顶点如何处理？
对于新加入图的顶点viv_i ，若该顶点与图中顶点存在边相连，我们只需要固定模型的其他参数，优化如下两个目标之一即可：

−∑j∈N(i)wjilog⁡p1(vj,vi)A或−∑j∈N(i)wjilog⁡p1(vj∣vi)-\sum_{j \in N(i)} w_{j i} \log p_{1}\left(v_{j}, v_{i}\right)_{\mathbb{A}} 或 -\sum_{j \in N(i)} w_{j i} \log p_{1}\left(v_{j} | v_{i}\right)

若不存在边相连，则需要利用一些side information。

Experiments

实验中涉及到的数据集如下：

实验结果如下：

结果可视化如下：

Thoughts

本文提出了一种称为“LINE”的新型node embedding模型，它可以很容易地扩展到具有数百万个顶点和数十亿边缘的网络。它精心设计的目标函数保留了一阶和二阶的相似性，这些相似性是互补的。针对模型提出了一种有效的边抽样方法，解决了加权边缘随机梯度下降的局限性，同时又不影响效率。各种实际网络的实验结果证明了LINE的高效性和有效性。

联系作者