NOMAD: Generating Embeddings for Massive Distributed Graphs
This work addresses the problem of inefficient graph embedding for large-scale applications in web and science domains, offering a scalable solution that is incremental by building on existing proximity-based models like LINE.
The paper tackles the scalability challenge of generating graph embeddings for massive graphs with millions-to-billions of edges by introducing NOMAD, a distributed-memory framework using MPI, which achieves median speedups of 10-100x over reference implementations and 12-370x end-to-end speedups on real-world graphs while maintaining competitive embedding quality.
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.