概述
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。
![](https://img.ultipa.cn/2022-09-13-15-14-24-info-network.jpg)
在此图示中,边的粗细代表权重大小。
- 节点6和7在嵌入空间的位置应该很接近,因为它们之间的边权重很高,具有一阶相似度。
- 虽然节点5和6之间没有边相连,但它们有很多共同邻居,也应该被嵌入到相互靠近的位置,因为它们具有二阶相似性。
LINE模型
LINE模型的设计旨在将图G = (V,E)中的节点嵌入到较低维的向量空间,保留节点间的一阶相似度或二阶相似度。
一阶相似度
对于每条边(i,j) ∈ E,LINE模型定义其两个端点vi和vj间的联合概率为:
![](https://img.ultipa.cn/2022-09-13-16-45-04-f1.jpg)
其中ui是节点vi在嵌入空间的表示。联合概率p1的取值范围是0到1,两个向量越接近,它们的点积越大,联合概率就越高。
同时定义节点vi和vj之间联合概率的经验分布为:
![](https://img.ultipa.cn/img/2023-11-22-15-35-00-e-p1.jpg)
其中wij表示节点vi和vj 间的边权重,W是图中所有边的权重和。
LINE采用KL散度衡量这两个概率分布的差异:
![](https://img.ultipa.cn/2022-09-13-16-56-53-f3.jpg)
这是模型保留一阶相似度训练时需要最小化的目标函数。
二阶相似度
为了捕获二阶相似度,LINE为每个节点定义两种身份:一是节点自身,二是作为其他节点的上下文(这个概念来自 Skip-gram模型)。相应地,每个节点对应两种不同的向量表示。
对于每条边(i,j) ∈ E,LINE定义在节点vi周围观察到上下文节点vj的概率为:
![](https://img.ultipa.cn/2022-09-13-16-48-02-f4.jpg)
其中u'j是节点vj被视为上下文时的向量表示。重要的是,上式的分母涵盖图中所有的上下文。
对应的经验概率定义为:
![](https://img.ultipa.cn/img/2023-11-22-17-57-12-e-p2.jpg)
其中wij表示边(i,j)权重,di表示节点vi的加权度。
类似地,LINE采用KL散度来衡量两个概率分布的差异:
![](https://img.ultipa.cn/2022-09-13-16-57-00-f5.jpg)
这是模型保留二阶相似度训练时需要最小化的目标函数。
模型优化
负采样
为了提高计算效率,LINE采用负采样技术根据噪声分布为每条边(i,j)选择若干负样本(边)。具体来说,两个目标函数调整为:
![](https://img.ultipa.cn/img/2023-11-23-15-36-55-ng.jpg)
其中,σ是Sigmoid函数,K个负样本是依据噪声分布Pn(v) ∝ dv3/4选取的,dv是节点v的加权度。
边采样
两个目标函数中都包含边权重,这些权重与梯度相乘可能导致梯度爆炸,从而影响性能。为了解决这个问题,LINE以与边权重成正比的概率对边进行采样,然后将采样的边视为二进制边。
特殊说明
- LINE算法忽略边的方向,按照无向边进行计算。
语法
- 命令:
algo(line)
- 参数:
名称 |
类型 |
规范 |
默认 |
可选 |
描述 |
---|---|---|---|---|---|
edge_schema_property | []@<schema>?.<property> |
数值类型,需LTE | / | 否 | 用作边权重的属性,权重值为所有指定属性值的和 |
dimension | int | ≥2 | / | 否 | 嵌入向量的维度 |
train_total_num | int | ≥1 | / | 否 | 模型训练的总次数 |
train_order | int | 1 , 2 |
1 |
是 | 要保留的相似度,1 代表一阶相似度,2 代表二阶相似度 |
learning_rate | float | (0,1) | / | 否 | 模型训练的初始学习率,学习率会在每次训练迭代后逐渐减小,直至达到min_learning_rate |
min_learning_rate | float | (0,learning_rate ) |
/ | 否 | 在训练过程中逐渐减小的学习率的最小阈值 |
neg_num | int | ≥0 | / | 否 | 每个正样本对应的负样本数量,建议设置在0到10之间 |
resolution | int | ≥1 | 1 |
是 | 用于提高负采样效率的参数;较高的值能提供更接近原始噪声分布的近似分布;建议设置为10、100等 |
limit | int | ≥-1 | -1 |
是 | 返回的结果条数,-1 返回所有结果 |
示例
文件回写
配置项 | 回写内容 |
---|---|
filename | _id ,embedding_result |
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'
}})
属性回写
配置项 | 回写内容 | 回写至 | 数据类型 |
---|---|---|---|
property | embedding_result |
点属性 | string |
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'
}})
直接返回
别名序号 | 类型 |
描述 |
列名 |
---|---|---|---|
0 | []perNode | 点及其嵌入结果 | _uuid , embedding_result |
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
流式返回
别名序号 | 类型 |
描述 |
列名 |
---|---|---|---|
0 | []perNode | 点及其嵌入结果 | _uuid , embedding_result |
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