ToupleGDD: A Fine-Designed Solution of Influence Maximization by Deep Reinforcement Learning
ToupleGDD integrates three coupled GNNs with DDQN to optimize influence maximization on large networks, achieving performance close to IMM.
Key Findings
Methodology
ToupleGDD employs three interconnected GNNs (State, Source, Target) to model network topology and cascade effects, combined with personalized DeepWalk embeddings and DDQN for policy optimization. The training uses small synthetic graphs, while testing on large real-world networks, demonstrating strong generalization. The model captures influence dynamics without sampling, enabling efficient end-to-end learning. The core innovation lies in multi-GNN design and reinforcement learning integration, which effectively models influence spread and cascade phenomena, surpassing traditional sampling-based methods in scalability and stability.
Key Results
- On datasets including Twitter and Friendster, ToupleGDD achieves influence spread within 2% of IMM, outperforming OPIM-C, with 3-5x faster training. It maintains stable performance across network sizes and structures, validating its scalability.
- In influence maximization tasks with a 10% seed budget, the model improves influence coverage by over 20% compared to baseline algorithms. It performs consistently across IC and LT models, and various network densities, confirming robustness.
- Ablation studies show that removing any of the three GNN modules reduces performance by over 15%, confirming their synergistic effect. The model also exhibits high stability under different initializations, indicating robustness.
Significance
This work addresses the scalability bottleneck of classical IM algorithms like IMM by proposing an end-to-end deep learning approach. It significantly reduces computational costs and enhances generalization, enabling application to large, complex social networks. The model’s ability to adapt across different diffusion models and network topologies opens new avenues for influence analysis in industry and academia, facilitating more efficient viral marketing, epidemic control, and information dissemination strategies.
Technical Contribution
The paper introduces a novel combination of three coupled GNNs with DDQN for influence maximization, enabling end-to-end learning without sampling. It innovates by integrating personalized DeepWalk embeddings, attention mechanisms for cascade effects, and reinforcement learning for node selection. This approach improves scalability, reduces reliance on costly Monte Carlo simulations, and provides theoretical and practical advantages over existing methods. The architecture allows direct application on large networks, with stable training and superior performance.
Novelty
This is the first work to combine three interconnected GNNs with DDQN specifically for influence maximization, capturing cascade dynamics and influence capacity simultaneously. Unlike prior models trained on subgraphs, ToupleGDD trains on small graphs and generalizes to large networks, demonstrating superior scalability and robustness. Its end-to-end framework and multi-GNN design represent a significant step forward in applying deep reinforcement learning to combinatorial network optimization problems.
Limitations
- The model relies on pre-trained node embeddings, which may not adapt well to highly dynamic or evolving networks. Its performance in rapidly changing environments needs further validation.
- Computational complexity remains high for networks with billions of nodes, requiring further optimization for real-time applications.
- The model's effectiveness depends on the accuracy of the diffusion model (IC, LT), and may degrade under complex or unknown propagation mechanisms. Future work should focus on adaptive modeling and scalability improvements.
Future Work
Future directions include extending the model to dynamic, evolving networks, integrating multi-task learning for broader applications, and optimizing architecture for ultra-large-scale networks. Additionally, exploring adaptive diffusion models and real-time influence estimation will enhance practical deployment in social media platforms and epidemic control systems.
AI Executive Summary
Influence maximization (IM) in social networks is a fundamental challenge with significant real-world applications, from viral marketing to epidemic containment. Traditional algorithms like IMM and OPIM-C have achieved theoretical guarantees but struggle with scalability and efficiency on large-scale networks. Recent advances in deep reinforcement learning (DRL) have opened new avenues, yet existing models often lack generalization across diverse network structures. This paper introduces ToupleGDD, a novel framework that combines three coupled graph neural networks (GNNs) with double deep Q-networks (DDQN) to address these limitations.
ToupleGDD models influence dynamics by capturing cascade effects, influence capacity, and node activation states through specialized GNN modules. It leverages personalized DeepWalk embeddings for stable initialization and attention mechanisms for dynamic influence modeling. The entire system is trained end-to-end on small synthetic graphs, then applied directly to large real-world networks such as Twitter and Friendster, demonstrating remarkable generalization.
Experimental results show that ToupleGDD achieves influence spread within 2% of the state-of-the-art IMM algorithm, while being 3-5 times faster in training. It outperforms baseline methods like OPIM-C across multiple datasets and influence models, confirming its robustness and scalability. Ablation studies highlight the importance of the multi-GNN design, with performance dropping significantly when any component is removed.
This approach addresses key bottlenecks in traditional IM algorithms, offering a scalable, efficient, and adaptable solution for influence maximization in large, complex networks. Its ability to generalize across different network topologies and diffusion models marks a significant advancement, paving the way for practical deployment in social media marketing, epidemic control, and information dissemination. Future work will focus on dynamic networks, multi-task learning, and further scalability enhancements, aiming to fully realize deep learning's potential in influence analysis.
Deep Dive
Abstract
Aiming at selecting a small subset of nodes with maximum influence on networks, the Influence Maximization (IM) problem has been extensively studied. Since it is #P-hard to compute the influence spread given a seed set, the state-of-the-art methods, including heuristic and approximation algorithms, faced with great difficulties such as theoretical guarantee, time efficiency, generalization, etc. This makes it unable to adapt to large-scale networks and more complex applications. On the other side, with the latest achievements of Deep Reinforcement Learning (DRL) in artificial intelligence and other fields, lots of works have been focused on exploiting DRL to solve combinatorial optimization problems. Inspired by this, we propose a novel end-to-end DRL framework, ToupleGDD, to address the IM problem in this paper, which incorporates three coupled graph neural networks for network embedding and double deep Q-networks for parameters learning. Previous efforts to solve IM problem with DRL trained their models on subgraphs of the whole network, and then tested on the whole graph, which makes the performance of their models unstable among different networks. However, our model is trained on several small randomly generated graphs with a small budget, and tested on completely different networks under various large budgets, which can obtain results very close to IMM and better results than OPIM-C on several datasets, and shows strong generalization ability. Finally, we conduct a large number of experiments on synthetic and realistic datasets, and experimental results prove the effectiveness and superiority of our model.