Boosting large-scale graph embedding with multi-level graph coarsening

Official URL: https://risc01.sabanciuniv.edu/record=b2486357 _(Table of contents)

Graphs can be found anywhere from protein interaction networks to social networks. However, the irregular structure of graph data constitutes an obstacle for running machine learning tasks such as link prediction, node classification, and anomaly detection. Graph embedding is the process of representing graphs in a multidimensional space, which enables machine learning tasks to be run on graphs. Although, embedding is proven to be advantageous by a series of works, it is computeintensive. Current embedding approaches either can not scale to large graphs or they require expensive hardware for such purposes. In this work we propose a novel, parallel multi-level coarsening method to boost the performance of graph embedding both in terms of speed, and accuracy. We integrate the proposed coarsening approach into a GPU-based graph embedding tool called Gosh, which is able to embed large-scale graphs with a single GPU at a fraction of the time compared to the state-of-the-art. When coarsening is introduced, the run-time of Gosh improves by 14× while scoring greater AUCROC for the majority of medium-scale graphs. For the largest graph in our data-set with 66 million vertices, and 1.8 billion edges, embedding takes under an hour, and 93.4% AUCROC is achieved. Moreover, we investigate the relationship between quality of the coarsening on the quality of the embeddings. Our preliminary experiments show that the coarsening decisions must be balanced and the proposed coarsening strategy novel performs well for graph embedding