Source: https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/fastrp/
Documentation version: v5.3.2

# 快速随机投影（FastRP）

本文介绍快速随机投影（Fast Random Projection，FastRP）算法，并演示如何在 GQL 中生成点嵌入向量。

## 算法简介

FastRP 是一种可扩展的图嵌入算法。它将每个点映射为一个稠密向量，结构相似的点通常具有相似向量。

本文中的过程实现逻辑如下：

1. 计算点的度（与该点相连的边数）与全局边数，用于归一化以用于防止超级点的影响力过载。
2. 用基于度的缩放`(deg / m)^beta`初始化点权重。
3. 使用[确定性伪随机生成器](https://zh.wikipedia.org/wiki/%E4%BC%AA%E9%9A%8F%E6%9C%BA%E6%95%B0%E7%94%9F%E6%88%90%E5%99%A8)构造稀疏随机投影向量。
4. 沿无向边迭代传播并归一化嵌入向量。
5. 按迭代深度加权聚合各轮结果，得到最终嵌入向量。

## 数据模型

本文使用如下图模型：

- 使用`fr_node`表示点。
- 使用`fr_edge`表示边。
- 在图类型定义与查询匹配中，边模式均为无向（`~[ ]~`）。

## 过程参数

 | 参数 | 类型 | 说明
 | `iteration_weights` | `LIST<DOUBLE>` | 每个传播深度的权重。列表长度决定迭代轮数。
 | `beta` | `DOUBLE` | 初始点权重中基于度的归一化指数。
 | `embedding_dimension` | `INT64` | 输出嵌入向量维度。
 | `sampling_constant` | `INT64` | 控制随机投影稀疏度。默认值为`3`。
 | `random_seed` | `INT64` | 用于确定性随机投影的种子。默认值为`42`。

## 操作步骤

在悦数图管理的控制台中，按顺序执行以下代码块。首次使用时，先按[准备算法示例数据](https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/prepare-data/)确认操作位置和目录挂载。

### 1. 准备图数据[]()

1. 

创建图类型。

````
'''
CREATE GRAPH TYPE IF NOT EXISTS fastrp_gt AS {
  NODE TYPE fr_node (LABEL fr_node {id INT PRIMARY KEY}),
  EDGE TYPE fr_edge (fr_node)~[LABEL fr_edge {MULTIEDGE KEY()}]~(fr_node)
}
'''

````

2. 

下载以下 CSV 文件，保留文件名，保存到部署目录下的`examples/algorithms/fastrp/`：

  - [fastrp_nodes.csv](https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/files/fastrp/fastrp_nodes.csv)：点数据。
  - [fastrp_edges.csv](https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/files/fastrp/fastrp_edges.csv)：边数据。

查看 CSV 内容

fastrp_nodes.csv

````
id
1
2
3
4
5
6
7
8

````

fastrp_edges.csv

````
src_id,dst_id
1,2
2,3
3,1
3,4
4,5
5,3
2,6
6,7
7,8
8,6
5,7
1,8

````

3. 

创建临时图并导入数据。

````
CREATE TEMPORARY GRAPH IF NOT EXISTS #fastrp_g TYPED fastrp_gt

````

````
'''
USE #fastrp_g IMPORT INTO GRAPH {
  NODE (v@fr_node{id: id}) FROM DATAFILE {
    FORMAT: "csv",
    PATH: "file:///examples/algorithms/fastrp/fastrp_nodes.csv"
  },
  EDGE (id:src_id)~[e@fr_edge{}]~(id:dst_id) FROM DATAFILE {
    FORMAT: "csv",
    PATH: "file:///examples/algorithms/fastrp/fastrp_edges.csv"
  }
}
'''

````

导入成功后，在控制台执行以下查询核对点数：

````
'''
USE #fastrp_g
MATCH (n)
RETURN count(n) AS node_count
'''

````

`node_count`应为`8`。点数不符时，先按[文件问题排查](https://dev-docs.yueshu.com.cn/v5.3.2/analytic/algorithms/prepare-data/#troubleshooting)检查文件和导入结果。

### 2. 创建过程[]()

选择一种输出方式，执行对应页签中的过程定义。后续调用时使用相同方式。

导出至文件导出至表

````
'''
CREATE OR REPLACE PROCEDURE fastRP(
  iteration_weights LIST<DOUBLE>,
  beta DOUBLE,
  embedding_dimension INT64,
  sampling_constant INT64 DEFAULT 3,
  random_seed INT64 DEFAULT 42
) RETURNS () AS {

    NODE VALUE embedding_arr        MapAgg<INT64, SumAgg<DOUBLE>>
    NODE VALUE final_embedding_arr  MapAgg<INT64, SumAgg<DOUBLE>>
    NODE VALUE final_embedding_list ListAgg<DOUBLE>
    NODE VALUE L                    SumAgg<DOUBLE> = 0.0
    NODE VALUE out_degree           SumAgg<INT64> = 0
    VALUE m                         SumAgg<DOUBLE> = 0.0

    // 线性同余生成器 (PRNG) 的常量：r = (r * mult + inc_v) % mod_v。
    // 使用相同的 random_seed 可确保多次运行产生完全一致的投影结果。
    VALUE mod_v INT64 = 2147483647
    VALUE mult INT64  = 1664525
    VALUE inc_v INT64 = 1013904223
    // 用于初始化的稀疏随机投影：
    // - 以 p1 的概率：投影为 +√s (v1)
    // - 以 p2 的概率：投影为 -√s (v2)
    // - 以 (1 - p1 - p2) 的概率：投影为 0 (v3，用于保证稀疏性)
    VALUE p1 DOUBLE = 0.5 / sampling_constant
    VALUE p2 DOUBLE = p1
    VALUE v1 DOUBLE = sqrt(sampling_constant)
    VALUE v2 DOUBLE = -sqrt(sampling_constant)
    VALUE v3 DOUBLE = 0.0

    VALUE depth INT64 = 0
    VALUE max_depth INT64 = size(iteration_weights) - 1

    VALUE verts ACTIVE_SET

    FILE output_file {id INT64, embedding LIST<DOUBLE>} = DATAFILE {
        PATH: "file:///examples/algorithms/fastrp/output",
        FORMAT: "CSV"
    }

    MATCH (s)-[e]-(t)
    PER PATH {
        // 收集点的度与全局边数，用于归一化处理。
        SET s.@out_degree += 1
        SET @m += 1.0
    }
    FINALLY {
        SET verts = s
    }

    MATCH (s)
    WHERE s IN verts
    PER NODE (s) {
        VALUE base_val DOUBLE = s.@out_degree / @m

        // 初始点权重：(deg / m)^beta。
        SET s.@L = power(base_val, beta)
    }

    // 通过将每个源点投影到其邻居点来初始化嵌入向量。
    MATCH (s)-[e]-(t)
    WHERE s IN verts
    PER PATH {
        VALUE act_inc INT64 = s.id + inc_v
        VALUE r INT64 = (act_inc + mult * random_seed) % mod_v
        VALUE mr DOUBLE = 0.0
        VALUE i INT64 = 0

        WHILE i < embedding_dimension THEN {
            SET r = ((r * mult) + act_inc) % mod_v
            SET mr = (r * 1.0) / mod_v

            // 在每个维度上进行稀疏随机投影。
            IF mr <= p1 THEN {
                SET t.@embedding_arr += TUPLE(i, v1 * s.@L)
            } ELSE {
                IF mr <= (p1 + p2) THEN {
                    SET t.@embedding_arr += TUPLE(i, v2 * s.@L)
                } ELSE {
                    SET t.@embedding_arr += TUPLE(i, v3 * s.@L)
                }
            }

            SET i = i + 1
        }
    }

    WHILE depth <= max_depth THEN {
        MATCH (s)-[e]-(t)
        WHERE s IN verts
        PER PATH {
            // 将嵌入向量传播给当前深度的邻居点。
            SET t.@embedding_arr += s.@embedding_arr
        }
        FINALLY {
            SET verts = s
        }

        MATCH (t)
        WHERE t IN verts
        PER NODE (t) {
            VALUE square_sum DOUBLE = 0.0
            VALUE outv DOUBLE = t.@out_degree
            VALUE idx INT64 = 0
            VALUE embedding_list = t.@embedding_arr
            VALUE i INT64 = 0
            VALUE weight DOUBLE = iteration_weights[depth]

            IF outv < 1.0 THEN {
                SET outv = 1.0
            }
            WHILE idx < length(embedding_list) THEN {
                VALUE pair = embedding_list[idx]
                VALUE val DOUBLE = pair._1
                VALUE base_val DOUBLE = val / outv
                SET square_sum = square_sum + (base_val * base_val)
                SET idx = idx + 1
            }
            SET square_sum = sqrt(square_sum)

            IF square_sum > 0.0 THEN {
                WHILE i < embedding_dimension THEN {
                    VALUE current_val DOUBLE = t.@embedding_arr.get(i)
                    VALUE val DOUBLE = current_val / outv / square_sum

                    // 累加当前深度下经过加权和归一化处理的嵌入向量。
                    SET t.@final_embedding_arr += TUPLE(i, val * weight)

                    // 用归一化后的值更新工作中的嵌入向量。
                    SET t.@embedding_arr += TUPLE(i, -current_val)
                    SET t.@embedding_arr += TUPLE(i, val)

                    SET i = i + 1
                }
            }
        } // 结束 PER NODE

        SET depth = depth + 1
    }

    MATCH (s)
    WHERE s IN verts
    PER NODE (s) {
        VALUE i INT64 = 0
        // 对所有深度的结果求平均，生成最终的嵌入向量列表。
        WHILE i < embedding_dimension THEN {
            VALUE avg_val DOUBLE = s.@final_embedding_arr.get(i) / (max_depth + 1)
            SET s.@final_embedding_list += round(avg_val, 5)
            SET i = i + 1
        }
        EXPORT s.id, s.@final_embedding_list INTO output_file
    }
}
'''

````

````
'''
CREATE OR REPLACE PROCEDURE fastRP(
  iteration_weights LIST<DOUBLE>,
  beta DOUBLE,
  embedding_dimension INT64,
  sampling_constant INT64 DEFAULT 3,
  random_seed INT64 DEFAULT 42
) RETURNS (id INT64, embedding LIST<DOUBLE>) AS {
    NODE VALUE embedding_arr        MapAgg<INT64, SumAgg<DOUBLE>>
    NODE VALUE final_embedding_arr  MapAgg<INT64, SumAgg<DOUBLE>>
    NODE VALUE final_embedding_list ListAgg<DOUBLE>
    NODE VALUE L                    SumAgg<DOUBLE> = 0.0
    NODE VALUE out_degree           SumAgg<INT64> = 0
    VALUE m                         SumAgg<DOUBLE> = 0.0

    // 线性同余生成器 (PRNG) 的常量：r = (r * mult + inc_v) % mod_v。
    // 使用相同的 random_seed 可确保多次运行产生完全一致的投影结果。
    VALUE mod_v INT64 = 2147483647
    VALUE mult INT64  = 1664525
    VALUE inc_v INT64 = 1013904223
    // 用于初始化的稀疏随机投影：
    // - 以 p1 的概率：投影为 +√s (v1)
    // - 以 p2 的概率：投影为 -√s (v2)
    // - 以 (1 - p1 - p2) 的概率：投影为 0 (v3，用于保证稀疏性)
    VALUE p1 DOUBLE = 0.5 / sampling_constant
    VALUE p2 DOUBLE = p1
    VALUE v1 DOUBLE = sqrt(sampling_constant)
    VALUE v2 DOUBLE = -sqrt(sampling_constant)
    VALUE v3 DOUBLE = 0.0

    VALUE depth INT64 = 0
    VALUE max_depth INT64 = size(iteration_weights) - 1

    VALUE verts ACTIVE_SET

    // 面向行的输出表。
    TABLE embeddings_table TYPED TABLE {vid INT64, embedding LIST<DOUBLE>}

    MATCH (s)-[e]-(t)
    PER PATH {
        // 收集点的度与全局边数，用于归一化处理。
        SET s.@out_degree += 1
        SET @m += 1.0
    }
    FINALLY {
        SET verts = s
    }

    MATCH (s)
    WHERE s IN verts
    PER NODE (s) {
        VALUE base_val DOUBLE = s.@out_degree / @m

        // 初始点权重：(deg / m)^beta。
        SET s.@L = power(base_val, beta)
    }

    // 通过将每个源点投影到其邻居点来初始化嵌入向量。
    MATCH (s)-[e]-(t)
    WHERE s IN verts
    PER PATH {
        VALUE act_inc INT64 = s.id + inc_v
        VALUE r INT64 = (act_inc + mult * random_seed) % mod_v
        VALUE mr DOUBLE = 0.0
        VALUE i INT64 = 0

        WHILE i < embedding_dimension THEN {
            SET r = ((r * mult) + act_inc) % mod_v
            SET mr = (r * 1.0) / mod_v

            // 在每个维度上进行稀疏随机投影。
            IF mr <= p1 THEN {
                SET t.@embedding_arr += TUPLE(i, v1 * s.@L)
            } ELSE {
                IF mr <= (p1 + p2) THEN {
                    SET t.@embedding_arr += TUPLE(i, v2 * s.@L)
                } ELSE {
                    SET t.@embedding_arr += TUPLE(i, v3 * s.@L)
                }
            }

            SET i = i + 1
        }
    }

    WHILE depth <= max_depth THEN {
        MATCH (s)-[e]-(t)
        WHERE s IN verts
        PER PATH {
            // 将嵌入向量传播给当前深度的邻居点。
            SET t.@embedding_arr += s.@embedding_arr
        }
        FINALLY {
            SET verts = s
        }

        MATCH (t)
        WHERE t IN verts
        PER NODE (t) {
            VALUE square_sum DOUBLE = 0.0
            VALUE outv DOUBLE = t.@out_degree
            VALUE idx INT64 = 0
            VALUE embedding_list = t.@embedding_arr
            VALUE i INT64 = 0
            VALUE weight DOUBLE = iteration_weights[depth]

            IF outv < 1.0 THEN {
                SET outv = 1.0
            }
            WHILE idx < length(embedding_list) THEN {
                VALUE pair = embedding_list[idx]
                VALUE val DOUBLE = pair._1
                VALUE base_val DOUBLE = val / outv
                SET square_sum = square_sum + (base_val * base_val)
                SET idx = idx + 1
            }
            SET square_sum = sqrt(square_sum)

            IF square_sum > 0.0 THEN {
                WHILE i < embedding_dimension THEN {
                    VALUE current_val DOUBLE = t.@embedding_arr.get(i)
                    VALUE val DOUBLE = current_val / outv / square_sum

                    // 累加当前深度下经过加权和归一化处理的嵌入向量。
                    SET t.@final_embedding_arr += TUPLE(i, val * weight)

                    // 用归一化后的值更新工作中的嵌入向量。
                    SET t.@embedding_arr += TUPLE(i, -current_val)
                    SET t.@embedding_arr += TUPLE(i, val)

                    SET i = i + 1
                }
            }
        } // 结束 PER NODE

        SET depth = depth + 1
    }


    MATCH (s)
    WHERE s IN verts
    PER NODE (s) {
        VALUE i INT64 = 0
        // 对所有深度的结果求平均，生成最终的嵌入向量列表。
        WHILE i < embedding_dimension THEN {
            SET s.@final_embedding_list += (s.@final_embedding_arr.get(i) / (max_depth + 1))
            SET i = i + 1
        }
        EXPORT s.id, s.@final_embedding_list INTO embeddings_table
    }

    FOR r IN embeddings_table
    RETURN r.vid AS id, transform(r.embedding, x -> round(x,5))AS embedding
}
'''

````

### 3. 调用过程

以下调用使用`[1.0,0.5,0.25]`作为层权重、`-0.5`作为度归一化指数，生成`4`维嵌入向量。选择与创建过程时相同的输出方式。

导出至文件导出至表

````
'''
USE #fastrp_g
CALL fastRP([1.0,0.5,0.25], -0.5, 4)
FINISH
'''

````

此调用将结果写入 CSV，控制台不返回结果表。 在宿主机的部署目录下，打开`examples/algorithms/fastrp/output/`中的 CSV 文件查看结果。

````
'''
USE #fastrp_g
CALL fastRP([1.0,0.5,0.25], -0.5, 4)
RETURN id, embedding
'''

````

返回：

````
+----+--------------------------------------+
| id | embedding                            |
+----+--------------------------------------+
| 6  | [-0.57722,-0.03564,0.00092,0.06213]  |
| 5  | [-0.56361,-0.01248,0.14596,-0.00529] |
| 3  | [-0.56215,0.01227,0.14946,-0.03554]  |
| 4  | [-0.55761,0.01836,0.16216,-0.04786]  |
| 7  | [-0.57977,-0.00408,-0.01832,0.04049] |
| 8  | [-0.58156,-0.036,0.00091,0.01238]    |
| 1  | [-0.57787,0.00422,0.0773,-0.01049]   |
| 2  | [-0.57428,0.0042,0.0769,-0.05473]    |
+----+--------------------------------------+

````

如果需要稳定且可复现的结果，请保持`random_seed`、图数据和参数组合一致。

`iteration_weights`应为非空列表。在该实现中，传播轮数等于`size(iteration_weights)`。

当前实现通过匹配边初始化工作点集合，因此孤立点（无关联边）不会出现在返回结果中。

将结果写入图中

如果希望将结果持久化到图，而不仅导出到文件，请参见 [EXPORT](https://dev-docs.yueshu.com.cn/v5.3.2/database-gql-reference/in-out/export/)。