修改密码

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

修改昵称

当前昵称:
提交

申请证书

证书详情

Please complete this required field.

  • Ultipa Graph V4

Standalone

Please complete this required field.

Please complete this required field.

服务器的MAC地址

Please complete this required field.

Please complete this required field.

取消
申请
ID
产品
状态
核数
申请天数
审批时间
过期时间
MAC地址
申请理由
审核信息
关闭
基础信息
  • 用户昵称:
  • 手机号:
  • 公司名称:
  • 公司邮箱:
  • 地区:
  • 语言:
修改密码
申请证书

当前未申请证书.

申请证书
Certificate Issued at Valid until Serial No. File
Serial No. Valid until File

Not having one? Apply now! >>>

ProductName CreateTime ID Price File
ProductName CreateTime ID Price File

No Invoice

v5.0
搜索
    v5.0

      快速随机投影

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

      概述

      快速随机投影(Fast Random Projection,FastRP)是一种可扩展且高性能的算法,用于学习图中节点的嵌入表示。FastRP实现了节点嵌入的迭代计算,主要包含两个步骤:一是构造节点相似度矩阵构造,二是通过随机投影对矩阵进行降维。

      FastRP算法是由H. Chen等人于2019年提出的:

      FastRP工作框架

      FastRP的作者提出,大多数图(节点)嵌入方法基本上由两部分组成:(1)构造一个节点相似度矩阵或从中隐式地采样节点对,然后(2)对该矩阵进行降维得到嵌入结果。

      关于降维,许多流行的算法(如Node2Vec)都依赖于Skip-gram等耗时的方法。但作者认为,这些算法的成功并不归功于它们采用的降维方法,而是源于对相似度矩阵的正确构建。

      因此,FastRP采用非常稀疏的随机投影(Very Sparse Random Projection)这种可扩展的高效降维技术。

      非常稀疏的随机投影

      随机投影(Random Projection)是一种降维方法,能够将数据点从高维空间嵌入到低维空间,同时大致保持数据点之间的相对的距离。随机投影的理论基础主要是约翰逊-林登斯特劳斯引理

      随机投影背后的思想非常简单:要将矩阵Mn×m(对于图数据,有n = m)降维成矩阵Nn×d(d ≪ n),可以简单地将M乘以一个随机投影矩阵Rm×d,即N = M ⋅ R。

      矩阵R中的每个元素是独立基于一个分布生成的。具体来说,FastRP采用非常稀疏的随机投影方法,其中R的元素基于以下分布生成:

      其中s=sqrt(m)。

      非常稀疏的随机投影具有优越的计算效率,因为它只需要进行矩阵乘法,并且R中占比(1-1/s)的元素都为零。

      此外,嬴图支持使用一些数值类点属性(特征)来影响矩阵R的初始化。在这种情况下,矩阵R中的每一行由两部分拼接而成:

      • 元素d1 ~ dx由非常稀疏随机投影算法生成。
      • 元素p1 ~ py是所选节点属性值的线性组合。
      • x + y等于最终嵌入的维度,其中y称为属性维度。
      • 所选节点属性的数量不必与属性维度相同。

      构造节点相似性矩阵

      FastRP算法在构建节点相似性矩阵时兼顾以下两点:

      1. 保留图的高阶接近性
      2. 对矩阵元素进行归一化处理

      令S为图G = (V, E)的邻接矩阵,D为节点度矩阵,A为转移概率矩阵且A = D-1S。下面展示了一个例子,图中每条边上的数字代表边的权重:

      事实上,矩阵A中的元素Aij表示从节点i经过长度为1的随机游走到达节点j的概率。进一步地,如果将矩阵A与自身相乘k次得到矩阵AkAkij则表示从节点i经过长度为k的随机游走到达节点j的概率。如此,矩阵Ak保留了图的高阶接近性。

      但是,当k → ∞,可以证明的是Akij → dj/2m,其中m = |E|,dj是第j个节点的度。由于许多真实世界的图是无标度的,因此Ak中的元素常呈现重尾分布。这意味着Ak中数据点之间的距离主要受具有异常大值的列影响,这使得它们的意义降低,并为下一步降维带来了挑战。

      为了解决这个问题,FastRP进一步对矩阵Ak进行归一化处理,方法是将其乘以对角线归一化矩阵L,其中Lij = (dj/2m)β,β是归一化强度。归一化强度控制节点度对嵌入的影响:当β为负时,削弱高节点度邻居的重要性,β为正数时,则相反。

      算法步骤

      FastRP算法的步骤如下:

      1. 生成随机映射矩阵R
      2. 对归一化的1步转移矩阵进行降维:N1 = A ⋅ L ⋅ R
      3. 对归一化的2步转移矩阵进行降维:N2 = A ⋅ (A ⋅ L ⋅ R) = A ⋅ N1
      4. 重复步骤3直到对归一化的k步转移矩阵进行降维:Nk = A ⋅ Nk-1
      5. 生成矩阵A的不同幂次的加权组合结果:N = α1N1 + ... + αkNk,其中α1,...,αk为迭代权重

      特殊说明

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

      语法

      • 命令:algo(fastRP)
      • 参数:
      名称
      类型
      规范
      默认
      可选
      描述
      dimension int ≥2 / 嵌入向量的维度
      normalizationStrength float / / 归一化强度β
      iterationWeights []float >0 [0.0,1.0,1.0] 每次迭代结果的权重,数组长度就是算法的迭代轮数
      edge_schema_property []@<schema>?.<property> 数值类型,需LTE / 用作边权重的属性,权重值为所有指定属性值的和
      node_schema_property []@<schema>?.<property> 数值类型,需LTE / 用作特征的点属性;propertyDimensionnode_schema_property需要同时配置或忽略
      propertyDimension int (0,dimension] / 属性维度的长度;propertyDimensionnode_schema_property需要同时配置或忽略
      limit int ≥-1 -1 返回的结果条数,-1返回所有结果

      示例

      文件回写

      配置项 回写内容
      filename _id, embedding_result
      algo(fastRP).params({
        dimension : 10,
        normalizationStrength: 1.5,
        iterationWeights: [0, 0.8, 0.2, 1],
        edge_schema_property: ['w1', 'w2'],
        node_schema_property: ['@default.f1', '@default.f2'],
        propertyDimension: 3
      }).write({
        file:{
          filename: 'embedding'
        }
      })
      

      属性回写

      配置项 回写内容 回写至 数据类型
      property embedding_result 点属性 string
      algo(fastRP).params({
        dimension : 10,
        normalizationStrength: 1.5,
        iterationWeights: [0, 0.8, 0.2, 1],
        edge_schema_property: ['w1', 'w2']
      }).write({
        db:{
          property: 'embedding'
        }
      })
      

      直接返回

      别名序号
      类型
      描述
      列名
      0 []perNode 点及其嵌入结果 _uuid, embedding_result
      algo(fastRP).params({
        dimension : 10,
        normalizationStrength: 1.5,
        iterationWeights: [0, 0.8, 0.2, 1]
      }) as embeddings
      return embeddings
      

      流式返回

      别名序号
      类型
      描述
      列名
      0 []perNode 点及其嵌入结果 _uuid, embedding_result
      algo(fastRP).params({
        dimension : 10,
        normalizationStrength: 1.5,
        iterationWeights: [0, 0.8, 0.2, 1]
      }).stream() as embeddings
      return embeddings
      
      请完成以下信息后可下载此书
      *
      公司名称不能为空
      *
      公司邮箱必须填写
      *
      你的名字必须填写
      *
      你的电话必须填写
      *
      你的电话必须填写