A Survey on Influence Maximization: From an ML-Based Combinatorial Optimization
arXiv:2211.03074 · doi:10.1145/3604559
Abstract
Influence Maximization (IM) is a classical combinatorial optimization problem, which can be widely used in mobile networks, social computing, and recommendation systems. It aims at selecting a small number of users such that maximizing the influence spread across the online social network. Because of its potential commercial and academic value, there are a lot of researchers focusing on studying the IM problem from different perspectives. The main challenge comes from the NP-hardness of the IM problem and \#P-hardness of estimating the influence spread, thus traditional algorithms for overcoming them can be categorized into two classes: heuristic algorithms and approximation algorithms. However, there is no theoretical guarantee for heuristic algorithms, and the theoretical design is close to the limit. Therefore, it is almost impossible to further optimize and improve their performance. With the rapid development of artificial intelligence, the technology based on Machine Learning (ML) has achieved remarkable achievements in many fields. In view of this, in recent years, a number of new methods have emerged to solve combinatorial optimization problems by using ML-based techniques. These methods have the advantages of fast solving speed and strong generalization ability to unknown graphs, which provide a brand-new direction for solving combinatorial optimization problems. Therefore, we abandon the traditional algorithms based on iterative search and review the recent development of ML-based methods, especially Deep Reinforcement Learning, to solve the IM problem and other variants in social networks. We focus on summarizing the relevant background knowledge, basic principles, common methods, and applied research. Finally, the challenges that need to be solved urgently in future IM research are pointed out.
arXiv comment45 pages
References in corpus (34)
- Distributed Representations of Words and Phrases and their Compositionality
- Sequence to Sequence Learning with Neural Networks
- A Comprehensive Survey on Graph Neural Networks
- DeepWalk: Online Learning of Social Representations
- Inductive Representation Learning on Large Graphs
- Learning Combinatorial Optimization Algorithms over Graphs
- struc2vec: Learning Node Representations from Structural Identity
- Hierarchical Graph Representation Learning with Differentiable Pooling
- DeepInf: Social Influence Prediction with Deep Learning
- Decision Transformer: Reinforcement Learning via Sequence Modeling
- Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search
- Visual Reinforcement Learning with Imagined Goals
- Deep Reinforcement Learning meets Graph Neural Networks: exploring a routing optimization use case
- Sketch-based Influence Maximization and Computation: Scaling up with Guarantees
- Adaptive Influence Maximization in Dynamic Social Networks
- Reinforcement Learning for Solving the Vehicle Routing Problem
- StaticGreedy: solving the scalability-accuracy dilemma in influence maximization
- Online Influence Maximization (Extended Version)
- Holistic Influence Maximization: Combining Scalability and Efficiency with Opinion-Aware Models
- ToupleGDD: A Fine-Designed Solution of Influence Maximization by Deep Reinforcement Learning
- Community Aware Random Walk for Network Embedding
- Multi-Agent Reinforcement Learning is a Sequence Modeling Problem
- End to end learning and optimization on graphs
- Deep Set Prediction Networks
- DiffNet++: A Neural Influence and Interest Diffusion Network for Social Recommendation
- Grain: Improving Data Efficiency of Graph Neural Networks via Diversified Influence Maximization
- Influence Maximization in Social Networks: A Survey of Behaviour-Aware Methods
- Adaptive Influence Maximization: If Influential Node Unwilling to Be the Seed
- Transfer Learning of Graph Neural Networks with Ego-graph Information Maximization
- GAC: A Deep Reinforcement Learning Model Toward User Incentivization in Unknown Social Networks
- Continuous Profit Maximization: A Study of Unconstrained Dr-submodular Maximization
- Graph Representation Learning for Popularity Prediction Problem: A Survey
- StratLearner: Learning a Strategy for Misinformation Prevention in Social Networks
- USCO-Solver: Solving Undetermined Stochastic Combinatorial Optimization Problems