修改密码

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

修改昵称

当前昵称:
提交

??certificate-table.title_zh_CN??

??certificate-table.name_zh_CN?? ??certificate-table.issued-at_zh_CN?? ??certificate-table.valid-until_zh_CN?? ??certificate-table.serial_zh_CN?? ??certificate-table.actions_zh_CN??
??certificate-table.serial_zh_CN?? ??certificate-table.valid-until_zh_CN?? ??certificate-table.actions_zh_CN??

??certificate-table.no-data.p1_zh_CN?? ??certificate-table.no-data.p2_zh_CN??

??invoice-table.title_zh_CN??

??invoice-table.name_zh_CN?? ??invoice-table.create-time_zh_CN?? ??invoice-table.id_zh_CN?? ??invoice-table.price_zh_CN?? ??invoice-table.actions_zh_CN??
??invoice-table.name_zh_CN?? ??invoice-table.create-time_zh_CN?? ??invoice-table.id_zh_CN?? ??invoice-table.price_zh_CN?? ??invoice-table.actions_zh_CN??
v4.3
搜索
    中文EN
    v4.3

      快速随机投影

      概述

      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

      实时统计

      算法无统计值。

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