Timezone: »

Model-Independent Online Learning for Influence Maximization
Sharan Vaswani · Branislav Kveton · Zheng Wen · Mohammad Ghavamzadeh · Laks V.S Lakshmanan · Mark Schmidt

Sun Aug 06 06:06 PM -- 06:24 PM (PDT) @ C4.1

We consider \emph{influence maximization} (IM) in social networks, which is the problem of maximizing the number of users that become aware of a product by selecting a set of ``seed'' users to expose the product to. While prior work assumes a known model of information diffusion, we propose a novel parametrization that not only makes our framework agnostic to the underlying diffusion model, but also statistically efficient to learn from data. We give a corresponding monotone, submodular surrogate function, and show that it is a good approximation to the original IM objective. We also consider the case of a new marketer looking to exploit an existing social network, while simultaneously learning the factors governing information propagation. For this, we propose a pairwise-influence semi-bandit feedback model and develop a LinUCB-based bandit algorithm. Our model-independent analysis shows that our regret bound has a better (as compared to previous work) dependence on the size of the network. Experimental evaluation suggests that our framework is robust to the underlying diffusion model and can efficiently learn a near-optimal solution.

Author Information

Sharan Vaswani (University of British Columbia)
Branislav Kveton (Adobe Research)
Zheng Wen (Adobe Research)
Mohammad Ghavamzadeh (Adobe Research & INRIA)
Laks V.S Lakshmanan (University of British Columbia)
Mark Schmidt (University of British Columbia)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors