Pith. sign in

REVIEW 4 major objections 5 minor 14 references

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

T0 review · 4 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper claims that a lightweight two-layer graph neural network surrogate paired with batched multi-swap simulated annealing can outperform complex learning-based influence maximization frameworks that rely on continuous optimization.

desk verdict SIMBA's simple surrogate-plus-discrete-search recipe is genuinely promising and thoroughly tested, but the Digg IC comparison is internally inconsistent with IMM's approximation guarantee, so the headline empirical claim needs a controlled baseline rerun before it can be trusted. read the letter →

arxiv 2608.08406 v1 pith:PM5BAXX4 submitted 2026-08-09 cs.LG

Yiqiao Liao , Parinaz Naghizadeh This is my paper · ORCID
classification cs.LG
keywords influencemaximizationneuralsurrogatesimulatedannealinggraphnetworkdiscreteoptimizationdiffusion-model-agnosticseedselectiondataefficiency
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper argues that effective learning-based influence maximization does not require expressive neural architectures or continuous optimization over seed representations. It introduces SIMBA, which combines a two-layer graph neural network surrogate, uniformly anchored node embeddings, and batched multi-swap simulated annealing to search the discrete seed space directly. On five real-world graphs and one synthetic graph, under three diffusion models, SIMBA reports the highest influence spread in 62 of 72 settings and substantially lower time-to-solution than existing frameworks. The authors interpret this as evidence that the optimization strategy, not surrogate expressiveness, is the bottleneck, and that a small fraction of diffusion observations is enough to train the surrogate.

What carries the argument

The load-bearing object is the uniformly anchored node embedding: every node's learnable representation is initialized at the same random vector $c \in \mathbb{R}^d$, so that message passing learns purely from graph topology and diffusion outcomes, and a seed set is encoded by zeros for non-seed nodes. This trick makes unseen nodes share the anchor as a special token, and it appears to make the learned surrogate smooth over novel seed configurations. The second half of the machinery is batched multi-swap simulated annealing, which samples $r$ nodes to remove and $r$ to add per candidate, evaluates all $B$ candidates in a single batched forward pass, and accepts swaps by the standard annealing rule; this keeps every candidate a valid size-$k$ set without gradients or continuous relaxations.

What would settle it

On the largest graph's independent cascade benchmark, re-run SIMBA and the classical near-optimal baselines with identical propagation probabilities, 100 simulation steps, and the same seed budget; if the classical method's measured spread rises from the reported single digits to SIMBA's ~60% at 1% seeds, the central superiority claim would be an artifact of mismatched evaluation rather than a property of the method.

Watch

Extended reading notes

Core claim

SIMBA's central claim is that a deliberately simple pipeline can outperform sophisticated learning-based influence maximization. Every node embedding starts from the same random anchor, the seed configuration is expressed by masking non-seed embeddings to zero, and a two-layer graph neural network predicts the final infection state of every node. A batched multi-swap simulated annealer then generates candidate size-$k$ seed sets, evaluates all of them in one forward pass through the frozen surrogate, and keeps the best. The paper reports this combination reaches the highest influence spread in 86.1% of its 72 evaluation settings, and that the surrogate's predictions are smooth enough that expanding the search to nodes never seen during training improves rather than degrades results. The authors attribute this to the embedding geometry: anchored embeddings tend to form a low-dimensional manifold, which keeps surrogate-guided search away from uncalibrated local optima.

Load-bearing premise

The comparison assumes every baseline was run under exactly the same diffusion parameters, simulation lengths, and seed budgets as SIMBA on every dataset; if a classical near-optimal baseline was evaluated under a different protocol, the reported spread gaps could reflect evaluation conditions rather than method quality.

Editorial extensions

If this is right

  • If the results hold, learning-based influence maximization can drop autoencoders, latent seed vectors, and sheaf layers; a two-layer graph network plus swap-based annealing suffices.
  • Time-to-solution drops because training is quick and each search step is one batched forward pass, making the approach practical for graphs with hundreds of thousands of nodes.
  • Because the surrogate trains on a small fraction of seed-outcome pairs, diffusion-model-agnostic IM becomes usable where simulation data is scarce.
  • Expanding the search to nodes never seen during training improves spread, which means the surrogate extrapolates well beyond its training configurations.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Editorial extension: the largest reported gap (a classical baseline at single-digit spread vs SIMBA around 60% at 1% seeds) is consistent with an evaluation-protocol mismatch; a controlled replication with identical simulation length and seed budget would determine whether the advantage is real.
  • Editorial extension: if the manifold explanation is right, then regularizing embeddings to stay near a low-dimensional subspace could further stabilize surrogate-guided search, which the paper does not test.
  • Editorial extension: the same template - cheap neural evaluator plus batched multi-swap search - may transfer to other combinatorial problems with expensive-to-simulate objective functions, such as sensor placement or experimental design.
  • Editorial extension: because SIMBA is diffusion-model-agnostic, a natural stress test is time-varying or competitive diffusion, where the surrogate would have to adapt without architectural changes; the paper only tests three static models.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 5 minor

Summary. This paper challenges the assumption that learning-based influence maximization (IM) requires complex neural architectures and continuous optimization over seed representations. SIMBA combines uniformly anchored node embeddings (all node embeddings initialized from a shared vector, with seed sets encoded by masking), a two-layer GraphSAGE surrogate trained to predict final infection states, and batched multi-swap simulated annealing that searches directly in discrete seed space. The framework is evaluated on six graphs under IC, LT, and SIS models at 1%, 5%, 10%, and 20% seed budgets, with reported influence spread computed from actual diffusion simulations rather than from the surrogate. The paper claims that SIMBA achieves the highest influence spread in 62 of 72 settings, substantially reduces time-to-solution, and retains performance with as little as 1% of the training data, and it offers ablations and a geometric analysis of the learned embeddings.

Significance. If the empirical claims hold, the paper makes a useful conceptual contribution: it suggests that the main bottleneck in prior neural-surrogate IM work is the continuous optimization/search strategy rather than surrogate capacity, and it offers a lightweight, data-efficient alternative. The manuscript has clear strengths: the method is described precisely, the code is publicly linked, the headline evaluation uses actual simulations so the reported spread is not circularly defined by the surrogate, and the ablation study (initialization, embedding dimension, binary-input variant) is relatively thorough. The main caveats concern the fairness and statistical grounding of the baseline comparisons: the anomalous Digg results are difficult to reconcile with the approximation guarantees of classical near-optimal baselines, baseline error bars are absent, and a baseline included in an appendix contradicts the statement that SIMBA is consistently the strongest. These issues are load-bearing and need to be resolved before the central claims can be accepted.

major comments (4)
  1. [Section 5.1, Table 1 (Digg IC) with Appendix B and C] The reported Digg IC result at 1% seeds (SIMBA (C) 60.3% versus IMM 7.4%) is hard to reconcile with IMM's (1-1/e-epsilon) approximation guarantee under the same diffusion model. Since Appendix B states the IC setting is p_u,v = 1/d_in(v) with 100 simulation steps, and Appendix C says all methods are evaluated by the same 5x100 simulation rounds, a feasible seed set with true spread 60.3% would imply OPT >= 60.3%, so IMM should return at least roughly 38% (for small epsilon). The paper does not rule out an evaluation mismatch, for example baseline numbers being taken from prior papers run under different diffusion parameters, simulation lengths, or seed budgets. This is load-bearing for the central comparative claim, and the authors should either rerun all classical baselines under the exact evaluation protocol used for SIMBA or provide per-baseline verification that the same IC parameters, simulation length, and seed budget were used.
  2. [Section 5.1, Table 1, and Appendix E.2] Only SIMBA's standard deviations are reported; all baselines are point estimates. Many of the claimed wins are small in magnitude (e.g., Power Grid SIS at 1% seeds is 1.9 for essentially all methods, and many Synthetic SIS differences are 0.2-0.4 percentage points), and the 62/72 count treats every setting equally regardless of effect size. Without error bars or significance tests for the baselines, the claim that SIMBA 'consistently achieves the strongest performance' is statistically unsupported. The authors should report variance over repeated runs for all baselines, or at least for the near-tie settings and the settings used to support the headline count.
  3. [Section 5.1 versus Appendix E.3, Table 8] The headline claim that SIMBA achieves the highest influence spread in 62 of 72 settings counts only the baselines in Table 1. The appendix's comparison with DynaFLUX shows that DynaFLUX and DynaFLUX+ outperform SIMBA by large margins in many settings (e.g., Cora-ML IC at 1% seeds: 35.3/38.4 versus 14.2-17.2 for SIMBA; Jazz IC at 1% seeds: 26.0/26.3 versus 10.4-12.3). If DynaFLUX is a legitimate baseline, then the 'consistently strongest' claim is false as stated. If it is excluded because it requires access to the underlying diffusion model, the paper should say so explicitly and restrict the positioning to model-agnostic learning-based methods.
  4. [Section 5.3, Table 3] The claim that SIMBA's performance 'saturates rapidly' with a small fraction of training data is not clearly supported by the numbers. For example, on Jazz LT at 10% seeds, SIMBA (U) achieves 58.7% with 1% training data but only 48.0% with 100% training data, and there are other non-monotonic swings of several percentage points (e.g., Jazz SIS at 20% seeds: 28.9% with 20% data versus 30.8% with 100% data). Since no standard deviations are reported for these runs, the reader cannot distinguish signal from noise. The data-efficiency claim needs error bars or a paired analysis over repeated training-data fractions.
minor comments (5)
  1. [Algorithm 1 and Section 5 implementation details] With T0 = 1e-6 and alpha = 1, the acceptance rule never accepts a non-improving move, so the method is effectively a batched multi-swap hill-climbing search rather than simulated annealing; the authors should rename it or explicitly describe this configuration as a greedy variant.
  2. [Table 1 and other large tables] Several numeric entries are concatenated in the rendering (e.g., '41.549.9', '36.961.0', '8.526.9', and similar), making columns hard to parse; the tables should be reformatted so every number is clearly separated.
  3. [Appendix B] The statement that diffusion configurations are 'consistent with prior works' is too vague for reproduction; please provide the exact parameters used for each baseline and, where baseline numbers are taken from prior papers, cite the source table or figure for each dataset.
  4. [Section 4.4 and Section 5.2] The claim that both training and optimization 'scale linearly' is asserted informally; the search cost also depends on the number of steps I, batch size B, and swap size r, so a precise cost model would make the scalability discussion more rigorous.
  5. [Section 5.4] The geometric interpretation (e.g., 'linear scalability' and 'prevents uncalibrated local maxima') is not directly established by the embedding plots; these statements should be qualified as observations or supported by a quantitative analysis.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: SIMBA's reported influence spreads are measured by external diffusion simulations, not by the surrogate's own predictions, and no load-bearing claim reduces to its inputs by construction.

full rationale

Walked the derivation chain. The paper trains a two-layer GraphSAGE surrogate on observed (seed set, final infection state) pairs (Section 4.2), then uses batched multi-swap simulated annealing with the surrogate as the objective (Section 4.3). The final reported influence spreads are obtained by running 100 diffusion simulations per round, repeated over 5 rounds, with the produced seed sets (Appendix C), so the evaluation is against the true diffusion process, not against the surrogate's own predictions. The surrogate is not defined in terms of the evaluation target, no fitted parameter is renamed as a prediction, and the paper does not invoke a uniqueness theorem or self-citation to justify its design choice. The anchored embedding is an initialization scheme whose value is established by the independent Table 4 comparison against random initialization, and the geometric analysis in Section 5.4 is a post hoc empirical observation. The apparent IMM discrepancy on Digg IC (Section 5.1, Table 1) is a possible experimental/protocol correctness concern, not a circularity: it does not show that any claimed result is equivalent to its inputs by construction. Therefore no circular step is identified.

Assumptions & free parameters 7 free parameters · 4 assumptions · 0 invented entities

The central method depends on learned model parameters and per-dataset search hyperparameters, all fitted or chosen without a formal principle. The key unproven premise is that a shallow surrogate trained on a few seed-outcome pairs gives trustworthy evaluations for unseen seed sets; the paper provides empirical evidence but no guarantee. No new entities are introduced.

free parameters (7)
  • Search steps I = 10,000 (small graphs), 50,000 (Synthetic), 20,000 (Digg)
    Chosen per graph size; larger budgets on larger graphs. Affects solution quality and time-to-solution.
  • Batch size B = 4 (small graphs), 1 (Synthetic, Digg)
    Batched inference throughput tradeoff; different for large graphs.
  • Number of swaps r = 1 (small/Synthetic), 20 (Digg)
    Neighborhood exploration aggressiveness tuned per dataset.
  • Temperature T0 and cooling alpha = T0=1e-6, alpha=1
    Set to effectively disable random acceptance; the procedure is greedy hill-climbing, not true annealing.
  • Embedding dimension d = 8
    Model hyperparameter; d=2 also tested in Appendix E.8.
  • Hidden dimension, learning rate, weight decay, epochs = 128, 5e-4, 1e-4, 200
    Fixed across experiments.
  • Digg training samples = 80 reduced to 2
    For Digg TTS experiments, training samples reduced to 2, a per-dataset choice affecting data efficiency claims.
assumptions (4)
  • domain assumption The training data pairs (seed set, final infection states) are generated by the same diffusion process used for evaluation.
    Section 3 and Appendix B define the data generation; the method's success depends on this consistency.
  • domain assumption A two-layer GraphSAGE surrogate, trained on a small number of pairs, predicts final infection states accurately enough to guide discrete search on unseen seed sets and nodes.
    Section 4.2 and Section 5.1 (U vs C) rely on this generalization.
  • standard math Monte Carlo spread estimates from 5 rounds of 100 simulations are unbiased and sufficiently low-variance to compare methods.
    Appendix C; large error bars in Appendix E.2 partially undermine this.
  • domain assumption All baselines were run under identical diffusion settings and seed budgets across datasets.
    Implicit in Section 5; the large Digg gap over IMM suggests this may not hold.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Rethinking Learning-Based Influence Maximization: Simple Neural Surrogates and Native Discrete Search." pith.science (2026). https://pith.science/paper/PM5BAXX4

@misc{pith2026260808406,
  author       = {Pith},
  title        = {Pith review of: Rethinking Learning-Based Influence Maximization: Simple Neural Surrogates and Native Discrete Search},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/PM5BAXX4}},
  note         = {Machine review of arXiv:2608.08406}
}
read the original 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.

Figures

Figures reproduced from arXiv: 2608.08406 by the authors.

Figure 1
Figure 1. TTS across datasets. High influence quality alone is insufficient for practical deployment. Existing learning-based IM frameworks often achieve fast inference only after substantial offline computa￾tion devoted to training. Consequently, reporting inference time alone provides an incomplete picture of the overall computational cost. As DeepIM runs much faster than ear￾lier learning-based frameworks (Ling et al., 202… view at source ↗
Figure 2
Figure 2. TTS scalability of SIMBA. To improve the TTS scalability of SIMBA, we implement two strategies for experiments on Digg that target the train￾ing and inference stages, respectively. First, we reduce the number of training samples from 80 to 2. Second, we re￾duce the number of search steps from 50,000 to 20,000 and increase the number of swaps from 1 to 20 to enable more exploratory search [PITH_FULL_IMAGE:figures/fu… view at source ↗
Figure 3
Figure 3. Learned node embeddings of Cora-ML. Red: seen nodes; blue: unseen nodes. [PITH_FULL_IMAGE:figures/full_fig_p009_3.png] view at source ↗
Figures from the paper (3 more)
Figure 4
Figure 4. Figure 4: Learned node embeddings of Network Science. Red: seen nodes; blue: unseen nodes. [PITH_FULL_IMAGE:figures/full_fig_p009_4.png]
Figure 5
Figure 5. Figure 5: Learned node embeddings of Power Grid. Red: seen nodes; blue: unseen nodes. [PITH_FULL_IMAGE:figures/full_fig_p009_5.png]
Figure 6
Figure 6. Figure 6: Learned node embeddings of Jazz. Red: seen nodes; blue: unseen nodes. [PITH_FULL_IMAGE:figures/full_fig_p009_6.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

14 extracted references · 12 canonical work pages

  1. [1]

    An o (m) algorithm for cores decomposition of networks

    Vladimir Batagelj and Matjaz Zaversnik. An o (m) algorithm for cores decomposition of networks. arXiv preprint cs/0310049,

    arXiv

  2. [14]

    and PyTorch Geometric (Fey & Lenssen, 2019; Fey et al.,

    work page 2019

  3. [1978]

    Qintian Guo, Sibo Wang, Zhewei Wei, and Ming Chen

    ISSN 00029602, 15375390. Qintian Guo, Sibo Wang, Zhewei Wei, and Ming Chen. Influence maximization revisited: Efficient reverse reachable set generation with bound tightened. InProceedings of the 2020 ACM SIGMOD international conference on management of data, pp. 2167–2181,

    work page 2020

  4. [1998]

    Dynaflux: Implicit dynamics-preserving reinforcement learning for topology-free influence maximization

    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. InProceedings of the ACM Web Conference 2026, pp. 4940–4951, 2026a. Haotian Zhang, Kai Han, Zhizhuo Yin, Shuang Cui, Jing Tang, and Pan Hui. Imgnn: An efficient,...

    work page 2026

  5. [2007]

    Disco: Influence maximization meets network embedding and deep learning.arXiv preprint arXiv:1906.07378, 2019a

    Hui Li, Mengting Xu, Sourav S Bhowmick, Changsheng Sun, Zhongyuan Jiang, and Jiangtao Cui. Disco: Influence maximization meets network embedding and deep learning.arXiv preprint arXiv:1906.07378, 2019a. Hui Li, Mengting Xu, Sourav S Bhowmick, Joty Shafiq Rayhan, Changsheng Sun, and Jiangtao Cui. Piano: Influence maximization meets deep reinforcement learn...

    arXiv 1906

  6. [2012]

    Online processing algorithms for influence maximization

    Jing Tang, Xueyan Tang, Xiaokui Xiao, and Junsong Yuan. Online processing algorithms for influence maximization. InProceedings of the 2018 international conference on management of data, pp. 991–1005,

    work page 2018

  7. [2014]

    Influence maximization in near-linear time: A martingale approach

    Youze Tang, Yanchen Shi, and Xiaokui Xiao. Influence maximization in near-linear time: A martingale approach. InProceedings of the 2015 ACM SIGMOD international conference on management of data, pp. 1539–1554,

    work page 2015

  8. [2015]

    Social Contagion: An Empirical Study of Information Spread on Digg and Twitter Follower Graphs

    Kristina Lerman, Rumi Ghosh, and Tawan Surachawala. Social contagion: An empirical study of information spread on digg and twitter follower graphs.arXiv preprint arXiv:1202.3162,

    work page Pith review arXiv

Show all 14 references
  1. [2016]

    All models are trained for 200 epochs using AdamW (Kingma & Ba, 2015; Loshchilov & Hutter,

    is added to the second layer. All models are trained for 200 epochs using AdamW (Kingma & Ba, 2015; Loshchilov & Hutter,

    2015

  2. [2018]

    Influence maximization: Near-optimal time complexity meets practical efficiency

    Youze Tang, Xiaokui Xiao, and Yanchen Shi. Influence maximization: Near-optimal time complexity meets practical efficiency. InProceedings of the 2014 ACM SIGMOD international conference on Management of data, pp. 75–86,

    2014

  3. [2019]

    Pyg 2.0: Scalable learning on real world graphs

    Matthias Fey, Jinu Sunil, Akihiro Nitta, Rishi Puri, Manan Shah, Blaž Stojanoviˇc, Ramona Bendias, Alexandria Barghi, Vid Kocijan, Zecheng Zhang, Xinwei He, Jan Eric Lenssen, and Jure Leskovec. Pyg 2.0: Scalable learning on real world graphs. InTemporal Graph Learning Workshop...

    2025

  4. [2022]

    While these architectural improvements enhance predictive capacity, they also introduce training complexity

    that takes in binary seed set vectors with one-hot-coded unique node degrees and incorporates an additional learnable node scoring mechanism during inference. While these architectural improvements enhance predictive capacity, they also introduce training complexity. Limitatio...

    2023

  5. [2024]

    Stop-and-stare: Optimal sampling algorithms for viral marketing in billion-scale networks

    Hung T Nguyen, My T Thai, and Thang N Dinh. Stop-and-stare: Optimal sampling algorithms for viral marketing in billion-scale networks. InProceedings of the 2016 international conference on management of data, pp. 695–710,

    2016

  6. [2025]

    Specifically, it replaces conventional message-passing networks with a sheaf neural network (Hansen & Gebhart, 2020; Bodnar et al.,

    follows a similar surrogate-based optimization frame- work but focuses on improving diffusion prediction accuracy through a more sophisticated graph architecture. Specifically, it replaces conventional message-passing networks with a sheaf neural network (Hansen & Gebhart, 202...

    2020

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.