概述

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