Online Learning of Independent Cascade Models with Node-level Feedback
This work addresses a gap in modeling social network influence propagation for applications where only aggregated node-level data is available, representing an incremental advance over existing edge-level feedback methods.
The paper tackles the problem of online learning for Independent Cascade models with node-level feedback, where edge outcomes are censored, and achieves a cumulative regret of O(√T), matching the theoretical bound for edge-level feedback models.
We propose a detailed analysis of the online-learning problem for Independent Cascade (IC) models under node-level feedback. These models have widespread applications in modern social networks. Existing works for IC models have only shed light on edge-level feedback models, where the agent knows the explicit outcome of every observed edge. Little is known about node-level feedback models, where only combined outcomes for sets of edges are observed; in other words, the realization of each edge is censored. This censored information, together with the nonlinear form of the aggregated influence probability, make both parameter estimation and algorithm design challenging. We establish the first confidence-region result under this setting. We also develop an online algorithm achieving a cumulative regret of $\mathcal{O}( \sqrt{T})$, matching the theoretical regret bound for IC models with edge-level feedback.