How Node2Vec Works – A Random Walk-Based Node Embedding Method

Node2Vec is a graph-based node embedding method developed by Aditya Grover and Jure Leskovec that uses biased random walks to explore network neighborhoods flexibly. Unlike traditional random walks, Node2Vec incorporates two hyperparameters, p and q, to influence the walk sampling, allowing it to mimic either Breadth-First Search (BFS) or Depth-First Search (DFS) strategies. This bias enables the algorithm to capture either homophily or structural equivalence among nodes, essential for prediction tasks like link prediction and node classification. The method calculates edge transition probabilities using these biases and normalizes them to guide the walks, which are then used to generate node embeddings. These embeddings reflect the structural or community-based relationships within the graph, optimized by maximizing the probability of observing neighborhood nodes in the embedded space. The algorithm is already implemented in Python's gensim module and is applicable for real-time graph analytics.