概述

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

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

• H. Chen, S.F. Sultan, Y. Tian, M. Chen, S. Skiena, Fast and Accurate Network Embeddings via Very Sparse Random Projection (2019)

FastRP工作框架

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

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

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

非常稀疏的随机投影

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

随机投影背后的思想非常简单：要将矩阵M_n×m（对于图数据，有n = m）降维成矩阵N_n×d（d ≪ n），可以简单地将M乘以一个随机投影矩阵R_m×d，即N = M ⋅ R。

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

其中s=sqrt(m)。

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

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

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

构造节点相似性矩阵

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

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

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

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

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

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

算法步骤

FastRP算法的步骤如下：

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

特殊说明

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

语法

• 命令：algo(fastRP)
• 参数：

示例

文件回写

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'
  }
})

属性回写

algo(fastRP).params({
  dimension : 10,
  normalizationStrength: 1.5,
  iterationWeights: [0, 0.8, 0.2, 1],
  edge_schema_property: ['w1', 'w2']
}).write({
  db:{
    property: 'embedding'
  }
})

直接返回

algo(fastRP).params({
  dimension : 10,
  normalizationStrength: 1.5,
  iterationWeights: [0, 0.8, 0.2, 1]
}) as embeddings
return embeddings

流式返回

algo(fastRP).params({
  dimension : 10,
  normalizationStrength: 1.5,
  iterationWeights: [0, 0.8, 0.2, 1]
}).stream() as embeddings
return embeddings