DeepWalk, in depth: truncated random walks, skip-gram with hierarchical softmax, the matrix it implicitly factorises, and evaluation that does not leak

Why a random walk is a sentence

Word2vec works because word frequencies in natural text follow a power law and because words that share contexts share meaning. The DeepWalk paper's motivating observation is that the frequency with which vertices appear in short random walks on a scale-free graph also follows a power law, so the statistical shape of the corpus is the one skip-gram was built for.

There is a simple reason. A random walk on a connected, non-bipartite undirected graph has a stationary distribution proportional to degree: vertex v is visited with probability deg(v) / 2m in the long run. If the degree distribution is heavy-tailed, so is the visit distribution. In our test graph, with ten 40-step walks per vertex, the correlation between a vertex's visit count and its degree was 0.98. That has a practical consequence you will meet again: hubs dominate the corpus, and low-degree vertices receive few training updates.

The second ingredient is the distributional hypothesis transplanted to graphs. Two vertices that are reachable from each other in a few steps, or that share many short-path neighbours, co-occur within a window often. Skip-gram pushes their vectors together. What counts as a context is set by the window w and the walk length t; that is the whole inductive bias.

The pipeline

The paper's experiments used gamma = 80 walks per vertex, walk length t = 40, window w = 10 and d = 128 dimensions. Every stage is embarrassingly parallel except the optimiser, which word2vec implementations run as lock-free asynchronous SGD across threads. The pipeline also streams: walks can be generated and consumed without ever materialising the full corpus, which is how DeepWalk scaled to graphs with millions of vertices in 2014.

Generating the walk corpus

Walk generation is uniform: at each step pick a neighbour of the current vertex uniformly at random. The outer loop shuffles the vertex order each pass, as the paper does, so SGD does not see all walks from one region consecutively.

import random

def deepwalk_corpus(adj, gamma=80, t=40, seed=0):
    # adj: dict vertex -> list of neighbours (undirected, no isolated vertices)
    rng = random.Random(seed)
    nodes = list(adj)
    for _ in range(gamma):
        rng.shuffle(nodes)
        for start in nodes:
            walk = [start]
            while len(walk) < t:
                nbrs = adj[walk[-1]]
                if not nbrs:          # dead end in a directed graph: stop early
                    break
                walk.append(rng.choice(nbrs))
            yield [str(v) for v in walk]   # word2vec tools expect string tokens

The corpus size is n x gamma x t tokens: a million-vertex graph at the paper's settings yields 3.2 billion tokens. The generator yields walks, but gensim reads the corpus twice (vocabulary, then training), so pass a list or a restartable iterable that regenerates walks per pass. Weighted graphs replace rng.choice with sampling proportional to edge weight; precompute cumulative weights per vertex and binary-search them, or use alias tables if memory allows.

Skip-gram with hierarchical softmax

Skip-gram maximises the log probability of each context vertex given the centre vertex. The full softmax over n vertices costs O(n) per prediction, which is unaffordable. DeepWalk used hierarchical softmax: arrange the vertices as leaves of a binary tree, and model the probability of a leaf as the product of binary decisions (left or right, each a logistic regression on the centre vector) along its root-to-leaf path. Each prediction costs O(log n) and updates only the inner-node vectors on one path. Word2vec builds this tree as a Huffman code, so frequent tokens, here the hubs, get short paths.

Negative sampling, which most modern runs use instead, replaces the tree with k sampled noise vertices per positive pair. In practice both work; negative sampling is easier to reason about (see the NetMF view below) and usually faster for d around 128. With gensim 4, either is a flag:

from gensim.models import Word2Vec

walks = list(deepwalk_corpus(adj, gamma=80, t=40))
model = Word2Vec(
    sentences=walks, vector_size=128, window=10, min_count=0,
    sg=1,            # skip-gram, not CBOW
    hs=1, negative=0,  # hierarchical softmax, as in the paper
    workers=8, epochs=1, seed=0,
)
emb = {v: model.wv[str(v)] for v in adj}

Set min_count=0: the default of 5 silently drops low-degree vertices that were visited fewer than five times, and they then have no embedding at all. For bit-reproducible runs you also need workers=1 and a fixed PYTHONHASHSEED; with multiple threads the asynchronous updates make each run slightly different.

What DeepWalk actually computes: the NetMF view

Qiu et al. ("Network Embedding as Matrix Factorization", WSDM 2018) showed what DeepWalk with negative sampling converges to as walks become long. Let A be the adjacency matrix, D the diagonal degree matrix, P = D^-1A the transition matrix, vol(G) the sum of all degrees, T the window size and b the number of negative samples. DeepWalk implicitly factorises

log( vol(G) / (bT) · (P + P² + ... + P^T) · D^-1 )

Entry (i, j) is large when a T-step walk from i lands on j more often than degree alone predicts. It is a pointwise mutual information matrix for walk co-occurrence. Their NetMF algorithm for small T computes it directly, clamps entries below 1 to avoid log 0, and takes a rank-d SVD:

import numpy as np

def netmf_small_T(A, T=10, b=1.0, d=128):
    deg = A.sum(axis=1)
    vol = deg.sum()
    P = A / deg[:, None]
    S, Pr = np.zeros_like(A, dtype=float), np.eye(len(A))
    for _ in range(T):
        Pr = Pr @ P
        S += Pr
    M = (vol / (b * T)) * S / deg[None, :]
    L = np.log(np.maximum(M, 1.0))      # shifted-PPMI style clamp
    U, s, _ = np.linalg.svd(L)
    return U[:, :d] * np.sqrt(s[:d])

This is O(n²) memory and O(n³) time, so it is only practical up to tens of thousands of vertices (the paper gives an eigen-decomposition approximation for large T). Its value is as a reference: on our 200-vertex graph we counted window-5 co-occurrences from real walks, and the log of their empirical PMI correlated at 0.97 with log M over the 10,196 vertex pairs that co-occurred more than 20 times. When your sampled embeddings disagree badly with NetMF on a sample graph, suspect your walk code before your hyperparameters.

Worked example: two communities

The test graph has two blocks of 100 vertices; an edge appears with probability 0.08 inside a block and 0.008 across blocks, giving 844 edges and degrees from 2 to 16. We embedded it with NetMF at d = 16, split the vertices 50/50, and labelled each test vertex by its most cosine-similar training vertex. Accuracy was 0.98 for T = 1, 0.99 for T = 5 and 0.98 for T = 10.

Two lessons follow. First, on a graph this clean, almost anything works. The block structure is visible even at T = 1, where M reduces to a degree-normalised adjacency matrix. Do not tune on easy graphs and expect the setting to transfer. Second, a larger window does not buy accuracy when communities are already separable at one hop. It helps when the signal lies two or three hops away, for example on sparse graphs where direct neighbours are few, and it hurts when it blurs small communities into large ones. Choose the window from the structure you want to capture.

Hyperparameters and what they trade

Treat the paper's values as a starting prior, then confirm them on a validation split of your own graph.

Evaluating without leaking

Two protocols dominate, and both are easy to get wrong.

Multi-label node classification. The DeepWalk paper embeds the whole graph without labels, then trains one-vs-rest logistic regression on a random fraction of labelled vertices and scores Micro-F1 and Macro-F1 on the rest, repeated over several splits. That protocol is transductive: the test vertices took part in training the embedding. That is fine if your production use is the same (label a fixed graph), and misleading if new vertices arrive daily. Report the variance across splits, because single-split differences between embedding methods are often within noise.

Link prediction. Hide a fraction of edges, embed the remaining graph, then score hidden edges against sampled non-edges, typically with a Hadamard product of endpoint vectors fed to a classifier. The classic leak is walking on the full graph and only hiding edges at scoring time. Then the walks have already seen the test edges and AUC looks superb. A subtler leak: removing edges can disconnect vertices, so many pipelines keep a spanning tree intact, and the protocol should say so. Sample negatives with the same degree distribution as positives, or the classifier simply learns that hubs connect.

Operational guidance

• Corpus size planning. Tokens = n x gamma x t. Measure throughput on a slice and extrapolate; start with gamma around 10 on very large graphs, and raise it only while validation metrics improve.
• Embeddings are not comparable across runs. Any rotation of the vectors is an equally good solution, so retraining tomorrow gives coordinates unrelated to today's even if the geometry is the same. Downstream models trained on yesterday's vectors break. Either retrain the consumers together with the embedding, or align runs with orthogonal Procrustes on a set of stable anchor vertices.
• New vertices. DeepWalk is transductive. For a few new vertices, run walks touching them and continue training with the old vectors frozen (gensim supports build_vocab(update=True)). For heavy churn, use an inductive model such as GraphSAGE.
• Directed and weighted graphs. Sinks end walks early; add a teleport probability or treat the graph as undirected if direction is not part of the signal. Weight sampling must use the same weights your similarity notion assumes.
• Memory. The input and output (or inner-node) tables are each n x d float32: about 1 GB for two tables at n = 1M and d = 128. Walk corpora on disk can dwarf that, so stream them.

Failure modes

• Structural roles are invisible. Two hubs at opposite ends of the graph play the same role but never co-occur, so DeepWalk puts them far apart. If you need role similarity, use struc2vec-style or degree-feature methods, not proximity embeddings.
• Disconnected components drift. Vertices in different components never share a window, so their relative positions are arbitrary. Distances across components mean nothing.
• Bipartite graphs. Odd window offsets always land on the other side, so the co-occurrence pattern mixes both sides. Decide whether you want same-side similarity, and if so count only even offsets or embed a projected graph.
• Hub domination. Because visits are proportional to degree, the loss is dominated by hubs. Low-degree vertices end up with under-trained vectors that look like noise. Check embedding quality bucketed by degree, not just overall.
• Silent vocabulary drops. Leaving min_count at its default removes rare vertices, and KeyError surfaces much later in a downstream job.

Trade-offs

Continue with node2vec for biased walks, Word2Vec in depth for the skip-gram and PMI derivation, spectral clustering for the eigenvector route to the same communities, PageRank for another use of the random-walk transition matrix, and graph neural networks when you have node features.

What to do next

1. Build adjacency lists, confirm there are no isolated vertices, and decide whether to treat the graph as undirected.
2. Generate a corpus with gamma = 10, t = 40 and log the visit counts; plot them against degree to see your hub skew.
3. Train skip-gram with sg=1 and min_count=0, then sanity-check nearest neighbours of a few vertices you understand.
4. On a sample of up to a few thousand vertices, compute the NetMF embedding and compare neighbour lists with the sampled run.
5. Evaluate with a leak-free split: hide edges or labels before any walk is generated, and report variance across at least five splits.
6. Bucket the evaluation by degree, and fix low-degree quality with more walks or features before tuning anything else.
7. Before shipping, plan for retraining: Procrustes alignment or co-training of downstream models, and a path for new vertices.