✓ 文件回写 ✓ 属性回写 ✓ 直接返回 ✓ 流式返回 ✕ 统计值

概述

LINE（Large-scale Information Network Embedding，大规模信息网络嵌入）作为一种图嵌入模型，能够保留网络的局部或全局结构特征，能应用到各类非常大型的网络上。

LINE 算法最初是在 2015 年提出的：

• J. Tang, M. Qu, M. Wang, M. Zhang, J. Yan, Q. Zhu, LINE: Large-scale Information Network Embedding (2015)

基本概念

一阶相似度和二阶相似度

网络中两个节点的一阶相似度（First-order Proximity）取决于相连关系，它们之间存在边或存在较大权重的边（此处不考虑负权重），则表示一阶相似度更高。如果两个节点之间不存在边，则它们的一阶相似度为 0。

另一方面，一对节点之间的二阶相似度（Second-order Proximity）则表示它们邻域结构之间的相似性，这是通过共同邻居确定的。如果两个节点没有共同邻居，则它们的二阶相似度为 0。

在此图示中，边的粗细代表权重大小。

• 节点 6 和 7 在嵌入空间的位置应该很接近，因为它们之间的边权重很高，具有一阶相似度。
• 虽然节点 5 和 6 之间没有边相连，但它们有很多共同邻居，也应该被嵌入到相互靠近的位置，因为它们具有二阶相似性。

LINE 模型

LINE 模型的设计旨在将图 G = (V,E) 中的节点嵌入到较低维的向量空间，保留节点间的一阶相似度或二阶相似度。

一阶相似度

对于每条边 (i,j)∈E，LINE 模型定义其两个端点 v_i 和 v_j 间的联合概率为：

其中 u_i 是节点 v_i 在嵌入空间的表示。联合概率 p₁ 的取值范围是 0 到 1，两个向量越接近，它们的点积越大，联合概率就越高。

同时定义节点 v_i 和 v_j 之间联合概率的经验分布为：

其中 w_ij 表示节点 v_i 和 v_j 间的边权重，W 是图中所有边的权重和。

LINE 采用 KL 散度衡量这两个概率分布的差异：

这是模型保留一阶相似度训练时需要最小化的目标函数。

二阶相似度

为了捕获二阶相似度，LINE 为每个节点定义两种身份：一是节点自身，二是作为其他节点的上下文（这个概念来自 Skip-gram 模型）。相应地，每个节点对应两种不同的向量表示。

对于每条边 (i,j)∈E，LINE 定义在节点 v_i 周围观察到上下文节点 v_j 的概率为：

其中 u'_j 是节点 v_j 被视为上下文时的向量表示。重要的是，上式的分母涵盖图中所有的上下文。

对应的经验概率定义为：

其中 w_ij 表示边 (i,j) 权重，d_i 表示节点 v_i 的加权度。

类似地，LINE 采用 KL 散度来衡量两个概率分布的差异：

这是模型保留二阶相似度训练时需要最小化的目标函数。

模型优化

负采样

为了提高计算效率，LINE 采用负采样技术根据噪声分布为每条边 (i,j) 选择若干负样本（边）。具体的，两个目标函数调整为：

其中，σ 是 Sigmoid 函数，K 个负样本是依据噪声分布 P_n(v) ∝ d_v^3/4 选取的，d_v 是节点 v 的加权度。

边采样

两个目标函数中都包含边权重，这些权重与梯度相乘可能导致梯度爆炸，从而影响性能。为了解决这个问题，LINE 以与边权重成正比的概率对边进行采样，然后将采样的边视为二进制边。

特殊说明

• LINE 算法忽略边的方向，按照无向边进行计算。

语法

• 命令：algo(line)
• 参数：

示例

文件回写

algo(line).params({
  dimension: 20,
  train_total_num: 10,
  train_order: 1,
  learning_rate: 0.01,
  min_learning_rate: 0.0001,
  neg_number: 5,
  resolution: 100,
  limit: 100
}).write({
  file:{
    filename: 'embeddings'
}})

属性回写

algo(line).params({
  edge_schema_property: '@branch.distance',
  dimension: 20,
  train_total_num: 10,
  train_order: 1,
  learning_rate: 0.01,
  min_learning_rate: 0.0001,
  neg_number: 5,
  limit: 100
}).write({
  db:{
    property: 'vector'
}})

直接返回

algo(line).params({
  edge_schema_property: '@branch.distance',
  dimension: 20,
  train_total_num: 10,
  train_order: 1,
  learning_rate: 0.01,
  min_learning_rate: 0.0001,
  neg_number: 5,
  limit: 100
}) as embeddings
return embeddings

流式返回

algo(line).params({
  edge_schema_property: '@branch.distance',
  dimension: 20,
  train_total_num: 10,
  train_order: 2,
  learning_rate: 0.01,
  min_learning_rate: 0.0001,
  neg_number: 5,
  limit: 100
}).stream() as embeddings
return embeddings