【论文笔记】LINE：大规模信息网络嵌入

古城微笑少年丶 2021-12-14 03:53 152阅读 0赞

## LINE: Large-scale Information Network Embedding ##

[Arxiv 1503.03578][]

## 三、问题定义 ##

我们使用一阶和二阶邻近度，正式定义了大规模信息网络嵌入问题。 我们首先定义一个信息网络如下：

定义 1（信息网络）：信息网络定义为`G = (V, E)`，其中`V`是顶点集合，每个顶点代表一个数据对象，`E`是顶点之间的边集合，每个边代表两个数据对象之间的关系。每个边`e ∈ E`是有序对`e = (u, v)`并且与权重`w[uv] > 0`相关联，其表示关系的强度。 如果`G`是无向的，我们有`(u, v) ≡ (v, u)`和`w[uv] = w[vu]`；如果`G`是有向的，我们有`(u, v) ≢ (v, u)`和`w[uv] ≢ w[vu]`。

在实践中，信息网络可以是定向的（例如引文网络）或无向的（例如，Facebook 中的用户的社交网络）。边的权重可以是二元的，也可以是任意实数。 请注意，虽然负边权重是可能的，但在本研究中我们只考虑非负权重。 例如，在引文网络和社交网络中，你需要二元值；在不同对象之间的共现网络中，`w[uv]`可以取任何非负值。 一些网络中的权重可能会分散，因为一些对象共同出现很多次，而其他对象可能只共同出现几次。

将信息网络嵌入低维空间在各种应用中都很有用。 要进行嵌入，必须保留网络结构。 第一个直觉是，必须保留局部网络结构，即顶点之间的局部成对邻近度。 我们将局部网络结构定义为顶点之间的一阶邻近度：

定义 2（一阶邻近度）：网络中的一阶邻近度是两个顶点之间的局部成对邻近度。 对于由边`(u, v)`链接的每对顶点，该边上的权重`w[uv]`表示`u`和`v`之间的一阶邻近度。 如果在`u`和`v`之间没有观察到边，则它们的一阶邻近度为 0。

一阶邻近度通常意味着现实世界网络中两个节点的相似性。 例如，在社交网络中彼此成为朋友的人倾向于分享相似的兴趣；在万维网中相互链接的页面倾向于谈论类似的主题。 由于这一重要性，许多现有的图嵌入算法，如 IsoMap，LLE，拉普拉斯特征映射和图分解，目标是保留一阶邻近度。

然而，在现实世界的信息网络中，观察到的链接只占很小的比例，许多其他的链接是缺失的 \[10\]。缺失链接上的一对节点的一阶邻近度为零，即使它们本质上彼此非常相似。 因此，单独的一阶邻近不足以保留网络结构，并且重要的是寻求解决稀疏问题的替代邻近概念。 一种自然的直觉是，共享相似邻居的顶点往往彼此相似。 例如，在社交网络中，分享类似朋友的人往往具有相似的兴趣，从而成为朋友；在词共现网络中，总是与同一组词共同出现的词往往具有相似的含义。 因此，我们定义了二阶邻近度，它补充了一阶邻近度并保留了网络结构。

定义 3（二阶邻近度）：网络中一对顶点`(u, v)`之间的二阶邻近度，是它们的邻域网络结构之间的相似性。 在数学上，让`p[u] = (w[u, 1], … , w[u, |V|])`表示`u`与所有其他顶点的一阶邻近度，然后`u`和`v`之间的二阶邻近度由`p[u]`和`p[v]`之间的相似性确定。如果`u`和`v`没有链接到相同的顶点，则`u`和`v`之间的二阶邻近度为 0。

我们研究了网络嵌入的一阶和二阶邻近度，其定义如下。

定义 4（大规模信息网络嵌入）：给定大型网络`G = (V, E)`，大规模信息网络嵌入的问题，旨在将每个顶点`v ∈ V`在低维空间`R^d`表示，即学习函数`f[G]: V -> R^d`，其中`d << |V|`。 在空间`R^d`中，保留顶点之间的一阶邻近度和二阶邻近度。

接下来，我们介绍一种大规模网络嵌入模型，它保留了一阶和二阶邻近度。

## 四、LINE：大规模信息网络嵌入 ##

用于现实世界信息网络的理想嵌入模型必须满足若干要求：首先，它必须能够保留顶点之间的一阶邻近和二阶邻近度；第二，它必须适用于非常大的网络，比如数百万个顶点和数十亿个边；第三，它可以处理具有任意类型边的网络：有向，无向和/或加权，无权。 在本节中，我们提出了一种新的网络嵌入模型，称为“LINE”，它满足所有这三个要求。

### 4.1 模型描述 ###

我们描述 LINE 模型来分别保留一阶邻近度和二阶邻近度，然后介绍一种组合两个邻近度的简单方法。

#### 一阶邻近度 ####

一阶邻近度是指网络中顶点之间的局部成对邻近度。 为了模拟一阶邻近度，对于每个无向边`(i, j)`，我们定义顶点`v[i]`和`v[j]`之间的联合概率，如下所示：

![aHR0cDovL2xhdGV4LmNvZGVjb2dzLmNvbS9naWYubGF0ZXg][] (1)

其中`u[i] ∈ R^d`是顶点`v[i]`的低维矢量表示。公式（1）定义空间`V×V`上的分布`p(·,·)`，其经验概率可定义为`^p[1](i, j) = w[ij]/W`，其中`W = Σw[ij], (i, j) ∈ E`。 为了保留一阶邻近度，一种直接的方法是最小化以下目标函数：

![aHR0cHM6Ly91c2VyLWdvbGQtY2RuLnhpdHUuaW8vMjAxOS83LzcvMTZiY2MxNzUxYmNhMDEyOA][] (2)

其中`d(·,·)`是两个分布之间的距离。 我们选择最小化两个概率分布的 KL 散度。 用 KL 散度代替`d(·,·)`并省略一些常数，我们得到：

![aHR0cHM6Ly91c2VyLWdvbGQtY2RuLnhpdHUuaW8vMjAxOS83LzcvMTZiY2MxNzUxOTJmM2JiZA][] (3)

请注意，一阶邻近度仅适用于无向图，而不适用于有向图。 通过找到最小化公式（3）中的目标的`{u[i]}, i = 1 .. |V|`，我们可以表示`d`维空间中的每个顶点。

### 二阶邻近度 ###

二阶邻近度适用于有向图和无向图。给定网络，在不失一般性的情况下，我们假设它是有向的（无向边可以被认为是具有相反方向和相等权重的两个有向边）。 二阶邻近度假设共享与其他顶点的许多连接的顶点彼此相似。 在这种情况下，每个顶点也被视为特定的“上下文”，并且假设在“上下文”中具有相似分布的顶点是相似的。 因此，每个顶点扮演两个角色：顶点本身和其他顶点的特定“上下文”。 我们引入两个向量`u[ i]`和`u'[i]`，其中`u[i]`是`v[i]`在被视为顶点时的表示，而`v'[i]`是当`v[ i]`被视为特定“上下文”时的表示。 对于每个有向边`(i, j)`，我们首先将顶点`v[i]`生成“上下文”`v[j]`的概率定义为：

![aHR0cHM6Ly91c2VyLWdvbGQtY2RuLnhpdHUuaW8vMjAxOS83LzcvMTZiY2MxNzUxYmYxMzVkMg][] (4)

![aHR0cHM6Ly91c2VyLWdvbGQtY2RuLnhpdHUuaW8vMjAxOS83LzcvMTZiY2MxNzUxYzRjOTBiMA][] (5)

通过学习使这个目标最小化的`{u[i]}, i = 1 .. |V|`以及`{u'[i]}, i = 1 .. |V|`，我们能够用`d`维向量`u[i]`表示每个顶点`v[i]`。

#### 组合一阶和二阶邻近度 ####

要通过保留一阶和二阶邻近度来嵌入网络，我们在实践中找到的一种简单而有效的方法是训练 LINE 模型，分别保留一阶邻近和二阶邻近度，然后连接由两种方法为每个顶点训练的嵌入向量。结合两种邻近度的更原则性方法，是联合训练目标函数（3）和（6），我们将其留作未来的工作。

### 4.2 模型优化 ###

优化目标（6）在计算上是昂贵的，其在计算条件概率`p[2]`时需要对整个顶点集合求和。 为了解决这个问题，我们采用 \[13\] 中提出的负采样方法，根据每条边`(i, j)`的一些噪声分布采样多个负边。 更具体地说，它为每个边`(i, j)`指定以下目标函数：

![aHR0cDovL2xhdGV4LmNvZGVjb2dzLmNvbS9naWYubGF0ZXg][] (7)

其中`σ(x) = 1 / (1 + exp(-x))`是 sigmoid 函数。 第一项用于模拟观察到的边，第二项用于模拟从噪声分布中提取的负边，K 是负边的数量。 我们设置 \[13\] 中提出的`P[n](v) ∝ d[v]^3/4`，其中`d[v]`是顶点`v`的出度。

对于目标函数（3），存在一个简单的解决方案：`u[ik] = ∞`，对于`i = 1, ..., |V|`和`k = 1, ..., d`。 为了避免这种简单的解决方案，我们仍然可以通过将`u'[j]^T`改为`u[j]^T`来利用负采样方法（7）。

我们采用异步随机梯度算法（ASGD）\[17\] 来优化公式（7）。 在每个步骤中，ASGD 算法对小批量边进行采样，然后更新模型参数。 如果采样边`(i, j)`，则顶点`i`的嵌入向量`u[i]`的梯度为将计算为：

![aHR0cHM6Ly91c2VyLWdvbGQtY2RuLnhpdHUuaW8vMjAxOS83LzcvMTZiY2MxNzU2NzE1NmJjYQ][] (8)

请注意，梯度将乘以边的权重。 当边的权重具有高方差时，这将成为问题。 例如，在单词共现网络中，一些单词共同出现多次（例如，数万次），而一些单词仅共同出现几次。 在这样的网络中，梯度的尺度发散，很难找到良好的学习率。 如果我们根据小权重的边选择较大学习率，大权重的边缘上的梯度将爆炸，并且如果我们根据大权重的边选择较小学习率，梯度将变得太小。

#### 优化 VS 边采样 ####

解决上述问题的直觉是，如果所有边的权重相等（例如，具有二元边的网络），则不存在选择适当学习率的问题。 因此，简单的处理是将加权边展开成多个二元边缘，例如，权重为`w`的边展开成`w`个二元边。 这将解决问题，但会显着增加内存需求，特别是当边的权重非常大时。 为了解决这个问题，可以从原始边采样并将采样边视为二元边，采样概率与原始边权重成正比。 通过这种边采样处理，总体目标函数保持不变。 问题归结为如何根据权重对边采样。

### 4.3 讨论 ###

我们讨论了 LINE 模型的几个实际问题。

低度顶点：一个实际问题是如何精确地嵌入低度顶点。 由于此类节点的邻居数量非常少，因此很难准确地推断其表示，尤其是基于二阶邻近度的方法，这种方法严重依赖于“上下文”的数量。对此的直观解决方案是扩展 这些顶点的邻居通过添加更高阶的邻居，例如邻居的邻居。 在本文中，我们只考虑向每个顶点添加二阶邻居，即邻居的邻居。 顶点`i`与其二阶邻居`j`之间的权重测量为：

![aHR0cHM6Ly91c2VyLWdvbGQtY2RuLnhpdHUuaW8vMjAxOS83LzcvMTZiY2MxNzU2NzYyNDIxNA][]

实际上，人们只能添加顶点`{j}`的子集，它与低度顶点`i`具有最大邻近度。

新顶点：另一个实际问题是如何找到新到达顶点的表示。 对于新的顶点`i`，如果已知其与现有顶点的连接，我们可以在现有顶点上获得经验分布`^p[1](·, v[i])`和`^p[2](·|v[i])`。 根据目标函数公式（3）和（6），为了获得新顶点的嵌入，一种直接的方法是最小化以下任一目标函数。

![aHR0cHM6Ly91c2VyLWdvbGQtY2RuLnhpdHUuaW8vMjAxOS83LzcvMTZiY2MxNzU2N2JjZWIxOA][] (10)

通过更新新顶点的嵌入并保持现有顶点的嵌入。 如果没有观察到新顶点和现有顶点之间的连接，我们必须求助于其他信息，例如顶点的文本信息，并将其作为我们未来的工作。

[Arxiv 1503.03578]: https://arxiv.org/abs/1503.03578
[aHR0cDovL2xhdGV4LmNvZGVjb2dzLmNvbS9naWYubGF0ZXg]: /images/20211213/27b8ad6ea8e74607be54db94fabf63ea.png
[aHR0cHM6Ly91c2VyLWdvbGQtY2RuLnhpdHUuaW8vMjAxOS83LzcvMTZiY2MxNzUxYmNhMDEyOA]: /images/20211213/a8418168b134435e928d6aadf494737f.png
[aHR0cHM6Ly91c2VyLWdvbGQtY2RuLnhpdHUuaW8vMjAxOS83LzcvMTZiY2MxNzUxOTJmM2JiZA]: /images/20211213/b049b982cd7c4150bdfb1b4ba6872ab4.png
[aHR0cHM6Ly91c2VyLWdvbGQtY2RuLnhpdHUuaW8vMjAxOS83LzcvMTZiY2MxNzUxYmYxMzVkMg]: /images/20211213/36e380806cb94f948f6cf2c5dfb5af10.png
[aHR0cHM6Ly91c2VyLWdvbGQtY2RuLnhpdHUuaW8vMjAxOS83LzcvMTZiY2MxNzUxYzRjOTBiMA]: /images/20211213/907062fccfd64a1782d44baca1a32591.png
[aHR0cHM6Ly91c2VyLWdvbGQtY2RuLnhpdHUuaW8vMjAxOS83LzcvMTZiY2MxNzU2NzE1NmJjYQ]: /images/20211213/16d1f7aa4562443e9edb4dd7438be2e7.png
[aHR0cHM6Ly91c2VyLWdvbGQtY2RuLnhpdHUuaW8vMjAxOS83LzcvMTZiY2MxNzU2NzYyNDIxNA]: /images/20211213/96e719003f6a47e6aeb4ffaf93672166.png
[aHR0cHM6Ly91c2VyLWdvbGQtY2RuLnhpdHUuaW8vMjAxOS83LzcvMTZiY2MxNzU2N2JjZWIxOA]: /images/20211213/2cc97c9ca3fc41d1b46cf28b7f3caf12.png