Efficient Online Influence Maximization under the Independent Cascade Model with Node-Level Feedback

Arpit Agarwal, Varad Deolankar, Rohan Ghuge
Proceedings of the 43rd International Conference on Machine Learning, PMLR 306:769-793, 2026.

Abstract

Influence maximization is an important research area in social network analysis, where the goal is to select a small set of seed nodes so as to maximize the expected spread of influence under a stochastic diffusion process. Classical approximation algorithms for this problem rely on full knowledge of the underlying influence probabilities and operate in an offline manner. In many real-world settings, however, these probabilities are unknown and must be learned from data, raising the question: can one still obtain strong performance guarantees while simultaneously learning the diffusion model parameters through repeated interactions? In this paper, we study the problem of online influence maximization under the independent cascade model, where influence probabilities are unknown and feedback is limited to node-level activation outcomes. Prior work relies on a pair oracle which needs to perform a joint optimization over seed sets and feasible parameters. This oracle is difficult to implement in practice and it was open whether one can achieve sublinear regret using only a standard offline oracle. We resolve this question by designing an online learning algorithm that achieves $\widetilde{O}(\sqrt{T})$ regret using only a standard offline oracle. Finally, we validate our theoretical results via experiments on real and synthetic data.

Cite this Paper

BibTeX
@InProceedings{pmlr-v306-agarwal26a, title = {Efficient Online Influence Maximization under the Independent Cascade Model with Node-Level Feedback}, author = {Agarwal, Arpit and Deolankar, Varad and Ghuge, Rohan}, booktitle = {Proceedings of the 43rd International Conference on Machine Learning}, pages = {769--793}, year = {2026}, editor = {Zhang, Tong and Dudik, Miroslav and Jaggi, Martin and Agarwal, Alekh and Li, Sharon and Schuurmans, Dale and Zhu, Jerry and Berkenkamp, Felix and Dong, Hanze and Bietti, Alberto}, volume = {306}, series = {Proceedings of Machine Learning Research}, month = {06--11 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v306/main/assets/agarwal26a/agarwal26a.pdf}, url = {https://proceedings.mlr.press/v306/agarwal26a.html}, abstract = {Influence maximization is an important research area in social network analysis, where the goal is to select a small set of seed nodes so as to maximize the expected spread of influence under a stochastic diffusion process. Classical approximation algorithms for this problem rely on full knowledge of the underlying influence probabilities and operate in an offline manner. In many real-world settings, however, these probabilities are unknown and must be learned from data, raising the question: can one still obtain strong performance guarantees while simultaneously learning the diffusion model parameters through repeated interactions? In this paper, we study the problem of online influence maximization under the independent cascade model, where influence probabilities are unknown and feedback is limited to node-level activation outcomes. Prior work relies on a pair oracle which needs to perform a joint optimization over seed sets and feasible parameters. This oracle is difficult to implement in practice and it was open whether one can achieve sublinear regret using only a standard offline oracle. We resolve this question by designing an online learning algorithm that achieves $\widetilde{O}(\sqrt{T})$ regret using only a standard offline oracle. Finally, we validate our theoretical results via experiments on real and synthetic data.} }
Endnote
%0 Conference Paper %T Efficient Online Influence Maximization under the Independent Cascade Model with Node-Level Feedback %A Arpit Agarwal %A Varad Deolankar %A Rohan Ghuge %B Proceedings of the 43rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2026 %E Tong Zhang %E Miroslav Dudik %E Martin Jaggi %E Alekh Agarwal %E Sharon Li %E Dale Schuurmans %E Jerry Zhu %E Felix Berkenkamp %E Hanze Dong %E Alberto Bietti %F pmlr-v306-agarwal26a %I PMLR %P 769--793 %U https://proceedings.mlr.press/v306/agarwal26a.html %V 306 %X Influence maximization is an important research area in social network analysis, where the goal is to select a small set of seed nodes so as to maximize the expected spread of influence under a stochastic diffusion process. Classical approximation algorithms for this problem rely on full knowledge of the underlying influence probabilities and operate in an offline manner. In many real-world settings, however, these probabilities are unknown and must be learned from data, raising the question: can one still obtain strong performance guarantees while simultaneously learning the diffusion model parameters through repeated interactions? In this paper, we study the problem of online influence maximization under the independent cascade model, where influence probabilities are unknown and feedback is limited to node-level activation outcomes. Prior work relies on a pair oracle which needs to perform a joint optimization over seed sets and feasible parameters. This oracle is difficult to implement in practice and it was open whether one can achieve sublinear regret using only a standard offline oracle. We resolve this question by designing an online learning algorithm that achieves $\widetilde{O}(\sqrt{T})$ regret using only a standard offline oracle. Finally, we validate our theoretical results via experiments on real and synthetic data.
APA
Agarwal, A., Deolankar, V. & Ghuge, R.. (2026). Efficient Online Influence Maximization under the Independent Cascade Model with Node-Level Feedback. Proceedings of the 43rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 306:769-793 Available from https://proceedings.mlr.press/v306/agarwal26a.html.

Related Material