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

arXiv:2608.08406 · cs.LG · Submitted 2026-08-09 · Read on arXiv

Yiqiao Liao, Parinaz Naghizadeh

cs.LG

Submitted: 2026-08-09

Updated: 2026-08-11

Code: https://github.com/yl489/rethink-IM

License: http://creativecommons.org/licenses/by-nc-sa/4.0/

The gist: Existing learning-based influence maximization frameworks rely heavily on complex neural architectures and continuous optimization over seed representations.

Terminology

Abstract

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.

Sources

Related papers