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

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: \emph{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 \emph{online influence maximization} under the independent cascade model, where influence probabilities are unknown and feedback is limited to \emph{node-level} activation outcomes. Prior work relies on a \emph{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 \emph{standard} offline oracle. We resolve this question by designing an online learning algorithm that achieves $\widetilde{O}(\sqrt{T})$ regret using only a \emph{standard} offline oracle. Finally, we validate our theoretical results via experiments on real and synthetic data.

Imagine you want to spread a message through a social network: a new product, a public-health campaign, an idea. You can only nudge a small handful of people directly, and you're hoping the message catches on and ripples outward through their friends, and their friends' friends. Which handful should you pick? This is the classic $\textit{influence maximization}$ problem, and it has a clean answer when you already know how likely each person is to convince each of their contacts. But in practice, you almost never know those numbers. You have to learn them by trying campaigns and watching what happens. And you only get to see $\textit{who}$ ended up convinced, not $\textit{which}$ of their friends did the convincing. That makes learning genuinely hard, since many different explanations of "who influences whom" can fit the same observed outcomes. We give the first algorithm that solves this problem efficiently while still coming with a mathematical guarantee that it learns nearly as well as if it had known the answers all along. The trick is to give up on identifying each individual friendship's influence strength and instead learn slightly coarser quantities that $\textit{are}$ recoverable from what we can observe, and to do this using only standard, off-the-shelf tools rather than the specialized machinery prior work required. Experiments on real social networks and stress-test synthetic ones confirm that the algorithm works well in practice, not just in theory.