νMG-LPA and νBM-LPA: Memory Efficient GPU-based Label Propagation Algorithms (LPA) for Community Detection

Community detection involves grouping nodes in a graph with dense connections within groups, than between them. Recently, efficient multicore (GVE-LPA) and GPU-based (ν -LPA) implementations of Label Propagation Algorithm (LPA) for community detection have been proposed. 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 paper, we introduce memory-efficient GPU-based LPA, using weighted Boyer-Moore (BM) and Misra-Gries (MG) sketches. Our ν MG8-LPA, using an 8-slot MG sketch, reduces memory usage by 98 × and 44 × compared to GVE-LPA and ν -LPA, respectively. It is also 2.4 × faster than GVE-LPA and only 1.1 × slower than ν -LPA, with minimal quality loss (below $5\%$ on average).