DeepWalk

DeepWalk is an unsupervised representation learning method for graphs. Introduced in 2014 by Bryan Perozzi, Rami Al-Rfou, and Steven Skiena, it learns low-dimensional vector representations of nodes that preserve network neighborhoods and structural similarities.

The core idea is to generate a large corpus of node sequences by performing truncated random walks on the graph. Each walk produces a sequence of node identifiers, which is treated as a sentence. A skip-gram model, as in Word2Vec, is then trained to maximize the likelihood of observing a node’s context within a fixed window given the node as the center. Negative sampling is typically used to scale the training. The result is a dense embedding for every node in the graph.

DeepWalk relies on uniform random walks to capture both local and global network structure. The learned embeddings reflect proximity in the graph and can also reveal community structure. The method is unsupervised and scalable, suitable for large networks, and can be applied to unweighted graphs directly (or extended to weighted graphs with adjusted walk probabilities).

Applications include node classification, link prediction, clustering, and visualization. DeepWalk demonstrated that language-modeling techniques could be effectively applied to graphs and influenced subsequent work, such as node2vec and other graph representation learning approaches that explore alternative walk strategies or incorporate supervision.

Limitations include sensitivity to hyperparameters (walk length, number of walks, window size, embedding dimension), and its original design for static, undirected graphs without edge attributes.