TL;DR
gIM is a high-performance GPU-accelerated algorithm that speeds up state-of-the-art Influence Maximization (IM) by up to 220x. By redesigning the Reverse Influence Sampling (RIS) workflow for massive parallelism and implementing a "reservoir queue" to manage limited GPU memory, high-precision influence analysis becomes feasible for social networks with millions of nodes.
The Challenge of Influence Maximization
Influence Maximization (IM) involves finding a small set of "seed" nodes in a social network to trigger the largest possible information cascade. This task is computationally daunting because finding the optimal seed set is NP-hard, and estimating the "influence spread" is #P-hard.
Reverse Influence Sampling (RIS) is the current gold standard for IM, providing strong theoretical guarantees. However, RIS-based algorithms like IMM are notoriously slow on large-scale graphs when high accuracy is required. gIM breaks this bottleneck by leveraging the massive parallel processing power of GPUs.
Methodology and Implementation
gIM parallelizes the two main phases of the IMM algorithm: Sampling (RR Set Generation) and Seed Selection (Maximum Coverage).
Graph Representation
To handle large-scale data on the GPU, gIM uses efficient data structures like the Compressed Sparse Row (CSR) format to represent the network and its edge weights. Graph representation and CSR data structures for RIS Source, p. 6
Parallel RR Set Generation
The primary bottleneck is generating Reverse Reachable (RR) sets, which requires thousands of small Breadth-First Searches (BFS). gIM optimizes this through:
- Simultaneous BFS: Instead of speeding up a single traversal, gIM runs many traversals in parallel across different CUDA blocks.
- Intra-Block Parallelism: Within each block, threads collaboratively traverse node edges, which is highly effective for high-degree nodes.
- Warp-Level Optimization: By using 32-thread blocks (one warp), gIM utilizes implicit hardware synchronization to minimize overhead.
Reservoir Queues for Memory Management
GPU shared memory is fast but limited. gIM introduces a "reservoir queue" mechanism to prevent overflows during BFS traversals. Execution flow of gIM showing shared and reservoir queue management Source, p. 8 As illustrated in the execution flow, the algorithm uses shared memory ($Q_{shr}$) for the active frontier but offloads overflows to a "reservoir" ($Q_{res}$) in global memory. This ensures stability on dense graphs without sacrificing performance.
Key Results and Insights
The authors evaluated gIM on diverse real-world datasets from the SNAP repository, including Orkut (117M edges) and LiveJournal.
- Massive Speedups: gIM achieved speedups of 33x to 220x over the CPU-based IMM algorithm and consistently outperformed other parallel frameworks like Ripples and cuRipples.
- Density-Driven Performance: Interestingly, gIM performs better as graph density increases, as higher node degrees allow for fuller utilization of the 32 threads in a warp.
- Real-World Efficiency: On the Orkut dataset, gIM solved the IM problem in just 3.6 seconds, compared to over 13 minutes for the standard IMM.
Conclusion
By redesigning the RIS workflow for the GPU, gIM enables high-precision influence analysis on a scale previously unattainable. While currently limited by VRAM for extremely large graphs and focused on static networks, gIM represents a significant leap forward in computational social science. Future work may explore multi-GPU implementations and dynamic graph updates.
Summary updated