2 edited tags
| link
source | link

How can node2vec help find similar "roles" within a graph (nodes whose connections have similar structure within the graph)?

I have a question on the node2vec algorithm described in this paper.

Node2vec is a deep learning algorithm that word2vec to graphs to learn embeddings. The authors claim that it can help find nodes with similar "roles", or nodes whose connections have similar structure within the graph (structural equivalence), such as two nodes that are both hubs.

However, it uses word2vec, specifically the Skipgram architecture. The Skipgram algorithm takes text as input and for each word, it looks within a window and finds specific nearby words within the vocabulary. Then for a word i, it then aims to learn the probability that word j appears near it, for j = 1,...,N (N being the vocabulary size). In the end, words with similar context will have similar embeddings.

Applied to a graph, each word is a node. The authors determine the window of nearby nodes by doing repeated random walks starting from that node. So from my understanding, node2vec should only be able to learn similar embeddings for nodes that are in the same community (i.e. appear in the same "context"). How can it produce similar embeddings for nodes that are in distinct communities, but who share the same structural role?

To make it clearer with an example: Say that node A and node B have the same structure but are in different communities. Thus, they should have similar embeddings. However, the nodes that are near node A are extremely different from the nodes near node B. Thus the windows produced by random walks would be extremely different. For node A, the Skipgram architecture learns to find nodes within its window (nodes near node A), so nodes A and B should have different embeddings. So how would node2vec find similar embeddings for A and B?

Thanks so much for your help!