PAPERS-07-003 · Paper — node2vec

The paper

The paper “node2vec: Scalable Feature Learning for Networks” by Aditya Grover and Jure Leskovec, published in 2016 at KDD, is a landmark because it introduced a flexible way to learn graph embeddings that outperformed earlier methods.

Before this paper

Before node2vec, DeepWalk used uniform random walks to generate node sequences, capturing only one fixed notion of similarity. This approach worked well for some graphs but struggled when different tasks required different notions of node relatedness. As a result, embeddings often missed important structural or community information needed for tasks like classification or link prediction. Think of DeepWalk as a single‑lens camera that can only focus at one distance, whereas node2vec brings a zoom lens that can adjust focus to capture both close‑up details and the broader scene.

The key idea

The key insight of node2vec is to guide random walks with two tunable parameters, allowing the walks to smoothly interpolate between staying close to a node (breadth‑first) and exploring far away (depth‑first). By adjusting these parameters, the same algorithm can capture either structural roles or community membership as needed, effectively letting the walk “choose” the right perspective for the downstream task.

How it works

node2vec first builds a biased random walk sampler. At each step it considers the previous node and applies a return parameter that controls the likelihood of backtracking, and an in‑out parameter that controls the preference for exploring outward versus staying local. These biases produce walks that can be more BFS‑like or DFS‑like depending on the settings. For example, setting the return parameter p = 0.5 and the in‑out parameter q = 2 makes the walk favor outward exploration while discouraging immediate back‑tracking, yielding longer‑range context. The generated walks are then fed into the skip‑gram model, exactly as DeepWalk did, to learn low‑dimensional embeddings for each node.

See it — tuning the walk

flowchart LR
  A["Return param p<br/>+ in-out param q"] --> B["Biased walk"]
  B --> C["BFS: local roles"]
  B --> D["DFS: communities"]

What they showed

The authors showed that by tuning the walk, node2vec produced better, task‑adaptable embeddings and improved node classification and link prediction over DeepWalk.

What it changed

node2vec made graph embeddings flexible, turning the random‑walk strategy into a tunable tool rather than a fixed one. This flexibility quickly made it a widely used baseline for network representation learning, influencing many later methods. Next: Graph Convolutional Networks (GCN).

The one-line takeaway

A simple bias in random walks can turn a one‑size‑fits‑all embedding into a task‑specific powerhouse.

Read it / meet it

Reading the original node2vec paper reveals the elegant simplicity behind its success and helps you understand many modern graph‑learning techniques. Its legacy lives on in countless libraries and papers that build on its biased‑walk framework.