ToupleGDD: A Fine-Designed Solution of Influence Maximization by Deep Reinforcement Learning

Tiantian Chen, Siwen Yan, Jianxiong Guo, Weili WuIEEE Trans. Comput. Soc. Syst 2022 · DOI · OpenReview

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

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.
BibTeX
@article{chen2022touplegdd,
  author = {Tiantian Chen and Siwen Yan and Jianxiong Guo and Weili Wu},
  title = {{ToupleGDD: A Fine-Designed Solution of Influence Maximization by Deep Reinforcement Learning}},
  journal = {IEEE Trans. Comput. Soc. Syst.},
  year = {2022},
  doi = {10.1109/tcss.2023.3272331},
}
Figure