node2vec and Biased Random Walks

Word2vec turns words into useful numeric vectors by looking at which words tend to sit near each other in sentences. A graph has no sentences — but it does have paths. node2vec's trick is to manufacture sentences by taking random walks across the graph: start at a node, hop to a random neighbor, hop again, and again, recording the sequence of nodes visited as if it were a sentence of "words." Feed enough of these walk-sentences into the same skip-gram model word2vec uses, and nodes that tend to appear near each other in walks end up with similar vectors — a graph embedding, built entirely by borrowing an NLP algorithm.

The analogy: two ways to explore a city

Imagine exploring an unfamiliar city on foot with two very different strategies. One: stick close, wandering the same few blocks over and over, learning every alley of this specific neighborhood in depth. The other: keep pushing outward, block after block, sampling many different neighborhoods but shallowly. Neither is "correct" — it depends what you want to learn. If you want to know "which houses belong to the same tight community," staying local works better. If you want to know "which houses play a similar structural role — corner house, cul-de-sac, main-street house — regardless of which neighborhood they're in," ranging widely works better. node2vec's whole contribution is giving the random walk a dial to choose between these two exploration styles.

The two knobs: $p$ and $q$

A plain DeepWalk takes a uniform random walk — from the current node, jump to any neighbor with equal probability. node2vec instead biases the next step based on where the walk just came from, using two parameters:

• Return parameter $p$: controls how likely the walk is to immediately go back to the node it just left. A high $p$ discourages backtracking, pushing the walk to keep exploring outward (like the "range widely" strategy above).
• In-out parameter $q$: controls how likely the walk is to move to a node farther from where it started versus staying close. A low $q$ encourages venturing outward (DFS-like, structural/role similarity); a high $q$ keeps the walk hugging the local neighborhood (BFS-like, community similarity).

Formally, if the walk just moved from node $t$ to node $v$, and is choosing the next node $x$ among $v$'s neighbors, the unnormalized transition weight is:

$$\pi(v, x) = \begin{cases} 1/p & \text{if } x = t \\ 1 & \text{if } x \text{ is also a neighbor of } t \\ 1/q & \text{if } x \text{ is farther from } t \end{cases}$$

In words: going straight back to where you came from is scaled by $1/p$; staying within the previous node's neighborhood (a "local" move) gets weight $1$; pushing further away from where you started gets scaled by $1/q$. Small $p$ makes backtracking cheap (more local, BFS-flavored); small $q$ makes pushing outward cheap (more exploratory, DFS-flavored).

Worked example 1: computing transition weights by hand

Take a walk that just moved from node $A$ to node $B$, and $B$ has three neighbors: $A$ itself, node $C$ (which is also a neighbor of $A$), and node $D$ (which is not a neighbor of $A$, i.e. farther away). Set $p = 0.5$, $q = 2$. The unnormalized weights are: back to $A$: $1/p = 1/0.5 = 2$; to $C$ (shared neighbor): $1$; to $D$ (farther): $1/q = 1/2 = 0.5$. Total $= 2 + 1 + 0.5 = 3.5$, so the walk returns to $A$ with probability $2/3.5 \approx 0.57$, goes to $C$ with probability $1/3.5 \approx 0.29$, and to $D$ with probability $0.5/3.5 \approx 0.14$. With this $p,q$ pair the walk strongly favors staying local — exactly the BFS-like, community-detecting regime.

Worked example 2: same graph, opposite regime

Same setup, but now $p = 2$, $q = 0.5$: back to $A$ gets $1/2 = 0.5$; to $C$ (shared) gets $1$; to $D$ (farther) gets $1/0.5 = 2$. Total $= 3.5$, so probabilities are $0.14$, $0.29$, $0.57$ respectively — now the walk strongly favors pushing outward to $D$, the farther node. The exact same graph, the exact same starting position, produces an almost mirror-image walk simply by flipping $p$ and $q$ — and the resulting embeddings end up organized around different notions of similarity: community membership in the first case, structural role in the second.

The path behavior above — some paths drifting, some snapping back toward a center — is the same kind of tension node2vec's $p,q$ knobs control on a graph: whether the walk snaps back locally or keeps drifting outward.

What this means in practice

In finance, node2vec-style embeddings are used on networks like supply chains, co-ownership graphs, or lead-lag correlation graphs to produce a numeric vector per company that downstream models (a classifier, a clustering algorithm, a similarity search) can consume directly, without hand-engineering graph features. The $p,q$ choice matters for what the embedding actually captures: tuned for community structure, embeddings will cluster stocks by sector or supply-chain neighborhood; tuned for structural role, they will group companies that play a similar position in their respective networks — say, "hub supplier" — even across unrelated sectors.

Practice

1. Redo worked example 1 with $p = 1, q = 1$ (equivalent to plain DeepWalk) and confirm the three probabilities are equal.
2. Explain in plain English why a low $q$ pushes the walk toward DFS-like, structural-role-capturing behavior.
3. A desk wants embeddings that group companies by tight supply-chain cluster, not by shared structural role. Would they set $q$ high or low, and why?