In the node2vec paper1 it is mentioned that when using BFS to embed nodes, the results correspond to structural equivalence (i.e. nodes that are "bridge nodes" would get embedded close together) rather than homophily (where nodes that are part of the same network community, a result of DFS). I understand how embeddings of in-the-same-community nodes can have the close together embeddings, since "you know a word by the company it keeps"; or put another way, you are training the word2vec model based on context.

What I don't understand is how structural equivalence happens, i.e. how a bridge node in one part of a large network can have a similar embedding to a bridge node in a totally different part of the network. I would assume that the random walks generated never (or at least, seldom) have both nodes. Then how can we guarantee (or even expect) similar embeddings for such pairs? What is the intuition behind this?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.