# NOMAD: Generating Embeddings for Massive Distributed Graphs

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

## Key facts

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

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

- [Efficient Estimation of Word Representations in Vector Space](https://mlsanity.com/paper/1301.3781/) (2013)
- [Distributed Representations of Words and Phrases and their Compositionality](https://mlsanity.com/paper/1310.4546/) (2013)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [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)
- [Representation Learning on Graphs: Methods and Applications](https://mlsanity.com/paper/1709.05584/) (2017)
- [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)
- [Graph Convolutional Networks for Graphs Containing Missing Features](https://mlsanity.com/paper/2007.04583/) (2020)
- [GraphVite: A High-Performance CPU-GPU Hybrid System for Node Embedding](https://mlsanity.com/paper/1903.00757/) (2019)
- [Accelerating Graph Sampling for Graph Machine Learning using GPUs](https://mlsanity.com/paper/2009.06693/) (2020)
- [C-SAW: A Framework for Graph Sampling and Random Walk on GPUs](https://mlsanity.com/paper/2009.09103/) (2020)
- [NuPS: A Parameter Server for Machine Learning with Non-Uniform Parameter Access](https://mlsanity.com/paper/2104.00501/) (2021)
- [GRAPE for Fast and Scalable Graph Processing and random walk-based Embedding](https://mlsanity.com/paper/2110.06196/) (2021)
- [Distributed Graph Embedding with Information-Oriented Random Walks](https://mlsanity.com/paper/2303.15702/) (2023)
- [Efficient Graph Computation for Node2Vec](https://mlsanity.com/paper/1805.00280/) (2018)

## Abstract (arXiv)

Successful machine learning on graphs or networks requires embeddings that not only represent nodes and edges as low-dimensional vectors but also preserve the graph structure. Established methods for generating embeddings require flexible exploration of the entire graph through repeated use of random walks that capture graph structure with samples of nodes and edges. These methods create scalability challenges for massive graphs with millions-to-billions of edges because single-node solutions have inadequate memory and processing capabilities. We present NOMAD, a distributed-memory graph embedding framework using the Message Passing Interface (MPI) for distributed graphs. NOMAD implements proximity-based models proposed in the widely popular LINE (Large-scale Information Network Embedding) algorithm. We propose several practical trade-offs to improve the scalability and communication overheads confronted by irregular and distributed graph embedding methods, catering to massive-scale graphs arising in web and science domains. NOMAD demonstrates median speedups of 10/100x on CPU-based NERSC Perlmutter cluster relative to the popular reference implementations of multi-threaded LINE and node2vec, 35-76x over distributed PBG, and competitive embedding quality relative to LINE, node2vec, and GraphVite, while yielding 12-370x end-to-end speedups on real-world graphs.