Resource-Efficient FirmCore Decomposition on Billion-Scale Multilayer Graphs
TL;DR
This work introduces serial and parallel algorithms for multi-core CPUs, as well as the first GPU-based algorithm for multi-core CPUs, and introduces a grid structure the authors call FC-Grid, which is exploited to distribute work among threads.
Abstract
Multilayer (ML) graphs offer a convenient paradigm for modeling complex node-to-node interactions, such as social or semantic connections, as layers of a graph. In such graphs, FirmCore decomposition represents an established technique to identify cohesive groups of nodes with strong ties across layers. Unfortunately, the fastest FirmCore decomposition method fails to fully harness the resources, leading to underutilized and idle threads. Our main observation is that FirmCores enjoy a grid structure we call FC-Grid, which we exploit to distribute work among threads. Building on this structure, we introduce serial and parallel algorithms for multi-core CPUs, as well as the first GPU-based algorithm. Owing to this new design, our solutions show greatly improved performance and resource utilization. Our experiments on 12 datasets show 9× speedup on average for our serial version FC-Grid compared to existing serial methods. Furthermore, our parallel algorithm achieves an average 100.3× speedup over the state-of-the-art parallel algorithm. For the challenging NP-hard densest subgraph mining problem in ML graphs, our algorithms achieve 15× speedup on average.