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]之间的联合概率，如下所示：

(1)

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

(2)

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

(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]的概率定义为：

(4)

其中|V|是顶点或“上下文”数量。对于每个顶点v[i]，公式（4）实际上定义了上下文中（即网络中的整个顶点集）的条件分布p[2](·|v[i])。 如上所述，二阶邻近度假设在上下文中具有相似分布的顶点彼此相似。 为了保持二阶邻近度，我们应该使由低维表示指定的上下文条件分布p[2](·|v[i])邻近经验分布^p[2](·|v[i])。 因此，我们最小化以下目标函数：

(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)指定以下目标函数：

(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]的梯度为将计算为：

(8)

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

优化 VS 边采样

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

4.3 讨论

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

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

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

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

(10)

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