DeepWalk and Node2Vec

Why Does This Exist?

In the early 2010s, natural language processing experienced a revolution when Word2Vec revealed that dense word representations could be learned efficiently by sliding context windows over text sentences. Graph practitioners wanted similar continuous embeddings for network nodes, but graphs lack a natural sequential ordering: there is no single "beginning", "middle", or "end" to a graph topology.

Computing global pairwise distances across millions of nodes using matrix factorization algorithms (like spectral decomposition of the Laplacian) incurs an intractable $\mathcal{O}(|V|^3)$ or $\mathcal{O}(|V|^2)$ computational cost and collapses when graph edges evolve. DeepWalk (Perozzi et al., 2014) solved this by realizing that truncated random walks on a network exhibit the exact same power-law frequency distribution as words in natural language corpora. Node2Vec (Grover & Leskovec, 2016) generalized DeepWalk by introducing parameterized, second-order random walks that allow practitioners to interpolate smoothly between local community clustering (homophily) and structural network roles (such as hubs or bridges).

Think of It Like This

How It Actually Works

2nd-Order Biased Walks and Skip-Gram Objective

Node2Vec defines a flexible neighborhood $\mathcal{N}_S(u)$ for every node $u$ by simulating second-order random walks. Suppose a walk just traversed edge $(t, v)$ and is currently positioned at node $v$. The probability of taking the next step to a neighbor $x \in \mathcal{N}(v)$ is:

$P(c_i = x \mid c_{i-1} = v, c_{i-2} = t) = \frac{\pi_{vx}}{\sum_{y \in \mathcal{N}(v)} \pi_{vy}}$

The unnormalized transition probability $\pi_{vx}$ is the product of the edge weight $w_{vx}$ and a search bias $\alpha_{pq}(t, x)$:

$\pi_{vx} = \alpha_{pq}(t, x) \cdot w_{vx}$

The search bias $\alpha_{pq}(t, x)$ depends on the shortest-path distance $d_{tx} \in \{0, 1, 2\}$ between the previous node $t$ and candidate neighbor $x$:

$\alpha_{pq}(t, x) = \begin{cases} \frac{1}{p} & \text{if } d_{tx} = 0 \quad (\text{return to previous node } t) \\ 1 & \text{if } d_{tx} = 1 \quad (\text{visit mutual neighbor of } t \text{ and } v) \\ \frac{1}{q} & \text{if } d_{tx} = 2 \quad (\text{explore outward to unseen node}) \end{cases}$

• Return parameter $p$: High $p$ ($> 1$) discourages revisiting recent nodes, reducing 2-hop redundancy. Low $p$ ($< 1$) forces the walk to stay local, emulating Breadth-First Search (BFS) to capture homophily (nodes in the same community get similar embeddings).
• In-out parameter $q$: Low $q$ ($< 1$) encourages the walk to venture outward, emulating Depth-First Search (DFS) to capture structural equivalence (nodes serving identical topological roles, like hubs or peripheral leaves, get similar embeddings regardless of distance).
• DeepWalk Equivalence: Setting $p = 1.0$ and $q = 1.0$ recovers the uniform random walk of DeepWalk.

Once a corpus of random walks $\mathcal{W}$ is generated, the embeddings are optimized using the Skip-Gram architecture with Negative Sampling:

$\max_f \sum_{u \in V} \sum_{c \in \mathcal{N}_S(u)} \left[ \log \sigma(\mathbf{z}_c^\top \mathbf{z}_u) + \sum_{k=1}^K \mathbb{E}_{n_k \sim P_n(V)} \left[ \log \sigma(-\mathbf{z}_{n_k}^\top \mathbf{z}_u) \right] \right]$

where $\mathbf{z}_u \in \mathbb{R}^d$ is the center representation of node $u$, $\mathbf{z}_c \in \mathbb{R}^d$ is the context representation of neighbor $c$, $\sigma(x) = \frac{1}{1 + e^{-x}}$, and $K$ is the number of negative samples drawn from noise distribution $P_n(V) \propto (\text{deg}(v))^{3/4}$.

Worked Example

Let a walk transition from $t$ to $v$. The neighbors of $v$ are $\{t, a, b\}$:

• $t$: distance $d_{tx} = 0$.
• $a$: edge $(t, a)$ exists in the graph, so distance $d_{ta} = 1$.
• $b$: no edge between $t$ and $b$, so distance $d_{tb} = 2$.

Assume unweighted edges ($w = 1.0$), return parameter $p = 0.5$, and in-out parameter $q = 2.0$:

1. Calculate unnormalized biases $\alpha_{pq}(t, x)$: $\alpha(t, t) = \frac{1}{p} = \frac{1}{0.5} = 2.0$ $\alpha(t, a) = 1.0$ $\alpha(t, b) = \frac{1}{q} = \frac{1}{2.0} = 0.5$

2. Compute normalization denominator $Z$: $Z = \pi_{vt} + \pi_{va} + \pi_{vb} = 2.0 + 1.0 + 0.5 = 3.5$

3. Compute exact transition probabilities: $P(t \mid v, t) = \frac{2.0}{3.5} \approx 0.5714 \quad (57.1\%)$ $P(a \mid v, t) = \frac{1.0}{3.5} \approx 0.2857 \quad (28.6\%)$ $P(b \mid v, t) = \frac{0.5}{3.5} \approx 0.1429 \quad (14.3\%)$

Because $p < 1$ and $q > 1$, the walker is $4\times$ more likely to double back to $t$ than to step out toward distant node $b$, heavily favoring local community clustering.

Code

1import random2from typing import Dict, List3
4
5def sample_node2vec_step(6    prev_node: int,7    curr_node: int,8    adjacency: Dict[int, List[int]],9    p: float,10    q: float,11) -> int:12    """Sample next node in 2nd-order biased random walk given (prev_node, curr_node)."""13    neighbors = adjacency[curr_node]14    prev_neighbors = set(adjacency[prev_node])15
16    weights: List[float] = []17    for nbr in neighbors:18        if nbr == prev_node:19            # d(prev, nbr) == 020            weights.append(1.0 / p)21        elif nbr in prev_neighbors:22            # d(prev, nbr) == 1 (mutual neighbor)23            weights.append(1.0)24        else:25            # d(prev, nbr) == 2 (outward step)26            weights.append(1.0 / q)27
28    # Weighted random sampling29    chosen: int = random.choices(neighbors, weights=weights, k=1)[0]30    return chosen31
32
33# Test with graph: 0-1, 1-2 (with edge 0-2), 1-3 (no edge 0-3)34adj: Dict[int, List[int]] = {35    0: [1, 2],36    1: [0, 2, 3],37    2: [0, 1],38    3: [1],39}40
41# Fix seed for reproducible check42random.seed(42)43counts: Dict[int, int] = {0: 0, 2: 0, 3: 0}44for _ in range(10_000):45    nxt = sample_node2vec_step(prev_node=0, curr_node=1, adjacency=adj, p=0.5, q=2.0)46    counts[nxt] += 147
48# Node 0 (return) ~57%, Node 2 (mutual) ~28%, Node 3 (outward) ~14%49print(f"Empirical distribution: 0: {counts[0]/10000:.3f}, 2: {counts[2]/10000:.3f}, 3: {counts[3]/10000:.3f}")50# -> Empirical distribution: 0: 0.573, 2: 0.285, 3: 0.142

Watch Out For

The Quick Version

• DeepWalk transforms graphs into text sequences by generating uniform random walks, applying Skip-Gram with Negative Sampling to learn continuous node vectors.
• Node2Vec introduces second-order walk biases controlled by two hyperparameters: return parameter $p$ and exploration parameter $q$.
• Setting $p < 1$ prioritizes Breadth-First Search (BFS) to preserve local community homophily, while $q < 1$ prioritizes Depth-First Search (DFS) to learn structural network roles.

What to Read Next

• Message Passing Neural Networks
• Advanced Graph Architectures
• Loss Functions