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