Design of memory-efficient OpenMP-based Parallel Leiden algorithm for community detection.

Community detection in graphs identifies groups of nodes that are more densely connected within the groups than between them. While many studies focus on enhancing detection performance, managing memory becomes critical for processing large graphs on shared-memory systems. Recently, we developed efficient implementations of the Leiden, Leiden, and Label Propagation Algorithms (LPA) for community detection, though these methods incur high memory costs due to collision-free per-thread hashtables. To mitigate this, we introduce memory-efficient alternatives based on weighted Misra-Gries (MG) sketches, which replace the per-thread hashtables and significantly reduce memory usage in Leiden, Leiden, and LPA implementations. This approach achieves only a minor quality reduction (up to 1%) with moderate runtime penalties. We believe these slightly slower but memory-efficient methods are well-suited for parallel processing and could offer better performance than current memory-intensive techniques on systems with numerous threads.

Below we plot the time taken by Default Leiden, weighted Boyer-Moore (BM) based Leiden, and weighted Misra-Gries (MG) based Leiden with k=64 slots, on 13 different graphs. MG64 Leiden is, on average, 3.19x slower than Default Leiden, but requires significantly less memory (i.e., just 0.5 KB per thread).

Next, we plot the modularity of communities identified by Default Leiden, BM Leiden, and MG8 Leiden. MG8 Leiden, on average, achieves a modularity within 1% of Default Leiden - and is thus a viable memory-efficient alternative to the Default Leiden. Higher values of k can be chosen for even better modularity, if needed.

Refer to our technical report for more details:
Memory-Efficient Community Detection on Large Graphs Using Weighted Sketches.

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 is as follows:

- 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
- inc/batch.hxx: Batch update generation functions
- inc/bfs.hxx: Breadth-first search algorithms
- inc/csr.hxx: Compressed Sparse Row (CSR) data structure functions
- inc/dfs.hxx: Depth-first search algorithms
- inc/duplicate.hxx: Graph duplicating functions
- inc/Graph.hxx: Graph data structure functions
- inc/leiden.hxx: Leiden community detection algorithm functions
- inc/leidenLowmem.hxx: Memory-efficient Leiden community detection algorithm functions
- inc/main.hxx: Main header
- inc/mtx.hxx: Graph file reading functions
- inc/properties.hxx: Graph Property functions
- inc/selfLoop.hxx: Graph Self-looping functions
- inc/symmetrize.hxx: Graph Symmetrization functions
- inc/transpose.hxx: Graph transpose functions
- inc/update.hxx: Update functions
- main.cxx: Experimentation code
- process.js: Node.js script for processing output logs

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

• Fast unfolding of communities in large networks; Vincent D. Blondel et al. (2008)
• Community Detection on the GPU; Md. Naim et al. (2017)
• Scalable Static and Dynamic Community Detection Using Grappolo; Mahantesh Halappanavar et al. (2017)
• From Louvain to Leiden: guaranteeing well-connected communities; V.A. Traag et al. (2019)
• CS224W: Machine Learning with Graphs | Louvain Algorithm; Jure Leskovec (2021)
• The University of Florida Sparse Matrix Collection; Timothy A. Davis et al. (2011)