node2vec, in depth: second-order biased walks, the p and q parameters, alias tables versus rejection sampling, and a measured skip-gram pipeline

The pipeline

The pipeline has three stages, which the paper runs one after another. First, preprocessing computes transition probabilities. Second, walk simulation starts r walks of length l from every node. Third, optimisation trains skip-gram with a context window of k over the walks. The output is a d-dimensional vector per node. These vectors then feed a classifier for node labels, or are combined pairwise for link prediction. Of the four operators the paper tried for combining two node vectors into an edge feature, the element-wise (Hadamard) product was the most stable.

The paper's experiments used d = 128, r = 10, l = 80 and k = 10, with a single epoch of optimisation. p and q were chosen by grid search over {0.25, 0.5, 1, 2, 4}, with 10-fold cross-validation on 10% labelled data. These are reasonable starting points, not laws. The experiment below uses smaller values because the graph is small.

The second-order walk

Suppose the walk has just traversed the edge from t to v and must choose the next node x among v's neighbours. node2vec sets an unnormalised weight pi(v, x) = alpha(t, x) * w(v, x), where w is the edge weight (1 for unweighted graphs). alpha depends only on the hop distance d(t, x) between the previous node and the candidate:

• alpha = 1/p if d(t, x) = 0, that is, x is t itself and the walk returns;
• alpha = 1 if d(t, x) = 1, that is, x is also a neighbour of t;
• alpha = 1/q if d(t, x) = 2, that is, x moves away from t.

p is the return parameter. A low p makes the walk backtrack and stay near its start, while a high p discourages returning. q is the in-out parameter. With q above 1, the walk prefers nodes close to t and samples a local, breadth-first-like view. The paper connects that view to structural equivalence, meaning nodes with similar roles. With q below 1, the walk moves outward like a depth-first search, which the paper connects to homophily, meaning nodes in the same community. With p = q = 1 every alpha is 1, and node2vec reduces to DeepWalk's uniform walk.

Worked example

Take the configuration in the figure: v has four neighbours, namely t, x1 (also adjacent to t), x2 and x3. With p = 4 and q = 0.5, the weights are 1/4, 1, 2 and 2, summing to 5.25. So the probabilities are 0.048 to return, 0.190 to stay near t, and 0.381 each to move out to x2 or x3. This walk explores outward. Swap the setting to p = 0.25 and q = 4, and the weights become 4, 1, 0.25 and 0.25, summing to 5.5. Now the walk returns to t with probability 0.727 and reaches each outward node with only 0.045. That walk stays inside a small ball around its start. Same graph, two very different samples of each node's neighbourhood.

Sampling in O(1) with alias tables

Because the probabilities depend on the pair (t, v), you can precompute one discrete distribution per directed edge and sample from it in O(1) with Walker's alias method. The paper says the transition probabilities can be precomputed and then sampled in O(1) time this way. The Alias Method explains the construction. Here is a direct implementation:

import numpy as np

def alias_setup(probs):
    n = len(probs)
    q = np.asarray(probs, dtype=float) * n / np.sum(probs)
    J = np.zeros(n, dtype=np.int64)
    small = [i for i in range(n) if q[i] < 1.0]
    large = [i for i in range(n) if q[i] >= 1.0]
    while small and large:
        s, l = small.pop(), large.pop()
        J[s] = l
        q[l] -= 1.0 - q[s]
        (small if q[l] < 1.0 else large).append(l)
    for i in small + large:
        q[i] = 1.0
    return J, q

def alias_draw(J, q, rng):
    i = rng.integers(len(J))
    return i if rng.random() < q[i] else J[i]

class Node2Vec:
    def __init__(self, adj, p=1.0, q=1.0):          # adj: list of neighbour lists
        self.adj = [np.array(sorted(a)) for a in adj]
        nbr = [set(a) for a in adj]
        self.edge_alias = {}
        for t in range(len(adj)):
            for v in self.adj[t]:
                w = [1.0 / p if x == t else (1.0 if x in nbr[t] else 1.0 / q)
                     for x in self.adj[v]]
                self.edge_alias[(t, v)] = alias_setup(w)

    def walk(self, start, length, rng):
        w = [start, self.adj[start][rng.integers(len(self.adj[start]))]]
        while len(w) < length:
            J, qq = self.edge_alias[(w[-2], w[-1])]
            w.append(self.adj[w[-1]][alias_draw(J, qq, rng)])
        return w

The first step has no previous node, so it is uniform. Every later step reads the table for the edge it just crossed.

The memory wall, measured

The table for edge (t, v) has deg(v) entries, and every neighbour t of v owns one. Total storage is therefore the sum over nodes of deg(v)^2, not the number of edges. Real graphs have hubs, and hubs dominate that sum. I generated preferential-attachment graphs, which have a heavy-tailed degree distribution, and counted entries:

Each entry stores a probability and an alias index, so 33 million entries is roughly half a gigabyte for a graph with half a million edges. The ratio keeps growing with the largest hubs. On social or web graphs with nodes of degree 10^5, precomputation is not an option.

Rejection sampling instead

Rejection sampling removes the tables. Propose a neighbour x of v uniformly, which is the cheap first-order step, then accept it with probability alpha(t, x) / max(1/p, 1, 1/q). Accepted samples follow exactly the node2vec distribution. The only state needed is adjacency plus a fast membership test for 'is x a neighbour of t', such as a hash set or a binary search in a sorted adjacency list.

def walk_rejection(adj, nbr, start, length, p, q, rng):
    amax = max(1.0 / p, 1.0, 1.0 / q)
    w = [start, adj[start][rng.integers(len(adj[start]))]]
    while len(w) < length:
        t, v = w[-2], w[-1]
        while True:
            x = adj[v][rng.integers(len(adj[v]))]
            a = 1.0 / p if x == t else (1.0 if x in nbr[t] else 1.0 / q)
            if rng.random() * amax < a:
                break
        w.append(x)
    return w

The cost is wasted proposals. On the experiment graph below, the mean acceptance rate was 1.000 for p = q = 1, 0.874 for p = 1 and q = 0.5, and 0.775 for p = 4 and q = 0.25. For p = 0.25 and q = 4 it fell to 0.255, so three of four proposals were thrown away, because the large 1/p sets a high ceiling that most candidates fall far below. To check correctness, I compared node-visit frequencies from 3,000 walks of length 40 started at the same node. The total variation distance between the alias walk and the rejection walk was 0.045. Between two alias runs with different seeds it was 0.050, so the two samplers are indistinguishable at this sample size.

Skip-gram with negative sampling

Skip-gram with negative sampling turns walks into vectors. For every node u at position i of a walk and every node c within k positions of it, raise log sigmoid(W[u] . C[c]). At the same time, lower the score against a few noise nodes drawn from the node frequency distribution raised to the power 0.75. W holds the embeddings you keep; C is the context table you throw away. The minibatch version in numpy:

def sgns(walks, n, dim=32, window=5, neg=5, lr=0.025, seed=0):
    rng = np.random.default_rng(seed)
    W = (rng.random((n, dim)) - 0.5) / dim
    C = np.zeros((n, dim))
    pairs = np.array([(u, w[j]) for w in walks for i, u in enumerate(w)
                      for j in range(max(0, i - window), min(len(w), i + window + 1)) if j != i])
    freq = np.bincount(np.concatenate(walks), minlength=n) ** 0.75
    noise = freq / freq.sum()
    rng.shuffle(pairs)
    for s in range(0, len(pairs), 512):
        a = lr * max(1e-4, 1 - s / len(pairs))             # linear decay
        u, ctx = pairs[s:s + 512, 0], pairs[s:s + 512, 1:2]
        ctx = np.concatenate([ctx, rng.choice(n, (len(u), neg), p=noise)], axis=1)
        label = np.zeros(ctx.shape); label[:, 0] = 1
        score = np.einsum("bd,bkd->bk", W[u], C[ctx])
        g = (label - 1 / (1 + np.exp(-score))) * a
        gw = np.einsum("bk,bkd->bd", g, C[ctx])
        np.add.at(C, ctx.ravel(), (g[:, :, None] * W[u][:, None, :]).reshape(-1, dim))
        np.add.at(W, u, gw)
    return W

At scale, use an optimised word2vec implementation, such as gensim's Word2Vec in skip-gram mode, or a GPU implementation in a graph learning library. The code above exists to show the objective, not to compete with them.

Measured: when do p and q matter?

The test graph is a stochastic block model with 6 communities of 50 nodes. Each pair inside a community is linked with probability 0.12, and each pair across communities with 0.004. That gave 300 nodes and 1,048 edges, with degrees from 1 to 15. I held out 10% of the edges for link prediction before generating walks, so the embeddings never saw them. Then I ran 10 walks of length 40 per node, with d = 32, window 5, 5 negatives and one epoch. Node classification predicts the community label with logistic regression on half the nodes. Link prediction scores held-out edges against an equal number of random non-edges by cosine similarity.

The honest result: on a graph whose labels are its communities, p and q barely matter. All five settings classify 97 to 98% of nodes correctly, and the AUC spread of 0.022 is within what one seed can move. The outward-exploring setting, p = 4 with q = 0.25, came out on top for link prediction, which is consistent with the theory, but this experiment cannot separate that from noise. The paper found larger gains where labels mix community and role. On BlogCatalog, node2vec at p = q = 0.25 reached macro-F1 0.2581 against DeepWalk's 0.2110. Tune p and q when the task needs it, and measure against p = q = 1 first. Note also where the time went: skip-gram dominated every run, so walk cleverness matters less than an efficient trainer until the graph is large.

Operating it

node2vec is transductive: it embeds the nodes it saw. A new node needs retraining, or an approximation such as averaging its neighbours' vectors. Two training runs produce embeddings that differ by an arbitrary rotation plus noise, so a downstream model trained on one cannot read the other. Either retrain the consumers with the embedding, or align the runs on shared nodes with orthogonal Procrustes, which removes the rotation and leaves the noise. For link prediction, remove evaluation edges before walking, as above. Otherwise the walk traverses the answer and the AUC is fiction. Directed graphs need walks along edge direction, and dead-end nodes need a stopping or restart rule. Weighted graphs multiply alpha by the weight, so a few very heavy edges can trap walks. For the background on walk behaviour on graphs, such as mixing and hitting times, see Random Walks.

Trade-offs

Failure modes

• Edge leakage in evaluation. Held-out edges included in walks inflate link-prediction scores.
• Alias tables exhausting memory on hub-heavy graphs; switch to rejection sampling.
• Low-p settings wasting most rejection proposals (0.255 acceptance above); budget for it or use tables for hubs only.
• Comparing embeddings across retrains without alignment.
• Isolated nodes produce no walks and keep their random initial vectors; filter or flag them.
• Grid-searching p and q on the test set rather than a validation split.

What to do next

1. Run the code with p = q = 1 for a DeepWalk baseline, evaluated on held-out edges or labels.
2. Compute the sum of squared degrees before choosing alias tables; if it is many times the edge count, use rejection sampling.
3. Grid-search p and q over {0.25, 0.5, 1, 2, 4} on a validation split, and keep a change only if it beats the baseline by more than seed-to-seed noise.
4. Move skip-gram to an optimised trainer before tuning walk code; it is where the time goes.
5. If new nodes arrive constantly or nodes have features, evaluate a GNN instead.