修改密码

请输入密码
请输入密码 请输入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

搜索
    中文

      快速随机投影

      概述

      FastRP(Fast Random Projection,快速随机投影)算法是一种比传统的随机游走方式更快、更有效的图嵌入方法,它通过迭代计算节点嵌入,避免了显式地构造相似性矩阵而带来的时间损耗。FastRP 算法是由 H. Chen 等人于 2019 年提出的。

      算法的相关资料如下:

      工作框架

      FastRP 图嵌入算法的工作框架主要由两部分组成:首先,构建节点相似性矩阵;然后,通过随机投影的方法将该矩阵降维,得到节点的嵌入结果。

      构造节点相似性矩阵

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

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

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

      然而,直接使用矩阵 S 或 A 进行降维是有问题的。现实世界的网络通常非常稀疏,这意味着 S 或 A 中的大多数元素都为 0。但是,两个节点之间没有边直接相连并不意味着它们之间就没有关联。

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

      下面考虑将矩阵 Ak 归一化的问题。首先,现实网络中 Ak 常呈现出重尾分布,需要平衡节点度对嵌入结果的影响,因此归一化很重要。另外,可被证明的是,当 k → ∞ 时,Akij → dj/2m,其中 m = |E| 是图中边的数量,dj 是第 j 个节点的度。

      由此构造一个归一化对角矩阵 L,元素 Lij = (dj/2m)β,其中 β 为归一化强度。归一化强度能控制节点度对嵌入结果的影响:β 为负数时,会削弱高节点度邻居的重要性,β 为正数时反之。

      矩阵降维

      约翰逊-林登斯特劳斯引理

      随机投影的理论基础是约翰逊-林登斯特劳斯引理(Johnson–Lindenstrauss Lemma,简称 JL Lemma),该理论最初是由 W. Johnson 和 J. Lindenstrauss 于 1984 年提出的,经过后人的继续研究,目前被普遍接受的描述为:

      一个高维欧几里得空间中点集 M 能通过一个线性映射 R 嵌入到一个低维空间中,并大致保持各点两两之间的距离,即

      其中 0 < ϵ < 1 为可接受的距离误差,嵌入的维度 d 与点集原来的维度无关,而与点集的大小 n = |M|ϵ 有关:

      随机投影

      随机投影(Random Projection)是一种简单但有效的降维(Dimensionality Reduction)方法:

      1. 输入维度为 n×m 的数据集 Mn 为元素数量,m 为原始维度(特征数量)
      2. 构建维度为 m×d 的随机映射矩阵 Rd 为欲降至的维数(d ≪ n
      3. 通过 N = M × R 计算降维矩阵 N,最终维度为 n×d

      维度 d 取决于数据集大小 n,而不是原始的维度 m。在 FastRP 算法中,有 m = n

      不同随机映射算法的区别在于矩阵 R 的构建,FastRP 算法采用 P. Li 等人提出的非常稀疏的随机映射(Very Sparse Random Projection)方法:

      其中 s=sqrt(m)

      算法步骤

      FastRP 算法的步骤如下:

      1. 生成随机映射矩阵 R
      2. 第 1 次迭代:生成降维矩阵 N1 = A ⋅ L ⋅ R
      2. 第 2 次迭代:生成降维矩阵 N2 = A2 ⋅ L ⋅ R = A ⋅ N1
      3. 第 k 次迭代:生成降维矩阵 Nk = A ⋅ Nk-1
      4. 计算最终的嵌入结果,即降维矩阵 N = α1N1 + ... + αkNk,其中 α1,...,αk 为迭代权重

      命令和参数配置

      • 命令:algo(fastRP)
      • params() 参数配置如下:
      名称
      类型
      默认值
      规范
      描述
      dimension int / >=1 节点嵌入向量的维度
      normalizationStrength float / / 归一化强度 β
      iterationWeights []float [0.0,1.0,1.0] >0 每次迭代结果的权重,数组的长度就是算法的迭代轮数
      edge_schema_property []@<schema>?.<property> / 数值类的边属性,需LTE 边权重所在的属性名称,带不带 schema 均可,允许指定多个属性;无该属性的边不参与计算
      node_schema_property []@<schema>?.<property> / 数值类的点属性,需LTE 作为输入特征的点属性,带不带 schema 均可,允许指定多个属性;无该属性的点不参与计算
      propertyDimension int / (0,dimension] 随机映射矩阵 R 由两部分拼接组成:第一部分由非常稀疏的随机映射算法生成,第二部分是由指定的点属性作为权重进行线性组合形成的属性向量(长度为 propertyDimension
      limit int -1 -1 或 >=0 需要返回的结果的条数,-1 表示返回所有结果

      算法执行

      任务回写

      1. 文件回写

      配置项
      各列数据
      filename _id, embedding_result

      2. 属性回写

      算法不支持属性回写。

      3. 统计回写

      算法无统计值。

      直接返回

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

      流式返回

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

      实时统计

      算法无统计值。

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