IMGPU: Breaking the Scalability Barrier in Social Influence Maximization

TL;DR

Researchers have developed IMGPU, a framework that shifts Influence Maximization (IM) from a slow sequential process to a massively parallel GPU-accelerated one. By utilizing a "Bottom-Up Traversal" logic and hardware-specific optimizations, IMGPU handles networks with 11 million nodes and achieves a 60x speedup over prior SOTA, finally making high-accuracy viral marketing analysis feasible for massive datasets.

The Scalability Crisis in Viral Marketing

The goal of Influence Maximization is simple: find the $K$ most influential people to kickstart a "word-of-mouth" campaign. However, the math is a nightmare. Proven to be NP-hard, the standard solution (Greedy + Monte Carlo simulation) is agonizingly slow. While heuristics like PMIA exist, they often "guess" influence and lose accuracy.

The irregular nature of social networks—where one "influencer" might have millions of followers (high degree) while others have ten (low degree)—makes traditional GPU porting inefficient due to thread divergence. When a GPU tries to process these users in parallel, the threads waiting on the "influencer" stay idle, wasting the hardware's potential.

Methodology: The IMGPU Logic

The authors' core insight is that influence computation has a natural flow that can be captured in a Directed Acyclic Graph (DAG).

1. Bottom-Up Traversal Algorithm (BUTA)

Instead of running thousands of separate simulations, BUTA collapses Strongly Connected Components (SCCs) and traverses the resulting DAG from the "leaves" upward. Because a node's influence only depends on its children, all nodes at the same "level" can be calculated simultaneously.

Figure 1: By traversing from bottom to top, nodes at the same level (a, b, c, d) are computed in parallel.

2. Hardware-Aware Optimizations

To prevent the GPU from "stalling" on irregular data, the framework introduces three tactical moves:

• Data Reorganization: Pre-sorting nodes by level and degree so that GPU thread warps handle similar workloads, slashing divergence.
• K-Level Combination: If a level has too few nodes, the algorithm logically merges it with adjacent levels to keep all GPU cores busy.
• Memory Coalescence: Unrolling loops to ensure that data fetched from memory is stored in consecutive chunks, maximizing bandwidth.

Performance: 60x Speedup

The results are striking when compared to MixGreedy (the sequential baseline) and ESMCE.

Efficiency vs. Scalability

On the Amazon dataset, IMGPU reached a speedup of 60.14x. More importantly, on the Twitter dataset (11.3M nodes), where MixGreedy usually times out or crashes, IMGPU finished selection with significantly higher accuracy than rapid heuristics.

Figure 2: Execution time across different datasets. Note the logarithmic scale showing the massive orders of magnitude improvement.

Accuracy (Influence Spread)

Unlike heuristics that sacrifice precision, IMGPU's influence spread remains consistently high, virtually matching the "gold standard" greedy results while being exponentially faster.

Critical Insight: Why This Matters

The real contribution of IMGPU isn't just the 60x number; it's the demonstration of hardware-algorithm alignment. By recognizing that the "level" of a node in a DAG is the natural grain of parallelism for a GPU, the authors bridged the gap between theoretical NP-hard problems and practical, large-scale deployment.

Limitations: The framework requires a preprocessing step (DAG conversion and sorting), which, while minimal (3.7% of total time), reflects a trade-off. Future work might involve dynamic graph updates where the network topology changes in real-time.

Conclusion

IMGPU proves that we don't have to choose between speed and accuracy. By rethinking the traversal logic of influence diffusion and optimizing for the SIMT (Single Instruction, Multiple Threads) architecture of modern GPUs, we can now analyze global-scale social networks in a fraction of the time.