DeepWalk

Chapter 1: The Random Walk ↔ Language Analogy

Here's the core insight of the paper, stated plainly: a random walk on a graph is a sentence. Each node is a word. The sequence of nodes visited is the corpus.

Take a social network. Start at node 3. Walk randomly: 3 → 7 → 2 → 7 → 9 → 4. That's a "sentence": [3, 7, 2, 7, 9, 4]. Run thousands of such walks. You now have a text corpus made of node IDs. Feed it to Word2Vec. Get node embeddings.

This seems almost absurd. Why would a language model technique work on a graph? The paper's answer is empirical and then theoretical. Empirically: it works better than hand-crafted features. Theoretically: random walks on graphs obey the same statistical distribution as words in natural language — both follow a power law. (We'll explore this in Chapter 3.)

What Word2Vec Actually Learns

Word2Vec (specifically the skip-gram variant) takes a word and tries to predict the words surrounding it in a window. "The cat sat on the mat" with window 2 around "sat": predict {cat, on} from "sat." After training on millions of sentences, the resulting vectors encode semantic relationships — famous king − man + woman ≈ queen.

Applied to graphs: given a node v seen in a random walk, predict the nodes that appear near v within a window of size w. After training on thousands of walks, the resulting vectors encode structural relationships — nodes that appear in similar walk contexts embed nearby.

Chapter 2: Skip-Gram on Graphs

The skip-gram objective: given a node v at position i in a walk, predict all nodes within a window of size w around it. For walk [3, 7, 2, 7, 9, 4] with w=1 and center node at position 2 (node 2), the context nodes are {7, 7} — the immediate neighbors in the walk sequence.

Formally, for each walk of length t and each node v_i in that walk, we want to maximize:

This is summed over all walks. Each term asks: how likely is the context node v_i+j given the center node v_i? We model this likelihood with a softmax over all nodes in the graph.

The Softmax

The probability of observing node u as context given center node v is:

Here e_v is the embedding vector for node v. The numerator rewards high dot product between embeddings of co-occurring nodes. The denominator normalizes over the entire graph — which is expensive when the graph has millions of nodes. (That's why DeepWalk uses hierarchical softmax, covered in Chapter 4.)

The Showcase: Walks Become Context Pairs

The simulation below shows the full pipeline: random walk → sliding window → (center, context) training pairs → skip-gram update. Watch how a single walk generates many training examples, and how repeated updates pull co-occurring node embeddings closer.

Chapter 3: The Power Law Connection

Why does a language model technique work on graphs? The paper's theoretical justification is elegant: the two domains share the same statistical structure.

In natural language, word frequencies follow Zipf's law: the most common word appears roughly twice as often as the second most common, three times as often as the third, and so on. If you plot word frequency vs. rank on a log-log scale, you get a straight line — a power law. "The" appears millions of times; "ephemeral" appears rarely.

Now look at random walks on a social network. How often does each node appear across all random walks? The popular, well-connected nodes appear frequently — they're hard to avoid. The peripheral nodes appear rarely. The authors of DeepWalk measure this empirically on several social networks and find: node visit frequency in random walks also follows a power law.

What a Power Law Means in Practice

A power law distribution P(x) ∝ x^-α has a "heavy tail." Most nodes appear rarely. A small number of nodes (high-degree hubs) appear constantly. This is exactly the social network phenomenon known as the Pareto principle or the "80-20 rule": 20% of nodes do 80% of the connecting.

For the skip-gram objective, this means: hub nodes accumulate enormous training signal because they appear in many walk windows. Peripheral nodes get sparse signal. Word2Vec handles this gracefully — it was designed for a similar imbalance in language.

Chapter 4: Algorithm Details

Let's be precise about what DeepWalk actually does. The full algorithm has three hyperparameters: γ (walks per node), t (walk length), and w (window size). Each node gets exactly γ random walks started from it, each of length t. Every walk feeds (center, context) pairs into the skip-gram objective.

Hierarchical Softmax

The raw softmax over all |V| nodes is expensive — O(|V|) per training step. DeepWalk uses hierarchical softmax, a trick from language modeling. Build a binary tree (a Huffman tree, where frequent nodes get shorter codes). The probability of a node is computed as a product of probabilities along its path from root to leaf — O(log |V|) per step instead of O(|V|).

Each internal tree node has a learnable parameter vector. For a leaf node u with root-to-leaf path b₀, b₁, ..., b_log|V|:

where σ is sigmoid, b_l ∈ {±1} is the branching direction, and Ψ[n_l] is the parameter of internal node n_l. Frequent nodes (high degree) get short paths — fewer multiplications, faster training.

The Code

python
import numpy as np
import random
from collections import defaultdict

def random_walk(graph, start, length):
    """Single random walk from `start` of given `length`."""
    walk = [start]
    for _ in range(length - 1):
        neighbors = list(graph[walk[-1]])
        if not neighbors:
            break  # dead end
        walk.append(random.choice(neighbors))
    return walk

def generate_walks(graph, gamma, t):
    """Generate gamma walks of length t from every node."""
    walks = []
    nodes = list(graph.keys())
    for _ in range(gamma):
        random.shuffle(nodes)         # shuffle order each epoch
        for v in nodes:
            walks.append(random_walk(graph, v, t))
    return walks                      # list of lists of node IDs

def deepwalk(graph, d=128, gamma=10, t=40, w=5):
    """
    graph: dict mapping node -> list of neighbors
    d:     embedding dimension
    gamma: walks per node
    t:     walk length
    w:     skip-gram window size
    """
    walks = generate_walks(graph, gamma, t)

    # Convert walks to strings for gensim Word2Vec
    str_walks = [[str(n) for n in walk] for walk in walks]

    from gensim.models import Word2Vec
    model = Word2Vec(
        str_walks,
        vector_size=d,
        window=w,
        min_count=0,       # keep all nodes even if rare
        sg=1,              # sg=1 means skip-gram (not CBOW)
        hs=1,              # hs=1 means hierarchical softmax
        workers=4,
        epochs=1           # gensim iterates; we already loop gamma times
    )
    # Return embedding matrix indexed by node ID
    embeddings = {int(k): model.wv[k] for k in model.wv.key_to_index}
    return embeddings

Chapter 5: Results — Multi-Label Node Classification

The paper evaluates on three large social networks with ground-truth community labels. The task is multi-label node classification: each node can belong to multiple communities simultaneously. The evaluation protocol is standard: train a one-vs-rest logistic regression on a fraction of labeled nodes, test on the rest.

Datasets

These are real, messy social networks. BlogCatalog is bloggers linking to each other; labels are the topics they write about. Flickr is photo-sharing users; labels are interest groups. YouTube is video creators; labels are genre communities. None of this structure is trivially decodable from degree statistics alone.

Baselines

DeepWalk is compared to several feature engineering baselines:

• SpectralClustering: Uses eigenvectors of the graph Laplacian as features. This is the classic approach to "graph structure as features" — but computing eigenvectors is O(|V|³), infeasible at YouTube scale.
• Modularity: Uses community detection to assign nodes to clusters, then encodes cluster membership.
• EdgeCluster: Assigns edge labels via clustering, uses them as node features.
• wvRN (weighted-vote Relational Neighbor): A label-propagation method that uses labeled neighbors directly — this is "cheating" in the sense that it needs labeled data; DeepWalk needs none.

Key Numbers

On BlogCatalog with 10% labeled nodes:

DeepWalk beats all baselines including the semi-supervised wvRN which uses the actual labels. With only 1% labeled data, the gap is even larger — DeepWalk doesn't need labels at training time. The unsupervised embeddings transfer to the classification task with minimal labeled examples needed.

Sensitivity to Training Fraction

A critical result: as labeled training data decreases from 90% to 1%, DeepWalk's relative advantage increases. With 90% labels, supervised methods can get close. With 1% labels, DeepWalk wins decisively. This is the characteristic signature of good unsupervised representation learning — it's most valuable when labeled data is scarce.

Chapter 6: Why This Paper Matters

DeepWalk was published at KDD 2014. By 2024 it had over 8,000 citations. To understand why, you need to understand the moment it arrived in.

In 2014, graph machine learning meant one of two things: (1) hand-engineer features from graph statistics and feed them to a classifier, or (2) use graph kernels that computed structural similarity directly but were computationally expensive and didn't generalize. Neither approach scaled, neither was learnable end-to-end, and neither transferred across tasks.

DeepWalk changed the paradigm. It said: don't engineer features, learn representations. This is the same shift that ImageNet + ConvNets caused for vision in 2012, and that Word2Vec caused for NLP in 2013. DeepWalk brought that shift to graphs.

What It Got Right

The paper's enduring contributions aren't just the algorithm — it's the framing. By showing that random walks produce power-law-distributed sequences, the authors gave a theoretical reason to believe NLP-style training would work on graphs. This principled justification made the approach more than a hack — it was a bridge between two fields.

DeepWalk also established the benchmark protocol that subsequent graph representation learning papers still use: multi-label classification on BlogCatalog, Flickr, and YouTube. Papers like LINE (2015), node2vec (2016), GraphSAGE (2017), and GCN (2017) all compare against DeepWalk as the baseline. You cannot read graph ML papers without understanding DeepWalk.

What It Got Wrong (Or Didn't Address)

Uniform random walks capture local co-occurrence structure but treat all neighbors equally. They can't distinguish between homophily (community membership) and structural equivalence (role similarity) — that's exactly the problem node2vec was designed to solve. DeepWalk also doesn't use node or edge features — it works purely from topology. GCN and GraphSAGE extend this to feature-rich graphs. DeepWalk is also transductive: you can't embed new nodes without running new walks through the entire training procedure.

Chapter 7: Connections & What Came Next

DeepWalk sits at the root of a family tree of graph representation learning methods. Understanding where each successor improves on DeepWalk clarifies the field's development.

The Crucial Limitations DeepWalk Exposed

The Connection to Self-Supervised Learning

DeepWalk is, in modern terms, a self-supervised pre-training method. It creates a proxy task (predict context nodes from center nodes) from unlabeled data, and the representations learned for the proxy task transfer to downstream tasks. This is exactly what BERT does for text and SimCLR does for images — both from 2019, five years later.

Related Veanors Lessons

To go deeper:

• node2vec — the direct extension with biased walks and p,q parameters

"If you want to understand graphs, walk on them." — DeepWalk's implicit philosophy, now the foundation of graph deep learning.