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

Warning The system is temporarily closed to updates for reporting purpose.

Akyıldız, Taha Atahan (2020) Boosting large-scale graph embedding with multi-level graph coarsening. [Thesis]

PDF - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader

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

Item Type:Thesis
Uncontrolled Keywords:Graph coarsening. -- graph embedding. -- GPU. -- parallel graph algorithms. -- link prediction. -- çizge irileştirme. -- çizge katıştırma. -- ekran kartı. -- bağlantı tahmini. -- paralel algoritmalar.
Subjects:T Technology > TK Electrical engineering. Electronics Nuclear engineering > TK7800-8360 Electronics > TK7885-7895 Computer engineering. Computer hardware
ID Code:41179
Deposited By:IC-Cataloging
Deposited On:24 Oct 2020 12:00
Last Modified:24 Oct 2020 12:00

Repository Staff Only: item control page