Sequential decision based learning method for influence maximization

Influence maximization (IM) involves choosing an initial group of users within a social network to optimize the expected spread of influence across other users. Recently, learning-based combinatorial optimization (CO) methods have been developed to learn generalized policies for specific CO problems on graphs. However, current learning-based algorithms struggle with diverse diffusion patterns, which restricts their generalization ability. In this paper, we apply reverse influence sampling to simplify the IM problem, reducing it to a stochastic maximum coverage problem using hyperedges. We then model this as a Markov decision process and propose two sequential decision-based learning methods. These methods leverage the symmetry of solutions with respect to sequence order and utilize the submodular reward function. By jointly training on multiple graphs, our approach learns a transferable seed selection policy that generalizes effectively to previously unseen test graphs. Extensive experiments demonstrate that our method outperforms recent learning-based approaches as well as traditional methods on both real and synthetic datasets for the IM problem.

Authors

• Zizhen Zhang
• Deying Li
• Yongcai Wang
• Wenping Chen
• Yuqing Zhu

Keywords

• Influence maximization
• Hypergraph
• Generative flow networks
• Submodular reinforcement learning