FastRP

Algorithm introduction

FastRP (Fast Random Projection) is a scalable graph embedding algorithm. It maps each node to a dense vector, and structurally similar nodes tend to have similar vectors.

The procedure works as follows:

1. Compute node degree (the total number of edges connected to the node) and global edge count for normalization to prevent influence overload of supernodes.
2. Initialize node weight with degree-based scaling (deg / m)^beta.
3. Generate sparse random projection vectors with a deterministic pseudo-random generator.
4. Propagate and normalize embeddings iteratively along undirected edges.
5. Aggregate weighted embeddings from each iteration depth into final embeddings.

Data model

The following data model is used:

• Nodes are represented by fr_node.
• Edges are represented by fr_edge.
• The edge pattern is undirected (~[ ]~) in both graph type definition and query matching.

Procedure parameters

Parameter	Type	Description
iteration_weights	LIST<DOUBLE>	Weight of each propagation depth. Its length determines the number of iterations.
beta	DOUBLE	Degree-based normalization exponent for initial node weight.
embedding_dimension	INT64	Output embedding dimension.
sampling_constant	INT64	Controls sparsity of random projection. Default is 3.
random_seed	INT64	Seed for deterministic random projection. Default is 42.

Steps

Run the following code blocks in order in the NebulaGraph Studio CONSOLE. For first-time setup, follow Prepare algorithm sample data to check where to run commands and how the directory is mounted.

1. Prepare graph data

1. Create a graph type.

   '''
   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. Download these CSV files and save them with their original names in examples/algorithms/fastrp/ under your deployment directory:

   • fastrp_nodes.csv: Node data.
   • fastrp_edges.csv: Edge data.
   Preview the CSV files

   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 a temporary graph and import data.

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

   After the import succeeds, run this query in the console to check the node count:

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

   The expected node_count is 8. If it differs, check the files and import results before continuing.

2. Create a procedure

Choose an output option and run the procedure definition in that tab. Use the same option when calling it.

Export to fileExport to table

'''
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 constants for a linear congruential generator: r = (r * mult + inc_v) % mod_v.
    // Using the same random_seed yields identical projections across runs.
    VALUE mod_v INT64 = 2147483647
    VALUE mult INT64  = 1664525
    VALUE inc_v INT64 = 1013904223
    // Sparse random projection for initialization:
    // - With prob p1: project to +√s (v1)
    // - With prob p2: project to -√s (v2)
    // - With prob (1 - p1 - p2): project to 0 (v3, for sparsity)
    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 {
        // Collect degree and edge count for normalization.
        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

        // Initial node strength: (deg / m)^beta.
        SET s.@L = power(base_val, beta)
    }

    // Initialize embeddings by projecting each source node into its neighbors.
    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

            // Sparse random projection per dimension.
            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 {
            // Propagate embeddings to neighbors at current depth.
            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

                    // Accumulate weighted, normalized embedding for this depth.
                    SET t.@final_embedding_arr += TUPLE(i, val * weight)

                    // Update working embedding with normalized values.
                    SET t.@embedding_arr += TUPLE(i, -current_val)
                    SET t.@embedding_arr += TUPLE(i, val)

                    SET i = i + 1
                }
            }
        } // END PER NODE

        SET depth = depth + 1
    }

    MATCH (s)
    WHERE s IN verts
    PER NODE (s) {
        VALUE i INT64 = 0
        // Average over depths into a final embedding list.
        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 constants for a linear congruential generator: r = (r * mult + inc_v) % mod_v.
    // Using the same random_seed yields identical projections across runs.
    VALUE mod_v INT64 = 2147483647
    VALUE mult INT64  = 1664525
    VALUE inc_v INT64 = 1013904223
    // Sparse random projection for initialization:
    // - With prob p1: project to +√s (v1)
    // - With prob p2: project to -√s (v2)
    // - With prob (1 - p1 - p2): project to 0 (v3, for sparsity)
    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

    // Row-oriented output table.
    TABLE embeddings_table TYPED TABLE {vid INT64, embedding LIST<DOUBLE>}

    MATCH (s)-[e]-(t)
    PER PATH {
        // Collect degree and edge count for normalization.
        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

        // Initial node strength: (deg / m)^beta.
        SET s.@L = power(base_val, beta)
    }

    // Initialize embeddings by projecting each source node into its neighbors.
    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

            // Sparse random projection per dimension.
            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 {
            // Propagate embeddings to neighbors at current depth.
            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

                    // Accumulate weighted, normalized embedding for this depth.
                    SET t.@final_embedding_arr += TUPLE(i, val * weight)

                    // Update working embedding with normalized values.
                    SET t.@embedding_arr += TUPLE(i, -current_val)
                    SET t.@embedding_arr += TUPLE(i, val)

                    SET i = i + 1
                }
            }
        } // END PER NODE

        SET depth = depth + 1
    }


    MATCH (s)
    WHERE s IN verts
    PER NODE (s) {
        VALUE i INT64 = 0
        // Average over depths into a final embedding list.
        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. Call the procedure

The following calls use layer weights [1.0,0.5,0.25] and degree normalization exponent -0.5 to generate 4-dimensional embeddings. Select the same output option used when creating the procedure.

Export to fileExport to table

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

This call writes the results to CSV files and does not return a table in the console.

On the Docker host, open the CSV files in examples/algorithms/fastrp/output/ under your deployment directory to view the results.

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

Return:

+----+--------------------------------------+
| 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]    |
+----+--------------------------------------+

If you need stable and reproducible results, keep the same random_seed, graph data, and parameter set.

iteration_weights should be a non-empty list. In this procedure, the number of propagation rounds is size(iteration_weights).

The current implementation initializes the working node set from matched edges, so isolated nodes (with no incident edges) are not returned.

Write results to a graph

If you want to persist the results in a graph instead of only exporting to files, see EXPORT.