mlsanityData to 7 Oct 2026

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

arXiv 2211.03074 ↗First posted 6 Nov 2022cs.SI cs.LGcited by 15

Not on the map. Why?

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.

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

Builds on

93 of 258 references.

References · 93

  1. 2017Attention Is All You Needcited by 59,932
  2. 2018BERT: Pre-training of Deep Bidirectional Transformers for Language Understandingcited by 40,204
  3. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
  4. 2017Graph Attention Networkscited by 8,854
  5. 2017Inductive Representation Learning on Large Graphscited by 6,284
  6. 2014Neural Machine Translation by Jointly Learning to Align and Translatecited by 4,530
  7. 2013Efficient Estimation of Word Representations in Vector Spacecited by 4,346
  8. 2013Distributed Representations of Words and Phrases and their Compositionalitycited by 3,462
  9. 2015Continuous control with deep reinforcement learningcited by 3,279
  10. 2014Sequence to Sequence Learning with Neural Networkscited by 2,974
  11. 2019A Comprehensive Survey on Graph Neural Networkscited by 2,906
  12. 2014Empirical Evaluation of Gated Recurrent Neural Networks on Sequence Modelingcited by 2,341
38 more
  1. 2016Convolutional Neural Networks on Graphs with Fast Localized Spectral Filteringcited by 2,085
  2. 2016node2vec: Scalable Feature Learning for Networkscited by 1,913
  3. 2015Deep Reinforcement Learning with Double Q-learningcited by 1,704
  4. 2014DeepWalk: Online Learning of Social Representationscited by 1,543
  5. 2021Decision Transformer: Reinforcement Learning via Sequence Modelingcited by 1,528
  6. 2013Spectral Networks and Locally Connected Networks on Graphscited by 1,097
  7. 2017Hindsight Experience Replaycited by 1,096
  8. 2015Pointer Networkscited by 882
  9. 2018Hierarchical Graph Representation Learning with Differentiable Poolingcited by 786
  10. 2018Attention, Learn to Solve Routing Problems!cited by 646
  11. 2018Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizoncited by 612
  12. 2016Neural Combinatorial Optimization with Reinforcement Learningcited by 600
  13. 2017Learning Combinatorial Optimization Algorithms over Graphscited by 557
  14. 2018Deep Learning on Graphs: A Surveycited by 393
  15. 2018Reinforcement Learning for Solving the Vehicle Routing Problemcited by 327
  16. 2019An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problemcited by 265
  17. 2018Visual Reinforcement Learning with Imagined Goalscited by 248
  18. 2017struc2vec: Learning Node Representations from Structural Identitycited by 214
  19. 2018Learning a SAT Solver from Single-Bit Supervisioncited by 198
  20. 2022Online Decision Transformercited by 194
  21. 2018Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Searchcited by 182
  22. 2022Multi-Agent Reinforcement Learning is a Sequence Modeling Problemcited by 153
  23. 2018Learning Scheduling Algorithms for Data Processing Clusterscited by 133
  24. 2016Discriminative Embeddings of Latent Variable Models for Structured Datacited by 130
  25. 2018DeepInf: Social Influence Prediction with Deep Learningcited by 128
  26. 2021Self-Supervised Multi-Channel Hypergraph Convolutional Network for Social Recommendationcited by 101
  27. 2020Transfer Learning of Graph Neural Networks with Ego-graph Information Maximizationcited by 93
  28. 2019Exploratory Combinatorial Optimization with Reinforcement Learningcited by 82
  29. 2019Combinatorial Optimization by Graph Pointer Networks and Hierarchical Reinforcement Learningcited by 78
  30. 2022When does return-conditioned supervised learning work for offline reinforcement learning?cited by 73
  31. 2019Deep Set Prediction Networkscited by 71
  32. 2019A Neural Influence Diffusion Model for Social Recommendationcited by 69
  33. 2020Combining Reinforcement Learning and Constraint Programming for Combinatorial Optimizationcited by 63
  34. 2018Learning to Solve NP-Complete Problems - A Graph Neural Network for Decision TSPcited by 58
  35. 2019Deep Reinforcement Learning meets Graph Neural Networks: exploring a routing optimization use casecited by 53
  36. 2016DeepCas: an End-to-end Predictor of Information Cascadescited by 48
  37. 2020DiffNet++: A Neural Influence and Interest Diffusion Network for Social Recommendationcited by 46
  38. 2019End to end learning and optimization on graphscited by 44

50 most cited of 93 All 93 (JSON)

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 1; 2024: 6; 2025: 7; 2026: 1.

15 papers.

Sort:

By area:

  1. 2024Graph Bayesian Optimization for Multiplex Influence Maximizationcited by 4
  2. 2024Influence Maximization via Graph Neural Banditscited by 4
  3. 2024DeepSN: A Sheaf Neural Framework for Influence Maximizationcited by 4
  4. 2024MIM-Reasoner: Learning with Theoretical Guarantees for Multiplex Influence Maximizationcited by 1
  5. 2024Predicting Cascading Failures with a Hyperparametric Diffusion Modelcited by 1
  6. 2025Critical Nodes Identification in Complex Networks: A Surveycited by 1
  7. 2025A Pressure-Based Diffusion Model for Influence Maximization on Social Networkscited by 1
  8. 2025DQ4FairIM: Fairness-aware Influence Maximization using Deep Reinforcement Learningcited by 1
  9. 2023Online Influence Maximization: Concept and Algorithmcited by 0
  10. 2024Non-Progressive Influence Maximization in Dynamic Social Networkscited by 0
  11. 2025Influence Strength Estimation in Hyperbolic Space for Social Influence Maximizationcited by 0
  12. 2025Influence Maximization in Temporal Social Networks with a Cold-Start Problem: A Supervised Approachcited by 0
3 more
  1. 2025Vulnerable Agent Identification in Large-Scale Multi-Agent Reinforcement Learningcited by 0
  2. 2025Bridging Computational Social Science and Deep Learning: Cultural Dissemination-Inspired Graph Neural Networkscited by 0
  3. 2026Revealing Positive and Negative Role Models to Help People Make Good Decisionscited by 0