NOMAD: Generating Embeddings for Massive Distributed Graphs

Aishwarya Sarkar; Sayan Ghosh; Nathan R. Tallent; Ali Jannesari

cs.LGApr 10, 2026

NOMAD: Generating Embeddings for Massive Distributed Graphs

Authors: Aishwarya Sarkar, Sayan Ghosh, Nathan R. Tallent, Ali Jannesari

Abstract

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.

Figures & tables

Framework	CPU	GPU	Distributed	Sampling	Training	Scale Up	Scale Out	Partitioned graph	Notes
NOMAD (this work)	✓	✗	✓	✓	✓	✓	✓	✓	MPI collective communication and synchronization
PyTorch-BigGraph [ 1 ]	✓	✗	✓	✓	✓	✓	✓	✓	Parameter-server architecture with shared parameter synchronization
Fast-Node2vec [ 2 ]	✓	✗	✓	✓	✓	✓	✓	✓	Pregel-like iterative BSP
GraphVite [ 3 ]	✓	✓	✗	✓	✓	✓	✗	✗	Hybrid, OpenMP threads for sampling; GPU-based training
Grape [ 4 ]	✓	✗	✗	✓	✓	✓	✗	✗	Thread-level SIMD parallelism
CuGraph [ 5 ]	✗	✓	✓	✓	✗	✓	✓	✓	Dask-based multi-GPU random walk sampling (no training)

TABLE I : Comparison of NOMAD with existing graph sampling and embedding systems.

Fig. 1 : With sync: processes observe up-to-date context. Without sync: delayed updates result in stale context, affecting quality.

Panel of Figure 3 — Algorithm 1 NOMAD: Distributed Node Embedding Inputs: $G_{p}=(V_{p},E_{p})$ portion of the (undirected) graph $G$ on Process $p$ , containing “local” and “ghost” vertices (not owned by process $p$ ) that have an edge with a vertex $v\in V_{p}$ ; batch size $B$ ; #negatives per positive pair: K; $\lambda$ : weight decay; $\eta$ : learning rate; $\alpha_{\text{neg}}$ : negative weight; Output: Embeddings $\mathbf{U}$ and $\mathbf{C}$

Panel of Figure 4 — Algorithm 2 Random Walks using MPI peer-to-peer interface. Input : $G_{p}=(V_{p},E_{p})$ partition of (undirected) graph $G$ in process $p$ , containing “local” and “ghost” vertices (not owned by process $p$ ) that have an edge with a vertex $v\in V_{p}$ . $SIZE$ is the outgoing/incoming buffer size, $steps$ is the walk length, {u, v} is the root edge to begin the walk and $\mathcal{N}(x)$ represents the (weighted) neighborhood of an arbitrary vertex $x$ . InOut : Edges in random walk over $G$ : $\mathcal{P}$ (local) and $\mathcal{P^{\prime}}$ (remote).

Panel of Figure 5 — Algorithm 3 Invoking random walks for generating batches for sampling. Input : $G_{p}=(V_{p},E_{p})$ portion of the (undirected) graph $G$ on process $p$ . InOut : Edges in random walk over $G$ : $\mathcal{P}$ (local) and $\mathcal{P^{\prime}}$ (remote).

Datasets	$\|V\|$	$\|E\|$	$\min/\max(\sigma_{E_{p}})$	Speedup
pubmed [ 40 ]	20K	89K	12 $/\penalty$ 152	12 $\times$
photo [ 41 ]	7.5K	238K	16 $/\penalty$ 1K	37 $\times$
computers [ 41 ]	13K	491K	39 $/\penalty$ 3K	58 $\times$
physics [ 41 ]	34K	495K	9 $/\penalty$ 181	23 $\times$
ogbn-arxiv [ 42 ]	169K	2.3M	60 $/\penalty$ 2K	99 $\times$
youtube [ 43 ]	1.1M	9.8M	199 $/\penalty$ 6K	370 $\times$

TABLE II: Best speedups observed across processes/variants.

Fig. 2 : Comparison of Nomad with LINE and node2vec.

Fig. 3 : Comparison of Nomad with PBG

Dataset	LINE		node2vec		GraphVite		Nomad (local)		Nomad (remote)
	Mi	Ma	Mi	Ma	Mi	Ma	Mi	Ma	Mi	Ma
computers	0.61	0.50	0.50	0.41	0.79	0.74	0.83	0.82	0.83	0.83
physics	0.59	0.31	0.74	0.69	0.60	0.41	0.78	0.69	0.83	0.77
pubmed	0.41	0.30	0.48	0.43	0.40	0.22	0.62	0.53	0.53	0.40
photo	0.77	0.73	0.51	0.48	0.77	0.70	0.84	0.82	0.89	0.88
youtube	0.25	0.06	0.40	0.29	0.31	0.14	0.27	0.11	0.25	0.07

TABLE III: Micro-F1 (Mi), Macro-F1 (Ma) on 10% test nodes.

Panel of Figure 10 — Fig. 4 : Embedding quality (Micro-F1, higher is better) on computers (left) and reddit (right) with increasing #processes.

Fig. 5 : End-to-end time of Nomad variants on ogbn-arxiv

Fig. 6 : Scalability of Nomad on 13 diverse datasets (Table II ) up to 16K processes. Top: AllReduce; Bottom: Ibarrier.

Fig. 7 : Distribution of positive samples across processes for AR-Local and AR-Remote (Reuse-Spill) on large datasets. Red markers denote IB-Local and IB-Remote (Reuse-Spill) , which show little or no variation across processes.

arxiv ( $\|E\|$ =2.3M, $\sigma_{E_{p}}$ =643)						youtube ( $\|E\|$ =9.8M, $\sigma_{E_{p}}$ =11,127)
Local (%MPI=99.4, Avg. Mem./PE=201 MiB)			Remote (%MPI=99.7, Avg. Mem./PE=208 MiB)			Local (%MPI=99.4, Avg. Mem./PE=247 MiB)			Remote (%MPI=98.8, Avg. Mem./PE=260 MiB)
% Total	% Imbal.	Function	%Total	% Imbal.	Function	% Total	% Imbal.	Function	% Total	% Imbal.	Function
46	9	MPI_Alltoallv	55	12	MPI_Allreduce	76	5	MPI_Alltoallv	80	1	MPI_Alltoallv
35	45	MPI File I/O	15	11	MPI_Barrier	11	14	MPI_Alltoall	9	13	MPI_Allreduce
12	35	MPI_Allreduce	13	5	MPI_Alltoallv	9	26	MPI_Allreduce	6	12	MPI_Alltoall
7	38	MPI_Barrier	9	40	MPI File I/O	2	30	MPI_Barrier	1	33	MPI_Barrier

TABLE IV : Communication analysis using CrayPAT on 2048 processes (

n

=32, ppn=64)

Fig. 8 : Breakdown of end-to-end execution time.

Fig. 9 : 2 MB huge pages on IB-Remote (Aug-Pair) . Top: sampling/training breakdown. Bottom: end-to-end time.

Fig. 10 : RMA variants increases load imbalance for Refresh-Spill (depicted by error bars): comparing regular against RMA for Refresh-Spill and Aug-Pair .

youtube (default) MPI utilization			youtube (RMA) MPI utilization
%-time	%-imb.	Function	%-time	%-imb.	Function
74	1	MPI_Alltoallv	51	42	MPI_Allreduce
15	10	MPI_Allreduce	27	51	MPI_Win_flush_all
6	10	MPI_Alltoall	13	58	MPI_Win_flush_local_all

TABLE V : Top #3 MPI util. (

>

90% of overall time) for default and RMA variants of Nomad for youtube (1024 processes).

Graph Embedding

Graph embedding maps nodes, edges, or whole graphs into vectors that capture structure for prediction, clustering, retrieval, and analysis.

See all 53 papers

FeLoG: Scalable and Efficient Distributed Graph Embedding with Feedback Loop Mechanism
Jun 20, 2026Peng Fang, Arijit Khan, Ziqiang Wu +4Communication-Efficient Distributed Training Graph Embedding
Huazhong University of Science and Technology · Bowling Green State University
EmbedPart: Embedding-Driven Graph Partitioning for Scalable Graph Neural Network Training
Apr 1, 2026Nikolai Merkel, Ruben Mayer, Volker Markl +1Graph Partitioning Graph Neural Networks
Technical University of Munich (TUM) · University of Bayreuth · TU Berlin, BIFOLD, DFKI +1
Random Wavelet Features for Graph Kernel Machines
Feb 17, 2026Valentin de Bassompierre, Jean-Charles Delvenne, Laurent JacquesGraph Representation Learning Graph Embedding
INMA/ICTEAM, UCLouvain, Belgium

Jun 20, 2026J/K move · Enter open · S save

FeLoG: Scalable and Efficient Distributed Graph Embedding with Feedback Loop Mechanism

Peng Fang, Arijit Khan, Ziqiang Wu, Zhenli Li+3

Huazhong University of Science and Technology · Bowling Green State University

Communication-Efficient Distributed Training Graph Embedding

Open paper AskPDF arXiv

Graph embedding maps graph nodes into low-dimensional vectors to support applications such as recommendation, fraud detection, and graph-based retrieval-augmented generation (GraphRAG). As graphs scale to billions of edges, scalable and efficient graph embedding has become increasingly important. Existing frameworks commonly adopt a sampling-training paradigm, in which mini-batches are constructed by sampling nodes and their neighbors. However, sampling is typically decoupled from evolving embedding quality, causing redundant exploration of well-trained regions while under-sampling undertrained nodes. At the system level, such decoupling further leads to excessive communication, serialized execution, and low resource utilization in distributed environments. We present FeLoG, a feedback loop-driven system for scalable distributed graph embedding. (1) FeLoG introduces feedback-coupled sampling and training, dynamically prioritizing undertrained nodes according to real-time embedding-quality feedback, thereby reducing redundant computation and accelerating convergence. (2) It employs activity-aware communication that compresses frequently occurring node sequences to reduce intra-machine PCIe traffic and selectively synchronizes frequently updated embeddings to reduce inter-machine communication. (3) It adopts a round-interleaved pipeline that overlaps next-round sampling with current-round training to improve CPU-GPU utilization. Experiments against six state-of-the-art baselines on large-scale graphs show that FeLoG achieves an average speedup of 27.9x, reduces communication cost by more than 53.1%, and sustains over 80% CPU-GPU utilization.

Abstract

Graph Embedding

Explore similar work

FeLoG: Scalable and Efficient Distributed Graph Embedding with Feedback Loop Mechanism

EmbedPart: Embedding-Driven Graph Partitioning for Scalable Graph Neural Network Training

Random Wavelet Features for Graph Kernel Machines