HyDetect: A Hybrid CPU-GPU Algorithm for Community Detection; Bhowmick and Vadhiyar (2019) : NOTES

notes-hydetect-a-hybrid-cpu-gpu-algorithm-for-community-detection.md

HyDetect: A Hybrid CPU-GPU Algorithm for Community Detection; Bhowmick and Vadhiyar (2019)

1. Graph is parititoned for CPU and GPU.
2. Louvain is independently performed to get psuedo-communities.
3. Determine doubtful vertices which do not belong to communities formed on a device.
4. Doubtful vertices are exchanged between the devices.
5. Executes Louvain algorithm again from subgraph on devices, which includes communities formed earlier and doubtful vertices.
6. This results in new communities and a new set of doubtful vertices.
7. Doubtful vertices are exchanged again.
8. Graph is coarsened to form a reduced graph of new vertices.
9. Continues until number of communities is small to accomodate on a single device.
10. Once accomodated, run it on a single device.

Partitioning is done using METIS.

Discussion

• Hybrid algorithm gives ~2x speedup over CPU-only, with less than 1% change in modularity.
• At least 42 - 73% lower runtime than state-of-the-art multicore algorithm (Grappolo).
• Are doubtful vertices overlapping? Most likely no. In any case, migration time is quite low. The time taken for identifying doubtful vertices is 5 - 25%.
• Partitioning is based on proportional performance of the two devices, using ratio-based METIS (using induced subgraphs). The partitioning time is around 10 to 50%.
• On CPU, Lu et al.'s algorithm is used (Grappolo), and on the GPU, Naim et al.'s algorithm is used. CPU used std::map and GPU used thrust, but details of hashtables are not provided (likely same as in the original paper by Naim et al.)
• The size of graphs used (max) is 2.27B edges.

notes-hydetect-a-hybrid-cpu-gpu-algorithm-for-community-detection.pdf