The Node2Vec Algorithm

What is Node2Vec?

The Node2Vec is an embedding generation algorithm for nodes. It is one of the most famous algorithms of this class and was proposed in 2016.

The Node2Vec algorithm tries to improve over the DeepWalk algorithm by introducing biasA parameter influencing how random walks explore nearby versus distant nodes, affecting the resulting node embeddings. in the random walks. This allows the researcher to choose between prioritizing local relationships between nodes or global characteristics of the graph.

The biased random walk

A biased random walk is governed by two parameters $p$ and $q$, and both can be considered probabilities. A biased random walk differs from a pure random walk because the probabilities of changing the states are not equal.

The parameter $p$ is used to prioritize breadth-first search (BFS). In this type of search, we look at all elements in the same neighborhood before going deeper. In other words, we try and explore all neighbors of a node before going further in the graph. The image below presents a BFS in a tree graph.

The parameter $q$ is used to prioritize a depth-first search (DFS). In this search, our focus is to go as deep inside the graph as possible, or in other words, as far away from the starting node as possible. This will favor moving to nodes not visited before, therefore favoring a global exploration of the network. The image below presents a DFS in a tree graph.

Let’s say we just move from node $t$ to node $v$ ...