research-article

Modeling Sparse Information Diffusion at Scale via Lazy Multivariate Hawkes Processes

Authors:

Maximilian Nickel,

Matthew LeAuthors Info & Claims

WWW '21: Proceedings of the Web Conference 2021

Pages 706 - 717

https://doi.org/10.1145/3442381.3450094

Published: 03 June 2021 Publication History

Abstract

Multivariate Hawkes Processes (MHPs) are an important class of temporal point processes that have enabled key advances in understanding and predicting social information systems. However, due to their complex modeling of temporal dependencies, MHPs have proven to be notoriously difficult to scale, what has limited their applications to relatively small domains. In this work, we propose a novel model and computational approach to overcome this important limitation. By exploiting a characteristic sparsity pattern in real-world diffusion processes, we show that our approach allows to compute the exact likelihood and gradients of an MHP – independently of the ambient dimensions of the underlying network. We show on synthetic and real-world datasets that our method does not only achieve state-of-the-art modeling results, but also improves runtime performance by multiple orders of magnitude on sparse event sequences. In combination with easily interpretable latent variables and influence structures, this allows us to analyze diffusion processes in networks at previously unattainable scale.

References

[1]

Massil Achab, Emmanuel Bacry, Stéphane Gaïffas, Iacopo Mastromatteo, and Jean-François Muzy. 2017. Uncovering causality from multivariate Hawkes integrated cumulants. The Journal of Machine Learning Research 18, 1 (2017), 6998–7025.

Digital Library

[2]

Ahmed M Alaa, Scott Hu, and Mihaela van der Schaar. 2017. Learning from clinical judgments: Semi-Markov-modulated marked Hawkes processes for risk prognosis. In Proceedings of the 34th International Conference on Machine Learning-Volume 70. JMLR. org, 60–69.

[3]

E. Bacry, M. Bompaire, S. Gaïffas, and S. Poulsen. 2017. tick: a Python library for statistical learning, with a particular emphasis on time-dependent modeling. ArXiv e-prints (July 2017).

[4]

Emmanuel Bacry, Iacopo Mastromatteo, and Jean-François Muzy. 2015. Hawkes processes in finance. Market Microstructure and Liquidity 1, 01 (2015), 1550005.

[5]

Frederick Boehmke, Mark Brockway, Bruce Desmarais, Jeffrey J. Harden, Scott LaCombe, Fridolin Linder, and Hanna Wallach. 2019. State Diffusion Networks - Latent Network Ties from SPID v1.0. https://doi.org/10.7910/DVN/1QJCDJ

[6]

Frederick J Boehmke, Mark Brockway, Bruce A Desmarais, Jeffrey J Harden, Scott LaCombe, Fridolin Linder, and Hanna Wallach. 2018. A New Database for Inferring Public Policy Innovativeness and Diffusion Networks. Available at SSRN 3199383(2018).

[7]

Béla Bollobás, Christian Borgs, Jennifer Chayes, and Oliver Riordan. 2003. Directed scale-free graphs. In Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms. Society for Industrial and Applied Mathematics, 132–139.

Digital Library

[8]

Richard H Byrd, Peihuang Lu, Jorge Nocedal, and Ciyou Zhu. 1995. A limited memory algorithm for bound constrained optimization. SIAM Journal on scientific computing 16, 5 (1995), 1190–1208.

[9]

Ricky TQ Chen, Brandon Amos, and Maximilian Nickel. 2020. Neural Spatio-Temporal Point Processes. arXiv preprint arXiv:2011.04583(2020).

[10]

Tian Qi Chen, Yulia Rubanova, Jesse Bettencourt, and David K Duvenaud. 2018. Neural ordinary differential equations. In Advances in neural information processing systems. 6571–6583.

[11]

Nan Du, Hanjun Dai, Rakshit Trivedi, Utkarsh Upadhyay, Manuel Gomez-Rodriguez, and Le Song. 2016. Recurrent marked temporal point processes: Embedding event history to vector. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 1555–1564.

Digital Library

[12]

Nan Du, Le Song, Manuel Gomez-Rodriguez, and Hongyuan Zha. 2013. Scalable Influence Estimation in Continuous-Time Diffusion Networks. In Advances in Neural Information Processing Systems 26: 27th Annual Conference on Neural Information Processing Systems 2013. Proceedings of a meeting held December 5-8, 2013, Lake Tahoe, Nevada, United States. 3147–3155.

[13]

Mehrdad Farajtabar, Yichen Wang, Manuel Gomez-Rodriguez, Shuang Li, Hongyuan Zha, and Le Song. 2017. Coevolve: A joint point process model for information diffusion and network evolution. The Journal of Machine Learning Research 18, 1 (2017), 1305–1353.

Digital Library

[14]

Mehrdad Farajtabar, Jiachen Yang, Xiaojing Ye, Huan Xu, Rakshit Trivedi, Elias B. Khalil, Shuang Li, Le Song, and Hongyuan Zha. 2017. Fake News Mitigation via Point Process Based Intervention. In Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6-11 August 2017. 1097–1106.

[15]

Manuel Gomez-Rodriguez, David Balduzzi, and Bernhard Schölkopf. 2011. Uncovering the Temporal Dynamics of Diffusion Networks. In Proceedings of the 28th International Conference on Machine Learning, ICML 2011, Bellevue, Washington, USA, June 28 - July 2, 2011. 561–568.

[16]

Manuel Gomez Rodriguez, Jure Leskovec, and Bernhard Schölkopf. 2013. Structure and dynamics of information pathways in online media. Proceedings of the sixth ACM international conference on Web search and data mining - WSDM ’13(2013). https://doi.org/10.1145/2433396.2433402

Digital Library

[17]

Alan G. Hawkes. 1971. Spectra of some self-exciting and mutually exciting point processes. Biometrika 58, 1 (1971), 83–90. https://doi.org/10.1093/biomet/58.1.83

[18]

Xinran He, Theodoros Rekatsinas, James Foulds, Lise Getoor, and Yan Liu. 2015. Hawkestopic: A joint model for network inference and topic modeling from text-based cascades. In International conference on machine learning. 871–880.

[19]

Gary R Holt, William R Softky, Christof Koch, and Rodney J Douglas. 1996. Comparison of discharge variability in vitro and in vivo in cat visual cortex neurons. Journal of neurophysiology 75, 5 (1996), 1806–1814.

[20]

Tomoharu Iwata, Amar Shah, and Zoubin Ghahramani. 2013. Discovering latent influence in online social activities via shared cascade poisson processes. In Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining. 266–274.

Digital Library

[21]

Martin Jankowiak and Manuel Gomez-Rodriguez. 2017. Uncovering the spatiotemporal patterns of collective social activity. In Proceedings of the 2017 SIAM International Conference on Data Mining. SIAM, 822–830.

[22]

Junteng Jia and Austin R. Benson. 2019. Neural Jump Stochastic Differential Equations. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, 8-14 December 2019, Vancouver, BC, Canada. 9843–9854.

[23]

How Jing and Alexander J. Smola. 2017. Neural Survival Recommender. In Proceedings of the Tenth ACM International Conference on Web Search and Data Mining(WSDM ’17). Association for Computing Machinery, New York, NY, USA, 515–524. https://doi.org/10.1145/3018661.3018719

Digital Library

[24]

Diederik P. Kingma and Jimmy Ba. 2015. Adam: A Method for Stochastic Optimization. In 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings.

[25]

Srijan Kumar, William L Hamilton, Jure Leskovec, and Dan Jurafsky. 2018. Community interaction and conflict on the web. In Proceedings of the 2018 World Wide Web Conference on World Wide Web. International World Wide Web Conferences Steering Committee, 933–943. https://snap.stanford.edu/data/soc-RedditHyperlinks.html

Digital Library

[26]

Srijan Kumar, Xikun Zhang, and Jure Leskovec. 2019. Predicting Dynamic Embedding Trajectory in Temporal Interaction Networks. In Proceedings of the 25th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM.

Digital Library

[27]

Rémi Lemonnier, Kevin Scaman, and Argyris Kalogeratos. 2017. Multivariate Hawkes Processes for Large-Scale Inference. In Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, February 4-9, 2017, San Francisco, California, USA. 2168–2174.

Digital Library

[28]

Jure Leskovec, Lars Backstrom, and Jon Kleinberg. 2009. Meme-tracking and the dynamics of the news cycle. In Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining. 497–506. https://snap.stanford.edu/data/memetracker9.html

Digital Library

[29]

Charalampos Mavroforakis, Isabel Valera, and Manuel Gomez-Rodriguez. 2017. Modeling the dynamics of learning activity on the web. In Proceedings of the 26th International Conference on World Wide Web. 1421–1430.

Digital Library

[30]

Hongyuan Mei and Jason Eisner. 2017. The Neural Hawkes Process: A Neurally Self-Modulating Multivariate Point Process. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, 4-9 December 2017, Long Beach, CA, USA. 6754–6764.

[31]

Nvidia. [n.d.]. NVidia V100 Tensor Core GPU. https://www.nvidia.com/en-us/data-center/v100/. Accessed: 2020-02-10.

[32]

Yosihiko Ogata. 1981. On Lewis’ simulation method for point processes. IEEE transactions on information theory 27, 1 (1981), 23–31.

[33]

Yosihiko Ogata. 1998. Space-time point-process models for earthquake occurrences. Annals of the Institute of Statistical Mathematics 50, 2(1998), 379–402.

[34]

T. Ozaki. 1979. Maximum likelihood estimation of Hawkes’ self-exciting point processes. Annals of the Institute of Statistical Mathematics 31, 1 (Dec 1979), 145–155. https://doi.org/10.1007/bf02480272

[35]

Benjamin Recht, Christopher Ré, Stephen J. Wright, and Feng Niu. 2011. Hogwild: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent. In Advances in Neural Information Processing Systems 24. 693–701.

[36]

Marian-Andrei Rizoiu, Swapnil Mishra, Quyu Kong, Mark Carman, and Lexing Xie. 2018. SIR-Hawkes: linking epidemic models and Hawkes processes to model diffusions in finite populations. In Proceedings of the 2018 World Wide Web Conference. 419–428.

Digital Library

[37]

Yulia Rubanova, Ricky T. Q. Chen, and David K Duvenaud. 2019. Latent Ordinary Differential Equations for Irregularly-Sampled Time Series. In Advances in Neural Information Processing Systems, Vol. 32.

[38]

Oleksandr Shchur, Marin Bilos, and Stephan Günnemann. 2019. Intensity-Free Learning of Temporal Point Processes. In International Conference on Learning Representations.

[39]

Shigeru Shinomoto, Keisetsu Shima, and Jun Tanji. 2003. Differences in spiking patterns among cortical neurons. Neural computation 15, 12 (2003), 2823–2842.

[40]

Ali Caner Türkmen, Gökhan Çapan, and Ali Taylan Cemgil. 2020. Clustering Event Streams With Low Rank Hawkes Processes. IEEE Signal Processing Letters 27 (2020), 1575–1579.

[41]

Shuai Xiao, Mehrdad Farajtabar, Xiaojing Ye, Junchi Yan, Xiaokang Yang, Le Song, and Hongyuan Zha. 2017. Wasserstein Learning of Deep Generative Point Process Models. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, 4-9 December 2017, Long Beach, CA, USA. 3247–3257.

[42]

Hongteng Xu, Mehrdad Farajtabar, and Hongyuan Zha. 2016. Learning Granger Causality for Hawkes Processes. In Proceedings of the 33nd International Conference on Machine Learning, ICML 2016, New York City, NY, USA, June 19-24, 2016. 1717–1726.

[43]

Qingyuan Zhao, Murat A Erdogdu, Hera Y He, Anand Rajaraman, and Jure Leskovec. 2015. Seismic: A self-exciting point process model for predicting tweet popularity. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 1513–1522.

Digital Library

[44]

Ke Zhou, Hongyuan Zha, and Le Song. 2013. Learning social infectivity in sparse low-rank networks using multi-dimensional Hawkes processes. In Artificial Intelligence and Statistics. 641–649.

Cited By

Agarwal AUsunier NLazaric ANickel M(2024)System-2 Recommenders: Disentangling Utility and Engagement in Recommendation Systems via Temporal Point-ProcessesProceedings of the 2024 ACM Conference on Fairness, Accountability, and Transparency10.1145/3630106.3659004(1763-1773)Online publication date: 3-Jun-2024
https://dl.acm.org/doi/10.1145/3630106.3659004
Chen ZXu BCai TYang ZLiao X(2023)A Dynamic Emotional Propagation Model over Time for Competitive EnvironmentsElectronics10.3390/electronics1224493712:24(4937)Online publication date: 8-Dec-2023
https://doi.org/10.3390/electronics12244937
Qu ZLyu CChi C(2022)MUSH: Multi-Stimuli Hawkes Process Based Sybil Attacker Detector for User-Review Social NetworksIEEE Transactions on Network and Service Management10.1109/TNSM.2022.318651319:4(4600-4614)Online publication date: Dec-2022
https://doi.org/10.1109/TNSM.2022.3186513
Show More Cited By

Recommendations

Multivariate hawkes processes for large-scale inference
AAAI'17: Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence

In this paper, we present a framework for fitting multivariate Hawkes processes for large-scale problems, both in the number of events in the observed history n and the number of event types d (i.e. dimensions). The proposed Scalable Low-Rank Hawkes ...
Opinion-aware information diffusion model based on multivariate marked Hawkes process
Abstract
Currently, information diffusion on online platforms plays an important role in social governance. Opinions contained in information have a significant influence on information diffusion. However, both classic and extended diffusion models lack ...
Highlights
- Proposed a novel opinion-aware information diffusion model based on the multivariate marked Hawkes Process.
- Compared the model to other classic information diffusion models and verified the prediction performance.
- Tested the model ...
Sparse and low-rank multivariate Hawkes processes

We consider the problem of unveiling the implicit network structure of node interactions (such as user interactions in a social network), based only on high-frequency timestamps. Our inference is based on the minimization of the least-squares loss ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

WWW '21: Proceedings of the Web Conference 2021

April 2021

4054 pages

ISBN:9781450383127

DOI:10.1145/3442381

Editors:
Jure Leskovec
Stanford
,
Marko Grobelnik
Jožef Stefan Institute
,
Marc Najork
Google
,
Jie Tang
Tsinghua University
,
Leila Zia
Wikimedia Foundation

Copyright © 2021 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGWEB: ACM Special Interest Group on Hypertext, Hypermedia, and Web

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 03 June 2021

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article
Research
Refereed limited

Conference

WWW '21

Sponsor:

SIGWEB

WWW '21: The Web Conference 2021

April 19 - 23, 2021

Ljubljana, Slovenia

Acceptance Rates

Overall Acceptance Rate 1,899 of 8,196 submissions, 23%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
300
Total Downloads

Downloads (Last 12 months)37
Downloads (Last 6 weeks)1

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Agarwal AUsunier NLazaric ANickel M(2024)System-2 Recommenders: Disentangling Utility and Engagement in Recommendation Systems via Temporal Point-ProcessesProceedings of the 2024 ACM Conference on Fairness, Accountability, and Transparency10.1145/3630106.3659004(1763-1773)Online publication date: 3-Jun-2024
https://dl.acm.org/doi/10.1145/3630106.3659004
Chen ZXu BCai TYang ZLiao X(2023)A Dynamic Emotional Propagation Model over Time for Competitive EnvironmentsElectronics10.3390/electronics1224493712:24(4937)Online publication date: 8-Dec-2023
https://doi.org/10.3390/electronics12244937
Qu ZLyu CChi C(2022)MUSH: Multi-Stimuli Hawkes Process Based Sybil Attacker Detector for User-Review Social NetworksIEEE Transactions on Network and Service Management10.1109/TNSM.2022.318651319:4(4600-4614)Online publication date: Dec-2022
https://doi.org/10.1109/TNSM.2022.3186513
Liu YGao JZhao ZLi JYue Z(2022)Understanding information diffusion with psychological field dynamicInformation Processing and Management: an International Journal10.1016/j.ipm.2022.10295659:4Online publication date: 1-Jul-2022
https://dl.acm.org/doi/10.1016/j.ipm.2022.102956

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

HTML Format

View this article in HTML Format.

Media

Figures

Other

Tables

View Table of Contents