TL;DR
This paper introduces ToupleGDD, a novel end-to-end deep reinforcement learning (DRL) framework for the Influence Maximization (IM) problem. By combining graph neural networks (GNNs) for network representation and Double Deep Q-Networks (DDQN) for learning, ToupleGDD achieves strong generalization across different networks and budgets, outperforming existing DRL methods and showing competitive results with state-of-the-art approximation algorithms.
What Problem Does This Paper Address?
The Influence Maximization (IM) problem aims to identify a small set of influential nodes in a network (like a social media platform) to maximize the spread of information or products. This problem is computationally hard (#P-hard), making exact solutions infeasible for large networks. Existing approximation algorithms, while effective, can struggle with scalability and adapting to diverse network structures. While Deep Reinforcement Learning (DRL) has shown promise for combinatorial optimization problems, prior DRL approaches for IM often trained on subgraphs and tested on the whole graph, leading to unstable performance across different network types. This paper addresses the need for a DRL solution that is efficient, scalable, and generalizes well to various network topologies and influence budgets.
Methods
ToupleGDD is an end-to-end DRL framework that tackles IM by modeling it as a reinforcement learning problem. The core components are:
- Personalized DeepWalk (PDW): This method is used to learn initial node embeddings, capturing both local and global network contexts. It's a departure from random initialization, aiming for more stable DRL training.
- Three Coupled Graph Neural Networks (ToupleGNN): These GNNs are designed to capture the intricate cascading effects of information diffusion and network topology. They learn node embeddings by iteratively aggregating information from neighbors, considering three aspects: node activation states, influence capacity, and tendency to be influenced.
- Double Deep Q-Networks (DDQN): Instead of standard Deep Q-Networks (DQN), ToupleGDD uses DDQN for parameter learning. DDQN is known to mitigate over-optimism issues present in DQN, leading to more stable and better performance. The DDQN learns a Q-function that approximates the marginal gain of adding a node to the seed set.
- Epsilon-Greedy Policy: This standard RL exploration strategy is used to select the next seed node.
- N-step Q-learning and Experience Replay: These techniques are employed for more accurate reward estimation and efficient learning.
Datasets
The paper uses a combination of synthetic and real-world datasets for evaluation:
- Synthetic Datasets: 20 random Erdős-Renyi (ER) graphs with node sizes ranging from 15 to 50 were generated for training and validation.
- Real-World Datasets: Seven datasets were used: soc-dolphins, Twitter, Wiki-1, caGr, Wiki-2, Epinions, and Youtube.
Key Insights and Ideas
- Generalization is Key: A major contribution is ToupleGDD's ability to train on small, randomly generated graphs and generalize effectively to completely different, larger networks and varying influence budgets. This addresses a significant limitation of previous DRL approaches.
- The Power of Coupled GNNs: The three coupled GNNs are crucial for capturing the complex dynamics of influence spread, moving beyond simpler node embedding methods. They explicitly model different facets of influence (state, source capacity, target tendency).
- DDQN for Stability: The choice of DDQN over standard DQN is shown to be important for stable learning and better performance in the IM context, especially when dealing with the inherent complexities of influence dynamics.
- Initial Embedding Matters: Using a learned initial embedding (PDW) rather than random initialization significantly improves model performance and stability, highlighting the importance of good starting representations.
- One-Time vs. Iterative Selection: The study suggests that a "one-time" seed selection (embedding once, then selecting top-b nodes) can achieve comparable results to iterative selection with significant time savings, making it more practical for large-scale applications.
Key Results
- Competitive Performance: ToupleGDD achieves influence spread results very close to the state-of-the-art approximation algorithm IMM and outperforms OPIM-C on several datasets.
- Superior DRL Performance: ToupleGDD consistently outperforms other DRL-based methods like S2V-DQN and PIANO across various datasets and settings, demonstrating its robustness and generalization.
- Generalization Demonstrated: The model shows strong generalization ability, performing well even when trained under one edge weight setting (in-degree) and tested on others (0.1-setting, 0.5-setting). It achieved at least 33% gain over S2V-DQN and 20% over PIANO in specific generalization tests.
- Efficiency: While not the absolute fastest, ToupleGDD's running time is competitive and acceptable, especially considering its DRL approach. The one-time selection strategy further enhances efficiency.
Limitations and Future Work
- Scalability of GNNs: While ToupleGDD is designed for large networks, the computational complexity of GNNs can still be a factor. The paper mentions that the time complexity of ToupleGNN is O(K(|V| + |E|)), where K is the number of iterations.
- Hyperparameter Tuning: The performance of DRL models is often sensitive to hyperparameter choices. The paper doesn't delve deeply into extensive hyperparameter optimization strategies.
- Future Work: The authors suggest that their model can be adapted to different diffusion models by revising the reward function. Further exploration of more advanced DRL techniques and their application to other combinatorial optimization problems is also a natural extension. The paper also hints at the potential for further optimization of the GNN architecture and DDQN implementation.
Summary updated