Understanding node2vec: Biased Random Walks for Graph Embedding

node2vec: Algorithm Principle, Implementation, and Applications

Previously we introduced DeepWalk (DFS‑based) and LINE (BFS‑based). node2vec is a graph‑embedding method that jointly considers DFS and BFS neighborhoods, essentially extending DeepWalk with biased random walks.

Algorithm Principle

Let f: V \rightarrow \mathbb{R}^d be the mapping from each vertex to an embedding vector. For each vertex we define the set of neighbor vertices sampled by a strategy and aim to maximize the conditional probability of these neighbors given the source vertex.

node2vec's optimization goal is to maximize, for each vertex, the probability that its neighbor vertices appear, which can be expressed as:

Because the normalization factor is costly to compute, negative sampling is used to optimize the objective.

Two Key Assumptions

Conditional independence: given a source vertex, the appearance of a neighbor vertex is independent of other vertices in the neighbor set.

Feature‑space symmetry: a vertex uses the same embedding vector whether it acts as a source or as a neighbor (unlike LINE, which uses separate vectors).

Under these assumptions the final objective function becomes:

Biased Random‑Walk Sampling Strategy

node2vec still uses random walks to obtain vertex sequences, but the walk is biased by two hyper‑parameters p (return parameter) and q (in‑out parameter). The transition probability from the current vertex v to a neighbor x, given the previous vertex t, is:

If p is large, the walk is less likely to return to the previous vertex; if q is large, the walk prefers vertices farther from t (DFS‑like), while a small q makes the walk stay close to t (BFS‑like).

Implementation Details

The core code closely follows the original paper and uses the Alias method for O(1) discrete sampling.

def node2vec_walk(self, walk_length, start_node):
    G = self.G
    alias_nodes = self.alias_nodes
    alias_edges = self.alias_edges
    walk = [start_node]
    while len(walk) < walk_length:
        cur = walk[-1]
        cur_nbrs = list(G.neighbors(cur))
        if len(cur_nbrs) > 0:
            if len(walk) == 1:
                walk.append(cur_nbrs[alias_sample(alias_nodes[cur][0], alias_nodes[cur][1])])
            else:
                prev = walk[-2]
                edge = (prev, cur)
                next_node = cur_nbrs[alias_sample(alias_edges[edge][0], alias_edges[edge][1])]
                walk.append(next_node)
        else:
            break
    return walk

def get_alias_edge(self, t, v):
    G = self.G
    p = self.p
    q = self.q
    unnormalized_probs = []
    for x in G.neighbors(v):
        weight = G[v][x].get('weight', 1.0)
        if x == t:
            unnormalized_probs.append(weight / p)
        elif G.has_edge(x, t):
            unnormalized_probs.append(weight)
        else:
            unnormalized_probs.append(weight / q)
    norm_const = sum(unnormalized_probs)
    normalized_probs = [float(u) / norm_const for u in unnormalized_probs]
    return create_alias_table(normalized_probs)

def preprocess_transition_probs(self):
    G = self.G
    alias_nodes = {}
    for node in G.nodes():
        unnormalized_probs = [G[node][nbr].get('weight', 1.0) for nbr in G.neighbors(node)]
        norm_const = sum(unnormalized_probs)
        normalized_probs = [float(u) / norm_const for u in unnormalized_probs]
        alias_nodes[node] = create_alias_table(normalized_probs)
    alias_edges = {}
    for edge in G.edges():
        alias_edges[edge] = self.get_alias_edge(edge[0], edge[1])
    self.alias_nodes = alias_nodes
    self.alias_edges = alias_edges
    return

Applications

Using node2vec on the Wiki dataset (2,405 pages, 17,981 links) for node classification and visualization with hyper‑parameters p=0.25 and q=4 yields micro‑F1=0.6757 and macro‑F1=0.5917, outperforming DeepWalk and LINE.

Visualization shows a more dispersed distribution of different categories.

Reference Implementation

The full training, evaluation, and visualization code is available at:

https://github.com/shenweichen/GraphEmbedding

Reference

Grover A, Leskovec J. node2vec: Scalable Feature Learning for Networks. KDD 2016.