STORM: Mastering Competitive Social Influence through Meta-RL and Game Theory

TL;DR

STORM is a learning-based framework that treats Influence Maximization (IM) as a strategic game. Unlike traditional greedy algorithms that pick seeds once, STORM uses Reinforcement Learning (RL) to pick the best strategy (like "Degree" or "Blocking") for each round of a multi-round competition. By training against simulated opponents, it learns to maximize long-term market share in social networks, even when the opponent's tactics are unknown.

The Shift from Static to Strategic Influence

Influence Maximization has long been viewed as a discrete stochastic optimization problem. However, the real world isn't a vacuum. Companies compete. If Party A picks a high-degree node, Party B might pick its neighbor to "block" the spread.

The authors identify four critical gaps in existing research:

1. Lack of Competition: Most models assume you are the only player.
2. Myopic Decisions: Most models assume seed selection happens in a single round.
3. Rigid Strategies: Heuristics like "Highest Degree" work on P2P networks but fail on Facebook; there is no "one-size-fits-all" algorithm.
4. Data Scarcity: Real-world propagation data is rare and expensive to label.

Methodology: The STORM Framework

STORM (STrategy-Oriented Reinforcement-Learning based influence Maximization) conceptualizes the social network as an environment and the influence propagation as the state transition.

1. Strategy-Oriented Actions (Meta-Learning)

Instead of picking individual nodes (which creates a massive, unlearnable action space), STORM's actions are Candidate Strategies. In each round, the agent chooses which meta-strategy to deploy:

• Degree: Target high-connectivity nodes.
• Weight: Target nodes with high-weight outgoing edges.
• Blocking: Specifically target nodes that neutralize the opponent's reach.
• SubGreedy: A high-performance heuristic targeting nodes with the best 2-step lookahead.

2. Handling the Unknown: Three Scenarios

STORM is designed for three levels of uncertainty:

• STORM-Q: For known/predictable opponents.
• STORM-QQ: Two agents train against each other simultaneously to find stable pure-strategy responses.
• STORM-MM (MinMax): Uses game theory to solve for Nash Equilibrium using mixed strategies, preparing for the most rational and "smart" opponents.

Figure: The Multi-round multi-party system model showing the iterative seed selection and propagation process.

Experiments and Results

The researchers tested STORM on various topologies, from Facebook social circles to P2P-Gnutella networks.

Adaptability Across Networks

The results proved that no single heuristic is dominant. While "Degree" excelled in P2P networks, "SubGreedy" was required for Facebook. STORM successfully learned to switch between these strategies based on the network features (e.g., sum of free degrees, max out-edge weight).

Beating the Strongest Heuristics

In the most challenging test—competing against an unknown opponent—STORM-MM (the MinMax version) consistently outperformed all fixed strategies and even a "Voting" meta-strategy.

Figure: Scores of STORM-Q showing significant improvement after training against different unknown strategies.

Critical Insight & Conclusion

The genius of STORM lies in its Data-Driven but Simulation-Based approach. It solves the "data scarcity" problem by generating its own experience through simulation. By training an agent to play its own "Influence Game," we can derive policies that are far more robust than any human-designed heuristic.

Takeaway: In competitive environments, the best strategy isn't a single algorithm—it's the ability to choose the right algorithm at the right time. STORM provides the mathematical and RL framework to make that choice optimally.