DeepWalk

DeepWalk is a learning technique that falls under the subcategory of algorithms where a random walk must be performed over the graph to find optimal embeddings. To make sense of random walk-based learning techniques, let’s rewind and pick up from where the previous section left off. Remember that the objective of this exercise is to come up with an embedding for every node in the graph so that pairs of embeddings are very similar in the vector space if – and only if – the nodes these embeddings represent are also very similar in the graph.

To achieve this goal, we must define what similar means in both the vector space and the graph. Similarity in the vector space is often defined using the cosine similarity function (other similarity functions can also be used, such as L1-similarity, but for the graph use case, cosine similarity remains the most popular). Let’s start by defining cosine similarity.

Let’s say we have the embeddings of...