Robust Influence Maximization for Hyperparametric Models

Dimitris Kalimeris, Gal Kaplun, Yaron Singer
Proceedings of the 36th International Conference on Machine Learning, PMLR 97:3192-3200, 2019.

Abstract

In this paper we study the problem of robust influence maximization in the independent cascade model under a hyperparametric assumption. In social networks users influence and are influenced by individuals with similar characteristics and as such they are associated with some features. A recent surging research direction in influence maximization focuses on the case where the edge probabilities on the graph are not arbitrary but are generated as a function of the features of the users and a global hyperparameter. We propose a model where the objective is to maximize the worst-case number of influenced users for any possible value of that hyperparameter. We provide theoretical results showing that proper robust solution in our model is NP-hard and an algorithm that achieves improper robust optimization. We make-use of sampling based techniques and of the renowned multiplicative weight updates algorithm. Additionally we validate our method empirically and prove that it outperforms the state-of-the-art robust influence maximization techniques.

Cite this Paper

BibTeX
@InProceedings{pmlr-v97-kalimeris19a, title = {Robust Influence Maximization for Hyperparametric Models}, author = {Kalimeris, Dimitris and Kaplun, Gal and Singer, Yaron}, booktitle = {Proceedings of the 36th International Conference on Machine Learning}, pages = {3192--3200}, year = {2019}, editor = {Chaudhuri, Kamalika and Salakhutdinov, Ruslan}, volume = {97}, series = {Proceedings of Machine Learning Research}, month = {09--15 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v97/kalimeris19a/kalimeris19a.pdf}, url = {https://proceedings.mlr.press/v97/kalimeris19a.html}, abstract = {In this paper we study the problem of robust influence maximization in the independent cascade model under a hyperparametric assumption. In social networks users influence and are influenced by individuals with similar characteristics and as such they are associated with some features. A recent surging research direction in influence maximization focuses on the case where the edge probabilities on the graph are not arbitrary but are generated as a function of the features of the users and a global hyperparameter. We propose a model where the objective is to maximize the worst-case number of influenced users for any possible value of that hyperparameter. We provide theoretical results showing that proper robust solution in our model is NP-hard and an algorithm that achieves improper robust optimization. We make-use of sampling based techniques and of the renowned multiplicative weight updates algorithm. Additionally we validate our method empirically and prove that it outperforms the state-of-the-art robust influence maximization techniques.} }
Endnote
%0 Conference Paper %T Robust Influence Maximization for Hyperparametric Models %A Dimitris Kalimeris %A Gal Kaplun %A Yaron Singer %B Proceedings of the 36th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2019 %E Kamalika Chaudhuri %E Ruslan Salakhutdinov %F pmlr-v97-kalimeris19a %I PMLR %P 3192--3200 %U https://proceedings.mlr.press/v97/kalimeris19a.html %V 97 %X In this paper we study the problem of robust influence maximization in the independent cascade model under a hyperparametric assumption. In social networks users influence and are influenced by individuals with similar characteristics and as such they are associated with some features. A recent surging research direction in influence maximization focuses on the case where the edge probabilities on the graph are not arbitrary but are generated as a function of the features of the users and a global hyperparameter. We propose a model where the objective is to maximize the worst-case number of influenced users for any possible value of that hyperparameter. We provide theoretical results showing that proper robust solution in our model is NP-hard and an algorithm that achieves improper robust optimization. We make-use of sampling based techniques and of the renowned multiplicative weight updates algorithm. Additionally we validate our method empirically and prove that it outperforms the state-of-the-art robust influence maximization techniques.
APA
Kalimeris, D., Kaplun, G. & Singer, Y.. (2019). Robust Influence Maximization for Hyperparametric Models. Proceedings of the 36th International Conference on Machine Learning, in Proceedings of Machine Learning Research 97:3192-3200 Available from https://proceedings.mlr.press/v97/kalimeris19a.html.

Related Material