Random walk

As explained in Graph Neural Networks in Action

A random walk is a stochastic traversal of a graph that repeatedly moves from a node to one of its connected neighbors according to transition probabilities.

A random walk explores a graph by moving from a node to a connected neighbor, then repeating the move. Running many walks from each node produces sequences of visited nodes. Methods such as Node2Vec use those sequences to capture neighborhood context as node embeddings: vectors that can support visualization and machine-learning tasks. section 2.1 section 2.4.3

Proximity as a chance of encounter

Suppose node B cannot be reached from node A in one hop. Its one-hop encounter probability is zero. Under an example’s assumptions of equally likely directions and no repeated nodes, one of three possible two-hop routes reaches B, giving a two-hop probability of 1/3. This is one way to express graph proximity. Embedding walks need not use the no-repeats assumption: they may backtrack or visit a node again. section 2.4.1 section 2.4.3

Two embedding approaches choose walks differently:

• DeepWalk runs several fixed-size walks per node, treating connected neighbors as equally likely at each step. section 2.4.3
• Node2Vec biases walks with p, which controls returning to the previous node, and q, which steers exploration toward nearby or farther nodes. section 2.4.3

Figure 2.13 Depth-first search (DFS) and breadth first search (BFS) on a graph where embeddings are generated based on random walks using these graph-traversal strategies. DFS (light arrows) prioritizes going deep down one path, while BFS (dark arrows) prioritizes checking all adjacent and nearby paths.

Compare breadth-first exploration of nearby paths with depth-first exploration along a path to see the neighborhood-versus-distance choice behind Node2Vec’s walk bias. section 2.4.3

In a graph of political books, nodes represent books and edges represent frequent co-purchases. A practical workflow sets walk length and walks per node in the Node2Vec Python library, generates embeddings, then projects them with UMAP for inspection. For supervised learning, align each embedding with its node label before training: independently generated walks do not guarantee that embedding order matches the graph’s node order. Node2Vec is suited to a fixed graph; its embeddings do not generalize to unseen data or graphs. section 2.1 section 2.3.1 section 2.5

How Graph Neural Networks in Action covers it

How deep it goes

Explains encounter probability and DeepWalk versus Node2Vec walk choices without deriving transition probabilities.

Examples

Illustrates walks with a two-hop encounter calculation and embeddings of frequently co-purchased political books.

What it assumes

Introduces nodes, edges, hops, and traversal probability through graph examples before comparing walk-based methods.

What you can do after

Apply it via the Node2Vec Python library to generate embeddings for visualization or machine-learning features.

How it connects

Links walks to node embeddings, DeepWalk, Node2Vec, breadth-first search, and depth-first search.

liveBookmanning.com

Read Graph Neural Networks in Action on liveBook Get the book at manning.com

Also explained in

• 

  liveBookmanning.com
  Investing for ProgrammersA random walk is a stochastic process whose successive movements are determined by random variation rather than a predictable directional pattern.
• 

  liveBookmanning.com
  Graph Algorithms for Data ScienceA random walk is a stochastic graph traversal that repeatedly moves from the current node to a neighboring node according to transition probabilities.

Compare how 3 books explain random walk →

Related concepts

• Node2Vecused by · Node2Vec is a graph representation-learning algorithm that learns node embeddings from biased random walks and their context relationships.
• corpusproduces · A corpus is an organized collection of documents, texts, or other language data assembled for processing, retrieval, analysis, training, or evaluation.
• encoder-decoder architectureimplements · An encoder-decoder architecture is a model design in which an encoder transforms input into an intermediate representation and a decoder uses that representation to produce output.
• second-order biased random walkincludes · A second-order biased random walk chooses its next node using both the current node and the node visited immediately before it.

This explainer was generated by Manning's knowledge graph from the text of Graph Neural Networks in Action. The section links point to the parts of the book it draws on.