LINE: Large-scale Information Network Embedding

发表于 2018/01/12 更新于 2024/01/27

作者 lipixun 11 分钟阅读

简介

本文提出了一种名为LINE的算法来计算图中的顶点的向量表示。关于图的顶点的向量表示上一篇DeepWalk: Online Learning of Social Representations以及写的比较详细了，这一篇主要会集中在LINE这个算法上。

与上一篇DeepWalk不同LINE具有更加直观的建模目标，其尝试学习一组顶点的向量表达使得这些向量之间的内积经过变换之后可以拟合两者的一阶（first order）连接概率和二阶（second order）连接概率

方法

KL散度

在介绍算法之前首先需要介绍一些KL散度，贴一段维基百科的说明：

相对熵（relative entropy）又称为KL散度（Kullback–Leibler divergence，简称KLD）[1]，信息散度（information divergence），信息增益（information gain）。 KL散度是两个概率分布P和Q差别的非对称性的度量。 KL散度是用来度量使用基于Q的编码来编码来自P的样本平均所需的额外的位元数。典型情况下，P表示数据的真实分布，Q表示数据的理论分布，模型分布，或P的近似分布。

GAN的诸多改进中有一项很重要的就是应用KL散度来优化生成器和鉴别器，不过这就是后话了以后有机会写一写。

KL散度的形式化定义如下：

离散分布：$D_{{{\mathrm {KL}}}}(P\|Q)=\sum _{i}P(i)\ln {\frac {P(i)}{Q(i)}}$

连续分布：$D_{{{\mathrm {KL}}}}(P\|Q)=\int _{{-\infty }}^{\infty }p(x)\ln {\frac {p(x)}{q(x)}}\,{{\rm {d}}}x$

一些KL散度的特性：

非负：$D_{{{\mathrm {KL}}}}(P\|Q)\geq 0$ 其中当P与Q处处相等时为0

非对称：$D_{{{\mathrm {KL}}}}(P\|Q)\neq D_{{{\mathrm {KL}}}}(Q\|P)$

由于非对称性，KL散度并不能作为通常意义上的距离度量来看待或者在用作这类用途时需要考虑计算方法。

KL散度与信息论中的各种信息量都有换算关系，我认为比较重要的是交叉熵（常用于分类算法的损失函数）和KL散度的关系：

${\mathrm {H}}(p,q)=E_{p}[-\log q]={\mathrm {H}}(p)+D_{{{\mathrm {KL}}}}(p\|q)$

通过这个关系也可以看出KL散度的非对称性。

注：以下使用的数学符号较原文有少许变化

一阶连接概率损失

$V_i, V_j$一阶连接概率 - 可以理解为把图中所有边看做一个集合，随机从这个集合中取出一条边，那么这条边是$E_{i,j}$的概率，形式化表达如下：

求解目标：$P(V_i, V_j) = \frac{1}{1 + exp(U_i \cdot U_j)}$ 实际上是一个sigmoid函数
真实概率：$Q(V_i, V_j) = \frac{w_{ij}}{W}$其中$W = \sum_{i,j}^Vw_{ij}$

应用P和Q的KL散度结果作为损失函数，当$D(Q

P)$为0时两个分布完全一致：

$O_1 = d(Q, P) = \sum_{ij} \frac {w_{ij}} {W} ln \frac {w_{ij}} {W * P(V_i, V_j)} = - \sum_{ij} \frac {w_{ij}} {W} ln P(V_i, V_j) + \sum_{ij} \frac {w_{ij}} {W} ln \frac {w_{ij}} {W}$

上式中的$W$以及第二个求和项在给定一个图的情况下都是常量，因此在计算损失时可以省略，所以省略之后的损失函数是：

$O_1 = - \sum_{ij} w_{ij} ln P(V_i, V_j)$

因此在使用一阶连接概率损失的情况下，既是学习一组向量表达来使得$O_1$最小。

二阶连接概率损失

$V_i, V_j$二阶连接概率相比于一阶连接概率要绕一些，。需要开动一下想象力。首先引入一个新的向量$U_i$，该向量期望去表示所有连接到节点i的所有节点的信息，那么$V_i \cdot U_i$相当于表示了节点i与所有与i相连的节点之间的度量信息，同时$V_i \cdot U_j$表示了节点i与所有与节点j相连的节点之间的度量信息，因此这个度量考虑了二阶关联信息。

求解目标：$P(U_j | V_i) = \frac {exp(U_j * V_i)} {\sum_{k=1}^V exp(U_k \cdot V_i)}$ 看起来是不是很像softmax函数？
真实概率：$Q(U_j | V_i) = \frac {w_{ij}} {d_i}$ 其中$d_i$表示节点i的出度（加权出度）。

应用P和Q的KL散度结果作为损失函数，当$D(Q

P)$为0时两个分布完全一致：

$O_2 = - \sum_{ij} w_{ij} ln P(U_j | V_i)$ 化简过程同上省略（给定一个图时$d_i$是一个常量可以省略）。

需要明确的是与一阶连接概率损失不同，二阶连接概率损失会给每个节点计算出两个向量$V$和$U$，所以这里留下了一个坑就是这两个向量如何同时使用？直接拼接在一起是一个方法但是明显不是非常的合理，在后续的优化章节里我会尝试提出几个方法。

负采样

无论是$O_1$还是$O_2$可以看到每计算一个节点的损失都要扫描一遍所有的节点，这样做是非常不划算的，因为对于一个特定的节点其所连接的节点数量是非常有限的，因此一个常见的优化就是对负标签进行采样。

训练

训练这两个模型可以应用各种梯度下降方法了，这里就不赘述了。

优化

本节会提出几种优化方法，包括论文中提到的优化方法以及我自己扩展的一些方法。

边采样

当图是一个加权图的时候，根据以上损失函数求得的导数会乘上权重。如果权重的分布非常的分散（方差非常大），那么存在梯度爆炸的可能性。一种通用的方法是去Clip梯度，论文中提出了另外一种方法就是对边按照权重进行采样。

按照边的权重进行采样，然后采样之后的边的权重全部按照1来计算，就避免了梯度爆炸的问题。所以训练过程变成：

  
for 迭代次数
  a. 按照权重换算的概率抽样一条边
  b. 按照同样的概率抽样K个负边
  c. 计算损失值以及梯度并更新网络

原文中提到了一个优化过的抽样方法A. Q. Li, A. Ahmed, S. Ravi, and A. J. Smola. Reducing the sampling complexity of topic models. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 891–900. ACM, 2014.之前没有了解过，打算读一读之后再写一篇文章。

二阶连接概率损失-改进

考虑一种简单的情况，如果我们拟合的是两个节点之间相对的连接概率，那么可以使用以下简单形式：

$P(V_i, V_j) = \frac {1} {1 + exp(V_i \cdot V_j)}$
$Q(V_i, V_j) = \frac {\sum_{k} w_{ik} + w_{jk}} {d_i + d_j} $其中$d_i = \sum_k w_{ik}$

那么$V_i$其实可以理解为节点i的二阶向量，同样应用KL散度来训练这个目标。但是这个方法就完全丢失了一阶信息，那么有没有办法同时将一阶和二阶的信息压缩到一个向量里尼？

我个人的判断是通过直接训练一个向量同时具有一阶和二阶信息是不太容易的，这需要去很好的建模这两个向量相乘的结果的意义。另一种方法是使用和原文类似的方法分别得到一阶和二阶向量，然后再增加一个两个向量的加权和作为新的向量使其同时具有一阶与二阶的信息，但是这个向量的学习目标就不容易确定了。

另一种方法就是保留原始的一阶与二阶的向量，在特定目标的网络中（譬如分类）同时输入这两个向量。这个方法在工程上我认为是靠谱的，但是如果期望从二阶扩展到更高阶（譬如无穷阶）的向量这一系列方法很难扩展，但是我相信存在一种可以推广到无穷阶的方法的。

论文快读

ml paper recommendation

本文由作者按照 CC BY 4.0 进行授权

简介

方法

KL散度

一阶连接概率损失

二阶连接概率损失

负采样

训练

优化

边采样

二阶连接概率损失-改进

热门标签