acceptodds
Under review as a conference paper at ICLR 2027

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

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 consists of three key components: 1) uniformly anchored node embeddings that eliminate initialization noise and encourage learning driven by graph topology and diffusion patterns, 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.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Influence Maximization, Graph Neural Networks

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_WZFPOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
3
Soundness
2
Read review
Paper summary

The paper introduces SIMBA, an influence-maximization framework combining a two-layer GraphSAGE surrogate with seed-set search. The surrogate learns from the graph and pairs of initial seed sets and final diffusion outcomes. Seed sets are subsequently optimized through batched multi-swap simulated annealing. The authors report the highest influence spread in 62 of 72 settings. They also report lower combined training and search time than DeepIM and DeepSN, while maintaining comparable performance with fewer training observations.

Critical strengths

The reported results are strong against the main-table baselines.

The simple architecture provides useful empirical evidence that greater model complexity is not always necessary.

The paper includes ablations on the node anchoring strategy and extra experiments which are informative.

Critical weaknesses

The method is not tested on large scale data (such as Orkut, FB, YT or Weibo), which is the main test for influence maximiation methods.

The paper provides no theoretical findings, which is vital for this literature and for the level of ICLR.

The code is not provided for validation.

The novelty is not substantial, as similar methods based on learning node embeddings and optimizing the search have been published in the past.

To my understanding, there is no ablation on the GraphSAGE weights initialization, which is standard for NN-based techniques.

Questions for authors

Can the authors provide results on additional large real-world networks, particularly million-edge graphs, including runtime and memory requirements?

Can they derive any theoretical evidence for the correctness of the method?

Will the authors release SIMBA’s code together with results across independent training and search runs?

Can they add ablation studies on the initialization of the GraphSAGE?

2 comments
  1. Our experiments already include Digg, a real-world million-edge network. The dataset statistics are provided in Appendix B. The training and search runtimes are reported in Section 5.2. We used the same data as all previous learning-based methods mentioned in the manuscript. This is to ensure all comparisons against the baselines are fair.
  2. Our results and findings are empirical. Theoretical results are not required by the conference. Our claims concern the demonstrated empirical performance, and we do not claim global optimality or a theoretical approximation guarantee.
  3. Our code is available at https://anonymous.4open.science/r/rethink-IM/. As we noted in our Appendix C and E.1, our results are averaged across independent training and search runs. Without cherry-picking from multiple rounds, our framework can outperform the baselines by a large margin.
  4. Our GNN layers use standard initialization. The initialization strategy introduced in our work applies to the learnable node embeddings. Our ablation therefore focuses on this component. The comparison against random initialization for learnable embeddings is included in the Experiments Section. The GNN architecture and weight initialization are kept unchanged.

We would like to clarify the contributions and novelty of our work. The proposed framework demonstrates that a lightweight surrogate combined with direct discrete search can achieve stronger influence spread in benchmark settings while substantially reducing the combined training and search cost. This establishes that the additional architectural and optimization complexity of previous frameworks is not necessary for strong performance under the evaluated conditions. Our work provides a concrete alternative design and empirical evidence about the complexity of learning-based influence maximization. We respectfully ask the reviewer to reassess their recommendation.

Reviewer_WZFPOpenReview ↗

Answer to authors

Thank you for your answer.

  1. Comparing with datasets that agree only with learning-based methods does not suffice, as IM techniques are tested in larger networks (such as the ones I mention above).
  2. Theoretical findings would substantially improve the paper, as many IM algorithms are followed with theoretical guarantees.
  3. The code was not included in the original submission.
  4. A standard initialisation of GNN layers is random, hence an ablation only on these weights is needed.

For these reasons I will retain my score.

Reviewer_wBLaOpenReview ↗
Rating
2(+1)
Confidence
4
Informativeness
2
Presentation
3
Soundness
1
Read review
Paper summary

This paper introduces SIMBA, a novel framework for influence maximization. Existing works use complex neural surrogates to predict influence estimates, then use a simple optimisation to optimise seed sets in a continuous latent space. SIMBA does the opposite by using a simple neural surrogate for influence estimation, and then performs aggressive discrete search for seed set optimisation.

Critical strengths
  1. The main argument of the paper is that influence maximisation benefits more from effective discrete search than from complex surrogate architectures and continuous optimisation. This is somewhat novel compared to existing deep learning architectures.

  2. The idea is simple and straightforward, which is good. The community would benefit from simple architectures that perform well, as it would increase their usability in real-world applications.

  3. The evaluation is broad. The provided experiments cover six graphs with different sizes, three diffusion models with diverse characteristics, and four seed budgets.

Critical weaknesses
  1. The major concerns I have are about the experiments, comparison fairness and reproducibility. First, many experimental details are missing. It's not clear how the influence estimation task is performed or how the data are split. There is no code provided for reproducibility. Seems they have used the code setup given by DeepIM/DeepSN and also used the baseline results of that papers. However, they don't mention that at all.

  2. There is no statistical significance provided for baselines. I know previous work has this limitation as well. However, the concern is sharper here. If the baseline results were imported from previous papers, the comparison may be unfair.

  3. The surrogate is trained with MSE loss, but its predictive accuracy is never reported. Therefore, I'm not really sure how well this simple surrogate performs compared with existing complex surrogates for influence esitmation task. Also, the paper claims that discrete search matters more than surrogate complexity, but it never tests that. It should run SIMBA’s search on the DeepIM and DeepSN surrogates, and the existing optimizers on SIMBA’s surrogate, so the effect of the surrogate and the effect of the search can be separated.

  4. The TTS figures count only surrogate training and search. It exclude the time to run diffusion simulations to create the seed and outcome pairs. That is the very cost the data efficiency section claims to reduce, so the speedup over DeepIM and DeepSN is overstated and not fair.

  5. The paper defines the surrogate target as a binary vector of length N showing whether each node is infected or not. However, SIS has no final absorbing state. Therefore, I'm not sure how fair is the experimental setup for this.

Questions for authors

Please refer to the weaknesses

5 comments
  1. Our code is available at https://anonymous.4open.science/r/rethink-IM/. The data pipeline, task formulation, and evaluation protocol are exactly the same as those in the official code repository of DeeIM (https://github.com/triplej0079/DeepIM/tree/main). The same data and evaluation protocol were also used by the previous learning-based methods mentioned in the manuscript. The influence estimation task is formally defined in the Problem Formulation Section and the Method Section, with implementation details provided in the Experiments Section.
  2. All comparisons are fair given that the data and evaluation protocol are exactly the same. Previous learning-based methods reported the average final spread given the same seed set across 100 simulations, as mentioned in [1,2,3]. Reproducing all baselines for getting statistical significance is not the focus of our work. However, we made an effort to solidify the performance of our proposed framework. As we noted in our Appendix C and E.1, we conducted 5 rounds of such 100 simulations, meaning we ran our framework 5 times, with one seed set produced each time, performed 100 diffusion simulations using each seed set to get the average spread per round, and reported the average spread of the average spread. Without cherry-picking from multiple rounds, our framework can outperform the baselines by a large margin.
  3. We would like to note that whether the surrogate model can predict the correct ordering of seed quality (i.e., seed sets with higher true spread have higher predicted spread by the surrogate) is important in providing effective guidance during search. MSE loss is an insufficient indicator of performance. Therefore, our results focus on the true spread of the seed sets found by our framework. We reported in Appendices E.8 and E.9 that less expressive node embeddings (i.e., weaker surrogates) still achieve strong performance, indicating that the surrogate complexity has a limited role in high-quality seed set identification. Existing optimizers are based on continuous optimization over the seeds. Our surrogate is only trained on binary seed indicators as input. With that said, we additionally test our search on DeepIM and DeepSN surrogates in Appendix E.10 of the updated manuscript. Using the authors’ released implementations (https://github.com/triplej0079/DeepIM/tree/main and https://github.com/Aselahp/DeepSN/tree/main), we compare each model’s original inference procedure with our search while holding the trained surrogate checkpoint fixed within each paired run. The resulting seed sets are evaluated using the same diffusion protocol and seed budget. We were unable to recover the published performance using the released code in certain settings, with substantial discrepancies in some cases. We therefore interpret these additional experiments as controlled comparisons of inference procedures within the released implementations. The published baseline values remain the references for our main benchmark comparisons, and we provide both published and reproduced values in Appendix E.10 for transparency. We acknowledge that the unresolved reproduction gaps limit generalization of these additional findings. For both DeepIM and DeepSN, applying our search strategy outperforms the original inference algorithm in most cases. This shows that the benefits of our search can extend to other neural surrogates, although their magnitude depends on the surrogate.
  4. We believe that there is a misunderstanding in the definition of time-to-solution (TTS) in this context. DeepIM [1] also reports training and search as their runtime. Diffusion simulations are not part of the runtime of the learning framework. They are used for data construction and seed set evaluation, two processes that are part of all baselines mentioned in the manuscript. When comparing the TTS, the reported runtime for all methods consists only of the training and search. The speedup over the baselines is therefore not an overstatement, and the comparison is fair.
  5. The experimental setup of our framework is the same as previous works. [1,2,3] all use the same target. We acknowledge that the infection state at the specified observation horizon would be more accurate for SIS and will make adjustments accordingly. Nonetheless, our setup is fair given that we strictly follow the previous works.

We thank the reviewer for highlighting the importance of experimental clarity and reproducibility. As detailed above, we have provided our code and additional experiments. We respectfully ask the reviewer to reassess the paper in light of these clarifications and new evidence.

[1] Chen Ling, Junji Jiang, Junxiang Wang, My T Thai, Renhao Xue, James Song, Meikang Qiu, and Liang Zhao. Deep graph representation learning and optimization for influence maximization. In International conference on machine learning, pp. 21350–21361. PMLR, 2023.

[2] Asela Hevapathige, Qing Wang, and Ahad N Zehmakan. Deepsn: a sheaf neural framework for influence maximization. Proceedings of the AAAI Conference on Artificial Intelligence, 39(16): 17177–17185, 2025.

[3] Daiyunke Zhang, Ting Deng, Tianchen Zhu, Shuai Ma, Daqing Li, Mingtian Peng, and Feng Tian. Dynaflux: Implicit dynamics-preserving reinforcement learning for topology-free influence maximization. In Proceedings of the ACM Web Conference 2026, pp. 4940–4951, 2026.

I thank the authors for their response, the released code, and the additional experiments. Two of my main concerns remain.

Contribution of the search strategy. Appendix E.10 shows that replacing the original inference procedure with simulated annealing improves spread in 37 of 48 settings for DeepSN. The results for DeepIM are mixed, with 25 improvements but 21 decreases, which is significant. These results show that the benefit of the proposed search procedure cannot be clearly proven.

Surrogate quality and cascade range. The two-layer surrogate cannot capture the influence of seeds beyond two hops. Its sufficiency may therefore reflect the diffusion regimes used in the benchmarks rather than a general property of influence maximization. The settings in Appendix B use IC propagation probabilities of 1/in-degree, LT thresholds drawn from [0.3, 0.6], and SIS infection and recovery probabilities of 0.001, under which influence is likely to remain close to the seeds. Maybe an evaluation under longer cascades, for example, IC with propagation probabilities above 1/in-degree, would help to clearly see whether the surrogate quality is required or not. This would help establish when the lightweight surrogate is sufficient.

Reviewer_rfsROpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper addresses influence maximization without explicit knowledge of the underlying diffusion model and proposes SIMBA, a framework that combines a lightweight neural surrogate for influence estimation with simulated annealing for discrete seed-set search. Experiments on six networks under three diffusion models demonstrate competitive influence spread and reduced time-to-solution, including both training and search time.

Critical strengths

By combining a lightweight neural surrogate with simulated annealing, SIMBA achieves competitive solution quality across multiple networks and diffusion models while reducing the total training and search time.

Critical weaknesses
  1. The contributions of the surrogate model and the search strategy are difficult to disentangle. Compared with methods such as DeepIM and DeepSN, SIMBA changes both the surrogate model and the search strategy. However, the experiments primarily compare complete frameworks, without the key controlled comparison that combines different surrogate models with the same simulated annealing strategy. Since these methods can also estimate the influence spread of seed sets, it remains unclear whether the performance gains primarily arise from the surrogate model, simulated annealing, or their interaction.

  2. The effectiveness of surrogate guidance in simulated annealing remains unclear. The paper does not track the true influence spread of the best candidate selected by the surrogate during search. Consequently, it is unclear whether improvements in predicted influence translate into higher true influence spread and how much the search improves upon the initial solution.

Questions for authors
  1. For component attribution analysis, how would DeepIM or DeepSN perform if their influence prediction models were combined with the simulated annealing strategy used in SIMBA?
  2. Does the surrogate model provide effective guidance for simulated annealing? Can the authors show how the true influence spread of the best candidate selected by the surrogate evolves during simulated annealing search, and quantify the improvement from the initial solution to the final output?
  3. The paper provides insufficient detail on training-data construction and sampling. Since training and testing are conducted on the same social network graph, can SIMBA find a solution with higher true influence spread than the best seed set in the training data under the same seed budget? If so, by how much? Furthermore, does constructing training datasets from seed sets of different quality (i.e., different levels of true influence spread) affect the surrogate model’s predictive performance and SIMBA’s final solution quality?
2 comments
  1. We have added experiments pairing the influence prediction models of DeepIM and DeepSN with our search strategy in Appendix E.10 of the updated manuscript. Using the authors’ released implementations (https://github.com/triplej0079/DeepIM/tree/main and https://github.com/Aselahp/DeepSN/tree/main), we compare each model’s original inference procedure with our search while holding the trained surrogate checkpoint fixed within each paired run. The resulting seed sets are evaluated using the same diffusion protocol and seed budget. We were unable to recover the published performance using the released code in certain settings, with substantial discrepancies in some cases. We therefore interpret these additional experiments as controlled comparisons of inference procedures within the released implementations. The published baseline values remain the references for our main benchmark comparisons, and we provide both published and reproduced values in Appendix E.10 for transparency. We acknowledge that the unresolved reproduction gaps limit generalization of these additional findings. For both DeepIM and DeepSN, applying our search strategy outperforms the original inference algorithm in most cases. This shows that the benefits of our search can extend to other neural surrogates, although their magnitude depends on the surrogate.
  2. The surrogate’s predicted influence is the sole objective used during the seed set search. It identifies the best seed set so far. To directly assess the effectiveness of this guidance, we have added trajectories of the true influence spread of the best candidate seed set across search iterations in Appendix E.12 of the updated manuscript. The observed improvements from the initial solutions to the final outputs provide empirical evidence that surrogate-guided search improves actual influence spread.
  3. The data is taken directly from the official code repository of DeepIM (https://github.com/triplej0079/DeepIM/tree/main/data). Using the established benchmark data maintains comparability with prior learning-based influence maximization methods and allows us to evaluate our framework without introducing changes to data construction. We have reported the spread achieved by the best training seed sets in Appendix E.11 of the updated manuscript. We agree that the quality of training seed sets may affect both the surrogate’s predictive performance and the quality of the resulting solutions. However, the focus of this work is to challenge and improve upon previous learning-based influence maximization frameworks. Therefore, using the same data is paramount in showing the effectiveness of the proposed framework. We acknowledge that effective data construction and controlled investigations of data quality are highly valuable directions for future work.

We thank the reviewer for the constructive questions. We respectfully ask the reviewer to reassess their recommendation in light of this additional evidence and the clarifications above.

Thank you for the valuable additional experiments and clarifications. However, they only partially address the concerns I raised.

  1. The value of surrogate training remains unclear. Appendix E.11 shows that in several settings, including Jazz (IC), Cora-ML (SIS), and Jazz (SIS), the best seed set in the training data achieves higher true influence spread than the final seed set returned by SIMBA. These results do not demonstrate a clear benefit from surrogate training. The authors do not explain when training the surrogate is worthwhile.
  2. The role of SIMBA’s training strategy in the effectiveness of simulated annealing remains unclear. Appendix E.10 shows that, for both DeepIM and DeepSN, the proposed simulated annealing search underperforms the original gradient-based inference procedure in some settings with the trained surrogate held fixed. Within SIMBA, the same search strategy generally improves performance. The authors do not explain which aspects of SIMBA’s surrogate training strategy contribute to these gains.

Given these concerns, I choose to keep my score unchanged and it is my final assessment.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.