Learning Diffusion using Hyperparameters

Dimitris Kalimeris, Yaron Singer, Karthik Subbian, Udi Weinsberg
Proceedings of the 35th International Conference on Machine Learning, PMLR 80:2420-2428, 2018.

Abstract

In this paper we advocate for a hyperparametric approach to learn diffusion in the independent cascade (IC) model. The sample complexity of this model is a function of the number of edges in the network and consequently learning becomes infeasible when the network is large. We study a natural restriction of the hypothesis class using additional information available in order to dramatically reduce the sample complexity of the learning process. In particular we assume that diffusion probabilities can be described as a function of a global hyperparameter and features of the individuals in the network. One of the main challenges with this approach is that training a model reduces to optimizing a non-convex objective. Despite this obstacle, we can shrink the best-known sample complexity bound for learning IC by a factor of |E|/d where |E| is the number of edges in the graph and d is the dimension of the hyperparameter. We show that under mild assumptions about the distribution generating the samples one can provably train a model with low generalization error. Finally, we use large-scale diffusion data from Facebook to show that a hyperparametric model using approximately 20 features per node achieves remarkably high accuracy.

Cite this Paper

BibTeX
@InProceedings{pmlr-v80-kalimeris18a, title = {Learning Diffusion using Hyperparameters}, author = {Kalimeris, Dimitris and Singer, Yaron and Subbian, Karthik and Weinsberg, Udi}, booktitle = {Proceedings of the 35th International Conference on Machine Learning}, pages = {2420--2428}, year = {2018}, editor = {Dy, Jennifer and Krause, Andreas}, volume = {80}, series = {Proceedings of Machine Learning Research}, month = {10--15 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v80/kalimeris18a/kalimeris18a.pdf}, url = {https://proceedings.mlr.press/v80/kalimeris18a.html}, abstract = {In this paper we advocate for a hyperparametric approach to learn diffusion in the independent cascade (IC) model. The sample complexity of this model is a function of the number of edges in the network and consequently learning becomes infeasible when the network is large. We study a natural restriction of the hypothesis class using additional information available in order to dramatically reduce the sample complexity of the learning process. In particular we assume that diffusion probabilities can be described as a function of a global hyperparameter and features of the individuals in the network. One of the main challenges with this approach is that training a model reduces to optimizing a non-convex objective. Despite this obstacle, we can shrink the best-known sample complexity bound for learning IC by a factor of |E|/d where |E| is the number of edges in the graph and d is the dimension of the hyperparameter. We show that under mild assumptions about the distribution generating the samples one can provably train a model with low generalization error. Finally, we use large-scale diffusion data from Facebook to show that a hyperparametric model using approximately 20 features per node achieves remarkably high accuracy.} }
Endnote
%0 Conference Paper %T Learning Diffusion using Hyperparameters %A Dimitris Kalimeris %A Yaron Singer %A Karthik Subbian %A Udi Weinsberg %B Proceedings of the 35th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2018 %E Jennifer Dy %E Andreas Krause %F pmlr-v80-kalimeris18a %I PMLR %P 2420--2428 %U https://proceedings.mlr.press/v80/kalimeris18a.html %V 80 %X In this paper we advocate for a hyperparametric approach to learn diffusion in the independent cascade (IC) model. The sample complexity of this model is a function of the number of edges in the network and consequently learning becomes infeasible when the network is large. We study a natural restriction of the hypothesis class using additional information available in order to dramatically reduce the sample complexity of the learning process. In particular we assume that diffusion probabilities can be described as a function of a global hyperparameter and features of the individuals in the network. One of the main challenges with this approach is that training a model reduces to optimizing a non-convex objective. Despite this obstacle, we can shrink the best-known sample complexity bound for learning IC by a factor of |E|/d where |E| is the number of edges in the graph and d is the dimension of the hyperparameter. We show that under mild assumptions about the distribution generating the samples one can provably train a model with low generalization error. Finally, we use large-scale diffusion data from Facebook to show that a hyperparametric model using approximately 20 features per node achieves remarkably high accuracy.
APA
Kalimeris, D., Singer, Y., Subbian, K. & Weinsberg, U.. (2018). Learning Diffusion using Hyperparameters. Proceedings of the 35th International Conference on Machine Learning, in Proceedings of Machine Learning Research 80:2420-2428 Available from https://proceedings.mlr.press/v80/kalimeris18a.html.

Related Material