# Boosting Graph Embedding on a Single GPU

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 17 of its 35 references that are in the map.
- First posted on arXiv 19 Oct 2021.

## Builds on (most cited first, 17 of 17)

- [node2vec: Scalable Feature Learning for Networks](https://mlsanity.com/paper/1607.00653/) (2016)
- [DeepWalk: Online Learning of Social Representations](https://mlsanity.com/paper/1403.6652/) (2014)
- [LINE: Large-scale Information Network Embedding](https://mlsanity.com/paper/1503.03578/) (2015)
- [Graph Embedding Techniques, Applications, and Performance: A Survey](https://mlsanity.com/paper/1705.02801/) (2017)
- [PyTorch-BigGraph: A Large-scale Graph Embedding System](https://mlsanity.com/paper/1903.12287/) (2019)
- [DGL-KE: Training Knowledge Graph Embeddings at Scale](https://mlsanity.com/paper/2004.08532/) (2020)
- [HARP: Hierarchical Representation Learning for Networks](https://mlsanity.com/paper/1706.07845/) (2017)
- [GraphZoom: A multi-level spectral approach for accurate and scalable graph embedding](https://mlsanity.com/paper/1910.02370/) (2019)
- [VERSE: Versatile Graph Embeddings from Similarity Measures](https://mlsanity.com/paper/1803.04742/) (2018)
- [NetSMF: Large-Scale Network Embedding as Sparse Matrix Factorization](https://mlsanity.com/paper/1906.11156/) (2019)
- [GraphVite: A High-Performance CPU-GPU Hybrid System for Node Embedding](https://mlsanity.com/paper/1903.00757/) (2019)
- [Marius: Learning Massive Graph Embeddings on a Single Machine](https://mlsanity.com/paper/2101.08358/) (2021)
- [Homogeneous Network Embedding for Massive Graphs via Reweighted Personalized PageRank](https://mlsanity.com/paper/1906.06826/) (2019)
- [Faster Graph Embeddings via Coarsening](https://mlsanity.com/paper/2007.02817/) (2020)
- [Swivel: Improving Embeddings by Noticing What's Missing](https://mlsanity.com/paper/1602.02215/) (2016)
- [Network-Efficient Distributed Word2vec Training System for Large Vocabularies](https://mlsanity.com/paper/1606.08495/) (2016)
- [Understanding Coarsening for Embedding Large-Scale Graphs](https://mlsanity.com/paper/2009.04925/) (2020)

## Abstract (arXiv)

Graphs are ubiquitous, and they can model unique characteristics and complex relations of real-life systems. Although using machine learning (ML) on graphs is promising, their raw representation is not suitable for ML algorithms. Graph embedding represents each node of a graph as a d-dimensional vector which is more suitable for ML tasks. However, the embedding process is expensive, and CPU-based tools do not scale to real-world graphs. In this work, we present GOSH, a GPU-based tool for embedding large-scale graphs with minimum hardware constraints. GOSH employs a novel graph coarsening algorithm to enhance the impact of updates and minimize the work for embedding. It also incorporates a decomposition schema that enables any arbitrarily large graph to be embedded with a single GPU. As a result, GOSH sets a new state-of-the-art in link prediction both in accuracy and speed, and delivers high-quality embeddings for node classification at a fraction of the time compared to the state-of-the-art. For instance, it can embed a graph with over 65 million vertices and 1.8 billion edges in less than 30 minutes on a single GPU.