The DeepWalk Algorithm

What is the DeepWalk algorithm?

The DeepWalk algorithm is an embedding generator algorithm, which means it receives a graph as an input and then outputs the embedding of the nodes of this graph as a vector representation.

This algorithm was proposed in 2014 as a way of learning representations for social online relationships and uses random walks as a core concept.

Random walk and similarity

The algorithm makes the assumption that nodes that are adjacent should have similar embeddings because they are similar in the network. Therefore, the concept of homophily is essential. Homophily states that similar nodes tend to connect in a network. In other words, if two nodes are expected to share some characteristic, such as having the same job, we say that this network has a homophily characteristic.

In order to assess the similarity between those nodes, we set, for each node, $k$ random walks, each with a length $l$.

For example, let’s consider the graph below with $k=3$ and $l=3$: