一句话总结

微软亚洲研究院、北京大学和密歇根大学的研究人员提出了LINE，这是一种可扩展的网络嵌入方法，适用于任意类型的网络，通过精心设计的目标函数和边采样算法同时保留局部结构和全局结构，能够在单机上在数小时内嵌入具有数百万顶点和数十亿条边的网络。

核心贡献

• 该论文介绍了LINE，这是一种可扩展的网络嵌入方法，适用于无向、有向和加权信息网络。

• 论文定义了一阶邻近性和二阶邻近性，并设计了目标函数，以同时保留局部成对关系和更广泛的邻域结构，使嵌入对稀疏链接更加鲁棒。

• 论文提出了一种边采样推断方法，改进了经典随机梯度下降对加权边的处理方式；在语言、社交和引文网络上的实验表明，LINE能够在典型单机上以数小时学习出具有数百万顶点和数十亿条边的网络嵌入。

引言

作者指出，信息网络是许多数据挖掘任务的核心，将顶点嵌入低维向量可实现可视化、节点分类、链接预测和推荐。以往的图嵌入方法要么难以扩展到具有数百万节点的网络，要么采用的目标函数并非用于保留更广泛的网络结构，尤其在观测边稀疏时。作者提出了LINE，一种有向、无向、加权和未加权图的可扩展网络嵌入模型，它保留一阶邻近性和二阶邻近性，并使用边采样与随机梯度下降在大规模加权网络上高效训练。

数据集

• 作者使用涵盖语言、社交和引文领域的四个网络数据集进行实验。

• 语言网络：基于全部英文维基百科页面构建。通过将每个5词滑动窗口内的单词视为共现对，构建词共现网络。频率低于5的词被移除。

• 社交网络：使用Flickr和YouTube。Flickr网络比YouTube网络更稠密，而YouTube网络与DeepWalk中使用的网络相同。

• 引文网络：从DBLP构建两个网络，一个在作者之间，另一个在论文之间。作者引文网络统计一位作者撰写并被另一位作者引用的论文数量，并在作者之间产生加权边。

• 总体数据集规模和特性：网络包含有向与无向、二元与加权等形式，每个网络至少包含五十万节点和数百万条边。最大网络约有两百万个节点和约十亿条边。

• 数据集使用：作者将这些网络作为信息网络实验的输入图数据，数据集统计信息汇总于表1。给定文本未报告明确的训练划分或混合比例。

方法

作者将LINE用作一个网络嵌入框架，旨在学习大规模信息网络的低维顶点表示，同时保留两种互补的邻近性概念。该模型围绕两个学习模块组织。第一个模块捕获一阶邻近性，反映相互连接顶点之间的直接局部关系。第二个模块捕获二阶邻近性，反映顶点基于其周围网络邻域的相似性。随后采用简单的组合策略融合两种学习得到的表示，形成最终顶点嵌入。

对于一阶邻近性，作者将每条无向边建模为其端点之间的直接局部关系。给定嵌入为 $\vec{u}_i$ui​ 的顶点 $v_i$vi​ 和嵌入为 $\vec{u}_j$uj​ 的顶点 $v_j$vj​，作者定义了一个联合概率

$$p_1(v_i, v_j) = \frac{1}{1 + \exp(-\vec{u}_i^T \cdot \vec{u}_j)}.$$p1​(vi​,vj​)=1+exp(−uiT​⋅uj​)1​.

当两个嵌入在逻辑打分函数下兼容时，该概率会增大。经验边分布来自观测到的边权重。若 $w_{ij}$wij​ 是边 $(i, j)$(i,j) 的权重，$W$W 是图中的总边权，则经验概率与 $w_{ij}/W$wij​/W 成正比。为了使学习得到的模型与该经验结构匹配，作者最小化经验联合分布与模型联合分布之间的KL散度。去除常数项后，优化目标变为

$$-\sum_{(i, j) \in E} w_{ij} \log p_1(v_i, v_j).$$−(i,j)∈E∑​wij​logp1​(vi​,vj​).

该一阶模块适用于直接连接承载主要语义或结构含义的图，但由于联合概率是对称的，它天然适用于无向图。

对于二阶邻近性，作者采用一种基于上下文建模的策略，该策略同时适用于有向和无向网络。在该模块中，每个顶点承担两种角色。它可以作为目标顶点出现，也可以作为其他顶点的上下文出现。为了区分这两种角色，每个顶点 $v_i$vi​ 与两个嵌入相关联：$\vec{u}_i$ui​ 表示顶点本身，而 $\vec{u}_i^\prime$ui′​ 表示该顶点作为其邻居上下文的表示。作者认为，连接模式相似的顶点应具有相似的上下文分布。因此，二阶邻近性通过上下文上的条件概率分布来建模。

对于有向边 $(i, j)$(i,j)，顶点 $v_j$vj​ 作为顶点 $v_i$vi​ 的上下文出现的概率，通过在整个顶点集合上的softmax定义：

$$p_2(v_j \mid v_i) = \frac{\exp(\vec{u}_j^{\prime T} \cdot \vec{u}_i)}{\sum_{k=1}^{|V|} \exp(\vec{u}_k^{\prime T} \cdot \vec{u}_i)}.$$p2​(vj​∣vi​)=∑k=1∣V∣​exp(uk′T​⋅ui​)exp(uj′T​⋅ui​)​.

该公式使 $p_2(\cdot \mid v_i)$p2​(⋅∣vi​) 成为由 $v_i$vi​ 生成的所有可能上下文上的分布。经验条件分布也基于观测边权重。若 $d_i$di​ 是顶点 $v_i$vi​ 的出度，则 $v_j$vj​ 被观测为 $v_i$vi​ 上下文时，其经验概率与 $w_{ij}/d_i$wij​/di​ 成正比。训练目标最小化每个顶点上经验上下文分布与模型上下文分布之间的KL散度。作者进一步引入声望权重，以考虑顶点重要程度可能不同这一事实。在作者的实际设定中，声望权重被设置为顶点的度，从而将目标简化为

$$-\sum_{(i, j) \in E} w_{ij} \log p_2(v_j \mid v_i).$$−(i,j)∈E∑​wij​logp2​(vj​∣vi​).

该二阶模块通过比较顶点的上下文分布来捕获全局邻域结构。

为了同时保留一阶邻近性和二阶邻近性，作者采用了一种简单但有效的训练方案。作者分别训练一阶邻近性模型和二阶邻近性模型，然后将每个顶点的两个学习嵌入进行拼接。由此得到的统一表示同时包含直接局部边信息和更广泛的邻域模式信息。作者还指出，也可以构造更具原则性的联合训练目标，但分别学习后再拼接对于大规模网络具有实用性和效率。

该方法的一个关键部分是可扩展优化。直接优化二阶softmax目标代价很高，因为每次预测都需要整个顶点集合上的归一化项。作者使用负采样解决这一问题。对于每条观测边 $(i, j)$(i,j)，模型最大化正上下文的似然，同时最小化若干采样负上下文的似然。一条边的优化目标变为

$$\log \sigma(\vec{u}_j^{\prime T} \cdot \vec{u}_i) + \sum_{n=1}^{K} \mathbb{E}_{v_n \sim P_n(v)} \left[\log \sigma(-\vec{u}_n^{\prime T} \cdot \vec{u}_i)\right],$$logσ(uj′T​⋅ui​)+n=1∑K​Evn​∼Pn​(v)​[logσ(−un′T​⋅ui​)],

其中 $\sigma(x) = 1/(1 + \exp(-x))$σ(x)=1/(1+exp(−x)) 是sigmoid函数，$K$K 是负样本数量。负采样分布与顶点出度的 $3/4$3/4 次方成正比，从而使采样偏向连接更多的顶点。对于一阶目标，作者也采用类似的负采样方法，但用顶点向量本身替代上下文向量。这也有助于避免嵌入幅度无限增长的平凡解。

训练过程使用异步随机梯度下降。在每一步中，采样的边形成小批量，并据此更新嵌入向量的梯度。这种异步设计支持大规模图上的高吞吐优化。然而，作者观察到真实网络中的边权重差异可能很大。当梯度包含原始边权重时，权重大边会产生极大更新，而权重小边会产生极小更新。这导致难以选择稳定的学习率。

为了解决这一问题，作者引入了一种边采样机制。作者不再用原始边权重乘以梯度，而是按照边权重对边进行采样，并将采样得到的边视为二元边。实际上，一条加权边被统计上展开为多条二元边，而无需显式实例化所有这些边。采样概率与原始边权重成正比。如果直接根据累积权重分布进行采样，每次采样需要线性时间，因此作者使用别名表进行高效采样。从别名表中采样一条边需要恒定时间。因此，每次优化步骤的时间与嵌入维度和负样本数量成正比，整体训练复杂度与边数量呈线性关系，而不是与顶点数量相关。

该框架还包括面向两种常见部署场景的实用机制。对于低度顶点，二阶模块可能不可靠，因为这些顶点只有很少的观测连接。作者通过为每个低度顶点补充更高阶邻居来缓解这一问题，具体是邻居的邻居。所添加的二阶连接权重通过经由中间邻居传播一阶权重来计算。这为原本难以良好表示的顶点提供了更多上下文证据。对于新加入的顶点，作者保持已有顶点的嵌入固定，只更新新顶点的嵌入。如果新顶点与已有网络存在观测连接，则使用基于第一阶或第二阶邻近项的局部目标优化其嵌入。如果不存在此类连接，则无法仅从图结构中推断其表示，而需要辅助信息。

实验

实验在大规模语言、社交和引文网络上评估了LINE嵌入方法，通过词类比、文档分类、顶点分类、网络可视化、稀疏性分析、参数敏感性和可扩展性测试，将其与图矩阵分解和DeepWalk进行比较。边采样处理被证明有效且高效：二阶邻近性最适合语义和稠密图，一阶邻近性在稀疏社交网络中更重要，两者的组合在许多任务中具有互补性。结果还表明，直接随机梯度下降在处理异质边权重时遇到困难，邻域重建可以缓解二阶嵌入的稀疏性，而异步优化在保持性能的同时实现接近线性的加速。

数据集统计信息涵盖语言、社交和引文网络，显示Wikipedia是一个非常庞大且稠密的加权词网络，而在社交网络中YouTube比Flickr稀疏得多。引文网络在方向性和稠密性上有所不同，作者引文图比论文引文图更稠密。社交网络实验表明，随着网络稠密度和节点度增加，二阶邻近性变得更有效。Wikipedia拥有最大的网络和最高的平均度，反映了稠密的词共现结构。Flickr比YouTube稠密，为比较稀疏和中等稠密社交网络提供了有用设定。尽管使用相同的DBLP来源，作者引文网络的连接程度仍高于论文引文网络。二阶邻近性方法在更稠密或经过重建的网络上表现更好，但在非常稀疏或低度区域可能表现不佳。

在Wikipedia词类比任务上，使用二阶邻近性学习得到的嵌入在语义、句法和整体设置中均取得最高准确率。该结果强于从原始语料库训练的Skip-Gram嵌入，也强于其他图嵌入基线方法。最佳模型的运行时间仍接近其他快速方法，而DeepWalk更慢且精度更低。二阶邻近性提升了语义类比和句法类比准确率。二阶模型超过Skip-Gram和其他图嵌入方法。DeepWalk尽管探索了网络结构，但落后于加权共现嵌入。

在Wikipedia页面分类任务上，随着保留更多网络链接，micro-F1总体有所提升。LINE(2nd)给出最强的整体性能，而图矩阵分解、LINE(1st)和SkipGram仍具有竞争力。在所有评估的链接稠密度下，LINE(2nd)始终强于一阶方法和随机游走方法。随着网络变得不那么稀疏，性能往往会上升，这表明更丰富的邻域信息有助于嵌入学习。

比较结果显示，二阶邻近性往往返回词汇上更接近或主题相关的词，例如information的拼写变体以及与图相关的术语。一阶邻近性也能产生相关词，但其中一些是更宽泛或更弱的匹配，例如作为good邻居的luck和faith。这些例子表明，二阶邻近性比一阶邻近性更直接地捕捉上下文替换模式。二阶相似词通常包括近似拼写形式或主题近邻，例如information的近邻包括infomation和informaton。一阶相似词可能关系不那么紧密，例如在good的顶部近邻中出现luck和faith。

在Flickr社交网络上，组合LINE模型取得最强的多标签分类性能，并在不同训练比例下均显著优于DeepWalk。一阶邻近性的表现略优于二阶邻近性，这与稀疏社交网络中更强的一阶连接以及邻域信息收益有限相一致。同时使用一阶邻近性和二阶邻近性的LINE优于所有比较方法。在该社交网络上，一阶邻近性比二阶邻近性更有效。图矩阵分解落后于DeepWalk和LINE各变体。组合邻近性类型提高了稀疏社交网络嵌入的鲁棒性。

该评估检验大规模语言、社交和引文网络，以测试一阶和二阶邻近性嵌入是否能够在不同稠密度下捕捉节点关系。实验验证表明，二阶邻近性在稠密或结构更丰富的网络中尤其有用，在Wikipedia词类比、页面分类和定性词邻域分析上带来更强性能。在更稀疏的Flickr社交网络上，一阶邻近性更有效，而结合一阶和二阶邻近性可取得最佳整体多标签分类结果，这支持了嵌入性能取决于网络稠密度和邻近性结构选择的结论。