Boosting Graph Embedding on a Single GPU
This addresses the scalability issue for researchers and practitioners working with large graphs, enabling efficient embedding with minimal hardware, though it is incremental as it builds on existing embedding methods with hardware optimizations.
The authors tackled the problem of expensive graph embedding for large-scale graphs by developing GOSH, a GPU-based tool that sets a new state-of-the-art in link prediction accuracy and speed, embedding a graph with over 65 million vertices and 1.8 billion edges in less than 30 minutes on a single GPU.
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.