The first presented algorithm [1]} for learning node embeddings works by generating random walks, starting from each node \(u\)  in the given graph, and then feeding the sequences of visited nodes into a word embedding learning algorithm such as word2vec [2]}. Later, these approaches were extended to a more general setting where different neighborhood definitions are supported and one can sample from these neighborhoods [3]}, [4]}, [5]}.
Algorithms based on random walks generate samples that are independent for different nodes, i.e., a random walk starting from a node \(u\)  is likely to be very different from a random walk starting at another node \(v\) , even if \(u\)  and \(v\)  have very similar neighborhoods, for some intuitive notion of similarity. By generating a large number of random walks the sets of sampled nodes for \(u\)  and \(v\)  will eventually reflect the similarity between \(u\)  and \(v\)  but individual samples are much less likely to preserve the similarity. As an illustration, consider a large social network such as twitter where nodes represent users and edges who-follows-whom relationships. Consider two nodes corresponding to the famous football managers Jürgen Klopp and Pep Guardiola. Maybe they don't have so many followers in common as they represent football rivals. Let \(K\)  and \(G\)  be Klopp's and Guardiola's 2-hop neighborhood local graphs, respectively. We might expect that the nodes in these “friends of friends” graphs, \(V(K)\)  and \(V(G)\) , will have a large overlap as they likely capture the majority of English football fans. However, if we sample nodes at random from \(V(K)\)  and \(V(G)\) , then most likely the sampled nodes will be different. But assume we were able to randomly permute the nodes in \(V(K) \cup V(G)\)  and then return the first node from \(V(K)\)  and \(V(G)\) , according to the total order defined by the permutation, as samples for Klopp and Guardiola. Then it would be much more likely to get the same node. In the case of random walks the probability for identical samples is \(\frac{|V(G) \cap V(K)|}{|V(G)||V(K)|}\)  and in the case of random permutations it is \(\frac{|V(G) \cap V(K)|}{|V(G) \cup V(K)|}\) , i.e., the samples already capture that Klopp and Guardiola are similar twitter users. And if we also consider the profiles of the sampled nodes, say by analyzing the activity of the corresponding users, then we might be able to infer that Klopp and Guardiola are Premier League managers.
