# VERSE: Versatile Graph Embeddings from Similarity Measures

arXiv: https://arxiv.org/abs/1803.04742 · HTML: https://mlsanity.com/paper/1803.04742/

## Key facts

- Cited by 54 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Mar 2018.

## Built on by (most cited first, 30 of 54)

- [A Survey on Graph Representation Learning Methods](https://mlsanity.com/paper/2204.01855/) (2022)
- [Boost then Convolve: Gradient Boosting Meets Graph Neural Networks](https://mlsanity.com/paper/2101.08543/) (2021)
- [Linkless Link Prediction via Relational Distillation](https://mlsanity.com/paper/2210.05801/) (2022)
- [Scalable Multitask Learning Using Gradient-based Estimation of Task Affinity](https://mlsanity.com/paper/2409.06091/) (2024)
- [Network Representation Learning: From Preprocessing, Feature Extraction to Node Embedding](https://mlsanity.com/paper/2110.07582/) (2021)
- [Source Localization of Graph Diffusion via Variational Autoencoders for Graph Inverse Problems](https://mlsanity.com/paper/2206.12327/) (2022)
- [A Broader Picture of Random-walk Based Graph Embedding](https://mlsanity.com/paper/2110.12344/) (2021)
- [Boosting Multitask Learning on Graphs through Higher-Order Task Affinities](https://mlsanity.com/paper/2306.14009/) (2023)
- [Differentially Private Graph Learning via Sensitivity-Bounded Personalized PageRank](https://mlsanity.com/paper/2207.06944/) (2022)
- [DeepGD: A Deep Learning Framework for Graph Drawing Using GNN](https://mlsanity.com/paper/2106.15347/) (2021)
- [Unsupervised Embedding Quality Evaluation](https://mlsanity.com/paper/2305.16562/) (2023)
- [Cleora: A Simple, Strong and Scalable Graph Embedding Scheme](https://mlsanity.com/paper/2102.02302/) (2021)
- [A Robust and Generalized Framework for Adversarial Graph Embedding](https://mlsanity.com/paper/2105.10651/) (2021)
- [Effective Clustering on Large Attributed Bipartite Graphs](https://mlsanity.com/paper/2405.11922/) (2024)
- [MOOMIN: Deep Molecular Omics Network for Anti-Cancer Drug Combination Therapy](https://mlsanity.com/paper/2110.15087/) (2021)
- [Recommending Related Products Using Graph Neural Networks in Directed Graphs](https://mlsanity.com/paper/2211.11583/) (2022)
- [From Cluster Assumption to Graph Convolution: Graph-based Semi-Supervised Learning Revisited](https://mlsanity.com/paper/2309.13599/) (2023)
- [The Graph Lottery Ticket Hypothesis: Finding Sparse, Informative Graph Structure](https://mlsanity.com/paper/2312.04762/) (2023)
- [Efficient Topology-aware Data Augmentation for High-Degree Graph Neural Networks](https://mlsanity.com/paper/2406.05482/) (2024)
- [Learning Based Proximity Matrix Factorization for Node Embedding](https://mlsanity.com/paper/2106.05476/) (2021)
- [Evaluating Node Embeddings of Complex Networks](https://mlsanity.com/paper/2102.08275/) (2021)
- [Multiple Kernel Representation Learning on Networks](https://mlsanity.com/paper/2106.05057/) (2021)
- [Contrastive Learning for Non-Local Graphs with Multi-Resolution Structural Views](https://mlsanity.com/paper/2308.10077/) (2023)
- [On the Role of Edge Dependency in Graph Generative Models](https://mlsanity.com/paper/2312.03691/) (2023)
- [Free Energy Node Embedding via Generalized Skip-gram with Negative Sampling](https://mlsanity.com/paper/2105.09182/) (2021)
- [Leveraging semantically similar queries for ranking via combining representations](https://mlsanity.com/paper/2106.12621/) (2021)
- [A Comprehensive Analytical Survey on Unsupervised and Semi-Supervised Graph Representation Learning Methods](https://mlsanity.com/paper/2112.10372/) (2021)
- [LoNe Sampler: Graph node embeddings by coordinated local neighborhood sampling](https://mlsanity.com/paper/2211.15114/) (2022)
- [Distributed Graph Embedding with Information-Oriented Random Walks](https://mlsanity.com/paper/2303.15702/) (2023)
- [Zoo Guide to Network Embedding](https://mlsanity.com/paper/2305.03474/) (2023)

## Abstract (arXiv)

Embedding a web-scale information network into a low-dimensional vector space facilitates tasks such as link prediction, classification, and visualization. Past research has addressed the problem of extracting such embeddings by adopting methods from words to graphs, without defining a clearly comprehensible graph-related objective. Yet, as we show, the objectives used in past works implicitly utilize similarity measures among graph nodes. In this paper, we carry the similarity orientation of previous works to its logical conclusion; we propose VERtex Similarity Embeddings (VERSE), a simple, versatile, and memory-efficient method that derives graph embeddings explicitly calibrated to preserve the distributions of a selected vertex-to-vertex similarity measure. VERSE learns such embeddings by training a single-layer neural network. While its default, scalable version does so via sampling similarity information, we also develop a variant using the full information per vertex. Our experimental study on standard benchmarks and real-world datasets demonstrates that VERSE, instantiated with diverse similarity measures, outperforms state-of-the-art methods in terms of precision and recall in major data mining tasks and supersedes them in time and space efficiency, while the scalable sampling-based variant achieves equally good results as the non-scalable full variant.