概述

FastRP（Fast Random Projection，快速随机投影）算法是一种比传统的随机游走方式更快、更有效的图嵌入方法，它通过迭代计算节点嵌入，避免了显式地构造相似性矩阵而带来的时间损耗。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)
• P. Li, T.J. Hastie, K.W. Church, Very Sparse Random Projections (2006)
• D. Achlioptas, Database-friendly random projections: Johnson-Lindenstrauss with binary coins (2002)

工作框架

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

构造节点相似性矩阵

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

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

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

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

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

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

由此构造一个归一化对角矩阵 L，元素 L_ij = (d_j/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 的数据集 M，n 为元素数量，m 为原始维度（特征数量）
2. 构建维度为 m×d 的随机映射矩阵 R，d 为欲降至的维数（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 次迭代：生成降维矩阵 N₁ = A ⋅ L ⋅ R
2. 第 2 次迭代：生成降维矩阵 N₂ = A² ⋅ L ⋅ R = A ⋅ N₁
3. 第 k 次迭代：生成降维矩阵 N_k = A ⋅ N_k-1
4. 计算最终的嵌入结果，即降维矩阵 N = α₁N₁ + ... + α_kN_k，其中 α₁,...,α_k 为迭代权重

命令和参数配置

• 命令：algo(fastRP)
• params() 参数配置如下：

算法执行

任务回写

1. 文件回写

2. 属性回写

算法不支持属性回写。

3. 统计回写

算法无统计值。

直接返回

流式返回

实时统计

算法无统计值。