Node Embeddings: node2vec and DeepWalk Explained

Both methods do the same three things: sample random walks, treat each walk as a sentence, and train word2vec’s skip-gram on it. They differ in exactly two places — how the walk chooses its next step, and how the softmax is approximated. Those two differences are the whole content of the pair.

The trick: a graph is a corpus

DeepWalk (Perozzi, Al-Rfou and Skiena, KDD 2014) makes an argument that is easy to skip past and is the reason any of this works. Word frequency in natural language follows a power law. If a graph’s degree distribution follows a power law — as most real networks approximately do — then the frequency with which vertices appear in short random walks also follows a power law. The statistics the language-model machinery was designed for are the statistics you get. So you can hand a set of walks to a tool built for sentences and it will behave.

Skip-gram, from Mikolov et al. (2013), learns a vector for each token by predicting the tokens that appear near it in a window. Applied to walks, it learns a vector per node by predicting the nodes that appear near it in a walk. Two nodes end up close in vector space when they keep showing up in each other’s windows.

DeepWalk: uniform walks and hierarchical softmax

DeepWalk’s walk is memoryless and uniform: from the current vertex, pick a neighbour at random with equal probability. The paper runs γ = 80 walks from every vertex, each of length t = 40, with window w = 10 and d = 128 dimensions.

Its optimiser is hierarchical softmax. The normalising sum in a softmax runs over every vertex, which is O(|V|) per training pair and hopeless at scale. Hierarchical softmax replaces it with a binary tree over the vertices — a Huffman tree, so frequent vertices get short codes — and predicts a path down the tree instead of a class, reducing the cost to O(log|V|). This is worth knowing because it is the one implementation detail that differs between the two methods and it is routinely stated backwards.

node2vec’s p and q, computed

node2vec (Grover and Leskovec, KDD 2016) replaces the uniform walk with a second-order one: the next step depends on the current node and the previous node. Having just moved from t to v, the unnormalised probability of stepping to a neighbour x of v is alpha_pq(t,x) times the edge weight, where:

alpha_pq(t, x) =  1/p   if d_tx = 0     (x is t — we go back)
                  1     if d_tx = 1     (x is also a neighbour of t)
                  1/q   if d_tx = 2     (x is one hop further out)

d_tx is the shortest-path distance from the PREVIOUS node t to x,
and it can only take the values 0, 1 or 2.

Take a concrete node. In the graph below the walk has just arrived at C from A, so t = A and v = C:

edges:  A-C   A-D   C-D   C-B   C-E   B-E   D-F

candidates from C:   A, B, D, E

d(A,A) = 0  → alpha = 1/p     (backtrack)
d(A,D) = 1  → alpha = 1       (D is also adjacent to A)
d(A,B) = 2  → alpha = 1/q     (outward)
d(A,E) = 2  → alpha = 1/q     (outward)

Now normalise for three settings.

p = 1, q = 1   (this is DeepWalk)
  weights  A=1, D=1, B=1, E=1        sum = 4
  P(A)=0.250  P(D)=0.250  P(B)=0.250  P(E)=0.250

p = 4, q = 0.25   (outward, DFS-like)
  weights  A=0.25, D=1, B=4, E=4     sum = 9.25
  P(A)=0.027  P(D)=0.108  P(B)=0.432  P(E)=0.432

p = 1, q = 4      (local, BFS-like)
  weights  A=1, D=1, B=0.25, E=0.25  sum = 2.5
  P(A)=0.400  P(D)=0.400  P(B)=0.100  P(E)=0.100

Read the second setting: 86% of the probability mass goes to the two nodes that are two hops from where the walk came from. The walk runs away from its origin, sees whole communities, and the embedding it produces groups nodes that sit together in a dense region. The paper calls this the DFS-like regime and associates it with homophily. Read the third: 80% of the mass stays on nodes within one hop of the origin, the walk circles a small neighbourhood, and nodes with similar local wiring — two bridge nodes on opposite sides of a graph, say — get similar vectors. That is the BFS-like regime and the paper associates it with structural equivalence.

The direction of that mapping is the single most commonly inverted fact about node2vec. q > 1 is local and structural; q < 1 is outward and community-flavoured. The paper searches p, q over {0.25, 0.5, 1, 2, 4} by cross-validation rather than picking a default, which is the right instinct: which regime you want is a property of your task, not of your graph. And node2vec with p = q = 1 is DeepWalk, a point the node2vec paper makes itself.

From walk to training pair

Once you have walks, the rest is mechanical. Slide a window over each walk and emit (centre, context) pairs:

walk:    A  C  E  B  C  D  F
window k = 2, centred on E (position 3):

  context = { A, C, B, C }
  pairs   = (E,A) (E,C) (E,B) (E,C)

Two details of that step are easy to lose. The window is symmetric and applies within a walk only, so no pair ever spans two walks — a walk boundary is a sentence boundary. And a node repeated inside one window, as C is here, emits the pair twice, which is not a bug: revisiting is exactly the local-structure evidence the p parameter is there to tune, and collapsing duplicates would erase the difference between the settings computed above.

Those pairs go into skip-gram exactly as word pairs would. node2vec uses negative sampling rather than hierarchical softmax — for each true pair it draws a handful of random nodes as negatives and does a logistic update, which its authors note is more efficient than DeepWalk’s tree. The published node2vec settings are d = 128 dimensions, r = 10 walks per node, l = 80 steps per walk, k = 10 window, and a single epoch over the sampled walks.

What these embeddings cannot do

• They are transductive. The output is a lookup table with one row per node that existed at training time. A node added tomorrow has no row, and there is no forward pass that will give it one — you re-run the whole thing. If nodes arrive continuously, this is disqualifying and you want an inductive method like GraphSAGE (Hamilton, Ying and Leskovec, NeurIPS 2017), which learns an aggregator over neighbour features instead of a table.
• They ignore node attributes entirely. Two nodes with identical wiring and completely different content get near-identical vectors. Everything the model knows came out of the topology.
• The second-order walk costs memory. To sample in constant time you precompute the transition distribution for every (previous, current) pair, which the node2vec paper gives as O(a²|V|) space for average degree a. Squaring the degree is fine for a = 10 and painful for a = 1,000, and it is the usual reason a node2vec job dies on a graph DeepWalk handles.
• Dimensions have no meaning. Only distances do, and only up to the arbitrary rotation the training landed in. Two runs with different seeds give incomparable coordinates; anything downstream must be retrained, not just re-pointed.

The walks themselves are worth understanding separately from the embedding pipeline that consumes them — what a walk converges to, and when it does not, is on random walk algorithms on graphs.