Source: https://dev-docs.nebula-graph.io/v5.3.2/analytic/algorithms/fastrp/
Documentation version: v5.3.2

# 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](https://en.wikipedia.org/wiki/Pseudorandom_number_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](https://dev-docs.nebula-graph.io/v5.3.2/analytic/algorithms/prepare-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](https://dev-docs.nebula-graph.io/v5.3.2/analytic/algorithms/files/fastrp/fastrp_nodes.csv): Node data.
  - [fastrp_edges.csv](https://dev-docs.nebula-graph.io/v5.3.2/analytic/algorithms/files/fastrp/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](https://dev-docs.nebula-graph.io/v5.3.2/analytic/algorithms/prepare-data/#troubleshooting) 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](https://dev-docs.nebula-graph.io/v5.3.2/database-gql-reference/in-out/export/).