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

2022-05-07 14:28:10 浏览数 (1)

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]表示uv之间的一阶邻近度。 如果在uv之间没有观察到边,则它们的一阶邻近度为 0。

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

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

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

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

0 人点赞