node2vec

Chapter 1: Random Walk Framework

node2vec inherits the encoder-decoder framework from DeepWalk. Nodes are mapped to d-dimensional vectors. Similarity is measured by dot product. The objective: find embeddings such that nodes co-occurring in random walks have high dot products.

The Neighborhood N_S(u)

For a node u, define its network neighborhood N_S(u) as the multiset of nodes visited during random walks from u using strategy S. The objective is:

where f: V → ℝ^d is the embedding function. Two simplifying assumptions (both from Word2Vec):

1. Conditional independence: The likelihood of each neighbor node in N_S(u) is independent of the others given f(u). So the product factorizes over individual terms.
2. Symmetry in feature space: A node's embedding as source and as context (neighbor) are the same. So Pr(n_i|f(u)) is modeled symmetrically.

The conditional probability of visiting node v given source node u is modeled with a softmax:

The strategy S is what makes node2vec different from DeepWalk. It controls HOW the random walk explores the graph — biased toward local or global structure. Different strategies produce different N_S(u), which changes what the optimization objective forces embeddings to encode.

Why Random Walks, Not BFS/DFS Directly?

You might ask: why not directly compute BFS neighborhoods or DFS neighborhoods and use those as N_S(u)? Two reasons. First, exact BFS/DFS neighborhoods can be huge — they scale with graph size. Random walks give a flexible, sampled approximation that's controllable via walk length. Second, pure BFS and DFS are the extremes. The power of node2vec is the ability to smoothly interpolate between them, finding the right balance for your task.

Chapter 2: BFS vs. DFS Neighborhoods

Consider a source node u. Two classical graph exploration strategies give very different notions of "neighborhood":

BFS: Breadth-First Sampling

Breadth-first search explores all direct neighbors of u before moving to any node two hops away. The BFS neighborhood N_BFS(u) stays tightly local — it's essentially the immediate neighborhood of u, perhaps up to depth 2 or 3.

BFS neighborhoods capture homophily. Two nodes with overlapping BFS neighborhoods — sharing many neighbors — are likely in the same community. BFS-based embeddings encode community membership: users in the same social circle embed nearby.

DFS: Depth-First Sampling

Depth-first search follows one path as far as possible before backtracking. The DFS neighborhood N_DFS(u) rapidly moves away from u, visiting distant nodes.

DFS neighborhoods capture structural equivalence. A long DFS walk from u visits nodes across the whole graph, exposing structural patterns. Two nodes where DFS walks have similar statistical distributions (visiting similar types of nodes in similar proportions) are likely structurally equivalent — even if they're in completely different parts of the graph.

Why Pure BFS or DFS Fails

Chapter 3: The p,q Parameters — Walk Explorer

node2vec introduces a second-order random walk. Unlike a standard random walk that only remembers the current node, node2vec's walk remembers the previous node too. This one extra bit of memory is enough to implement a continuous BFS–DFS tradeoff.

The Transition Probabilities

Suppose the walk has just traversed edge (t → v) — it came from node t and is now at node v. It must choose where to go next. For each neighbor x of v, the unnormalized transition weight α_pq(t, x) is:

where d_tx is the shortest-path distance from t to x. These unnormalized weights are then divided by their sum to give proper transition probabilities.

Intuition for p (Return Parameter)

p controls the likelihood of revisiting a node you just came from. High p: returning to t is very unlikely (1/p is small) — the walk prefers to explore new territory. Low p: returning to t is very likely — the walk tends to backtrack, staying local. Think of p as the "backtracking penalty."

Intuition for q (In-Out Parameter)

q controls whether the walk explores inward (toward t) or outward (away from t). Low q: 1/q is large — moving farther from t is preferred — the walk explores outward, DFS-style. High q: 1/q is small — moving farther from t is discouraged — the walk prefers nodes near t, BFS-style. Think of q as "how adventurous the walk is."

Chapter 4: Skip-gram Objective

Once walks are generated, node2vec uses the skip-gram objective from Word2Vec. The walk is treated as a "sentence": a sequence of node IDs. The skip-gram objective asks the model to predict the context (surrounding nodes within a window) given a source node.

Formally

Given a walk w₁, w₂, ..., w_L, for each node w_i, predict the nodes w_i-k, ..., w_i-1, w_i+1, ..., w_i+k in a window of size k. The objective maximizes:

The conditional probability uses the softmax:

What Is Each Element?

The Walk Generation Strategy

Before optimization, node2vec pre-generates all random walks. This is more efficient than sampling on-the-fly during training. The pipeline:

python
def node2vec_train(G, p, q, d=128, r=10, l=80, k=10):
    # Precompute transition probabilities (second-order Markov)
    probs = precompute_transition_probs(G, p, q)
    # probs[(t, v)] = dict {neighbor: weight} for each edge (t,v)

    # Generate walk corpus
    walks = []
    for _ in range(r):               # r walks per node
        for u in G.nodes():
            walk = biased_walk(G, probs, u, l)  # length l
            walks.append(walk)

    # Train skip-gram (Word2Vec) on walk corpus
    model = Word2Vec(walks, vector_size=d, window=k,
                      sg=1, min_count=0, workers=4)
    return {u: model.wv[u] for u in G.nodes()}
    # Returns dict: node_id -> np.array of shape (d,)

Chapter 5: Negative Sampling

The softmax denominator ∑_v∈V exp(f(u)·f(v)) is the core computational bottleneck. For a graph with a million nodes, computing this sum requires a million dot products — for every (u, context) pair in every training step. This is completely intractable.

The Noise-Contrastive Estimation (NCE) Idea

Instead of normalizing over all V nodes, reformulate as a binary classification problem: given node u and a candidate node v, is v a true context of u (from the walk), or is it noise (a random node)? This is noise-contrastive estimation.

Mikolov et al. showed that a simplified version — negative sampling — works well in practice. For each positive (u, v) pair from the walk, sample k negative nodes n₁, ..., n_k from a noise distribution P_n. The loss becomes:

This has two terms:

1. −log σ(f(v)·f(u)): Maximize the dot product between true co-occurring pairs. Pull their embeddings together.
2. −log σ(−f(n)·f(u)): Minimize the dot product with negative samples. Push those embeddings apart.

The Noise Distribution

node2vec follows Word2Vec: sample negative nodes with probability proportional to degree^3/4. Why 3/4 and not uniform? Uniform would under-sample high-degree nodes (hubs), which are the most informative negatives — they appear everywhere in the graph. Degree^3/4 biases toward frequent nodes without making them completely dominate:

Effect of k on Quality

python
import numpy as np

def sigmoid(x):
    return 1.0 / (1.0 + np.exp(-x))

def neg_sample_loss(f_u, f_v, Z, degrees, k=10):
    # f_u, f_v: embeddings of source and context node, shape (d,)
    # Z: all embeddings, shape (|V|, d)
    # degrees: node degree array, shape (|V|,)

    # Positive term
    pos_score = f_u @ f_v                          # scalar
    pos_loss = -np.log(sigmoid(pos_score) + 1e-8)

    # Negative sampling distribution: degree^0.75
    probs = degrees ** 0.75
    probs /= probs.sum()
    neg_idx = np.random.choice(len(degrees), size=k, p=probs)

    # Negative terms
    neg_scores = Z[neg_idx] @ f_u                  # shape (k,)
    neg_loss = -np.sum(np.log(sigmoid(-neg_scores) + 1e-8))

    return pos_loss + neg_loss / k

Chapter 6: Link Prediction with Embeddings

Node embeddings z_u were designed for nodes. But many tasks are about pairs of nodes — specifically, link prediction: given nodes u and v, does an edge exist between them (or will one form in the future)?

The trick: define an edge embedding using a binary operator on the two node embeddings. node2vec evaluates four operators:

Each operator produces a d-dimensional vector for each edge. This vector is then fed into a logistic regression classifier trained on known edges (positive examples) and non-edges (negative examples).

Training Setup

The link prediction setup requires careful handling to avoid data leakage:

1. Split edges into train/test sets. Remove test edges from the graph before generating walks.
2. Generate node embeddings using node2vec on the training graph only.
3. For each edge in train set and an equal number of non-edges, compute edge embedding using one of the four operators.
4. Train logistic regression on these edge embeddings.
5. Evaluate on test edges + equal non-edges using AUC-ROC.

python
from sklearn.linear_model import LogisticRegression
from sklearn.metrics import roc_auc_score
import numpy as np

def link_prediction(embeddings, train_edges, train_nonedges,
                    test_edges, test_nonedges, operator='hadamard'):
    def edge_emb(u, v):
        zu, zv = embeddings[u], embeddings[v]
        if operator == 'hadamard': return zu * zv
        if operator == 'avg':      return (zu + zv) / 2
        if operator == 'l1':       return np.abs(zu - zv)
        if operator == 'l2':       return (zu - zv) ** 2

    # Build training features and labels
    X_train = [edge_emb(u, v) for u, v in train_edges + train_nonedges]
    y_train = [1] * len(train_edges) + [0] * len(train_nonedges)

    clf = LogisticRegression().fit(X_train, y_train)

    # Evaluate on test set
    X_test = [edge_emb(u, v) for u, v in test_edges + test_nonedges]
    y_test  = [1] * len(test_edges) + [0] * len(test_nonedges)
    scores = clf.predict_proba(X_test)[:, 1]
    return roc_auc_score(y_test, scores)

Chapter 7: Results

The paper evaluates node2vec on two tasks: multi-label node classification and link prediction. The key result: node2vec outperforms all baselines on both tasks, on all datasets. And the p,q parameters are the reason.

Node Classification Datasets

Node Classification Results (F1 Score)

node2vec improves over DeepWalk by 22% on BlogCatalog (a social network — homophily) and 15% on PPI (a protein network — structural equivalence). The improvement comes from tuning p and q.

Link Prediction (AUC-ROC)

On Facebook (social network), node2vec achieves 0.9980 AUC — near-perfect link prediction. On PPI (protein interaction), it reaches 0.9760. Across all four datasets, node2vec achieves the highest AUC, with the Hadamard operator performing best.

Chapter 8: When to Use Which Settings

By now you understand the theory. But in practice, how do you choose p and q for a new graph? Here's a principled guide based on task type, graph structure, and what the literature shows.

Task-Based Guidelines

Graph Structure Signals

You can diagnose what type of similarity is dominant before training by examining graph structure:

• High clustering coefficient → tight communities → BFS-favoring (low p)
• Many structural holes (bridge nodes) → DFS-favoring (low q)
• Power-law degree distribution → hubs play special roles → DFS may help with role discovery
• Regular structure (lattice, grid) → uniform walks work fine

Hyperparameter Search Protocol

The paper uses a simple grid search: p ∈ {0.25, 0.5, 1, 2, 4}, q ∈ {0.25, 0.5, 1, 2, 4}. That's 25 combinations. Train node2vec once for each combination (walks only need to be regenerated, not the optimization from scratch for each). Evaluate on a 10% held-out node validation set. Pick the best p, q.

When NOT to Use node2vec

• New nodes (inductive setting): node2vec is a lookup table — new nodes have no embedding. Use GraphSAGE or a GNN instead.
• Rich node features: node2vec ignores node attributes. If nodes have feature vectors, GNNs that aggregate them will perform much better.
• Dynamic graphs: Node2vec requires retraining for any graph change. For evolving graphs, use CTDNE or streaming methods.
• Very small graphs (<100 nodes): the training corpus is tiny; random walk sampling is noisy. Spectral methods or direct GNNs are more reliable.

Chapter 9: Connections & Legacy

node2vec sits at the intersection of random walk theory, Word2Vec, and network science. Understanding its place in the literature explains both why it worked and where to go next.

Predecessors

What node2vec Got Right (That's Still True)

• BFS vs. DFS tradeoff is real. Even modern GNNs must choose their receptive field — local (shallow GNN) or global (deep GNN). The tension between homophily and structural equivalence is a fundamental graph property.
• Walk-based neighborhood sampling is efficient. PinSage (Pinterest, 2018) uses random walk sampling inside a GNN framework to avoid expensive full neighborhood aggregation on billion-node graphs.
• Simple baselines often win. On many industry benchmarks, node2vec with tuned p,q outperforms complex GNNs when node features are absent or low-quality.

What node2vec Got Wrong (Or Left Unresolved)

• No node features. Real nodes have attributes — user demographics, protein sequences, word embeddings. Ignoring them leaves signal on the table.
• Transductive. Can't embed new nodes. Unsuitable for streaming or growing graphs.
• O(|V|·d) parameter count. For 100M-node graphs, the embedding matrix itself is a memory bottleneck.
• No expressive power theory. GNNs have the Weisfeiler-Leman hierarchy; node2vec has no equivalent characterization of what graph structures it can distinguish.

Citation Impact

node2vec has over 14,000 citations (as of 2024). It is one of the most cited graph ML papers ever, and serves as the standard baseline for any node classification or link prediction task. "Did you beat node2vec?" is the minimum bar in graph ML papers.

"The key is to be able to control the kind of communities you're trying to learn — and that's exactly what p and q give you." — Jure Leskovec

Paper: Grover & Leskovec, "node2vec: Scalable Feature Learning for Networks," KDD 2016.
arXiv: 1607.00653  |  Code: github.com/aditya-grover/node2vec