Memory Efficient GPU-based Label Propagation Algorithm (LPA) for Community Detection on Large Graphs

Autor:	Sahu, Subhajit
Rok vydání:	2024
Předmět:	Computer Science - Distributed Parallel and Cluster Computing Computer Science - Social and Information Networks G.2.2 I.5.3
Druh dokumentu:	Working Paper
Popis:	Community detection involves grouping nodes in a graph with dense connections within groups, than between them. We previously proposed efficient multicore (GVE-LPA) and GPU-based ($\nu$-LPA) implementations of Label Propagation Algorithm (LPA) for community detection. However, these methods incur high memory overhead due to their per-thread/per-vertex hashtables. This makes it challenging to process large graphs on shared memory systems. In this report, we introduce memory-efficient GPU-based LPA implementations, using weighted Boyer-Moore (BM) and Misra-Gries (MG) sketches. Our new implementation, $\nu$MG8-LPA, using an 8-slot MG sketch, reduces memory usage by 98x and 44x compared to GVE-LPA and $\nu$-LPA, respectively. It is also 2.4x faster than GVE-LPA and only 1.1x slower than $\nu$-LPA, with minimal quality loss (4.7%/2.9% drop compared to GVE-LPA/$\nu$-LPA). Comment: 18 pages, 7 figures, 1 table
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2411.19901 Zobrazit plný text záznamu View this record from Arxiv