Fast Estimation of Causal Interactions using Wold Processes
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 GRANGER-BUSCA, 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, GRANGER-BUSCA is three times more accurate (in Precision@10) than the state of the art for the commonly explored subsets Memetracker. Due to GRANGER-BUSCA's much lower training complexity, our approach is the only one able to train models for larger, full, sets of data.
Summary: This work studies the Granger causality in a special type of point processes called Wold processes.  This type of processes is defined in terms of a Markovian transition on the inter-event times.  The Markovian transition between increments is established by the transition density functions. The intensity of the point processes considered in this work consists of two components. The first one is constant value that represents the exogenous events in the process and the other one is a summation of rational terms that capture the influences of the other processes including self-excitements. Learning the Granger causality in such processes boils down to learning the parameters of the second component. This work proposes an MCMC-based Algorithm for learning these parameters called Granger-Busca.  The complexity of the proposed algorithm is O(N(log N + log K)), where N being the total number of events and K the number of processes. They also validate their algorithm’s performance via several experiments.   Pros:  Studying the Granger causality in Wold point processes is novel and can be interesting to several disciplines.  The proposed algorithm is faster that the state of the art (for Multivariate Hawkes processes).   Cons:  The proposed method is designed for a special sub-class of Wold processes with particular form of the intensity function, Equation (3). Unlike the proposed methods for Hawkes processes, the proposed method in this work cannot be extended to processes more general forms of the transition functions. The comparison between the complexity of the proposed method and the previous algorithms for Hawkes is not a fair comparison, since there are dealing with different classes of point processes with different complexity. For instance, as also mentioned in the paper, Hawkes processes do not have finite memory.  The MemeTracker dataset was previously modeled via Hawkes processes and in this work using Busca processes. What is the justification for this modeling? What is their model validation criterion? It seems the authors merely refer the work of Bacry  and Song groups. Some very relevant references are missing. For instance: Learning network of multivariate hawkes processes: A time series approach Etesami et al UAI 2016.  Online learning for multivariate Hawkes processes Yang et al NIPS 2017.  Hawkes Process Modeling of Adverse Drug Reactions with Longitudinal Observational Data Bao et al. Machine Learning and Healthcare 2017.  The multivariate hawkes process in high dimensions: Beyond mutual excitation Chen et al.  ArXiv   Overall, this interesting work can be strengthened by generalizing the proposed algorithm to a broader class of transition functions. I rate this work as “marginally above acceptance” because their algorithm reduces the complexity extensively compared to the state of the art. However, as I mentioned the state of the art algorithms are considering Hawkes processes that have infinite memory.