Node2Vec

Definition

Node2Vec is an extension of DeepWalk that introduces more flexible random walks. The model can capture both local and global network structure

Algorithm

1. Run short fixed-length biased random walks starting from each node $u$ in the graph using some random walk strategy $R(p,q)$.

Consider a random walk that just traversed edge $(t,v)$ and now resides at node $v$. The unnormalized transition probability ${\alpha }_{pq}(t,x)$ on edges $(v,x)$ is given by ${\alpha }_{pq}(t,x)=\{\begin{array}{ll}\frac{1}{p}& d(t,x)=0\\ 1& d(t,x)=1\\ \frac{1}{q}& d(t,x)=2\end{array}$ where:

• $p$ is the return parameter, controlling the likelihood of immediately revisiting a node in the walk
• $q$ is the in-out parameter controlling the search strategy (depth-first vs. breadth-first)
• $d(u,x)\in \{0,1,2\}$ is the shortest path distance between node $t$ and $x$

2. These walks generate sequences of nodes $N_R(u)$ for each node, similar to sentences in natural language processing.
3. The sequences are then fed into a Word2Vec-like model to learn vector representations for each node.