快速随机投影（FastRP）

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

算法简介

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

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

1. 计算点的度（与该点相连的边数）与全局边数，用于归一化以用于防止超级点的影响力过载。
2. 用基于度的缩放(deg / m)^beta初始化点权重。
3. 使用确定性伪随机生成器构造稀疏随机投影向量。
4. 沿无向边迭代传播并归一化嵌入向量。
5. 按迭代深度加权聚合各轮结果，得到最终嵌入向量。

数据模型

本文使用如下图模型：

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

过程参数

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

操作步骤

在悦数图管理的控制台中，按顺序执行以下代码块。首次使用时，先按准备算法示例数据确认操作位置和目录挂载。

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：点数据。
   • 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。点数不符时，先按文件问题排查检查文件和导入结果。

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。