Fast Estimation of Causal Interactions using Wold Processes

Abstract

We here focus on the task of learning Granger causality matrices for multivariate point processes. In order to accomplish this task, our work is the first to explore the use of Wold processes. By doing so, we are able to develop asymptotically fast MCMC learning algorithms. With $N$ being the total number of events and $K$ the number of processes, our learning algorithm has a $O(N(\log (N)+\log (K)))$ cost per iteration. This is much faster than the $O(N^3{K}^2)$ or $O(K^3)$ for the state of the art. Our approach, called GrangerBusca, is validated on nine datasets. This is an advance in relation to most prior efforts which focus mostly on subsets of the Memetracker data. Regarding accuracy, GrangerBusca is three times more accurate (in Precision@10) than the state of the art for the commonly explored subsets Memetracker. Due to GrangerBusca's much lower training complexity, our approach is the only one able to train models for larger, full, sets of data.

arXiv comment32nd Conference on Neural Information Processing Systems (NeurIPS 2018), Montréal, Canada

References in corpus (8)

• Estimating Granger causality from Fourier and wavelet transforms of time series data
• Learning Granger Causality for Hawkes Processes
• Governance in Social Media: A case study of the Wikipedia promotion process
• Learning Network of Multivariate Hawkes Processes: A Time Series Approach
• The Multivariate Hawkes Process in High Dimensions: Beyond Mutual Excitation
• Scalable Bayesian Inference for Excitatory Point Process Networks
• Network Inference via the Time-Varying Graphical Lasso
• Techniques for proving Asynchronous Convergence results for Markov Chain Monte Carlo methods