rak-lowmem-communities-cuda

Design of memory-efficient CUDA-based Parallel Label Propagation Algorithm (LPA), aka RAK, for community detection.

https://github.com/puzzlef/rak-lowmem-communities-cuda

Science Score: 67.0%

This score indicates how likely this project is to be science-related based on various indicators:

✓
CITATION.cff file
Found CITATION.cff file
✓
codemeta.json file
Found codemeta.json file
✓
.zenodo.json file
Found .zenodo.json file
✓
DOI references
Found 2 DOI reference(s) in README
✓
Academic publication links
Links to: arxiv.org
○
Committers with academic emails
○
Institutional organization owner
○
JOSS paper metadata
○
Scientific vocabulary similarity
Low similarity (6.6%) to scientific vocabulary

Last synced: 6 months ago · JSON representation ·

Repository

Design of memory-efficient CUDA-based Parallel Label Propagation Algorithm (LPA), aka RAK, for community detection.

Basic Info

Host: GitHub
Owner: puzzlef
License: mit
Language: C++
Default Branch: main
Homepage: https://arxiv.org/abs/2411.19901
Size: 82 KB

Statistics

Stars: 0
Watchers: 1
Forks: 0
Open Issues: 0
Releases: 0

Created over 1 year ago · Last pushed 11 months ago

Metadata Files

Readme License Citation

README.md

Design of memory-efficient CUDA-based Parallel Label Propagation Algorithm (LPA), aka RAK, for community detection.

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).

Below we plot the memory usage of NetworKit LPA, GVE-LPA, ν-LPA, 𝜈MG8-LPA, and 𝜈BM-LPA on 13 different graphs. 𝜈MG8-LPA and 𝜈BM-LPA achieve, on average, 2.2x, 98x, and 44x lower memory usage than NetworKit LPA, GVE-LPA, and 𝜈-LPA.

Next, we plot the time taken by NetworKit LPA, GVE-LPA, ν-LPA, 𝜈MG8-LPA, and 𝜈BM-LPA on 13 different graphs. On average, 𝜈BM-LPA is 186x, 9.0x, 3.5x, and 3.7x faster than NetworKit LPA, GVE-LPA, 𝜈-LPA, and 𝜈MG8-LPA, respectively; while 𝜈MG8-LPA is 51x and 2.4x faster than NetworKit LPA and GVE-LPA, but 1.1x and 3.7x slower than 𝜈-LPA and 𝜈BM-LPA.

Further, we plot the speedup of 𝜈MG8-LPA over NetworKit LPA, GVE-LPA, and 𝜈-LPA.

Finally, we plot the modularity of communities identified by NetworKit LPA, GVE-LPA, 𝜈-LPA, 𝜈MG8-LPA, and 𝜈BM-LPA. 𝜈BM-LPA identifies communities that are of 27%, 24%, 23%, and 20% lower quality, respectively. However, the communities identified by 𝜈MG8-LPA are only 8.4%, 4.7%, and 2.9% lower in quality than NetworKit LPA, GVE-LPA, and 𝜈-LPA, and 25% higher than 𝜈BM-LPA.

Refer to our technical report for more details: \ Memory Efficient GPU-based Label Propagation Algorithm (LPA) for Community Detection on Large Graphs.

[!NOTE] You can just copy main.sh to your system and run it. \ For the code, refer to main.cxx.

Code structure

The code structure of νMG-LPA / νBM-LPA is as follows:

```bash

Main files

main.sh: Shell script for running experiments
process.js: Node.js script for processing output logs
main.cxx: Experimentation code

Key algorithms

rakLowmemCuda.hxx: Memory-efficient GPU-based LPA, i.e., νMG-LPA, νBM-LPA
rakLowmem.hxx: Memory-efficient CPU-based LPA, i.e., MG-LPA, BM-LPA
rakCuda.hxx: GPU-based LPA, i.e., ν-LPA
rak.hxx: CPU-based LPA, i.e., GVE-LPA
sketchCuda.hxx: Misra-Gries sketch for νMG-LPA
hashtableCuda.hxx: Hashtable for ν-LPA

Common graph operations

inc/main.hxx: Main header
inc/Graph.hxx: Graph data structure functions
inc/mtx.hxx: Graph file reading functions
inc/update.hxx: Update functions
inc/csr.hxx: Compressed Sparse Row (CSR) data structure functions
inc/bfs.hxx: Breadth-first search algorithms
inc/dfs.hxx: Depth-first search algorithms
inc/duplicate.hxx: Graph duplicating functions
inc/symmetrize.hxx: Graph Symmetrization functions
inc/transpose.hxx: Graph transpose functions
inc/selfLoop.hxx: Graph Self-looping functions
inc/properties.hxx: Graph Property functions
inc/batch.hxx: Batch update generation functions

Support headers

inc/_algorithm.hxx: Algorithm utility functions
inc/_bitset.hxx: Bitset manipulation functions
inc/_cmath.hxx: Math functions
inc/_ctypes.hxx: Data type utility functions
inc/_cuda.hxx: CUDA utility functions
inc/_debug.hxx: Debugging macros (LOG, ASSERT, ...)
inc/_iostream.hxx: Input/output stream functions
inc/_iterator.hxx: Iterator utility functions
inc/_main.hxx: Main program header
inc/_mpi.hxx: MPI (Message Passing Interface) utility functions
inc/_openmp.hxx: OpenMP utility functions
inc/_queue.hxx: Queue utility functions
inc/_random.hxx: Random number generation functions
inc/_string.hxx: String utility functions
inc/_utility.hxx: Runtime measurement functions
inc/_vector.hxx: Vector utility functions ```

Note that each branch in this repository contains code for a specific experiment. The main branch contains code for the final experiment. If the intention of a branch in unclear, or if you have comments on our technical report, feel free to open an issue.

References

Owner

Name: puzzlef
Login: puzzlef
Kind: organization

Website: https://puzzlef.github.io/
Repositories: 10
Profile: https://github.com/puzzlef

A summary of experiments.

Citation (CITATION.bib)

@article{sahu2024numglpa,
  title={Memory Efficient GPU-based Label Propagation Algorithm (LPA) for Community Detection on Large Graphs},
  author={Sahu, Subhajit},
  journal={arXiv preprint arXiv:2411.19901},
  year={2024}
}

GitHub Events

Total

Issues event: 2
Push event: 29
Public event: 1

Last Year

Issues event: 2
Push event: 29
Public event: 1

Committers

Last synced: 9 months ago

All Time

Total Commits: 21
Total Committers: 1
Avg Commits per committer: 21.0
Development Distribution Score (DDS): 0.0

Past Year

Commits: 21
Committers: 1
Avg Commits per committer: 21.0
Development Distribution Score (DDS): 0.0

Top Committers

Name	Email	Commits
Subhajit Sahu	w**7@g**m	21

Issues and Pull Requests

Last synced: 9 months ago

All Time

Total issues: 2
Total pull requests: 0
Average time to close issues: 22 days
Average time to close pull requests: N/A
Total issue authors: 1
Total pull request authors: 0
Average comments per issue: 9.0
Average comments per pull request: 0
Merged pull requests: 0
Bot issues: 0
Bot pull requests: 0

Past Year

Issues: 2
Pull requests: 0
Average time to close issues: 22 days
Average time to close pull requests: N/A
Issue authors: 1
Pull request authors: 0
Average comments per issue: 9.0
Average comments per pull request: 0
Merged pull requests: 0
Bot issues: 0
Bot pull requests: 0

ecosyste.ms

Data

Tools

Indexes

Applications

Experiments

Open Source Science

rak-lowmem-communities-cuda

Science Score: 67.0%

Repository

Basic Info

Statistics

Metadata Files

README.md

Code structure

Main files

Key algorithms

Common graph operations

Support headers

References

Owner

Citation (CITATION.bib)

GitHub Events

Total

Last Year

Committers

All Time

Past Year

Top Committers

Issues and Pull Requests

All Time

Past Year

Top Authors

Issue Authors

Pull Request Authors

Top Labels

Issue Labels

Pull Request Labels