IMGER: Mastering Social Influence Maximization through Graph Embeddings and Reinforcement Learning

TL;DR

Social Influence Maximization (IM) is the task of finding a small set of "seed nodes" in a network to trigger the largest possible cascade of information. While traditional algorithms struggle with the massive scale and dynamic nature of modern social media, IMGER (Influence Maximization via Graph Embedding and Reinforcement learning) solves this by training a neural agent to "play" the network. By combining Graph Attention Networks (GAT) with Deep Q-Learning, it learns to identify influential users with unprecedented precision and scalability.

Problem & Motivation: The Limits of Greedy Heuristics

The IM problem is fundamentally NP-hard. Since the landmark work of Kempe et al. (2003), the industry has relied on greedy approximation algorithms. However, these methods face three critical "walls":

1. Computational Wall: Simulating influence spread on billion-scale graphs is prohibitively slow.
2. Structural Wall: Most algorithms assume a static graph; when new users join (dynamic networks), the entire calculation must often be redone.
3. The "Probability" Gap: Traditional models usually guess influence weights between users rather than learning them from actual behavioral data.

The authors' insight was to treat seed selection as a sequential decision process. If an agent can learn the "latent value" of a node based on its structural position, it can select seeds rapidly across any network topology.

Methodology: The IMGER Architecture

The IMGER framework operates in two distinct phases: Representation Learning and Policy Learning.

1. User Representation via GAT

Instead of relying on simple metrics like degree centrality, IMGER uses a Graph Attention Network (GAT). This allows the model to assign different weights to different neighbors, capturing the nuance that "following" someone doesn't always imply "being influenced" by them.

The self-attention mechanism computes a coefficient ${\alpha }_{ij}$ which measures the importance of node $j$ to node $i$: ${\alpha }_{ij}=\frac{\exp (extLeakyReLU({\mathbf{a}}^T[{\mathbf{Wh}}_i||{\mathbf{Wh}}_j]))}{{\sum }_{l\in {\mathcal{N}}_i}\exp (extLeakyReLU({\mathbf{a}}^T[{\mathbf{Wh}}_i||{\mathbf{Wh}}_l]))}$

2. Seed Selection via Deep Q-Learning

Once nodes are vectorized, the problem becomes a Reinforcement Learning task:

• State ($s$): The set of currently selected seed nodes.
• Action ($a$): Choosing a new node $v$ to add to the seed set.
• Reward ($r$): The marginal increase in total influence spread.

The model uses Double DQN (DDQN) to minimize overestimation bias, training the agent to pick nodes that maximize the long-term expected influence.

Experiments: SOTA Performance

The authors evaluated IMGER on diverse datasets including Facebook, Twitter, and the massive Weibo dataset (1.8M nodes, 308M edges).

Influence Prediction

In predicting whether a user would be influenced, IMGER outperformed state-of-the-art models like Inf2vec and PSCN. By jointly capturing diffusion traces and user features, it attained higher AUC and F1-scores across all platforms.

Seed Selection Efficiency

The "Efficiency Ratio" (influenced nodes / seed set size) is the ultimate metric. As shown in the results, IMGER consistently finds higher-quality seed sets than the Stop-and-Stare (SSA) approximation algorithm and the SVDN learning-based baseline.

One of the most impressive findings is generalization: an IMGER model trained on a small-scale graph (e.g., a few thousand nodes) can be directly applied to a massive network (e.g., Flickr or Weibo) and still outperform traditional heuristics.

Critical Analysis & Conclusion

Takeaway

IMGER represents a significant shift from "algorithm design" to "model learning." It solves the cold-start problem for new users in dynamic networks by focusing on learned embeddings rather than fixed adjacency matrices.

Limitations & Future Work

While IMGER is highly effective, the Paper notes that the training phase for RL can be time-consuming. However, once trained, the inference (seed selection) is near-instantaneous. Future research could explore Multi-Agent RL where multiple competing brands try to maximize their influence simultaneously on the same network.

In conclusion, by marrying the structural awareness of GNNs with the strategic decision-making of RL, IMGER provides a robust, scalable, and highly accurate solution for the next generation of viral marketing and social network analysis.