Spatio-Temporal Change Detection Using Granger Sequence Pattern

1 Introduction

Spatio-temporal data is very common in real world, for example, weather system and social network. This work aims to detect a causal relation change from an input of a multidimensional event sequence. Specifically, given a sequence of multi-dimensional events along with their time stamps, this paper aims to find the appearances and disappearances of causal relations in the input data. Spatio-temporal causal relations in the real world include relations between weather system, or relations between earthquake and aftershock, of which the changes in the relations might indicate something is happening. For example, in Fig. 1, at time t0, there is a causal relation from cluster A to B, and from B to C. However, at time t1, the relation B to C has gone, but there is now have new relation B to D. Then, at time t2, all the existing relations have gone, with the new relation A to C occurring instead. Current research in spatio-temporal change detection [Atluri et al., 2018] does not try to detect any changes in relations at all.

One of the accepted methods to detect causality is a Granger causality measure [Granger, 1969]. Granger causality is based on the idea that: if A causes B, then it must be easier to predict B using all available data than to predict B using all available data except A.

The Cluster Sequence Mining (CSM) algorithm [Fukui et al., 2019] can be used to detect occurrence correlations in a multi-dimensional event sequence, but it does not detect causation. To the best of our knowledge, no existing methods can extract causal relations from spatio-temporal data.

This paper proposed a novel method of detecting changes in causal relations. Specifically, the CSM algorithm was extended with the adaption of the Granger causality for point process model [Kim et al., 2011] to detect causal relation. This paper then introduced the Pattern Time Signature of each relation, which was a probabilistic distribution of each relation over time. The change points could be calculated using the aforementioned pattern time signature.

Changes in spatio-temporal relationships may further understanding of many natural phenomenons. Furthermore, as many scientific researches focused on detection a causal relation, the changes are also important.

2 Granger Cluster Sequence Mining (G-CSM)

Assuming an event sequence X = {x(i) ∈ Rn } (|X| = N) with associated timestamps t(x(i) ) where t(x(1) ) < t(x(2) ) < ... < t(x(N) ), Granger cluster sequence pattern pattern (g-pattern) is defined with prior event cluster A and posterior event cluster B as:

where A and B is an assignment vector for set A and B respectively. 〈t(x(i) )|Ai = 1〉 must also Granger-cause 〈t(x(i) )|Bi = 1〉.

To extract g-patterns from the input event sequence, this paper substantially modified the CSM algorithm [Fukui et al., 2019]. Specifically, the time proximity of the original CSM was replaced with Granger causality based measure. Pairwise point-process Granger causality was adapted from [Kim et al., 2011] to determine the Granger causality between the prior and posterior event cluster.

A log-cumulative incidence function (log-CIF) λb of event B is defined as follow:

where θb is the parameter vector, Mb is the history length to consider, and Rq,m(t) is the counting measure for events occurring between time [t - mW, t - (m - 1)W] with W specifying the windows length.

A log-likelihood point process was used fit the parametric CIF in eq. (2). The Granger causality strength is then given as:

where the likelihood Lb(θb) was obtained from model fitting eq. (2), and the likelihood Lb(θa b ) was obtained using new CIF with history of A cut. The Granger causality strength in eq. (3) was used to determined time proximity function F as in eq. (4). The final evaluation score, L, in eq. (5) is the same as in original CSM. τ is an adjusting parameter.

The candidates were ranked and eliminated in the same manner as in the original CSM.

3 Change Detection

A Pattern Time Signature for any g-pattern SA→B is a probabilistic density function P(SA→B; t), and is defined as:

where P(A; t) is the probability density of event A at time t, P(B; t + tAB|A; t) is the probability density of event B at time t + tAB given that event A occurred at time t, and Ψ(tAB) is the likelihood of tAB.

To approximate P (A; t) and P (B; t + tAB|A; t), a kernel density method with Gaussian kernel was used. Bandwidth was chosen with the Silverman method. Each g-pattern was considered active (i.e. presence at a specific time) if the value of the time signature was above a set threshold.

4 Experiments

As with all causal detection, real-world data with known ground-truth are hard to come by. Synthetic data were used to test the proposed method. Relations were generated by sampling from two Gaussian distributions representing prior and posterior events, with time interval following an exponential distribution. Noise was randomly generated. The data distribution is shown in Fig. 2a, with different active time as shown in the black line in Fig. 2d. The algorithm correctly identified three relations as shown in Fig. 2b. The time signature and active time are shown in Fig. 2c and 2d respectively. The identified active time was very close to the ground truth.

5 Conclusion

This paper proposed an algorithm for change detection of causal relations using pattern time signature along with GCSM algorithm. The experiment with synthetic data shows that the method could identify correct relations, even under noisy environment.

However, there are still limitations of the proposed methods. It cannot detect other kinds of changes, and the G-CSM algorithm is still susceptible to temporal noise. Experiments also need to be done on real-world data.