# Rethinking Learning-Based Influence Maximization: Simple Neural Surrogates and Native Discrete Search

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 16 of its 45 references that are in the map.
- First posted on arXiv 9 Aug 2026.

## Builds on (most cited first, 16 of 16)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [Neural Sheaf Diffusion: A Topological Perspective on Heterophily and Oversmoothing in GNNs](https://mlsanity.com/paper/2202.04579/) (2022)
- [Sheaf Neural Networks](https://mlsanity.com/paper/2012.06333/) (2020)
- [PyG 2.0: Scalable Learning on Real World Graphs](https://mlsanity.com/paper/2507.16991/) (2025)
- [Influence Maximization: Near-Optimal Time Complexity Meets Practical Efficiency](https://mlsanity.com/paper/1404.0900/) (2014)
- [Deep Graph Representation Learning and Optimization for Influence Maximization](https://mlsanity.com/paper/2305.02200/) (2023)
- [Online Influence Maximization (Extended Version)](https://mlsanity.com/paper/1506.01188/) (2015)
- [Stop-and-Stare: Optimal Sampling Algorithms for Viral Marketing in Billion-scale Networks](https://mlsanity.com/paper/1605.07990/) (2016)
- [DISCO: Influence Maximization Meets Network Embedding and Deep Learning](https://mlsanity.com/paper/1906.07378/) (2019)
- [ToupleGDD: A Fine-Designed Solution of Influence Maximization by Deep Reinforcement Learning](https://mlsanity.com/paper/2210.07500/) (2022)
- [DeepSN: A Sheaf Neural Framework for Influence Maximization](https://mlsanity.com/paper/2412.12416/) (2024)
- [Promoting Fair Vaccination Strategies Through Influence Maximization: A Case Study on COVID-19 Spread](https://mlsanity.com/paper/2403.05564/) (2024)

## Abstract (arXiv)

Existing learning-based influence maximization frameworks rely heavily on complex neural architectures and continuous optimization over seed representations. We challenge this paradigm with SIMBA, a diffusion-model-agnostic framework pairing a lightweight neural surrogate with direct discrete search. SIMBA introduces three key components: 1) uniformly anchored node embeddings that eliminate initialization noise and encourage learning driven by graph topology and diffusion pattern, 2) a shallow two-layer graph neural network surrogate predicting final infection states, and 3) batched multi-swap simulated annealing that explores combinatorial seed space without gradients or continuous relaxation. By shifting compute from complex representation learning to effective discrete search, SIMBA drastically cuts time-to-solution while achieving superior influence spread and data efficiency. Our code is available at https://github.com/yl489/rethink-IM.