修改密码

请输入密码
请输入密码 请输入8-64长度密码 和 email 地址不相同 至少包括数字、大写字母、小写字母、半角符号中的 3 个
请输入密码
提交

修改昵称

当前昵称:
提交
搜索
v4.0
    v4.0

    LINE

    概述

    LINE 是 Large-scale Information Network Embedding(大规模信息网络嵌入)的简称,作为一种图嵌入模型,它使用节点的 BFS 邻域信息(一阶或二阶相似度)构造训练样本,并使用和 Node2Vec 类似的方式训练得到节点的嵌入向量。LINE 算法能应用到各类非常大型的网络上,是由微软的 Jian Tang 等人于 2015 年提出的。

    算法的相关资料如下:

    基本概念

    一阶相似性和二阶相似性

    在图中,节点间的一阶相似性(First-order Proximity)取决于相连关系,节点间的边权重越大(无权重图的边权值视为 1;仅考虑非负权重值),一阶相似性就越高,如果没有边,一阶相似度为 0。一阶相似性用于表示局部结构。

    二阶相似性(Second-order Proximity)则表示全局网络结构,它依赖于节点间的共同邻居。这个概念很容易理解,比如在社交网络中,两个人的共同好友越多,这两个人的相关性就越高。如果两个节点没有共同邻居,则它们的二阶相似度为 0。

    下图中,边的粗细代表权重大小。节点 6 和 7 在嵌入空间的位置应该很接近,因为它们之间的边权重很高,具有一阶相似性;另外,虽然节点 5 和 6 之间没有边相连,但它们有很多共同邻居,也应该被嵌入到相互靠近的位置,它们具有二阶相似性。

    模型描述

    我们分别介绍 LINE 模型如何保留一阶相似度和二阶相似度,以及合并这两种相似度的一种简单方法。

    保留一阶相似度

    对于图 G = (V, E),为描述一阶相似度,LINE 模型定义任意两个节点 vi 和 vj 间的联合概率分布为:

    其中 u 是节点在嵌入空间的表示。对应的经验概率分布可以表示为:

    其中 wij 表示节点 vi 和 vj 间的边的权重。

    为保留一阶相似度,一个直接的方法就是使上述两个概率分布的差异最小(即模型预测值接近于真实值)。LINE 采用 KL(Kullback-Leibler)散度衡量这个差异(忽略常数项):

    请注意,一阶相似度仅适用于无向图。

    保留二阶相似度

    每个节点可以有两种向量表示,一个是节点本身的向量表示,一个是节点作为其他节点的上下文时的向量表示。在“上下文”上具有相似分布的节点具有二阶相似度。给定节点 vi 时,产生其上下文(邻居)节点 vj 的概率定义为(为了不失一般性,假设图是有向的):

    其中 u' 为节点被视为上下文时的向量表示,|V| 为图中的节点总数。对应的经验概率分布可以表示为:

    其中 wij 表示节点 vi 和 vj 间的边的权重,di 表示节点 vi 的出度。

    类似地,LINE 采用 KL(Kullback-Leibler)散度衡量两个概率分布的差异(忽略常数项):

    二阶相似度既适用于无向图,也适用于有向图。

    合并一阶相似度和二阶相似度

    为了在嵌入结果同时保留一阶相似度和二阶相似度,一个简单的方法是分别训练保留一阶相似度和二阶相似度的模型,然后将每个节点两个嵌入结果拼接。

    模型优化

    负采样

    优化上述 O2 的计算量很大,因为计算条件概率 p2(·|vi) 需要考虑所有节点。为了解决这个问题,LINE 算法采用的优化方法是负采样。具体来说,从任意节点 vi 到 vj 的边的目标函数为:

    其中,σ 是 Sigmoid 函数,前半部分是观察到的边,后半部分是 K 个负样本(边),负样本的概率分布为 Pn(v) ∝ dv3/4,dv 是节点 v 的出度。

    关于负采样,读者可参考文档——Skip-gram 模型优化

    特殊处理

    孤点、不连通图

    孤点没有邻居节点,与其他任何节点都没有一阶相似度或二阶相似度。

    节点只会与同一连通分量内的节点有一阶相似度或二阶相似度。

    自环边

    节点的自环边不影响它与其他节点的一阶相似度或二阶相似度。

    有向边

    一阶相似度仅适用于无向图。二阶相似度既适用于无向图,也适用于有向图。

    命令和参数配置

    • 命令:algo(line)
    • params() 参数配置如下:
    名称
    类型
    默认值
    规范
    描述
    edge_schema_property []@<schema>?.<property> / 数值类的边属性,需LTE 边权重所在的一个或多个属性名称,带不带 schema 均可,无该属性的边不参与计算;忽略表示不加权
    dimension int / >=1 节点嵌入向量的维度
    resolution int / >=1 如:10、100
    learning_rate float / (0,1) 初始学习率,每次迭代后学习率都会降低,直至减到 min_learning_rate
    min_learning_rate float / (0,learning_rate) 最小学习率
    neg_num int / >=0 负采样时负样本数量,建议 0~10
    train_total_num int / >=1 模型训练次数
    train_order int 1 1 或 2 相似度类型,1 代表一阶相似度,2 代表二阶相似度
    limit int -1 >=-1 需要返回的结果条数,-1 或忽略表示返回所有结果

    算法执行

    任务回写

    1. 文件回写

    配置项
    各列数据
    filename _id, embedding_result

    2. 属性回写

    算法不支持属性回写。

    3. 统计回写

    算法无统计值。

    直接返回

    别名序号
    类型
    描述 列名
    0 []perNode 各点及其图嵌入结果 _uuid, embedding_result

    流式返回

    别名序号
    类型
    描述 列名
    0 []perNode 各点及其图嵌入结果 _uuid, embedding_result

    实时统计

    算法无统计值。

    请完成以下信息后可下载此书
    *
    公司名称不能为空
    *
    公司邮箱必须填写
    *
    你的名字必须填写
    *
    你的电话必须填写
    *
    你的电话必须填写