gIM: GPU Accelerated RIS-Based Influence Maximization Algorithm

Soheil Shahrouz, Saber Salehkaleybar, Matin Hashemi

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

Graph representation and CSR data structures for RIS

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.

Execution flow of gIM showing shared and reservoir queue management

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

Abstract

Given a social network modeled as a weighted graph $G$, the influence maximization problem seeks $k$ vertices to become initially influenced, to maximize the expected number of influenced nodes under a particular diffusion model. The influence maximization problem has been proven to be NP-hard, and most proposed solutions to the problem are approximate greedy algorithms, which can guarantee a tunable approximation ratio for their results with respect to the optimal solution. The state-of-the-art algorithms are based on Reverse Influence Sampling (RIS) technique, which can offer both computational efficiency and non-trivial $(1-\frac{1}{e}-ε)$-approximation ratio guarantee for any $ε>0$. RIS-based algorithms, despite their lower computational cost compared to other methods, still require long running times to solve the problem in large-scale graphs with low values of $ε$. In this paper, we present a novel and efficient parallel implementation of a RIS-based algorithm, namely IMM, on GPU. The proposed GPU-accelerated influence maximization algorithm, named gIM, can significantly reduce the running time on large-scale graphs with low values of $ε$. Furthermore, we show that gIM algorithm can solve other variations of the IM problem, only by applying minor modifications. Experimental results show that the proposed solution reduces the runtime by a factor up to $220 \times$. The source code of gIM is publicly available online.
BibTeX
@article{shahrouz2021gim,
  author = {Soheil Shahrouz and Saber Salehkaleybar and Matin Hashemi},
  title = {{gIM: GPU Accelerated RIS-Based Influence Maximization Algorithm}},
  journal = {IEEE Trans. Parallel Distributed Syst.},
  year = {2021},
  url = {https://openreview.net/forum?id=N8bSslutf2},
}
Figure