PAPERS-07-002 · Paper — DeepWalk

The paper

DeepWalk, introduced by Bryan Perozzi, Rami Al-Rfou, and Steven Skiena in 2014 at KDD, is considered a landmark because it was the first to bring word‑embedding techniques to graphs, opening a new way to learn node features automatically.

Before this paper

Before DeepWalk, graph‑based machine learning relied on hand‑crafted features, which were labor‑intensive and often limited. Models expected vector inputs, yet graphs are naturally described by nodes and edges. Researchers struggled to turn network structure into useful numeric representations without extensive domain knowledge. This bottleneck hindered progress on tasks like node classification when labeled data were scarce.

The key idea

The core insight of DeepWalk is to treat random walks on a graph like sentences of words. By feeding these walks into the word2vec skip‑gram model, each node learns a dense vector that reflects its context in the graph, much like word meanings are captured from text.

How it works

First, the algorithm performs many short random walks from each node, generating sequences of node IDs. These sequences are analogous to sentences, where each node plays the role of a word. Next, the skip‑gram model is trained on these “sentences,” trying to predict neighboring nodes within a fixed window for each target node. Through stochastic gradient descent, the model adjusts node embeddings so that nodes appearing close together in walks end up close in the vector space. The result is a low‑dimensional representation for every node that encodes both community proximity and structural roles, all without using any labels.

See it — walks as sentences

flowchart LR
  A["Random walks<br/>on the graph"] --> B["Treat walks<br/>as sentences"]
  B --> C["Skip-gram<br/>(word2vec)"]
  C --> D["Node vectors"]

What they showed

DeepWalk’s learned embeddings beat prior methods on node classification tasks, especially when labeled data were scarce, demonstrating the power of the random‑walk‑plus‑skip‑gram approach.

What it changed

The paper launched the field of graph representation learning by showing that ideas from natural‑language processing could be transferred to networks. It sparked a wave of node‑embedding techniques that have since been applied to recommendations, social‑network analysis, and many other domains. By providing a simple, scalable method, DeepWalk set a new standard for how researchers approach graph‑based feature learning. Next: node2vec.

The one-line takeaway

Random walks + word2vec turned graphs into easy‑to‑use vector embeddings, changing the game for network analysis.

Read it / meet it

Reading DeepWalk is rewarding because it explains the elegant bridge between language models and graphs. Its legacy lives on in modern graph neural networks and countless recommendation systems that still build on its random‑walk embedding foundation.