acceptodds
Under review as a conference paper at ICLR 2027

Budget-Independent Influence Maximization in Nearly Linear Time

Abstract

Influence maximization asks for seed vertices that maximize the expected spread of a diffusion process in a network. Standard near-optimal-time algorithms based on reverse-reachable sampling achieve a approximation, but their expected running-time bounds grow linearly with the seed budget . We remove this multiplicative dependence: for the independent cascade model, our algorithm succeeds with probability at least in expected time. The result extends to triggering models with explicitly charged local sampling costs. We reserve seed positions for cost-weighted random vertices, allowing reverse-reachable searches to terminate as soon as they encounter a reserved seed. An independent calibration procedure determines the sample count using a statistic that also controls the expected search cost. Matching these quantities eliminates the multiplicative dependence on while preserving the approximation guarantee.

Primary area:
optimization
Keywords:
influence maximization, nearly linear time, reverse-reachable sampling

Reviews

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

The paper proposes an influence-maximization algorithm for directed IC networks with a high-probability (1−1/e−epsilon) approximation and an expected-time bound without a multiplicative polynomial dependence on the seed budget k. It reserves at most floor(epsilon k/3) positions for vertices sampled proportionally to reverse-expansion cost. RR searches terminate exactly when they encounter a reserved seed, and greedy coverage fills the remaining positions. An independent estimation phase accumulates a capped search-cost statistic to determine the sample count. Matching that statistic's role in sample count and sample-generation cost removes its unknown mean from the total-work bound. The paper claims O((m+n) epsilon^−3 log(2n/delta)) expected time and an extension to triggering models with explicit sampling costs.

Critical strengths
  1. Eliminating the multiplicative budget factor for every valid cardinality budget would improve a concrete limitation of standard RR-based bounds. The paper openly exchanges epsilon^−2 for epsilon^−3 dependence and does not claim a single ordering that solves every budget simultaneously.

  2. Reserving any sufficiently small set limits approximation loss, while its cost-weighted distribution controls search work. Keeping estimation independent from both the reserved set and final samples is important. The text correctly distinguishes that independence from the dependence among searches sharing the same reserved set.

Critical weaknesses
  1. The supplied manuscript ends on page 11, without Appendices A–D. Those sections are needed for the coverage implementation, prefix-integral argument, exact capped-score procedure, stopping-time guarantees, and extension. For example, Lemma 4.4 asserts the high-probability sample-count sufficiency needed for approximation, but the necessary bridge between the statistic mean and OPT_k is not derived in the available text. This prevents a complete correctness and total-cost assessment of a paper whose principal contribution is its theorem.

  2. HIST already uses sentinel-based termination, and the manuscript discusses another budget-independent result with a restriction involving k epsilon. The distinction should be demonstrated across assumptions, approximation, failure probability, and local sampling costs, rather than relying mainly on the headline budget factor. The additional inverse-epsilon factor can offset the advantage at small budgets or high precision; when k<3/epsilon there are no prescribed draws.

Questions for authors
  1. Where are Appendices A–D in the official submission? Please identify the complete proofs of Lemmas 4.1, 4.3, and 4.4 and Theorem 4.6, together with ScoreRR and BucketGreedy. This is the principal material-access issue affecting the present assessment.
  2. What exact relation between the capped-score mean and OPT_k establishes sample sufficiency, and how is that high-probability argument separated from the unconditional moment calculation used for runtime? Please include the treatment of searches sharing the same prescribed set and all initialization, storage, and greedy-update costs.
  3. Can the paper give a theorem-level comparison with HIST and the cited budget-independent predecessor, including the small-k regime and triggering-model access assumptions? Which ranges of k and epsilon yield an asymptotic advantage once the precision dependence is included?
1 comment

Thank you for explaining which parts of the proof you could not access. We apologize for not making their location clear. The main PDF ends on p. 11; the file under Supplementary Material on the submission page is the full 21-page paper, with Appendices A–D on pp. 12–21. In that file, BucketGreedy is Algorithm B.1 on p. 13, and ScoreRR is Algorithm C.1 on p. 16. The proofs of Lemmas 4.1, 4.3, and 4.4 are on pp. 15, 17, and 18, respectively; the proof of Theorem 4.6 is on pp. 18–19. We will add a direct pointer in the main paper. We also give the key argument here.

The bridge to the optimum is nμ/2≤OPTkn\mu/2\leq\mathrm{OPT}_k (Lemma C.1, pp. 15–16). To see it, independently draw kk vertices with probabilities c(v)/Cc(v)/C, and let UU be the set of distinct draws. For a fixed RR set RR of total cost w(R)w(R), the probability that UU hits it is 1−(1−w(R)/C)k1-(1-w(R)/C)^k, which is at least 12min⁡{1,kw(R)/C}=X(R)/2\tfrac12\min\{1,kw(R)/C\}=X(R)/2. Averaging and applying the RR identity gives nμ/2≤E[σ(U)]≤OPTkn\mu/2\leq\mathbb E[\sigma(U)]\leq\mathrm{OPT}_k, since every realization of UU is feasible.

For sample sufficiency, Lemma 4.3 gives Γ/(2τ)≤μ\Gamma/(2\tau)\leq\mu with probability at least 1−δ/21-\delta/2. On this event, 4τ/Γ≥2/μ≥n/OPTk4\tau/\Gamma\geq 2/\mu\geq n/ OPT_k. Also n/k≥n/OPTkn/k\geq n/ OPT_k, since seeds activate themselves. Thus both terms in aτ=min⁡{n/k,4τ/Γ}a_\tau=\min\{n/k,4\tau/\Gamma\} are large enough, and the resulting sample count meets the threshold in Theorem 3.5. The fresh final samples contribute at most another δ/2\delta/2 failure probability.

For runtime, we do not condition on that event. Lemma 4.4 gives the unconditional bound μE[aτ]≤8\mu\mathbb E[a_\tau]\leq 8. Conditional on the estimation phase, NN is fixed, while the reserved set BB and the final RR samples retain their original distributions. Averaging over BB and one fresh sample gives expected work O(Cμ/(b+1))O(C\mu/(b+1)) per search. Linearity of expectation gives O(NCμ/(b+1))O(NC\mu/(b+1)) for all searches, even though their costs share BB. Theorem 4.6 also charges O(C)O(C) for initialization, O(CΓ/k)O(C\Gamma/k) for estimation, and O(n+I)O(n+I) for greedy selection, where II is the number of retained incidences. Vertex marks are initialized once and only touched entries are reset. Each retained incidence is already charged when stored and is scanned only a constant number of times by BucketGreedy.

Finally, you are right that when k<3/εk<3/\varepsilon there are no reserved draws. In that regime Eq. (C.5) retains the usual ε−2\varepsilon^{-2} dependence; when εk\varepsilon k grows, its denominator 1+⌊εk/3⌋1+\lfloor\varepsilon k/3\rfloor gives a growing improvement over the standard general-IC RR upper bound. HIST already uses early stopping, but selects and validates its sentinels for influence; our bound uses their cost-weighted distribution and the independent estimator. Lakshmanan’s Theorem 1 assumes kε<1k\varepsilon<1 and gives success probability at least 3/53/5, whereas our bound holds for every input budget at the requested accuracy and confidence. For the triggering extension, Definition D.1 and Theorem D.2 (p. 20) explicitly charge preprocessing and the cost of sampling and processing each local triggering set; an edge-linear bound applies only when the local representation supports it.

We hope these pointers and the argument above make it possible to assess the proofs that were missing from the main PDF.

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

This paper proposes a randomized influence maximization algorithm that eliminates the multiplicative dependence on the seed budget from the expected running-time bound. The method combines cost-weighted seed reservation, early termination of reverse-reachable searches, and independent sample-count estimation. It establishes a near-linear expected-time bound while preserving a (1−1/e−ε)(1-1/e-\varepsilon) approximation guarantee under the IC model.

Critical strengths
  1. Meaningful theoretical contribution. Eliminating the multiplicative dependence on the seed budget represents a significant improvement over classical RR-sampling algorithms.
  2. Interesting algorithmic design. The combination of cost-weighted seed reservation and early search termination provides an elegant mechanism for reducing computational complexity.
  3. Comprehensive theoretical analysis. The supplementary material provides detailed proofs of the approximation and running-time guarantees, including extensions to more general triggering models.
Critical weaknesses
  1. Lack of experimental validation. The paper provides no empirical evaluation, making it difficult to assess the practical significance of the proposed complexity improvement.
  2. Unclear practical efficiency advantages. The improved dependence on the seed budget comes at the cost of increasing the precision dependence from ε−2\varepsilon^{-2} to ε−3\varepsilon^{-3}. The practical implications of this trade-off remain unexplored.
  3. Limited methodological scope. The work primarily focuses on accelerating classical influence maximization, with limited discussion of its applicability to more recent or learning-based IM scenarios.
Questions for authors
  1. Can the authors provide empirical comparisons with IMM, OPIM-C, and HIST across different network sizes and seed budgets?
  2. Under what conditions does eliminating the budget dependence outweigh the increased dependence on ε\varepsilon?
  3. Can the authors further clarify the practical advantages of the proposed method over HIST, beyond the theoretical complexity improvement?
1 comment

Thank you for raising the tradeoff between budget and precision. There is a sharper answer to this question in the proof than in the headline theorem. In the IC model, keeping the number of reserved draws explicit in Eq. (C.5) gives the expected-time bound

\frac{(m+n)\,[k\ln(en/k)+\ln(4/\delta)]} {\varepsilon^2(1+\lfloor\varepsilon k/3\rfloor)} \right).$$ This shows what happens at both ends of the budget range. If $\varepsilon k<3$, the algorithm reserves no seeds: there is no saving from early stopping, but there is no extra inverse-$\varepsilon$ factor either. If $\varepsilon k$ grows, the denominator improves on the standard general-IC RR upper bound at matched accuracy and confidence. For example, at fixed $\varepsilon$, $\delta=1/n$, and $k=\lfloor\sqrt n\rfloor$, TIM’s bound in Eq. (1) is $O((m+n)\sqrt n\log n)$, whereas ours is $O((m+n)\log n)$. We will state the sharper bound in the main text so that readers can see the tradeoff without reconstructing it from the proof. On practical efficiency, the submission does not include benchmarks against IMM, OPIM-C, or HIST. One concrete difference from HIST is that constructing our stopping set requires only the indegrees and independent draws; it requires no RR samples to select or validate the reserved vertices. The algorithm still incurs the cost of estimating the final sample count, and HIST may select sentinels that are hit more often on a particular network. We therefore cannot infer a wall-clock or memory advantage over HIST from the theorem. A fair comparison would vary both $k$ and $\varepsilon$, include preprocessing and estimation in total runtime, and report retained incidences, peak memory, and independently evaluated influence. Regarding learning-based IM, the algorithm can be used for seed selection once a learned IC model is fixed. Its guarantee is then relative to the optimum under that fitted model. It does not account for error in the learned probabilities or for the cost of learning them. We will clarify this scope rather than imply an end-to-end learning guarantee.
Reviewer_AYV4OpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

The paper proposes a reverse-reachable sampling algorithm for influence maximization under the independent cascade model that achieves a (1−1/e−ε)(1-1/e-\varepsilon) approximation with probability at least 1−δ1-\delta in expected time O((m+n)ε−3[ln⁡(en/k)+k−1ln⁡(4/δ)])O((m+n)\varepsilon^{-3}[\ln(en/k)+k^{-1}\ln(4/\delta)]). It reserves ⌊εk/3⌋\lfloor\varepsilon k/3\rfloor cost-weighted random seeds, allowing searches to stop when they encounter one of them, and fills the remaining positions by greedy coverage. An independent estimation phase uses a capped search-cost statistic to determine the sample count. Its mean cancels against the expected cost per search, removing the multiplicative budget factor. The full paper also gives a time-capped implementation and a triggering-model extension with explicitly charged sampling costs. The contribution is theoretical; no experiments are reported.

Critical strengths
  1. The claimed runtime improvement is meaningful. A nearly linear expected-time guarantee across the full cardinality-budget range addresses an important limitation of standard RR-sampling bounds. The paper states the trade-offs clearly: precision dependence worsens from ε−2\varepsilon^{-2} to ε−3\varepsilon^{-3}, and the guarantee concerns one specified budget with all vertices eligible as equal-cost seeds. The triggering extension explicitly accounts for local sampling costs rather than hiding them in a free oracle.

  2. The full proof chain handles the main dependencies carefully. The prefix-integral argument uses membership testing before expansion; the capped score can be computed exactly without completing every search; and Lemma C.1 connects its mean to OPT through a feasible random seed set. Lemma 4.3 derives the stopping-time expectation by finite summation and controls early stopping with a fixed-length tail event. The final expected-work factorization is justified by independence from the estimation phase, without assuming that searches sharing the reserved set have independent costs. Appendix B also establishes linear total-time greedy coverage.

Critical weaknesses
  1. Practical improvements remain untested. The sample-count requirement still depends on the budget; the method spends some seed positions on cost-weighted random vertices, and the worst-case precision dependence is worse than that of standard RR approaches. It is therefore unclear when reduced search work outweighs these costs in practice. Experiments measuring search work, runtime, peak memory, and solution quality across budgets would strengthen the paper. This limits the practical conclusions.

  2. The comparison with the closest prior results could be more explicit. The paper already credits HIST for hit-and-stop sampling; the new contribution is the cost-weighted random stopping set combined with an estimator matched to search cost. The restriction attributed to Lakshmanan (2025), kε<1k\varepsilon<1, is central to the novelty claim and deserves a precise theorem-level comparison of assumptions, approximation, success probability, and runtime. The bounds should also be compared across precision and budget regimes rather than suggesting that the new method is uniformly faster.

Questions for authors
  1. Please provide the exact theorem statement supporting the kε<1k\varepsilon<1 restriction attributed to Lakshmanan (2025), and a concise comparison with the present guarantee and HIST. This would help establish the precise scope of the advance.

  2. Is implementation evidence available for runtime, retained RR incidences, and influence quality relative to HIST or another modern RR baseline as kk and ε\varepsilon vary? Such evidence could strengthen my recommendation, although the theoretical result can stand without it.

1 comment

Thank you for the careful reading. The result we refer to is Theorem 1 of K. Lakshmanan, Influence Maximization Independent of Seed Set Size (Operations Research Letters, 2025). For directed IC networks, its budget-independent guarantee gives a (1−1/e−ε)(1-1/e-\varepsilon) approximation with probability at least 3/53/5 under the condition kε<1k\varepsilon<1. The distinction is easiest to see by fixing the requested accuracy: at ε=0.1\varepsilon=0.1, for example, the theorem covers k≤9k\leq 9. For larger budgets one could use a finer internal accuracy, but the precision parameter in the running time would then depend on kk. Our Theorem 1.1 applies at the requested accuracy for every 1≤k≤n1\leq k\leq n, with success probability at least 1−δ1-\delta. We will make this comparison explicit and also acknowledge Seddighin’s independent all-budget result.

We agree that stopping a reverse search when it hits a seed is already present in HIST. HIST uses RR samples to select and validate a sentinel set for its influence. We instead draw vertices in proportion to their reverse-expansion costs, 1+d−(v)1+d^-(v). Their influence need not be estimated: the number of reserved positions bounds the possible loss in solution quality, while the sampling distribution bounds the expected cost of a search. The other ingredient is an independent estimator whose mean appears inversely in the sample-count bound and linearly in the search-cost bound. It is this cancellation, together with early stopping, that gives the all-budget running time.

The precision tradeoff is also milder than the headline bound suggests. In Eq. (C.5), the denominator retains the factor 1+⌊εk/3⌋1+\lfloor\varepsilon k/3\rfloor. When εk<3\varepsilon k<3, we reserve no seeds and the bound retains the usual ε−2\varepsilon^{-2} dependence. When εk\varepsilon k grows, the denominator gives a growing improvement over the standard general-IC RR time bound at the same accuracy and confidence. We will bring this distinction into the main text.

The submission contains no head-to-head experiments with HIST. In particular, we cannot say at what budget shorter searches translate into lower wall-clock time or peak memory on real networks. We agree that measuring edge examinations, retained RR incidences, and independently evaluated spread alongside runtime would make that comparison informative. Our claim is about the expected-time guarantee, not a measured speedup.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.