DeepWalk

Definition

DeepWalk is a random walk based Node Embedding method capturing the structural information of a Graph by performing random walks on it. This method can handle large graphs efficiently, and can be applied to various types of graphs (directed, undirected, weighted). However, it does not incorporate node attributes or features.

Algorithm

1. Run short fixed-length uniform random walks starting from each node $u$ in the graph.
2. These walks generate sequences of nodes $N(u)$ for each node, similar to sentences in natural language processing.
3. The sequences are then fed into a Word2Vec-like model to learn vector representations for each node.