ToupleGDD: A Fine-Designed Solution of Influence Maximization by Deep Reinforcement Learning
ToupleGDD: A Fine-Designed Solution of Influence Maximization by Deep Reinforcement Learning
复制标题
DOI：
10.1109/tcss.2023.3272331
复制
发表时间：
2022-10
影响因子：
5
通讯作者：
Tiantian Chen;Siwen Yan;Jianxiong Guo;Weili Wu
中科院分区：
文献类型：
--
作者：
Tiantian Chen;Siwen Yan;Jianxiong Guo;Weili Wu
影响最大化（IM）问题是一个以选择对网络具有最大影响力的节点子集为目标的问题。由于在给定种子集的情况下，影响扩散的计算是P-困难的，因此现有的启发式算法和近似算法在理论保证、时间效率和推广性等方面都面临着很大的困难，无法适应大规模网络和更复杂的应用。另一方面，随着深度强化学习（DRL）在人工智能等领域的最新研究成果，利用DRL求解组合优化问题成为研究的热点。受此启发，我们提出了一种新的端到端DRL框架ToupleGDD，以解决本文中的IM问题，它包含三个耦合图神经网络（GNNs）用于网络嵌入和双深度$Q$ -网络（DQNs）用于参数学习。以前使用DRL解决IM问题的努力是在整个网络的子图上训练他们的模型，然后在整个图上测试它们，这使得他们的模型在不同网络之间的性能不稳定。然而，我们的模型在几个小的随机生成的小图上进行训练，并在各种大预算下在完全不同的网络上进行测试，可以在几个数据集上获得非常接近IMM的结果，并且比OPIM-C的结果更好，并且表现出很强的泛化能力。最后，在人工数据集和真实数据集上进行了大量的实验，实验结果证明了该模型的有效性和优越性。
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, are faced with great difficulties such as theoretical guarantee, time efficiency, generalization, and so on. 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 work have been focused on exploiting DRL to solve combinatorial optimization (CO) problems. Inspired by this, we propose a novel end-to-end DRL framework, ToupleGDD, to address the IM problem in this article, which incorporates three coupled graph neural networks (GNNs) for network embedding and double deep $Q$ -networks (DQNs) for parameters learning. Previous efforts to solve the IM problem with DRL trained their models on subgraphs of the whole network and then tested them 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.