Memory Efficient GPU-based Label Propagation Algorithm (LPA) for Community Detection on Large Graphs
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929608961556480 |
|---|---|
| author | Sahu, Subhajit |
| author_facet | Sahu, Subhajit |
| contents | 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 ($ν$-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, $ν$MG8-LPA, using an 8-slot MG sketch, reduces memory usage by 98x and 44x compared to GVE-LPA and $ν$-LPA, respectively. It is also 2.4x faster than GVE-LPA and only 1.1x slower than $ν$-LPA, with minimal quality loss (4.7%/2.9% drop compared to GVE-LPA/$ν$-LPA). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_19901 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Memory Efficient GPU-based Label Propagation Algorithm (LPA) for Community Detection on Large Graphs Sahu, Subhajit Distributed, Parallel, and Cluster Computing Social and Information Networks G.2.2; I.5.3 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 ($ν$-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, $ν$MG8-LPA, using an 8-slot MG sketch, reduces memory usage by 98x and 44x compared to GVE-LPA and $ν$-LPA, respectively. It is also 2.4x faster than GVE-LPA and only 1.1x slower than $ν$-LPA, with minimal quality loss (4.7%/2.9% drop compared to GVE-LPA/$ν$-LPA). |
| title | Memory Efficient GPU-based Label Propagation Algorithm (LPA) for Community Detection on Large Graphs |
| topic | Distributed, Parallel, and Cluster Computing Social and Information Networks G.2.2; I.5.3 |
| url | https://arxiv.org/abs/2411.19901 |