puzzlef / louvain-communities-openmp

Design of OpenMP-based Parallel Louvain algorithm for community detection, that prevents internally disconnected communities.

Design of OpenMP-based Parallel Louvain algorithm for community detection,
that prevents internally disconnected communities.

Note

For the code of GVE-Louvain, refer to the arXiv-2312.04876 branch.

Community detection entails the identification of clusters of vertices that exhibit stronger connections within themselves compared to the wider network. The Louvain method, a commonly utilized heuristic for this task, employs a two-step process comprising a local-moving phase and an aggregation phase. This process iteratively optimizes the modularity metric, a measure of community quality. Despite its popularity, the Louvain method has been noted for producing internally fragmented and weakly connected communities. In response to these limitations, Traag et al. propose the Leiden algorithm, which incorporates a refinement phase between the local-moving and aggregation phases. This refinement step enables vertices to explore and potentially establish sub-communities within the identified communities from the local-moving phase.

However, the Leiden algorithm is not guaranteed to avoid internally disconnected communities, a flaw that has largely escaped attention. We illustrate this through both a counterexample and empirical findings. In our experimental evaluation, we note that approximately 1.3×10^−4 fraction of the communities identified using the original Leiden implementation exhibit this issue. Although this fraction is small, addressing the presence of disconnected communities is crucial for ensuring the accuracy and dependability of community detection algorithms. Several studies have addressed internally disconnected communities as a post-processing step. However, this may exacerbate the problem of poorly connected communities. Furthermore, the surge in data volume and their graph representations in recent years has been unprecedented. Nonetheless, applying the original Leiden algorithm to massive graphs has posed computational hurdles, primarily due to its inherently sequential nature, akin to the Louvain method. To tackle these challenged, we propose two new parallel algorithms: GSP-Leiden and GSP-Louvain, based on the Leiden and Louvain algorithms, respectively.

Below we plot the time taken by the original Leiden, igraph Leiden, NetworKit Leiden, GSP-Leiden, and GSP-Louvain on 13 different graphs. GSP-Leiden surpasses the original Leiden, igraph Leiden, and NetworKit Leiden by 341×, 83×, and 6.1× respectively, achieving a processing rate of 328M edges/s on a 3.8𝐵 edge graph.

Below we plot the speedup of GSP-Leiden and GSP-Louvain wrt original Leiden, igraph Leiden, and NetworKit Leiden.

Next, we compare the modularity of communities identified by the original Leiden algorithm, igraph Leiden, NetworKit Leiden, GSP-Leiden, and GSP-Leiden. On average, GSP-Louvain achieves 0.3% lower modularity than the original Leiden and igraph Leiden, respectively, and 25% higher modularity than NetworKit Leiden, particularly evident on road networks and protein k-mer graphs.

Finally, we plot the fraction of disconnected communities identified by each implementation. Absence of bars indicates the absence of disconnected communities. As anticipated, both GSP-Leiden and GSP-Louvain detect no disconnected communities. However, on average, the original Leiden, igraph Leiden, and NetworKit Leiden exhibit fractions of disconnected communities amounting to 1.3×10^−4, 7.9×10^−5, and 1.5×10^−2, respectively, particularly on web graphs (and especially on social networks with NetworKit Leiden).

Refer to our technical reports for more details:
GVE-Louvain: Fast Louvain Algorithm for Community Detection in Shared Memory Setting.
Addressing Internally-Disconnected Communities in Leiden and Louvain Community Detection Algorithms.

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 GVE-Leiden 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/louvian.hxx: Louvian algorithm functions
- inc/louvainSplit.hxx: Louvain with no disconnected communities
- 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/symmetricize.hxx: Graph Symmetricization 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)
• Fetch-and-add using OpenMP atomic operations

louvain-communities-openmp's Issues

How does Ghosh et al.'s multi-CPU Louvain work?

In the paper Scalable multi-node multi-GPU Louvain community detection algorithm for heterogeneous architectures by Bhowmick et al. (Section 6.4.1 Comparison with the work by Ghosh et al.):

The work by Ghosh et al. uses only the CPUs. In this work, the graph is partitioned randomly.

How does NetworKit Louvain (PLM) work?

In file include\networkit\community\PLM.hpp:

How does Bhowmick et al.'s multi-node multi-device (HyDetect) work?

I am not able to find details of how they implement Louvain algorithm. The source code isnt linked in the paper. Perhaps I should look at their HyDetect code. Another thing to focus is on parameter optimization.

Below is overview of thier algorithm.

How does Cheong et al.'s multi-GPU Louvain work?

The source code of their implementation is not available online. Lets see what I can find from their paper. They present some interesting profiling results - indicating most of the runtime is spent in the local-moving phase (when unoptimized).

At the highest level, the original network is partitioned into a number of subnetworks and a set of removed links which consists of the links that join nodes residing in different sub-networks. The Louvain method can then be applied to solve the community detection problem in each of the sub-networks in parallel.

After this, the resulting networks are combined into a single network using the removed links, and then the Louvain method is applied once more on this combined network to obtain the final community results.

The second level of parallelism involves visiting nodes in parallel during each iteration of the modularity optimization phase.

The third and lowest level of parallelism involves computing the gain in modularity of inserting a node into each of its neighboring communities in parallel. This level of parallelism is intuitive and would be effective when a node has a large number of neighboring communities.

GPU kernel 1 performs two functions. Based on the current community status of the network, the assigned GPU thread converts each neighboring node ID in the data structure to its corresponding community ID. The thread also prepares the key for the GPU radix sort in the next step.

The GPU radix sort arranges the entire array first in order of increasing node ID and then in order of increasing neighboring community ID for array elements with the same node ID. The radix sort in the Thrust library is used in this paper.

With the sorted array, each node is being assigned a GPU thread in GPU kernel 2. The thread goes down the array elements belonging to the node and sums up the weights for adjacent elements with the same neighboring community ID to give the final output of FNC.

It appears Cheong et al. do not perform aggregation phase on the GPU.

In the paper Scalable multi-node multi-GPU Louvain community detection algorithm for heterogeneous architectures by Bhowmick et al. (Section 6.4.2 Comparison with the work by Cheong et al.):

The GPU is used only to find neighbor communities and best neighbor community, while the other steps of the Louvain algorithm use multi-core CPU.

How does Nido (Chou and Ghosh) multi-GPU Louvain work?

In Nido, each thread manages one or more GPUs.

They appear to use full graph modularity computation, and backing off if the change in modularity is not positive. This is not efficient. It is easier to track delta-modularity instead.

They appear to be using unordered_maps during the aggregation phase. Exploring their program will take much longer than anticipated. Maybe some other day ...