# A Survey on Influence Maximization: From an ML-Based Combinatorial Optimization

arXiv: https://arxiv.org/abs/2211.03074 · HTML: https://mlsanity.com/paper/2211.03074/

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- Builds on 93 of its 258 references that are in the map.
- First posted on arXiv 6 Nov 2022.

## Builds on (most cited first, 30 of 93)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [Neural Machine Translation by Jointly Learning to Align and Translate](https://mlsanity.com/paper/1409.0473/) (2014)
- [Efficient Estimation of Word Representations in Vector Space](https://mlsanity.com/paper/1301.3781/) (2013)
- [Distributed Representations of Words and Phrases and their Compositionality](https://mlsanity.com/paper/1310.4546/) (2013)
- [Continuous control with deep reinforcement learning](https://mlsanity.com/paper/1509.02971/) (2015)
- [Sequence to Sequence Learning with Neural Networks](https://mlsanity.com/paper/1409.3215/) (2014)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [Empirical Evaluation of Gated Recurrent Neural Networks on Sequence Modeling](https://mlsanity.com/paper/1412.3555/) (2014)
- [Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering](https://mlsanity.com/paper/1606.09375/) (2016)
- [node2vec: Scalable Feature Learning for Networks](https://mlsanity.com/paper/1607.00653/) (2016)
- [Deep Reinforcement Learning with Double Q-learning](https://mlsanity.com/paper/1509.06461/) (2015)
- [DeepWalk: Online Learning of Social Representations](https://mlsanity.com/paper/1403.6652/) (2014)
- [Decision Transformer: Reinforcement Learning via Sequence Modeling](https://mlsanity.com/paper/2106.01345/) (2021)
- [Hindsight Experience Replay](https://mlsanity.com/paper/1707.01495/) (2017)
- [Spectral Networks and Locally Connected Networks on Graphs](https://mlsanity.com/paper/1312.6203/) (2013)
- [Pointer Networks](https://mlsanity.com/paper/1506.03134/) (2015)
- [Hierarchical Graph Representation Learning with Differentiable Pooling](https://mlsanity.com/paper/1806.08804/) (2018)
- [Attention, Learn to Solve Routing Problems!](https://mlsanity.com/paper/1803.08475/) (2018)
- [Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon](https://mlsanity.com/paper/1811.06128/) (2018)
- [Neural Combinatorial Optimization with Reinforcement Learning](https://mlsanity.com/paper/1611.09940/) (2016)
- [Learning Combinatorial Optimization Algorithms over Graphs](https://mlsanity.com/paper/1704.01665/) (2017)
- [Deep Learning on Graphs: A Survey](https://mlsanity.com/paper/1812.04202/) (2018)
- [Reinforcement Learning for Solving the Vehicle Routing Problem](https://mlsanity.com/paper/1802.04240/) (2018)
- [An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problem](https://mlsanity.com/paper/1906.01227/) (2019)
- [Visual Reinforcement Learning with Imagined Goals](https://mlsanity.com/paper/1807.04742/) (2018)
- [struc2vec: Learning Node Representations from Structural Identity](https://mlsanity.com/paper/1704.03165/) (2017)

## Built on by (most cited first, 15 of 15)

- [Graph Bayesian Optimization for Multiplex Influence Maximization](https://mlsanity.com/paper/2403.18866/) (2024)
- [Influence Maximization via Graph Neural Bandits](https://mlsanity.com/paper/2406.12835/) (2024)
- [DeepSN: A Sheaf Neural Framework for Influence Maximization](https://mlsanity.com/paper/2412.12416/) (2024)
- [Critical Nodes Identification in Complex Networks: A Survey](https://mlsanity.com/paper/2507.06164/) (2025)
- [MIM-Reasoner: Learning with Theoretical Guarantees for Multiplex Influence Maximization](https://mlsanity.com/paper/2402.16898/) (2024)
- [Predicting Cascading Failures with a Hyperparametric Diffusion Model](https://mlsanity.com/paper/2406.08522/) (2024)
- [A Pressure-Based Diffusion Model for Influence Maximization on Social Networks](https://mlsanity.com/paper/2509.12822/) (2025)
- [DQ4FairIM: Fairness-aware Influence Maximization using Deep Reinforcement Learning](https://mlsanity.com/paper/2512.00545/) (2025)
- [Revealing Positive and Negative Role Models to Help People Make Good Decisions](https://mlsanity.com/paper/2603.02495/) (2026)
- [Online Influence Maximization: Concept and Algorithm](https://mlsanity.com/paper/2312.00099/) (2023)
- [Non-Progressive Influence Maximization in Dynamic Social Networks](https://mlsanity.com/paper/2412.07402/) (2024)
- [Influence Strength Estimation in Hyperbolic Space for Social Influence Maximization](https://mlsanity.com/paper/2502.13571/) (2025)
- [Influence Maximization in Temporal Social Networks with a Cold-Start Problem: A Supervised Approach](https://mlsanity.com/paper/2504.11245/) (2025)
- [Vulnerable Agent Identification in Large-Scale Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2509.15103/) (2025)
- [Bridging Computational Social Science and Deep Learning: Cultural Dissemination-Inspired Graph Neural Networks](https://mlsanity.com/paper/2509.19084/) (2025)

## Abstract (arXiv)

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.