Spatial-Temporal Sequential Hypergraph Network for Crime Prediction with Dynamic Multiplex Relation Learning

1 Introduction

Criminal activities (e.g., Burglary, Robbery and Assault) have become a major social problem due to their adverse effect on public safety and economic development [Wortley and others, 2016]. For example, accurate crime prediction results could facilitate the decision making process of governments and prevent crimes happening for public safety and emergency management [Zhao and Tang, 2017]. In recent years, the availability of crime data has enabled the development of data-driven methods for forecasting the occurrences of crimes [Wang et al., 2016; Huang et al., 2019].

∗Both authors contribute equally to this work

†Corresponding author: Yong Xu

One solution in predicting crimes is to uncover effective features for each category of crimes based on handengineering domain-specific features (e.g., regional transportation information [Wei et al., 2019], meteorological conditions [Zheng et al., 2017]). However, without domainspecific expert knowledge (e.g., criminology and anthropology), we may not have sufficient and accurate external data sources to model their correlations with different types of crimes (e.g., burglary, felony assault) precisely [Zhang et al., 2017a]. Therefore, a general crime data learning framework is a necessity to reduce the effort of hand-crafted feature engineering for the crime prediction task.

Among various spatial-temporal prediction methods, deep learning-based methods stand out owing to the feature representation effectiveness of neural network architecture. There exist many recently proposed forecasting frameworks focusing on modeling the time-evolving regularities over the temporal dimension and the underlying region-wise geographical dependencies over the spatial dimension, such as attentional neural methods [Yao et al., 2019; Huang et al., 2018], convolution-based learning approach [Zhang et al., 2017b], spatial relation encoder with graph neural networks [Zheng et al., 2020; Zhang et al., 2021].

Despite their effectiveness, we argue that current spatialtemporal prediction models fall short in addressing unique challenges that are specifically for multi-dimensional crime data. Specifically, due to the crime data heterogeneity, there exist explicit and implicit dependencies among different categories of crimes. The intrinsic design of current methods, making them incapable of capturing cross-type crime influences in a fully dynamic scenario, with the integration of both spatial and temporal patterns.

Contribution. In light of the challenges, we propose to study the crime prediction with the goal of effectively encoding crime-type dependent representations, capturing spatialtemporal dynamics with the awareness of inherent crosstype crime influences. In this work, we present the SpatialTemporal Sequential Hypergraph Network (ST-SHN) crime prediction architecture. Technically, we develop a multichannel routing mechanism to model the cross-type crime influences at a fine-grained level of semantics under the graph neural network framework. Additionally, the developed hierarchical spatial dependency encoder via the hypergraph learning paradigm, endows the ST-SHN framework with the capability of exploring region-wise relations from locally to globally. To handle the time-wise crime patterns across different types, a graph temporal shift mechanism is developed to inject the time-varying spatial-temporal crime patterns into the representation process. ST-SHN reveals multi-view crime patterns for better model capacity and interpretability. In a nutshell, the dynamic multi-relational modeling of crimes allows us to encode relation dependencies and semantics corresponding to time, location and crime type dimensions. We conduct extensive experiments on two datasets, to demonstrate the advantages of our model for the effectiveness of crime prediction, modeling of latent cross-type crime influence, and interpretability of multi-view relations.

2 Preliminaries

We begin with some important notations and then introduce the formalized crime prediction problem. Considering a typical spatial-temporal forecasting scenario with R urban regions, T historical time slots (e.g., days), and C crime categories (e.g. theft, assault, criminal damage), we define the crime tensor X ∈ RR×T×C corresponding to the spatial, temporal and categorical dimension, respectively, in which each entry Xtr,c represents the number of c-th category of crime occurrences reported from region r at the t-th time slot.

Problem Statement. With the aforementioned definitions, the crime prediction task can be formalized as follows: learning a prediction function that takes the historical crime tensor X as the input, and yields predictions XT+1 ∈ RR×C on future crime occurrences. In this work, we tackle the tasks of both the binary crime occurrence prediction and forecasting the quantitative number of crime cases.

3 Methodology

3.1 Spatial Dependency Encoder

ST-SHN proposes to comprehensively capture the complex spatial dependencies across regions from different category views. We first generate the region graph G = (V, E), where V and E represents the set of regions ([r1, ..., rR]) and their spatially adjacent relations. Here, we use S × S grid scale to define geographical neighbors between region ri and rj .

Type-aware Crime Embedding Layer

With the consideration of cross-type crime influences in a dynamic enviroment, we describe a region r with multiple time-aware embeddings Etr,c ∈ Rd corresponding to the cth type of crime and t-th time slot. In particular, we first normalize the crime vector Xtr in tensor X using the mean μ and std σ ∈ RC value over all R regions and T time slots, i.e., ¯Xtr = (Xtr - μ)/σ. Formally, the time- and type-aware region embedding Etr,c is generated as: Etr,c = ¯Xtr,c · ec, where ec ∈ Rd denotes the global embedding vector under the crime type of c over all time periods, and d is the hidden state size. Hence, we associate each region r with C different type-specific embeddings at each time slot in our dynamic multiplex spatial-temporal relation learning.

Spatial Message Propagation Paradigm

Based on the generated region embedding Etr,c and spatial region graph G, we generalize our spatial relation encoder with multiplex message propagation paradigm over G:

where mti←j represents the message passed from region rj to ri at t-th time slot. The region-wise geographical relations are reflected by the spatial adjacent matrix A ∈ RR×R, in which Ai,j = 1 if edge (ri, rj) ∈ E. To debias the influence of node degree in information propagation, we further incorporate the normalization factor as ¯A = D12 AD12 , where D denotes the diagonal degree matrix. Additionally, the embedding propagation function Propagate(·) is determined by both the source and target region, with the awareness of latent influence across different crime types (e.g., Burglary, Robbery).

Multi-Channel Routing Mechanism

To comprehensively characterize the type-aware crime influences across different regions, we develop a routing mechanism under multiple channels as our information encoding function Propagate(·), which is formally presented as follows:

In our routing mechanism, we design a multiplex mutual attention network with the learnable weight αh c,c′ . In specific, αh c,c′ captures the explicit relevance between the c-th and c′ -th crime types under the h-th representation subspace. Vh ∈ Rd/H×d represents the c-channel transformation. || denotes the concatenation operation. Inspired by the architecture of Transformer network [Vaswani et al., 2017], we propose to respectively map the target region ri and source region rj into query and key vector projection:

where Qh ,Kh ∈ Rd/H×d are the h-channel transformation to acquire the query and key information.

Iterative Aggregation for High-order Connectivity

With the generated propagated message mti←j ∈ RC×d , STSHN conducts aggregation to smooth the neighboring nodes and refine new region representation with the summation as: ∑Rj=1 mti←j . To extract the long-range spatial connectivity between regions, we further stack multiple spatial embedding propagation and aggregation blocks. We denote the initial region embeddings as E(0) of size R × T × C × d, then the high-order message aggregation can be formalized as:

where σ(·) denotes the ReLU activation function with the incorporation of non-linear feature interactions. E(L) i is obtained with L iterations and is able to receive crime information from regions of L-hop distance.

3.2 Cross-Region Hypergraph Relation Learning

In addition to modeling spatial dependency between regions with location-aware information, we further enhance the cross-region relation learning without the limitation of adjacent connections by devising a hypergraph neural framework. With the incorporation of hypergraph neural network, we endow ST-SHN with the expressive power of global relation representation. Specifically, we first define a trainable adjacent matrix Ψ ∈ RE×R, where E is a hyperparameter denoting the number of hyperedges. ST-SHN performs the embedding propagation along Ψ between R regions and E hyperedges. During this process, hyperedges serve as the intermediate information hubs which correlate not only locally connected but also far away regions in the entire urban space. Formally, with adjacency Ψ and regional embeddings ˜E, the hypergraph message passing can be defined as follows:

where σ(·) denotes the activation function. DR ∈ RR×R, DE ∈ RE×E denotes the diagonal degree matrices.

3.3 Graph Temporal Shift Mechanism

We further propose a graph temporal shift mechanism to encode i) intra-region type-aware crime temporal dependencies; ii) inter-region type-aware crime influences across different time slots. Towards this end, we construct a spatial-temporal crime graph between R regions with the new adjacent matrix Γ ∈ RR×R, with the former dimension referring to R regions at the t-th time slot, and the latter one corresponding to R regions at the (t + 1)-th time slot. In particular, to reflect the intra-region type-aware crime dependencies over the temporal dimension, we set Γi,i = 1 for region ri. To enable the joint learning of inter-region and inter-type crime influence in a dynamic scenario, we set Γi,j = 1 between spatial adjacent region ri and rj in our graph temporal shift mechanism.

With the spatial-temporal adjacent matrix Γ and two multi-typed embedding tensors of adjacent time slots ¯E(0),t , ¯E(0),t+1 with the size R × C × d, ST-SHN recursively conducts the embedding recalibration and aggregation in a similar manner as our spatial relation encoder, as follows:

where Propagate T represents the temporal message passing paradigm which is built upon the designed multi-channel routing mechanism. ¯Γ = D12 ΓD12 is the normalized adjacent matrix where D is the corresponding degree matrix.

3.4 Model Prediction and Optimization

We integrate order-specific embeddings (E(0) , ..., E(L) ) with summation. At last, ST-SHN sums up the embeddings along the time dimension to generate the final embeddings Λ ∈ RR×C×d for making predictions of different types of crimes as: ˆXT+1 r,c = φ(w⊤c Λr,c), where φ(·) is Sigmoid for classification (crime occurrence) and φ(x) = x for regression (quantitative number of crime cases). For the classification and the regression tasks, ST-SHN is optimized by minimizing the following two loss functions, respectively:

where t iterates the time slots, and δ(·), ¯ δ(·) denotes the element-wise positive and negative indicator functions, respectively. The later terms are the regularization terms and λ denotes the decay weight.

Model Complexity Analysis

The spatial and the temporal pattern encoding share similar complexity: O((|A|LS + |Γ|LT )(C + d)TCd), where | · | denotes the number of edges in the graph, and LS, LT denotes the number of stacked graph layers for spatial and temporal modeling, respectively. The hypergraph model costs O(RELHTCd) complexity, which is relatively minor in practice. Therefore, our model achieves the comparable time complexity as compared to other graph attentive frameworks.

4 Evaluation

This section aims to answer the following research questions:

• RQ1: How does our developed ST-SHN framework perform as compared to various state-of-the-art methods?

• RQ2: How do different components (e.g., spatial context encoder, hypergraph relation learning, temporal shift mechanism) affect the results of ST-SHN?
• RQ3: What is the influence of parameters in ST-SHN?
• RQ4: Can ST-SHN provide the model interpretability w.r.t spatial, temporal and semantic dimensions?

4.1 Experimental Setup

Datasets

We evaluate our model on two real-world datasets collected from the crime reporting platforms on New York City and Chicago. Each record is formatted as (crime category, timestamp and geographical coordinates). Descriptive statistics for those datasets are presented in Table 1. Each dataset contains different categories of crimes, e.g., Burglary and Robbery in NYC crime data; Theft and Damage in Chicago crime data. The reported prediction performance is averaged over 90 consecutive days during the test period of time. The grid-based mapping strategy is applied to partition NYC and Chicago into disjoint geographical regions with 3km × 3km spatial unit. We use one day as the time interval to map the crime records into series. We generate the training and test set with the ratio of 7:1 and use the crimes of the last month in the training set as the validation data.

Evaluation Metrics

We adopt two types of metrics for performance evaluation. Specifically, to validate the prediction results of crime occurrences, Macro-F1 and F1-score [Huang et al., 2018] are used for evaluating the cross-type overall performance and typespecific forecasting accuracy, respectively. To evaluate the performance in predicting quantitative number of crimes, we utilize the Mean Absolute Error (MAE) and Mean Absolute Percentage Error (MAPE) [Geng et al., 2019] as metrics.

Alternative Baselines

We compare our model with various state-of-the-art baselines which can be summarized into 5 groups. 1) conventional time series analysis techniques (ARIMA, SVM); 2) convolutionbased learning model (ST-ResNet); 3) attentional spatial data prediction methods (STDN, DeepCrime, STtrans); 4) spatialtemporal prediction with graph neural networks (DCRNN, ST-GCN, GMAN); 5) deep hybrid spatial-temporal predictive solutions (UrbanFM, ST-MetaNet).

• ARIMA [Pan et al., 2012]: it is a time series analysis method which models the temporal structures with kernelbased variable regression on future values.
• SVM [Chang and Lin, 2011]: it is another time series prediction technique which transforms data into feature space.
• ST-ResNet [Zhang et al., 2017b]: it enhances the convolution neural network-based traffic prediction with the incorporation of residual network for model training efficiency.
• STDN [Yao et al., 2019]: it models the spatial similarity and long-term periodic temporal pattern with the designed flow gating mechanism and attention mechanism.
• DeepCrime [Huang et al., 2018]: it is an attentive recurrent neural model to encode the periodicity of crime data.
• STtrans [Wu et al., 2020]: it leverages the self-attentionbased transformer network to as the information encoder for predicting crime events.
• DCRNN [Li et al., 2018a]: it designs bidirectional random walks to capture spatial correlations and sampling-based encoder-decoder for temporal pattern modeling.
• ST-GCN [Yu et al., 2018a]: it proposes to use graph convolutional layers on the graph-structured time series data to model the corresponding spatial and temporal similarities.
• GMAN [Zheng et al., 2020]: GMAN is built upon the graph-based attention network for aggregating information from both spatial and temporal dimensions.
• UrbanFM[Liang et al., 2019]: it designs the convolutional feature extractor to consider local region-wise dependencies and a diffusion network to fuse meteorological factors.
• ST-MetaNet [Pan et al., 2019]: this is a meta-learning prediction approach which employs the meta knowledge from geo-graph attributes for spatial correlation modeling.

Parameter Settings

We implement ST-SHN using TensorFlow and adopt Adam as the optimizer. We present the default hyperparameter settings of ST-SHN as follows: the hidden state size d is set as 16. The adjacent spatial relation scale is configured with the 3 × 3 grid unit. In addition, the depth of our spatial path aggregation layers is set as 2. We integrate long-range temporal dependencies by stack 7 temporal shift layers. The number of latent channels is set as 4 in our multi-channel dynamic routing mechanism. We consider the number hyperedges as 128. The learning rate is initialized as 0.001 with 0.96 decay rate. We search the weight decay factor of regularization term in the range of {0, 0.0001, 0.001, 0.01}.

4.2 Performance Comparison (RQ1)

The empirical results of all methods for predicting crime occurrences (measured by F1-score and Macro-F1) and quantitative number of crime instances (measured by MAE and MAPE) are reported in Table 2 and Table 3, respectively. We can find that ST-SHN consistently outperforms all baselines on two datasets in terms of all measures. We attribute these improvements to: i) by uncovering type-aware crime influence between regions, ST-SHN could preserve the holistic semantics of people crime behaviors; ii) benefiting from our hypergraph relational learning, ST-SHN is able to characterize the region-wise dependencies under global urban space, which results in more powerful representations of regions;

iii) with the design of graph temporal shift mechanism, STSHN could better inject the dynamism of both intra- and interregion dependencies across various crime categories underlying the spatial-temporal crime graph.

Compared with graph neural network-based spatialtemporal prediction methods (ST-GCN, GMAN, DCRNN), we can see that although they utilize location-based region graph to guide the learning of region embeddings, these approaches fail to model crime dependencies based on multiple crime categories, results in lower performance than STSHN. Besides, we can observe that although DeepCrime and STtrans utilize attention networks to model category-aware crime patterns, ST-SHN still achieves better results than them. The reason lies in that they fall short in exploring the timeevolving implicit influence among different types of crime patterns. The obvious performance gap between ST-SHN and methods: ST-ResNet and ST-MetaNet shed light on the limitation of modeling stationary spatial dependencies.

4.3 Model Ablation Study (RQ2)

We consider four contrast models to evaluate the effectiveness of sub-modules in ST-SHN: 1) "-S": ST-SHN without the spatial relation encoder with the location-based contextual signals; 2) "-HG": ST-SHN without the hypergraph learning component to capture global region-wise relation; 3) "-T": ST-SHN without the graph temporal shift mechanism; 4) "- R": ST-SHN without the multi-channel routing mechanism. Figure 2 shows the comparison results. It is lean that the full version of ST-SHN achieves the best performance compared to other variants. Therefore, leaving cross-type crime influences across either the spatial or temporal dimension unexplored, will downgrade the prediction performance.

4.4 Hyperparameter Study (RQ3)

Dimensionality of Hidden State. The model performance is evaluated through varying the hidden dimensionality d from 4 to 32. We can notice that the best performance is achieved with the channel embedding size of 16. When we conduct feature representation with latent dimensionality > 16, the performance degrades due to the overfitting issue.

Depth of Spatial-Temporal Graph Neural Model. We search the number of graph layers for spatial, temporal dimension in the range of [0,8] and [0,14]. For spatial dimension, ST-SHN with 2 layers outperforms the others. For temporal dimension, the best performance is achieved with the propagation path of length 8. Clearly, increasing the model depth is capable of endowing our predictive model with better representation ability. Stacking more embedding propagation layers may involve noise in refining learned representations.

4.5 Explainability of ST-SHN (RQ4)

We offer several examples to give an intuitive impression of our model explainability. Specifically, Figure 4 visualizes i) different types of crime distribution (i.e. heat-map-based statistics) from top-3 regions ranked by their learned relevance values with hyperedges (e.g., e8, e41); ii) learned typespecific crime influence scores for message propagation in our multi-channel routing mechanism over spatial and temporal dimensions. First, we can see that ST-SHN enables the dynamic modeling of multiplex spatial-temporal dependencies for different types of crimes, which is helpful to provide relation interpretations for policy makers. Second, the observed similar distributions among the most relevant regions, indicates that we endow our ST-SHN with the capability of identifying dependent regions which are either spatially neighbors or not, by capturing local and global geographical relation structures. In addition, we visualize the relevance matrix between a specific hyperedge and all regions in Figure 5(a) and Figure 5(b). By jointly analyzing the visualized relevance matrix and the actual crime spatial distributions across different regions, we can notice that the consistent distribution patterns suggest that ST-SHN could well differentiate regions with their underlying crime patterns.

5 RelatedWork

Spatial-Temporal Prediction. Many prediction methods have been proposed to uncover the implicit dependencies between future data points and historical observations from various spatial-temporal data [Li et al., 2020]. Specifically, attention mechanism has been used to enhance the temporal representation of recurrent neural network [Yao et al., 2019; Feng et al., 2018; Huang et al., 2020]. Furthermore, convolution-based sequential models propose to capture the spatial-temporal information simultaneously [Feng et al., 2020; Zhang et al., 2017b]. In this work, we aim to predict crimes by exploring inherent dependencies across time, location and semantic dimensions.

Graph Neural Networks for Spatial-Temporal Data. The objective of graph neural networks is to project nodes from the generated graph into a low-dimensional vector space [Wang et al., 2019; Hu et al., 2020]. It is worth mentioning that several recent efforts provide insights into graph neural networks for mining spatial-temporal data [Song et al., 2020; Diao et al., 2019]. For example, ST-GCN [Yu et al., 2018b] takes inspiration from graph convolution network to model inter-region spatial dependency over the generated geography graph. DCRNN [Li et al., 2018b] captures the spatial correlations by performing the bidirectional random walks on the region graph. However, these methods fall short in encoding region-wise relations in a dynamic manner, due to their utilization of static spatially adjacency matrices.

6 Conclusion

In this paper, we propose a novel Spatial-Temporal Sequential Hypergraph Network (ST-SHN), which approaches better crime pattern learning from spatial, temporal and semantic dimensions. ST-SHN is equipped with multi-channel routing mechanism to capture region-wise relations at a fine-grained level and exhibit the explainable semantics. Furthermore, with the relational path-aware message aggregation, ST-SHN refines the spatial-temporal representations under the context of long-range and global dependencies. Experiments demonstrate that the proposed method significantly outperforms various baselines. In the future, we would like to extend our model for real-time crime prediction with streaming data.

Acknowledgments

We thank the anonymous reviewers for their constructive feedback and comments. This work is supported by National Nature Science Foundation of China (62072188), Major Project of National Social Science Foundation of China (18ZDA062), Science and Technology Program of Guangdong Province (2019A050510010).