Stop-and-Stare: Slashing Influence Maximization Latency from Days to Seconds

TL;DR

Influence Maximization (IM)—the task of finding $k$ seed users to maximize a product's viral spread—has long been a computational nightmare for "billion-scale" networks. This paper introduces SSA and D-SSA, two algorithms that use a "Stop-and-Stare" sampling engine. They provide the gold-standard $(1-1/e-ϵ)$ guarantee but run up to 1,200x faster than the previous SOTA, finishing tasks on massive graphs (like Friendster) in under 4 seconds.

Background: The Sampling Bottleneck

To find influential nodes, you need to estimate how much "influence" a candidate set has. Traditional methods used Monte Carlo simulations, which are glacially slow. A breakthrough called Reverse Influence Sampling (RIS) changed the game by looking at "Reverse Reachable" (RR) sets. However, even SOTA RIS methods (like IMM) struggled because they spent too much time calculating how many samples they needed, often overshooting the requirement significantly.

The Insight: Don't Predict, Just Stare

The authors' core observation is that we don't need to know the optimal number of samples ($N$) in advance. Instead of calculating a rigid, often loose theoretical threshold, the authors propose a dynamic strategy:

1. Stop: Generate samples in exponential batches (doubling each time).
2. Stare: Check if there is enough statistical evidence (the "stare") to verify that the current solution is within the $ϵ$-error margin.

Methodology: SSA vs. D-SSA

• SSA (Stop-and-Stare Algorithm): Uses fixed precision parameters. It verifies the solution quality by comparing the biased influence estimate from the main pool with an unbiased estimate from a smaller "check" pool.
• D-SSA (Dynamic SSA): The "gold standard." It dynamically adjusts the error parameters (${ϵ}_1,{ϵ}_2,{ϵ}_3$) at each checkpoint. This allows it to meet the Type-2 Minimum Threshold—the absolute minimum number of samples required mathematically to guarantee the solution quality.

Figure 1: The general framework of optimization over samples where the Stop-and-Stare strategy is applied.

Scalability at the Billion-Scale

The impact of this approach is most evident when looking at memory and time. Because D-SSA uses the minimum possible sample count, its memory footprint is significantly lighter.

Figure 2: Running time comparison under the Linear Threshold (LT) model. Note the log scale; the performance gap between D-SSA and IMM/TIM+ is massive.

In the Friendster dataset (65M nodes, 1.8B edges), D-SSA takes 3.5 seconds, while the previous best (IMM) takes over an hour. If you were to use the classic greedy approach (CELF++), you'd be waiting for years.

Beyond General Influence: Targeted Marketing

One of the coolest applications discussed is Targeted Viral Marketing (TVM). Instead of influencing everyone, you target users interested in specific topics (e.g., "Politics" or "Tech"). By modifying the sample generator to weight nodes based on interest, SSA and D-SSA outperformed existing TVM-specific algorithms (KB-TIM) by 500x.

Critical Insight & Future Work

The "Stop-and-Stare" philosophy is essentially an Anytime Algorithm approach to statistical sampling. It treats the theoretical threshold as a moving target that becomes clearer as you collect more data.

Limitations: While the algorithm is theoretically optimal for RIS, it still assumes a static graph. Real-world social networks are dynamic. The next frontier for "Stop-and-Stare" will likely be adapting these exponential checkpoints to streaming graphs where edges appear and disappear in real-time.

Conclusion

SSA and D-SSA represent the theoretical and practical limit of RIS-based Influence Maximization. By replacing pessimistic upper-bound calculations with active statistical verification, the authors have turned a "days-long" batch job into a "seconds-long" interactive task.