  In graph embedding, the connectivity information of a graph is used to
represent each vertex as a point in a d-dimensional space. Unlike the original,
irregular structural information, such a representation can be used for a
multitude of machine learning tasks. Although the process is extremely useful
in practice, it is indeed expensive and unfortunately, the graphs are becoming
larger and harder to embed. Attempts at scaling up the process to larger graphs
have been successful but often at a steep price in hardware requirements. We
present GOSH, an approach for embedding graphs of arbitrary sizes on a single
GPU with minimum constraints. GOSH utilizes a novel graph coarsening approach
to compress the graph and minimize the work required for embedding, delivering
high-quality embeddings at a fraction of the time compared to the
state-of-the-art. In addition to this, it incorporates a decomposition schema
that enables any arbitrarily large graph to be embedded using a single GPU with
minimum constraints on the memory size. With these techniques, GOSH is able to
embed a graph with over 65 million vertices and 1.8 billion edges in less than
an hour on a single GPU and obtains a 93% AUCROC for link-prediction which can
be increased to 95% by running the tool for 80 minutes.
