FastRP

Overview

FastRP (Fast Random Projection) is a scalable and efficient algorithm for learning node representations in a graph. It computes node embeddings iteratively through two main steps: first, constructing a node similarity matrix; second, reducing dimension using random projection.

FastRP was proposed by H. Chen et al. in 2019:

• H. Chen, S.F. Sultan, Y. Tian, M. Chen, S. Skiena, Fast and Accurate Network Embeddings via Very Sparse Random Projection (2019)

Concepts

Very Sparse Random Projection

Random projection is a dimension reduction method that approximately preserves pairwise distances between data points when embedding them from a high-dimensional space to a lower-dimensional space. Its theoretical foundation is primarily based on the Johnson-Lindenstrauss Lemma.

The idea behind random projection is very simple: to reduce a matrix Mn×m (n = m for graph data) to a lower-dimensional matrix Nn×d where d ≪ n, we multiply M by a random projection matrix Rm×d, i.e., N = M ⋅ R.

The matrix R is generated by independently sampling its entries from a random distribution. Specifically, FastRP uses very sparse random projection for dimension reduction, where each entry of R is sampled from the following distribution:

This implementation uses s = 3 (a standard choice from Achlioptas, 2003), giving 2/3 zero entries regardless of graph size.

FastRP Process

This implementation uses a simplified version of FastRP:

1. Initialize: Assign each node a random embedding vector of size dimensions from the matrix R.
2. Iterations: In each iteration, update each node's embedding with the degree-normalized sum of its neighbors' embeddings. The weight for each neighbor is (1/√deg(node)) × (1/√deg(neighbor)). L2-normalize all embeddings after each iteration.

The final embeddings capture higher-order neighborhood structure. More iterations incorporate information from farther neighbors.

Consider this graph with dimensions = 3, and iterations = 3.

Initialize: Each node gets a random vector from R:

Iteration 1: Replace each node's embedding with the degree-normalized sum of its neighbors' embeddings.

• A (deg 2, neighbors B, C):
  • w(B) = 1/√2 × 1/√2 = 0.5, w(C) = 1/√2 × 1/√3 = 0.408
  • New A = 0.5 × [-√3, √3, 0] + 0.408 × [0, -√3, √3] = [-0.866, 0.159, 0.707]
• B (deg 2, neighbors A, C):
  • w(A) = 1/√2 × 1/√2 = 0.5, w(C) = 1/√2 × 1/√3 = 0.408
  • New B = 0.5 × [√3, 0, -√3] + 0.408 × [0, -√3, √3] = [0.866, -0.707, -0.159]
• C (deg 3, neighbors A, B, D):
  • w(A) = w(B) = w(D) = 1/√3 × 1/√2 = 0.408
  • New C = 0.408 × ([√3, 0, -√3] + [-√3, √3, 0] + [√3, √3, 0]) = 0.408 × [√3, 2√3, -√3] = [0.707, 1.414, -0.707]
• D (deg 2, neighbors C, E):
  • w(C) = 1/√2 × 1/√3 = 0.408, w(E) = 1/√2 × 1/√1 = 0.707
  • New D = 0.408 × [0, -√3, √3] + 0.707 × [-√3, 0, √3] = [-1.225, -0.707, 1.932]
• E (deg 1, neighbor D):
  • w(D) = 1/√1 × 1/√2 = 0.707
  • New E = 0.707 × [√3, √3, 0] = [1.225, 1.225, 0]

L2-normalize each embedding:

Iteration 2: Aggregate using iteration 1's normalized embeddings, then L2-normalize.

Iteration 3: Aggregate using iteration 2's normalized embeddings, then L2-normalize.

The final embeddings after 3 iterations capture higher-order neighborhood structure. For example, D and E (connected by a direct edge at the graph's periphery) have similar embeddings, while C (the hub connecting the triangle to the tail) has a distinct representation.

Considerations

• The FastRP algorithm treats all edges as undirected, ignoring their original direction.

Example Graph

GQL
INSERT (A:default {_id: "A"}), (B:default {_id: "B"}),
       (C:default {_id: "C"}), (D:default {_id: "D"}),
       (E:default {_id: "E"}), (F:default {_id: "F"}),
       (G:default {_id: "G"}), (H:default {_id: "H"}),
       (I:default {_id: "I"}), (J:default {_id: "J"}),
       (A)-[:default]->(B), (A)-[:default]->(C),
       (C)-[:default]->(D), (D)-[:default]->(F),
       (E)-[:default]->(C), (E)-[:default]->(F),
       (F)-[:default]->(G), (G)-[:default]->(J),
       (H)-[:default]->(G), (H)-[:default]->(I)

Parameters

Run Mode

Returns:

GQL
CALL algo.fastrp({
  dimensions: 4,
  iterations: 3
}) YIELD nodeId, embedding

Result:

Stream Mode

Returns the same columns as run mode, streamed for memory efficiency.

GQL
CALL algo.fastrp.stream({
  dimensions: 4,
  iterations: 5
}) YIELD nodeId, embedding
RETURN nodeId, embedding

Result:

Stats Mode

Returns:

GQL
CALL algo.fastrp.stats({
  dimensions: 4
}) YIELD nodeCount, dimensions

Result:

Write Mode

Computes results and writes them back to node properties. The write configuration is passed as a second argument map.

Write parameters:

Writable columns:

Returns:

GQL
CALL algo.fastrp.write({dimensions: 4}, {
  db: {
    property: "embedding"
  }
}) YIELD task_id, nodesWritten, computeTimeMs, writeTimeMs