Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper introduces pLouvain and pLeiden, two GPU-accelerated parallel algorithms for community detection that enhance the performance of the traditional Louvain and Leiden methods. By employing a novel spanning-tree-based refinement and a lightweight symmetry-breaking technique, pLouvain and pLeiden achieve significant speedups of 3.1x and 8.8x, respectively, while maintaining the quality guarantees of the sequential Leiden algorithm. Notably, pLouvain consistently produces higher modularity scores across a diverse set of 57 graphs, showcasing its effectiveness in large-scale graph clustering tasks.
Achieving up to 8.8x speedup in community detection while preserving quality guarantees could redefine the efficiency of graph clustering in large datasets.
The sequential Louvain and Leiden algorithms are widely used techniques for modularity-optimizing clustering (or community detection) in large graphs. We present pLouvain and pLeiden, two new GPU parallelizations. pLouvain is based on the Louvain+ extension. pLeiden is the first parallel implementation to provably preserve all quality guarantees of sequential Leiden. We achieve this through a novel spanning-tree-based refinement approach. Both pLouvain and pLeiden use a lightweight symmetry-breaking technique that emulates an ordered traversal of vertices. For pLouvain, we develop an alternative iteration strategy to rectify the weak internal cluster connectivity observed in Louvain/Louvain+. Further, both pLouvain and pLeiden optimize the LambdaCC objective function, a generalization of modularity and the related Constant Potts model. On a collection of 57 graphs from 10 families, our results show that pLouvain and pLeiden achieve geometric mean speedups of 3.1x and 8.8x, respectively, over the current fastest open-source parallelizations of Louvain and Leiden. For the clusterings generated, pLouvain yields the highest modularity scores on nearly all tested graphs. The subroutines within these two multilevel approaches could aid in the parallelization of other Louvain-based techniques.