Graph Embedding之LINE

LINE(Larg-scale Information Network Embedding)由Jian Tang等于2015年提出的，该方法提出了一种可以应用在任意边类型的大型网络上的节点嵌入算法，并通过考虑first-order proximity（local structure）和second-order proximity（global structure）实现网络嵌入。总体来说，相比较之前的Graph/Network Embedding方法，LINE具有如下好处：

适用于任意类型的网络，这里的任意类型在该文中主要是指边的权重和方向是任意：有向，无向，有权重，无权重。（LINE并没有考虑不同节点类型和边类型下的异构网络，有一定的局限性。也就有了后来针对heterogeneous和homogeneous网络的研究）
LINE提出了一种边采样（edge-sampling）算法来提升和优化目标函数，从而克服了传统的随机梯度下降（stochastic gradient decent）的局限性。

模型描述（Model Description）

在具体介绍LINE算法的详细过程前，还需要了解两个概念：

First-order Proximity在LINE中用于表征local structure，具体反映在网络中就是任意两个顶点之间的距离，即如果两个顶点在图中有一条边，那么这个边上的权重就是这两个顶点之间的First-order Proximity，如果是无权重图，则该First-order Proximity就是1，如果两个顶点之间没有边之间相连，则为0。在现实中的表现就是，如果两个顶点相邻，且权重很大，那么这两个顶点在某种程度上是非常相似的。
Second-order Proximity在LINE中用于表征global structure，其基于一个假设：如果两个顶点共享大部分邻居顶点，那么这两个顶点之间也十分相似。如果两个顶点之间没有共享的邻居顶点，那么这两个顶点的Second-order Proximity为0。

下图直观的展示了First-order Proximity和Second-order Proximity的区别。

Figure 1: A toy example of information network. Edges can be undirected, directed, and/or weighted. Vertex 6 and 7 should be placed closely in the low-dimensional space as they are connected through a strong tie. Vertex 5 and 6 should also be placed closely as they share similar neighbors.

接下来正式介绍LINE的具体过程：

LINE with First-order Proximity

为了表征任意两个顶点之间的First-order Proximity，作者定义了两个顶点之间的联合分布，公式如下：
$\large p_1(v_i,v_j)=\frac{1}{1 + \exp(-\vec{u}_i^T \cdot \vec{u}_j)} \tag{1}$ 其中 $\small \vec{u} \in R^d$ 是顶点 $v_i$ 的低维向量表示，公式（1）定义了一个 $V \times V$ 空间下的概率分布 $\small p(\cdot,\cdot)$ ，它的经验分布可以表示为 $\small \hat{p_1}(i,j)=\frac{w_{ij}}{W}$ ，其中 $\small W=\sum(i,j)\in E^{w_{ij}}$ 。为了保留First-order Proximity，一个最直接的方法就是最小化如下的目标函数：
$\large O_1=d(\hat{p_1}(\cdot,\cdot),p_1(\cdot,\cdot)) \tag{2}$ 其中 $\small d(\cdot, \cdot)$ 表示两个分布之间的距离，作者采用KL-divergence来度量，因此公式（2）可以转化为：
$\large O_1=-\sum_{(i,j)\in E}w_{i,j}\log p_1(v_i,v_j) \tag{3}$ 针对First-order Proximity有一点需要特别注意一下：上述First-order Proximity只适用于不考虑边方向的网络或图，针对有向图并不适用。通过最小化公式(3)，我们可以找到每个顶点最优的 $\small d$ 维向量表示。

LINE with Second-order Proximity

Second-order Proximity既适用于无向图，也适用于有向图。对于一个网络或图，不失一般性，我们均假设其为有向图（无向边可以理解成两条方向相反，权重相同的有向边）。Second-order Proximity假定具有大量相同邻接顶点的两个顶点是相似的，在这种情况下，每个可以看作是一个特定的上下文（context），具有相同或相似上下文分布的顶点被认为是相似的。因此，在这种场景下，每个顶点扮演着两种不同的角色：顶点本身和其他顶点的上下文。基于此，作者提出了两种向量表示 $\small \vec{u}_i$ 和 $\small \vec{u}_i^\prime$ ，其中 $\small \vec{u}_i$ 为顶点 $\small v_i$ 作为顶点时的向量表示，而 $\small \vec{u}_i^\prime$ 为顶点 $\small v_i$ 作为context时的向量表示。对于每个有向边 $\small e_{ij}$ ，作者定义了顶点 $\small v_j$ 作为顶点 $\small v_i$ 的context的条件概率为：
$\large p_2(v_j|v_i)=\frac{\exp(\vec{u}_j^{\prime T} \cdot \vec{u}_i)}{\sum_{k=1}^{|V|} \exp(\vec{u}_k^{\prime T} \cdot \vec{u}_i)} \tag{4}$ 其中 $\small |V|$ 表示顶点 $\small v_i$ 的context的集合大小。公式（4）表示了每个顶点 $\small v_i$ 在其上下文context上的条件概率 $\small p_2(\cdot|v_i)$ ，也就在整个顶点集合上的条件概率，如上所述，如果两个顶点在其上下文上具有相近的分布，那么认为这两个顶点在表示上是相似的。为了保留Second-order Proximity，希望每个顶点在其上下文上的条件分布能最大程度的拟合其经验分布，于是作者针对Second-order Proximity提出了新的目标函数，即最小化下述目标函数：
$\large O_2=\sum_{i\in V} \lambda_id(\hat{p}_2(\cdot | v_i), p_2(\cdot | v_i)) \tag{5}$ 其中 $\small d(\cdot, \cdot)$ 表示两个分布之间的距离，作者同样采用了KL-divergence来度量，另外作者通过引入 $\small \lambda_i$ 来表示不同的顶点在网络或图中的重要性，该值可以通过PageRank等考察顶点重要性的方法来获得。经验分布 $\small \hat{p}_2(\cdot | v_i)$ 可以表示为 $\small \hat{p}_2(v_j | v_i)=\frac{w_{ij}}{d_i}$ ，其中 $\small w_{ij}$ 表示边 $\small e_{ij}$ 的权重， $\small d_i$ 表示顶点 $\small v_i$ 的出度，假设 $\small \lambda_i = d_i$ ，那么目标函数（5）可以优化如下：
$\large O_2=-\sum_{e_{ij}} \log p_2(v_j | v_i) \tag{6}$ 通过最小化目标函数学习 $\small \{ \vec{u}_i\}_{i=1..|V|}$ 和 $\small \{ \vec{u}_i^\prime\}_{i=1..|V|}$ ，我们可以得到每个顶点的 $\small d$ 维向量表示 $\small \vec{u}_i^\prime$

Combine First-order Proximity and Second-order Proximity

为了同事保留顶点的First-order Proximity和Second-order Proximity，作者提出了一种最简单的也被实验证明是有效的方法，即对于同一个顶点分别针对两个目标函数训练两个不同的模型，然后将各自Embedding的结果进行简单的联接（concatenate）即可。当然，作者也提出了在以后的工作中，可以尝试利用目标函数（3）和目标函数（6）进行联合训练以达到embedding的目的。

模型优化（Model Optimization）

学习目标函数（6）的过程的计算量是特别大的，因为它需要在整个数据集上计算其条件分布，特别是当图中的顶点和边的个数特别巨大的时候。为此作者提出了可以采用T. Mikolov提出的负采样方法（Negative Sampling），即根据每条边 $\small e_{ij}$ 的噪声分布进行多条负边采样，以达到降低计算量的目的。于是针对每条边，它明确了优化以下目标函数：
$\large \log \sigma(\vec{u}_j^{\prime T} \cdot \vec{u}_i) + \sum_{i=1}^{K}E_{v_n \widetilde{} P_n(v)[\log \sigma(\vec{u}_j^{\prime T} \cdot \vec{u}_i)]} \tag{7}$ 其中
$\sigma (x) = \frac{1}{1+\exp(-x)}$
是一个 $\small sigmoid$ 函数，公式（7）前半部分用来建模观察到的所有的边，而后办部分用来建模从噪声分布中负采样的边，其中 $\small K$ 表示负采样的边的数目。至于负采样的具体细节，具体可以参考Negative Sampling。
作者通过异步的随机梯度下降算法ASGD（asynchronous stochastic gradient algorithm）来优化公式（7）的学习过程。在每次迭代中，ASGD会随机选择一批边来更新模型的参数。如果一个边 $e_{ij}$ 被选中，那么关于顶点 $\small v_i$ 的嵌入向量 $\small \vec{u}_i$ 的梯度可以通过如下公式计算：
$\large \frac{\partial O_2}{\partial \vec{u}_i}=w_{ij} \cdot \frac{\partial \log p_2(v_j | v_i)}{\partial \vec{u}_i} \tag{8}$ 需要注意的是，这里的梯度需要乘以一个边的权重，如果边的权重有很大的方差的化就会有问题。例如，在一个单词网络中，有些单词之间共现多次(例如，几万次)，而有些单词之间仅共现几次。在这种情况下，梯度的比例是发散的，因此很难去寻找一个合适的学习速度。如果根据权值较小的边选择较大的学习率，则权值较大的边的梯度会发生爆炸；而根据权值较大的边选择较小的学习率，会导致梯度过小，长时间难以收敛。

Optimization via Edge Sampling

解决上述问题最直观的做法就是，如果所有边的权重都一样，那么选择一个合适的学习速率就没有任何问题。因此，一个最简单的处理方法就是将一个加权的边展开成多个二元边。即一个权重为 $\small w$ 的边可以拆分成 $\small w$ 个二元边。这样虽然能解决上述问题，但是又产生了一个新的问题，如此拆分会导致边的规模在原来基础上扩大很多倍，直接导致了内存的需求激增。为了解决这个问题，可以对原始边进行采样，采样概率与原始边的权值成正比，并将采样后的边视为二元边。通过这样的Edge Sampling采样处理，使得总体目标函数保持不变。这样问题就变成了如何根据边的权值对边进行采样。这里用 $\small W=(w_1,w_2, \dots, w_{|E|})$ 表示所有的边的权重序列，首先可以计算所有边的权重之和 $\small w_{sum}=\sum_{i=1}^{|E|}w_i$ ，然后在区间 $\small [0, w_{sum}]$ 范围内随机选择一个数，看这个数随机落在哪个区间 $\small [\sum_{j=0}^{i-1}w_j, \sum_{j=0}^{i}w_j)$ 中。该方法需要 $\small O(|E|)$ 的时间复杂度去抽取一个样本，当边的规模很大时，代价也是很大的。为此，作者使用一种别名表（alias table）的方式根据权重进行采样，当重复从相同的离散分布中采样时，只需要 $\small O(1)$ 的时间。使用别名表进行采样的时间复杂度是 $\small O(1)$ ，而负采样的时间复杂度是 $\small O(d(K + 1))$ ，其中K是负采样的大小。