Skip to Content

VERSE: Versatile Graph Embeddings from Similarity Measures

VERtex Similarity Embedding
Can a single model capture three highlighted node properties?

paper · pdf · code · slides pptx pdf


State-of-the-art graph embedding algorithms are neural similarity matrix compression algorithms.

In this paper:

  • We take the perspective of node similarities for node embedding.
  • We show how previous works1 implicitly utilize similarities.
  • We develop an algorithm (VERSE) to efficiently preserve similarities.
  • We create two VERSE versions: full that uses all node-to-node information, and sampled one that runs in linear time, yet provably converges to the full variant.
  • We provide code in efficient C++ for both full and sampled version. We also provide efficient implementations of our baseline algorithms: DeepWalk and node2vec.
  • We propose novel evaluation tasks (clustering, graph reconstruction) for graph embeddings.