Discriminative Learning of Infection Models

ABSTRACT

Infection and diffusion processes over networks arise in many domains. These introduce many challenging prediction tasks, such as influence estimation, trend prediction, and epidemic source localization. The standard approach to such problems is generative: assume an underlying infection model, learn its parameters, and infer the required output. In order to learn efficiently, the chosen infection models are often simple, and learning is focused on inferring the parameters of the model rather than on optimizing prediction accuracy. Here we argue that for prediction tasks, a discriminative approach is more adequate. We introduce DIMPLE, a novel discriminative learning framework for training classifiers based on dynamic infection models. We show how highly non-linear predictors based on infection models can be "linearized" by considering a larger class of prediction functions. Efficient learning over this class is performed by constructing "infection kernels" based on the outputs of infection models, and can be plugged into any kernel-supporting framework. DIMPLE can be applied to virtually any infection-related prediction task and any infection model for which the desired output can be calculated or simulated. For influence estimation in well-known infection models, we show that the kernel can either be computed in closed form, or reduces to estimating co-influence of seed pairs. We apply DIMPLE to the tasks of influence estimation on synthetic and real data from Digg, and to predicting customer network value in Polly, a viral phone-based development-related service deployed in low-literate communities. Our results show that DIMPLE outperforms strong baselines.

References

1. E. Bakshy, J. M. Hofman, W. A. Mason, and D. J. Watts. Everyone's an influencer: quantifying influence on twitter. In Proc. of the 4th int. conf. on Web search and data mining, pages 65--74. ACM, 2011.
2. E. Bakshy, B. Karrer, and L. A. Adamic. Social influence and the diffusion of user-created content. In Proc. of the 10th ACM conference on Electronic commerce, pages 325--334. ACM, 2009.
3. J. O. Berger. Statistical decision theory and Bayesian analysis. Springer, 1985.
4. D. Chakrabarti, Y. Zhan, and C. Faloutsos. R-mat: A recursive model for graph mining. In SDM, volume 4, pages 442--446. SIAM, 2004.
5. C.-C. Chang and C.-J. Lin. LIBSVM: A library for support vector machines. ACM Transactions on Intelligent Systems and Technology, 2:27:1--27:27, 2011.
6. W. Chen, C. Wang, and Y. Wang. Scalable influence maximization for prevalent viral marketing in large-scale social networks. In Proc. of the 16th int. conf. on Knowledge discovery and data mining, pages 1029--1038, 2010.
7. J. Cheng, L. Adamic, P. A. Dow, J. M. Kleinberg, and J. Leskovec. Can cascades be predicted? In Proc. of the 23rd int. conf. on World wide web, pages 925--936, 2014.
8. E. Cohen, D. Delling, T. Pajor, and R. F. Werneck. Sketch-based influence maximization and computation: Scaling up with guarantees. In Proc. of the 23rd int. conf. on Conference on Information and Knowledge Management, pages 629--638, 2014.
9. P. Domingos and M. Richardson. Mining the network value of customers. In Proc. of the 7th int. conf. on Knowledge discovery and data mining, pages 57--66. ACM, 2001.
10. N. Du, Y. Liang, E. M.-F. Balcan, and G. EDU. Influence function learning in information diffusion networks. In Proc. of The 31st int. conf. on Machine Learning, pages 2016--2024, 2014.
11. V. M. Eguiluz and K. Klemm. Epidemic threshold in structured scale-free networks. Phys. Rev. Letters, 89(10):108701, 2002.
12. G. Giakkoupis, A. Gionis, E. Terzi, and P. Tsaparas. Models and algorithms for network immunization. Technical report, University of Helsinki, 2005.
13. J. Goldenberg, B. Libai, and E. Muller. Talk of the network: A complex systems look at the underlying process of word-of-mouth. Marketing letters, 12(3):211--223, 2001.
14. M. Gomez Rodriguez, J. Leskovec, and A. Krause. Inferring networks of diffusion and influence. In Proc. of the 16th int. conf. on Knowledge discovery and data mining, pages 1019--1028. ACM, 2010.
15. A. Goyal, F. Bonchi, and L. V. Lakshmanan. Learning influence probabilities in social networks. In Proc. of the third ACM int. conf. on Web search and data mining, pages 241--250. ACM, 2010.
16. M. Granovetter. Threshold models of collective behavior. American journal of sociology, pages 1420--1443, 1978.
17. J. E. Hogan, K. N. Lemon, and B. Libai. Quantifying the ripple: Word-of-mouth and advertising effectiveness. Journal of Advertising Research, 44(03):271--280, 2004.
18. T. Jaakkola and D. Haussler. Exploiting generative models in discriminative classifiers. In Advances in Neural Inf. Processing Systems, pages 487--493, 1998.
19. D. Kempe, J. Kleinberg, and É. Tardos. Maximizing the spread of influence through a social network. In Proc. of the 9th int. conf. on Knowledge discovery and data mining, pages 137--146. ACM, 2003.
20. G. S. Kimeldorf and G. Wahba. A correspondence between bayesian estimation on stochastic processes and smoothing by splines. The Annals of Math. Stat., pages 495--502, 1970.
21. K. Lerman and R. Ghosh. Information contagion: An empirical study of the spread of news on digg and twitter social networks. ICWSM, 10:90--97, 2010.
22. J. Leskovec, L. Backstrom, R. Kumar, and A. Tomkins. Microscopic evolution of social networks. In Proc. of the 14th int. conf. on Knowledge discovery and data mining, pages 462--470. ACM, 2008.
23. J. Leskovec, A. Krause, C. Guestrin, C. Faloutsos, J. VanBriesen, and N. Glance. Cost-effective outbreak detection in networks. In Proc. of the 13th int. conf. on Knowledge discovery and data mining, pages 420--429. ACM, 2007.
24. W. J. Morokoff and R. E. Caflisch. Quasi-monte carlo integration. Journal of computational physics, 122(2):218--230, 1995.
25. S. Myers and J. Leskovec. On the convexity of latent social network inference. In Advances in Neural Inf. Processing Systems, pages 1741--1749, 2010.
26. P. Netrapalli and S. Sanghavi. Learning the graph of epidemic cascades. In ACM SIGMETRICS Performance Evaluation Review, volume 40, pages 211--222. ACM, 2012.
27. M. E. Newman, G. T. Barkema, and M. Newman. Monte Carlo methods in statistical physics, volume 13. Clarendon Press Oxford, 1999.
28. P. Ney and A. Joffe. Branching processes. Springer, 1978.
29. A. Y. Ng and M. I. Jordan. On discriminative vs. generative classifiers: A comparison of logistic regression and naive bayes. Advances in neural inf. processing systems, 2:841--848, 2002.
30. R. Pastor-Satorras and A. Vespignani. Epidemic spreading in scale-free networks. Phys. rev. letters, 86(14):3200, 2001.
31. W. H. Press and G. R. Farrar. Recursive stratified sampling for multidimensional monte carlo integration. Computers in Physics, 4(2):190--195, 1990.
32. A. Rahimi and B. Recht. Weighted sums of random kitchen sinks: Replacing minimization with randomization in learning. In Advances in neural inf. processing systems, pages 1313--1320, 2009.
33. A. A. Raza, M. Pervaiz, C. Milo, S. Razaq, G. Alster, J. Sherwani, U. Saif, and R. Rosenfeld. Viral entertainment as a vehicle for disseminating speech-based services to low-literate users. In Proc. of the Fifth int. conf. on Information and Communication Technologies and Development, pages 350--359. ACM, 2012.
34. A. A. Raza, F. Ul Haq, Z. Tariq, M. Pervaiz, S. Razaq, U. Saif, and R. Rosenfeld. Job opportunities through entertainment: Virally spread speech-based services for low-literate users. In Proc. of the SIGCHI Conference on Human Factors in Computing Systems, pages 2803--2812. ACM, 2013.
35. M. G. Rodriguez, D. Balduzzi, and B. Schölkopf. Uncovering the temporal dynamics of diffusion networks. arXiv preprint arXiv:1105.0697, 2011.
36. K. Saito, R. Nakano, and M. Kimura. Prediction of information diffusion probabilities for independent cascade model. In Knowledge-Based Intelligent Information and Engineering Systems, pages 67--75. Springer, 2008.
37. K. Saito, K. Ohara, Y. Yamagishi, M. Kimura, and H. Motoda. Learning diffusion probability based on node attributes in social networks. In Foundations of Intelligent Systems, pages 153--162. Springer, 2011.
38. B. Schölkopf, R. Herbrich, and A. J. Smola. A generalized representer theorem. In Computational learning theory, pages 416--426. Springer, 2001.
39. D. Shah and T. Zaman. Rumors in a network: Who's the culprit? Information Theory, IEEE Transactions on, 57(8):5163--5181, 2011.
40. J. Shawe-Taylor, P. L. Bartlett, R. C. Williamson, and M. Anthony. Structural risk minimization over data-dependent hierarchies. Information Theory, IEEE Transactions on, 44(5):1926--1940, 1998.
41. O. Tsur and A. Rappoport. What's in a hashtag? content based prediction of the spread of ideas in microblogging communities. In Proc. of the 5th int. conf. on web search and data mining, pages 643--652, 2012.
42. V. Vapnik. The nature of statistical learning theory. Springer, 2000.
43. J. Yang and J. Leskovec. Modeling information diffusion in implicit networks. In 10th int. conf. on Data Mining, pages 599--608. IEEE, 2010.

Index Terms

• Computing methodologies

  • Machine learning

    • Learning paradigms

    • Machine learning approaches

      • Markov decision processes

• Theory of computation

  • Theory and algorithms for application domains

    • Machine learning theory

      • Markov decision processes