Random Walk

Algorithm introduction

Random walk simulates probabilistic traversal paths and summarizes visit distribution across graph nodes.

Compute a single-path walk on a directed graph whose node primary key is id. Starting from source_id, each round selects one outgoing edge, returns the visited trajectory, stops after max_steps rounds, and stops early at sink nodes.

For more information, see Random Walk.

Data model

To implement the Random Walk algorithm in GQL, the following data model is used to create a graph type:

• Entities are represented by nodes of type Node, with properties id and rating.
• Relationships are represented by edges of type Link, with property weight.

For the complete definition of the graph type, see Prepare graph data.

Procedure implementation

To compute Random Walk results, a procedure is created.

For more information about the procedure, see Procedure implementation. The following section describes the key components of the procedure and how it works.

The procedure takes the following input parameters:

• source_id: INT64. ID of the starting node for the walk.
• max_steps: INT64. Maximum number of steps per walk.

Additionally, the following variables are defined within the procedure:

Variable name	Variable type	Description
frontier	Primitive value variable	Active set of walkers in the current step.
step	Primitive value variable	Current walk step counter.
next_id	Primitive value variable	Internal variable used during procedure execution.
next_pick	Global SumAgg aggregator value variable	Internal variable used during procedure execution.
walk_table	Table variable	Output table storing the walk path records.

The following steps outline the logic of the procedure:

1. Initialize each walk starting from its source node; add all starting nodes to frontier.
2. At each step, each walker in the frontier samples one outgoing neighbor using SAMPLE RIGHT.
3. Record the current node and step into walk_table; advance frontier to the sampled neighbors.
4. Stop when step reaches the walk length or no walker can move. Return the complete walk path records.

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 that matches your data model.

   '''
   CREATE GRAPH TYPE IF NOT EXISTS random_walk_graph_type AS {
       NODE Node (LABEL Node {id INT PRIMARY KEY, rating INT}),
       EDGE Link (Node)-[LABEL Link {weight INT, MULTIEDGE KEY()}]->(Node)
   }
   '''
   

2. Download these CSV files and save them with their original names in examples/algorithms/random_walk/ under your deployment directory:

   • random_walk_node.csv: Node data.
   • random_walk_edge.csv: Edge data.
   Preview the CSV files

   random_walk_node.csv

   id,rating
   1,0
   2,2
   3,1
   4,0
   5,0
   6,2
   7,1
   8,2
   9,0
   10,1
   11,0
   12,2
   13,1
   14,1
   15,0
   16,2
   17,0
   18,1
   19,2
   20,0
   21,2
   22,1
   23,0
   24,1
   

   random_walk_edge.csv

   src_id,dst_id,weight
   1,2,4
   1,3,2
   1,4,7
   1,5,9
   2,3,1
   2,4,6
   2,5,5
   2,6,2
   3,4,3
   3,5,4
   3,6,8
   4,6,2
   4,7,6
   4,8,5
   5,6,4
   5,8,7
   5,9,6
   6,8,1
   6,9,5
   6,10,6
   7,9,2
   7,10,9
   8,9,3
   8,11,6
   8,12,4
   9,10,4
   9,12,7
   9,13,2
   10,12,1
   10,13,8
   10,14,4
   11,12,2
   11,14,5
   11,15,7
   12,14,3
   12,15,6
   12,16,5
   13,15,2
   13,16,7
   14,15,4
   14,17,8
   14,18,2
   15,16,1
   15,18,5
   15,19,3
   16,18,3
   16,19,6
   17,18,2
   17,20,7
   17,21,5
   18,19,4
   18,21,9
   18,22,6
   19,21,1
   19,22,5
   20,21,3
   20,23,6
   20,24,8
   21,22,2
   21,23,4
   21,24,7
   22,24,4
   23,24,1
   

3. Create a temporary graph based on the graph type and load the data files into the temporary graph.

   CREATE TEMPORARY GRAPH IF NOT EXISTS #random_walk_graph TYPED random_walk_graph_type
   

   '''
   USE #random_walk_graph IMPORT INTO GRAPH {
         NODE (v@Node {id: id, rating: rating}) FROM DATAFILE {
             PATH: "file:///examples/algorithms/random_walk/random_walk_node.csv",
             FORMAT: "CSV",
             DELIMITER: ','
         },
         EDGE (id: src_id)-[e@Link {weight: weight}]->(id: dst_id) FROM DATAFILE {
             PATH: "file:///examples/algorithms/random_walk/random_walk_edge.csv",
             FORMAT: "CSV",
             DELIMITER: ','
         }
     }
   '''
   

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

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

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

2. Create a procedure

Create a procedure to implement the Random Walk algorithm. For more information about the procedure, see Procedure implementation.

'''
CREATE OR REPLACE PROCEDURE random_walk(
  source_id INT64,
  max_steps INT64
)
RETURNS (step_no INT64, node_id INT64)
COMMENT "Compute a single-path walk on a directed graph whose vertex primary key is id. Starting from source_id, each round selects one outgoing edge, returns the visited trajectory, stops after max_steps rounds, and stops early at sink vertices."
AS {
  VALUE frontier ACTIVE_SET

  VALUE step INT64 = 0
  VALUE next_id INT64 = 0
  VALUE next_pick TopKAgg<1, node_id INT64 ASC>

  TABLE walk_table TYPED TABLE {
    step_no INT64,
    node_id INT64
  }

  MATCH (s)
  WHERE s.id = source_id
  PER NODE (s) {
    EXPORT 0, s.id INTO walk_table
  }
  FINALLY {
    SET frontier = s
  }

  WHILE step < max_steps THEN {
    SET @next_pick.clear()

    MATCH (s)-[e]->(t)
    WHERE s IN frontier
    PER PATH {
      SET @next_pick += RECORD{node_id: t.id}
    }

    IF @next_pick.size() = 0 THEN {
      BREAK
    }

    SET next_id = @next_pick.min().node_id

    MATCH (t)
    WHERE t.id = next_id
    PER NODE (t) {
      EXPORT step + 1, t.id INTO walk_table
    }
    FINALLY {
      SET frontier = t
    }

    SET step = step + 1
  }

  FOR r IN walk_table
  RETURN r.step_no AS step_no, r.node_id AS node_id
  ORDER BY step_no ASC
}
'''

3. Call your procedure

Start a random walk at node 1 for at most 8 steps and return the node ID visited at each step.

USE #random_walk_graph CALL random_walk(1, 8) RETURN step_no, node_id

Returns:

Expand to view results

+---------+---------+
| step_no | node_id |
+---------+---------+
| 0       | 1       |
| 1       | 2       |
| 2       | 3       |
| 3       | 4       |
| 4       | 6       |
| 5       | 8       |
| 6       | 9       |
| 7       | 10      |
| 8       | 12      |
+---------+---------+

Note

Because Random Walk samples outgoing edges randomly, the returned walk trace can differ from one execution to another.

Save results to a file or graph

To save the returned results as CSV files or write them to a graph, see EXPORT. Match the exported fields to the returned columns and target properties.