pith. sign in

arxiv: 1907.01707 · v1 · pith:RUTPWHV4new · submitted 2019-07-03 · 💻 cs.SI

On Adaptivity Gaps of Influence Maximization under the Independent Cascade Model with Full Adoption Feedback

Wei Chen , Binghui Peng This is my paper

Pith reviewed 2026-05-25 10:07 UTC · model grok-4.3

classification 💻 cs.SI
keywords influence maximizationadaptivity gapindependent cascade modelfull adoption feedbackarborescencesbipartite graphsstochastic optimization
0
0 comments X

The pith

The adaptivity gap of influence maximization with full adoption feedback is at most 2e/(e-1) on in-arborescences and 2 on out-arborescences.

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

This paper establishes upper bounds on the adaptivity gap for influence maximization under the independent cascade model when full adoption feedback is available after each seed choice. It focuses on restricted graph families including in-arborescences, out-arborescences, and bipartite graphs, proving that the gap lies between e/(e-1) and 2e/(e-1) for in-arborescences and between e/(e-1) and 2 for out-arborescences. These are presented as the first constant upper bounds in the full-adoption feedback model. Sympathetic readers care because the results quantify the additional value of adaptive strategies over non-adaptive ones in network diffusion, informing whether adaptivity is worth the implementation cost in stochastic settings.

Core claim

We prove that the adaptivity gap for the in-arborescence is between [e/(e-1), 2e/(e-1)] and for the out-arborescence, the gap is between [e/(e-1), 2]. These are the first constant upper bounds in the full-adoption feedback model. We provide several novel ideas to tackle with correlated feedback appearing in the adaptive stochastic optimization, which we believe to be of independent interests. Similar constant bounds are derived for bipartite graphs.

What carries the argument

The adaptivity gap, the worst-case ratio of the expected spread achieved by an optimal adaptive policy to that of an optimal non-adaptive policy under the independent cascade model with full adoption feedback.

If this is right

  • Adaptive policies improve expected influence by at most a factor of 2e/(e-1) over non-adaptive policies on in-arborescences.
  • The improvement factor is at most 2 on out-arborescences.
  • Constant-factor bounds also hold on bipartite graphs.
  • Novel techniques handle correlated feedback arising in adaptive stochastic optimization.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The constant gaps imply that non-adaptive seeding strategies achieve near-optimal performance on these tree-structured graphs, reducing the need for complex adaptive algorithms in such cases.
  • The methods for managing correlated feedback may extend to other adaptive decision problems with partial observations beyond influence maximization.
  • Similar gap analysis could be attempted on additional restricted graph families like planar graphs or low-treewidth networks to test broader applicability.
  • pith_inferences

Load-bearing premise

The analysis assumes the underlying graphs belong to restricted families such as in-arborescences, out-arborescences, and bipartite graphs, with diffusion following the independent cascade model and full adoption feedback available after each seed choice.

What would settle it

An explicit in-arborescence instance where the adaptivity gap exceeds 2e/(e-1) under the independent cascade model with full adoption feedback would falsify the claimed upper bound.

read the original abstract

In this paper, we study the adaptivity gap of the influence maximization problem under independent cascade model when full-adoption feedback is available. Our main results are to derive upper bounds on several families of well-studied influence graphs, including in-arborescences, out-arborescences and bipartite graphs. Especially, we prove that the adaptivity gap for the in-arborescence is between $[\frac{e}{e-1}, \frac{2e}{e - 1}]$ and for the out-arborescence, the gap is between $[\frac{e}{e-1}, 2]$. These are the first constant upper bounds in the full-adoption feedback model. We provide several novel ideas to tackle with correlated feedback appearing in the adaptive stochastic optimization, which we believe to be of independent interests.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The paper studies the adaptivity gap (adaptive OPT over non-adaptive OPT) of influence maximization under the independent cascade model with full-adoption feedback. It derives the first constant upper bounds on this gap for restricted graph families: for in-arborescences the gap lies in [e/(e-1), 2e/(e-1)], and for out-arborescences in [e/(e-1), 2]; analogous results are given for bipartite graphs. Novel techniques are introduced to handle correlated feedback arising from the adaptive setting.

Significance. If the stated proofs are correct, the work supplies the first constant-factor upper bounds on the adaptivity gap under full-adoption feedback for these natural graph classes, together with explicit lower-bound constructions. The techniques developed for correlated feedback are likely to be reusable in other adaptive stochastic combinatorial optimization settings.

minor comments (2)
  1. [§1] §1: the definition of the adaptivity gap should explicitly reference the full-adoption feedback model in the notation to avoid ambiguity with the no-feedback case.
  2. [Proof of Theorem 3.2] The proof sketches for the upper bounds on out-arborescences could benefit from an explicit statement of the induction hypothesis used to bound the value of the adaptive policy.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive review, the recognition of the novelty of our constant upper bounds on adaptivity gaps under full-adoption feedback, and the recommendation to accept. We are glad that the reusable techniques for handling correlated feedback are viewed as potentially of independent interest.

Circularity Check

0 steps flagged

No significant circularity; self-contained theoretical proofs

full rationale

The paper establishes constant upper bounds on adaptivity gaps via direct mathematical analysis of correlated feedback under the independent cascade model, restricted to in-arborescences, out-arborescences, and bipartite graphs. These derivations rely on novel handling of adaptive stochastic optimization properties specific to the graph families and feedback model, without any reduction of claimed results to fitted parameters, self-definitions, or load-bearing self-citations. The bounds are derived as independent first-principles results on the defined quantities (adaptive OPT / non-adaptive OPT ratios), making the central claims self-contained.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Review is based solely on the abstract; no free parameters, invented entities, or non-standard axioms are identifiable from the given text. Standard assumptions of the independent cascade model are implicit but not detailed.

pith-pipeline@v0.9.0 · 5667 in / 1096 out tokens · 24493 ms · 2026-05-25T10:07:47.981916+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

40 extracted references · 40 canonical work pages · 3 internal anchors

  1. [1]

    , Sviridenko, M

    Adamczyk, M. , Sviridenko, M. , and W ard, J. 2016. Submodular stochastic probing on matroids. Mathematics of Operations Research 41, 3, 1022–1038

    work page 2016

  2. [2]

    , Gamzu, I

    Alon, N. , Gamzu, I. , and Tennenholtz, M. 2012. Optimizing budget allocation among channels and influencers. In WWW. ACM, 381–388

    work page 2012

  3. [3]

    and Nazerzadeh, H

    Asadpour, A. and Nazerzadeh, H. 2015. Maximizing stochastic monotone submodular functions. Management Science 62, 8, 2374–2391

    work page 2015

  4. [4]

    , Papadimitriou, C

    Badanidiyuru, A. , Papadimitriou, C. , Rubinstein, A. , Seeman, L. , and Singer, Y

    work page

  5. [5]

    Locally adaptive optimization: Adaptive seeding for monotone submodular functions. In SODA. SIAM

    work page

  6. [6]

    , Bonchi, F

    Barbieri, N. , Bonchi, F. , and Manco, G. 2012. Topic-aware social influence propagation models. In ICDM’12

    work page 2012

  7. [7]

    , Kempe, D

    Bharathi, S. , Kempe, D. , and Salek, M. 2007. Competitive influence maximization in social networks. In WINE. Springer, 306–311

    work page 2007

  8. [8]

    , Brautbar, M

    Borgs, C. , Brautbar, M. , Chayes, J. , and Lucier, B. 2014. Maximizing social influence in nearly optimal time. In SODA’14. ACM-SIAM, 946–957

    work page 2014

  9. [9]

    (Near) Optimal Adaptivity Gaps for Stochastic Multi-Value Probing

    Bradac, D. , Singla, S. , and Zuzic, G. 2019. (near) optimal adaptivity gaps for stochastic multi-value probing. arXiv preprint arXiv:1902.01461

    work page internal anchor Pith review Pith/arXiv arXiv 2019

  10. [10]

    , Chekuri, C

    Calinescu, G. , Chekuri, C. , P´al, M. , and Vondr ´ak, J. 2011. Maximizing a monotone submodular function subject to a matroid constraint. SIAM Journal on Computing 40, 6, 1740– 1766

    work page 2011

  11. [11]

    , Vondrak, J

    Chekuri, C. , Vondrak, J. , and Zenklusen, R. 2010. Dependent randomized rounding via exchange properties of combinatorial structures. In FOCS. IEEE, 575–584. 11

    work page 2010

  12. [12]

    , Lakshmanan, L

    Chen, W. , Lakshmanan, L. V. , and Castillo, C. 2013. Information and Influence Prop- agation in Social Networks . Morgan & Claypool Publishers

    work page 2013

  13. [13]

    , W ang, C., and W ang, Y

    Chen, W. , W ang, C., and W ang, Y. 2010. Scalable influence maximization for prevalent viral marketing in large-scale social networks. In KDD’10

    work page 2010

  14. [14]

    , W ang, Y., and Yang, S

    Chen, W. , W ang, Y., and Yang, S. 2009. Efficient influence maximization in social net- works. In Proceedings of the 15th ACM SIGKDD . ACM

    work page 2009

  15. [15]

    and Sakaue, S

    Fujii, K. and Sakaue, S. 2019. Beyond adaptive submodularity: Approximation guara ntees of greedy policy with adaptive submodularity ratio. In ICML. 2042–2051

    work page 2019

  16. [16]

    and Krause, A

    Golovin, D. and Krause, A. 2011. Adaptive submodularity:theory and applications in active learning and stochastic optimization. Journal of Artificial Intelligence Research 42 , 427–

    work page 2011

  17. [17]

    arXiv version (arxiv.org/abs/1003.3967) includes di scussions on the myopic feedback model

    work page internal anchor Pith review Pith/arXiv arXiv

  18. [18]

    , Nagarajan, V

    Gupta, A. , Nagarajan, V. , and Singla, S. 2016. Algorithms and adaptivity gaps for stochastic probing. In SODA. SIAM

    work page 2016

  19. [19]

    , Nagarajan, V

    Gupta, A. , Nagarajan, V. , and Singla, S. 2017. Adaptivity gaps for stochastic probing: Submodular and XOS functions. In SODA. SIAM

    work page 2017

  20. [20]

    , and Kawarabayashi, K.-I

    Hatano, D., Fukunaga, T. , and Kawarabayashi, K.-I. 2016. Adaptive budget allocation for maximizing influence of advertisements. In IJCAI. 3600–3608

    work page 2016

  21. [21]

    , Kleinberg, J

    Kempe, D. , Kleinberg, J. , and Tardos, ´E. 2003. Maximizing the spread of influence through a social network. In Proceedings of the ninth ACM SIGKDD . ACM, 137–146

    work page 2003

  22. [22]

    , Kleinberg, J

    Kempe, D. , Kleinberg, J. M. , and Tardos, ´E. 2015. Maximizing the spread of influence through a social network. Theory of Computing 11, 4, 105–147. Conference version appeared in KDD’2003

    work page 2015

  23. [23]

    , Krause, A

    Leskovec, J. , Krause, A. , Guestrin, C. , F aloutsos, C., V anbriesen, J. M. , and Glance, N. 2007. Cost-effective outbreak detection in networks. In ACM Knowledge Discovery and Data Mining . 420–429

    work page 2007

  24. [24]

    , F an, J., W ang, Y., and Tan, K

    Li, Y. , F an, J., W ang, Y., and Tan, K. 2018. Influence maximization on social graphs: A survey. IEEE Trans. Knowl. Data Eng. 30, 10, 1852–1872

    work page 2018

  25. [25]

    , Chen, W

    Lin, Y. , Chen, W. , and Lui, J. C. 2017. Boosting information spread: An algorithmic approach. In ICDE. IEEE, 883–894

    work page 2017

  26. [26]

    , Chen, W

    Lu, W. , Chen, W. , and Lakshmanan, L. V. 2015. From competition to complementarity: comparative influence diffusion and maximization. Proceedings of the VLDB Endowment 9, 2, 60–71

    work page 2015

  27. [27]

    , Zhang, Z

    Lu, Z. , Zhang, Z. , and Wu, W. 2017. Solution of bharathi–kempe–salek conjecture for influence maximization on arborescence. Journal of Combinatorial Optimization 33, 2, 803–808

    work page 2017

  28. [28]

    Adaptive Influence Maximization with Myopic Feedback

    Peng, B. and Chen, W. 2019. Adaptive influence maximization with myopic feedback . arXiv preprint arXiv:1905.11663

    work page internal anchor Pith review Pith/arXiv arXiv 2019

  29. [29]

    , Tziortziotis, N., and V azirgiannis, M

    Salha, G. , Tziortziotis, N., and V azirgiannis, M. 2018. Adaptive submodular influence maximization with myopic feedback. In ASONAM. IEEE, 455–462. 12

    work page 2018

  30. [30]

    and Singer, Y

    Seeman, L. and Singer, Y. 2013. Adaptive seeding in social networks. In FOCS. IEEE, 459–468

    work page 2013

  31. [31]

    Singer, Y. 2016. Influence maximization through adaptive seeding. ACM SIGecom Ex- changes 15, 1, 32–59

    work page 2016

  32. [32]

    , Kakimura, N

    Soma, T. , Kakimura, N. , Inaba, K. , and Kawarabayashi, K.-i. 2014. Optimal budget allocation: Theoretical guarantee and efficient algorithm. In ICML

    work page 2014

  33. [33]

    , Huang, W

    Sun, L. , Huang, W. , Yu, P. S. , and Chen, W. 2018. Multi-round influence maximization. In KDD. ACM, 2249–2258

    work page 2018

  34. [34]

    , Shi, Y

    Tang, Y. , Shi, Y. , and Xiao, X. 2015. Influence maximization in near-linear time: A martingale approach. In SIGMOD’15. ACM, 1539–1554

    work page 2015

  35. [35]

    , and Shi, Y

    Tang, Y., Xiao, X. , and Shi, Y. 2014. Influence maximization: near-optimal time complex- ity meets practical efficiency. In SIGMOD’14

    work page 2014

  36. [36]

    Tong, G. , Wu, W. , Tang, S. , and Du, D.-Z. 2017. Adaptive influence maximization in dynamic social networks. IEEE/ACM Transactions on Networking (TON) 25, 1, 112–125

    work page 2017

  37. [37]

    Vondr´ak, J. 2007. Submodularity in combinatorial optimization

    work page 2007

  38. [38]

    , and Cui, L

    W ang, A., Wu, W. , and Cui, L. 2016. On bharathi–kempe–salek conjecture for influence maximization on arborescence. Journal of Combinatorial Optimization 31, 4, 1678–1684

    work page 2016

  39. [39]

    and Tang, S

    Yuan, J. and Tang, S. 2017. No time to observe: Adaptive influence maximization wi th partial feedback. In IJCAI. 13 Appendix For convenience, we restate the lemmas and theorems in the ap pendix before the proofs. A Missing Proofs from Section 3 Lemma 3.2. E [f (Ψ(1))] = F (1 −e−x1, · · ·, 1 −e−xn) ≤F (x1, · · ·,x n). Proof. Notice that in the Poisson proc...

    work page 2017

  40. [40]

    Lemma 4.3

    ( 26) ( 27), we complete the proof. Lemma 4.3. For any i, we have F1(0, · · ·, 0,x i, · · ·,x n) −F1(0, · · ·, 0,x i+1, · · ·,x n) = xipi (1 −Fi(0, · · ·, 0,x i+1, · · ·,x n)). Proof. Since the node 1’s predecessors form a directed line, for any i we have F1(0, · · ·, 0,x i, · · ·,x n) −F1(0, · · ·, 0,x i+1, · · ·,x n) =pi · (Fi(0, · · ·, 0,x i, · · ·,x n...

    work page