# Crime Prediction with Graph Neural Networks and Multivariate Normal
Distributions

Selim Furkan Tekin and Suleyman S. Kozat, Selim Furkan Tekin and Suleyman S.
Kozat are with the Department of Electrical and Electronics Engineering,
Bilkent University, Bilkent, Ankara 06800, Turkey e-mail: {tekin;
<EMAIL_ADDRESS>
###### Abstract

Existing approaches to the crime prediction problem are unsuccessful in
expressing the details since they assign the probability values to large
regions. This paper introduces a new architecture with the graph convolutional
networks (GCN) and multivariate Gaussian distributions to perform high-
resolution forecasting that applies to any spatiotemporal data. We tackle the
sparsity problem in high resolution by leveraging the flexible structure of
GCNs and providing a subdivision algorithm. We build our model with Graph
Convolutional Gated Recurrent Units (Graph-ConvGRU) to learn spatial,
temporal, and categorical relations. In each node of the graph, we learn a
multivariate probability distribution from the extracted features of GCNs. We
perform experiments on real-life and synthetic datasets, and our model obtains
the best validation and the best test score among the baseline models with
significant improvements. We show that our model is not only generative but
also precise.

###### Index Terms:

crime forecasting, probabilistic graph models, graph neural networks.

##  I Introduction

Crimes are unlawful acts endangering public safety, leading to colossal life
and economic losses if governments do not take the necessary precautions.
Understanding the latent patterns of crimes in a geographical region of a city
is highly important for controlling human traffic and preventing upcoming
crimes with the required force placement that supervises the police to be ”in
the right place at the right time.” Thus, accurate and reliable forecasting
with the most descriptive way is essential to canalize the potential
reinforcements.

The crime prediction problem is a complex task that contains spatial,
temporal, and categorical complexities with inherent interrelations. Prior
works approached the crime prediction problem in two methods. The first method
is to divide the city area into a grid, where each cell contains the crime
information for each crime category that happened in the past. Thus, the idea
is to create a spatiotemporal series with tensors containing numerical data
such as crime count for each time step. The second method is to divide the
city area into unordered regions and create a graph structure that captures
the correlations among the regions with corresponding edge weights and node
features. After learning the graph structure, the model forecasts the crime
occurrences for all regions for the next time step.

However, the regions in both of the methods correspond to extremely wide
sections of the cities. To the best of our knowledge, the minimum size of a
region in grid-based methods has 4$\mathrm{km}^{2}$ area. And, for the graph-
based approaches, the regions correspond to the districts of a city, where
each district has different sizes. For instance, the districts of Chicago city
have a range of size that changes from 2$\mathrm{km}^{2}$ to
35$\mathrm{km}^{2}$. Thus, assigning a probability value to such a broad area
is not expedient and decreases the useability in real-life situations.

To this end, one can increase the number of regions to enhance the detailing.
However, this leads to problems in two approaches. For the grid-based
approach, as the grid size increases, the complexity exponentially grows. The
model used for capturing the spatial-temporal relations becomes too complex
with the growing number of parameters. Furthermore, the interrelations in
neighbors of the grid weaken with the high number of cells that contain no
crime events. As the cells with zero crime count take the majority, the
sparsity of the grid grows, and the data becomes imbalanced. Consequently,
grid-based approaches fail to learn the underlying pattern and perform poorly
caused by the memorization. On the other hand, it is difficult to define a
rule to add new regions to the graph in graph-based methods. In addition, as
we increase the number of nodes in the graph to be the same as the number of
regions in graph-based approaches, we will create a model with the same
complexity as the grid-based model. Thus, the problems we meet will be
analogous to the issues of the grid-based model.

This paper introduces a probabilistic graph-based model called High-Resolution
Crime Forecaster (HRCF) that performs grid-based crime prediction to remedy
these problems. We learn a multivariate probability distribution instead of
assigning one probability value to each node in a graph. We build our graph on
spatiotemporal data using a divide-and-conquer algorithm to up weight the
minority class. Specifically, the algorithm divides the city area into four
regions recursively until each has a total crime count below a threshold
value. Next we build our graph, where the nodes of the graph represent the
centers of each region, edge weights represent the distances between two
neighbor nodes. We model the underlying dynamics of each region with a
multivariate gaussian distribution with the objective of minimizing the cross
entropy. The architecture contains graph convolutional neural networks as
memory units, which capture the spatial and temporal correlations. Each time
step, the model predicts multivariate gaussian distributions for all regions
conditioned on the previous observations, allowing us to generate predictions
for any resolutions. We demonstrate significant performance gains through an
extensive set of experiments compared to the conventional methods and show
that our model is not only generative but also more precise.

###  I-A Prior Art and Comparisons

Numerous studies [1, 2, 3, 4, 5, 6, 7, 8] analyzed crime data in cities,
focusing on potential correlations between various features. However, our
study focuses on the algorithmic perspective to increase the model performance
in high-resolution forecasting for crime events and locations. Thus, we
focused on the works related to our methodology consisting of graphical and
grid-based approaches with deep learning models.

Earlier works, [9, 10], focused on implementing the Kernel Density Estimation
(KDE) in the spatial domain to predict the hotspots on the distribution of
crime events. However, performing predictions according to the fitted model is
problematic due to the temporal changes in short-term and long-term forecasts.
Inspiring from earthquake prediction, the authors of [11] implemented a self-
exciting point process to exhibit the space-time triggering function and
compared their methods with KDE modeled crime hotspot maps. Following this
work, the authors introduced a marked point process with the parameterized
triggering kernel function and compared their approaches with multivariate
Hawkes processes [12]. However, modeling with self-exciting processes makes
strong assumptions on the data, which decreases the expressive power of the
respective processes. Thus, the authors of [13] proposed Recurrent Marked
Temporal Point Processes (RMTPP) to model the crime events where recurrent
neural network parameterizes the intensity function. RMTPP can learn latent
temporal dynamics showed high performance compared to baseline processes
including Hawkes and Poisson.

Following these statistical approaches, deep learning structures appear in
literature to model crowd movements and showed higher performance. In [14],
authors implemented Deep-learning based prediction model for spatiotemporal
data (DeepST), where they model the crowd flow with the grid-based forecasting
system. Furthermore, [15] improved DeepST architecture by modeling the inflow
and outflow of crowds in every city region and called their architecture ST-
ResNet. Authors of [16] adapted the ST-ResNet to predict crime distribution
over the Los Angeles dataset and achieved high scores. However, they applied
spatial-temporal regularization to the data, which increased the computational
cost dramatically. Another grid-based deep learning structure is [17], where
authors designed multi-model units capturing spatial, temporal, and semantic
information and producing predictions for each crime type. They leveraged the
performance of attention mechanisms and LSTMs while performing predictions in
11x11 grid size. As designated in [17], the model performance decreases as the
spatial size increases. Likewise, all the other works above produce
predictions with small grid sizes.

Due to the high sparsity and complexity of grid-based approaches, graphical
models started to emerge in the literature. With the flexibility and
robustness of Graph Neural Networks (GNN) [18], they showed high performance
on spatiotemporal domains. For example, [19] authors introduced SRNN structure
to model human-object interactions on image sequences. In crime prediction,
[20] studied the problem of representing spatiotemporal crime data into a
graph structure. They formed the graph structure with modeling of independent
Hawkes processes in each node and obtained edge weights. Furthermore, they
used SRNN like structure with the multi-layered LSTMs on edges and performed
predictions for 50 regions in the CHI crime dataset. Another study [21]
implemented Gated Recurrent Network with Diffusion Convolution modules
following a Multi-Layer Perceptron (MLP). Their experiments on CHI data built
the graph according to districts where the edge values are the distance
between nodes. Recently, [22] introduced a homophily-aware constraint on the
loss function, so that neighboring region nodes share similar crime patterns.
Nevertheless, these works are non-generative and work on the districts, which
causes the problems mentioned in the introduction.

###  I-B Contributions

  * •

We introduce a subdivision algorithm to create a graph from grid-based
spatiotemporal data to reduce sparsity and make predictions with fewer
parameters.

  * •

We present a novel graphical architecture with multivariate Gaussian
distributions to jointly train the micro and macro probabilities and model the
actual data distribution.

  * •

With the generative structure of our model, we can produce accurate
predictions for the high spatial resolution with fewer parameters.

  * •

Through extensive experiments over real and synthetic datasets, we demonstrate
that our method brings significant improvements compared to baseline methods.

##  II Problem Definition

We first define various sets that represent information about the data. Next,
we define our graph structure and graph function. Following these definitions,
we define our objective and how we train our model.

We divide the city region with a grid-based approach into $I\times J$
disjointed cells, which creates the set
$M=(m_{1,1},\dots,m_{i,j},\dots,m_{I,J})$. Each cell contains the longitude,
$x$, and latitude, $y$, information, which we show as $m_{i,j}=(x,y)$. Next,
we partition the $M$ set into $N$ disjoint sets according to the algorithm
shown in section III to create the region set
$R=(r_{1},\dots,r_{i},\dots,r_{N})$, where each region contains arbitrary
number of cells. For a given time window T, we also split T as non-overlapping
and consequent time slots $T=(t_{1},\dots,t_{k},\dots,t_{K})$.

For each region $r_{i}$, we create event matrices
$\mathbf{X}_{i,1:\mathrm{K}}=(\mathbf{x}_{i,1},\dots,\mathbf{x}_{i,k},\dots,\mathbf{x}_{i,K})\in\mathbb{R}^{L\times
K}$ to denote all the crimes occured during the past K slots, where $L$ is
total crime categories. In particular, $x_{i,k}^{l}\in\mathbb{R}$ represents
the total event count observed at the region $r_{i}$ at time slot $k$ for the
crime type $l$. Similarly,
$\mathbf{X}_{1:N,t}=\mathbf{X}_{t}\in\mathbb{R}^{N\times L}$ denotes the event
matrix for all the regions and categories at the time step $t$.

We formulate region graph as
$\mathcal{G}=(\mathcal{V},\mathcal{E},\mathbf{A})$, where $\mathcal{V}$
represents the set of nodes with $|\mathcal{V}|=N$ where $N$ is the number of
regions and $\mathcal{E}$ is the set of undirected edges between region nodes,
$\mathbf{A}$ is the weight matrix. Let $v_{i}\in\mathcal{V}$ to denote a node
and $\epsilon_{ij}=(v_{i},v_{j})\in\mathcal{E}$ to denote an edge. The weight
matrix $\mathbf{A}$ has dimension of $N\times N$ with
$A_{i,j}=\mathrm{dist}(v_{i},v_{j})$ if $\epsilon_{i,j}\in\mathcal{E}$ and
$A_{i,j}=0$ if $\epsilon_{i,j}\not\in\mathcal{E}$. Furthermore, we define the
graph function, $g(.)$, which takes the event matrices as the input and
produces the state vectors, $\mathbf{h}_{i,t}\in\mathbb{R}^{d_{h}}$, for each
graph node, where $d_{h}$ is the hidden dimension. We formulate the graph
function as:

$\\{\mathbf{X}_{1},\dots,\mathbf{X}_{K},\mathcal{G}\\}\xrightarrow[]{\text{g(.)}}\\{\mathbf{h}_{1,\mathrm{K}+1},\dots,\mathbf{h}_{\mathrm{N},\mathrm{K}+1}\\},$
(1)

where the details of this function shown in section III.

Figure 1: We show the phases of creating our graph. First, we create a grid by
dividing the region into $I\times J$ cells, where each cell contains the total
event count. Second, with the sampling algorithm that favors the crowded
regions, we obtain graph regions. Third, we create the graph with nodes
representing the centers of each region and edges representing the distances
between nodes.

In this paper, our primary goal is to learn a generative model for crime
forecasting using previous crime events. Our first main assumption is that in
each time step, $t_{k}$, the probability of a crime event happening in a
region, $r_{i}$, is governed by a joint probability distribution conditioned
on the passed crime events:

$P(\mathcal{X}_{i,k},\mathcal{Y}_{i,k}|\mathbf{X}_{1:k-1})=f_{\mathcal{X}_{i,k},\mathcal{Y}_{i,k}}(x_{i,t},y_{i,t}|\mathbf{X}_{1:k-1}),$
(2)

where $x$ and $y$ represent the longitude and latitude of the crime locations.
Secondly, we model the joint probability with a likelihood model,
$l(x_{i,t},y_{i,t};\theta(\mathbf{h}_{i,k}))$, and parametrized by the
$\theta(.)$ function. Hence, the probability distribution function in equation
2 becomes:

$f_{\mathcal{X}_{i,k},\mathcal{Y}_{i,k}}(x_{i,t},y_{i,t}|\mathbf{X}_{1:k-1})=l(x_{i,t},y_{i,t};\theta(\mathbf{h}_{i,k})),$
(3)

where we decide the likelihood model to be Multivariate Gaussian Distribution.
Thus, $\theta(.)$ parametrize the mean vector and covariance matrix:

$\displaystyle\theta$ $\displaystyle=(\mathbf{\mu},\mathbf{\Sigma}),$
$\displaystyle\mathbf{\mu}$
$\displaystyle=\begin{bmatrix}\mu_{1}&\mu_{2}\end{bmatrix},$ (4)
$\displaystyle\mathbf{\Sigma}$ $\displaystyle=\begin{bmatrix}v_{1}^{2}&0\\\
0&v_{2}^{2}\end{bmatrix},$ (5)

where we design the covariates in the covariance matrix to take zero to
decrease the number of parameters we learn. In training, we could directly
maximize the log-likelihood (MLE) where we put the locations of each crime
event into the likelihood model:

$\mathcal{L}=\sum_{i=1}^{N}\log l(x_{i,t},y_{i,t};\theta(\mathbf{h}_{i,k})),$

and sum all the log-likelihoods in each region. However, MLE loss does not
directly suffer negative predictions, and in our experiments, we observed that
the model stuck on the local minimum. Therefore, we minimize the Kullback-
Leibler divergence between the actual distribution and the likelihood model,
which is equivalent to minimizing the cross-entropy:

$\mathcal{L}=-\sum_{i=1}^{N}\sum_{\begin{subarray}{c}x\in\mathcal{X}_{i,t}\\\
y\in\mathcal{Y}_{i,t}\end{subarray}}p(x,y)\log
l(x,y;\theta(\mathbf{h}_{i,k})),$ (6)

where the term $p(x,y)$ is still unknown and note that $x$ and $y$ are
continuous values. Recall that we quantized each region with the grid-based
approach where each cell takes one if a crime happened, zero otherwise. With
this approach, we can rewrite our equation 6 as binary-cross entropy:

$\mathcal{L}=-\frac{1}{\mathrm{I}\mathrm{J}}\sum_{i=1}^{N}\sum_{\begin{subarray}{c}x\in\mathcal{X}_{i,t}\\\
y\in\mathcal{Y}_{i,t}\end{subarray}}q\log
l(x,y;\theta)+(1-q)\log(1-l(x,y;\theta)),$ (7)

where $q(.)$ maps the longitude and latitude to the crime event value:

$q(x,y)=\begin{cases}1,&\mathrm{if\,event\,observed\,at}\,(x,y)\\\
0,&\mathrm{otherwise}\end{cases}$ (8)

and we optimize the loss function shown in equation 7 with Adam optimizer
using batches of training data.

##  III Methodology

In this section, we describe the subdivision algorithm to create our graph.
Next, we present the details of the graph model.

###  III-A Subdivision Algorithm

(a)

(b)

Figure 2: We show the distribution of events for the grid (a) and the graph
(b) structures. While the grid structure contains $60.42\%$ of cells with zero
events, the node structure contains $5.97\%$.

As we mention in section II, we divide the region into $I\times J$ cells, and
each cell contains the information of the longitude and latitude which creates
the $M$ set, which is indexed by the $i$th row and $j$th column. Following
this definition, we can represent the number of crimes in each cell regardless
of crime type at the time $t$ with
$\mathbf{E}_{t}=(e_{11},\dots,e_{ij},\dots,e_{IJ})\in\mathbb{R}^{I\times J}$.
Next, we create the grid matrix $\mathbf{Q}\in\mathbb{R}^{I\times J}$ by
summing each event matrix at time step $t$:

$\mathbf{Q}=\sum_{t=1}^{T}\mathbf{E}_{t},$ (9)

where we show the $\mathbf{Q}$ matrix in the first phase of the figure 1.
Observe that the number of cells that contain no events takes the majority. We
show this sparsity with the distribution of crime events in each cell in
figure 2(a).

We introduce a subdivision algorithm with a divide-and-conquer approach to
overcome this problem, allowing us to use a more flexible graph structure in
any spatially distributed data. Algorithm 1 shows the subdivision algorithm to
create regions. Our goal is to make all the regions contain a total event
count less than a threshold value, $\tau$. Our base condition is to have a
region larger than $(2,2)$ or a total event count less than the threshold
value. Since the problem contains sub-problems that can be solved
individually, we used a recursive approach.

After the subdivision process, we build our graph with the nodes representing
the centers of each region and the edges representing the distance between the
neighbor nodes. Figure 2(b) shows the distribution of events in each region.
Note that the change in zero ratios shows the sharp decrease in the sparsity,
which can be further decreased according to the threshold and minimum region
size selection.

Input: $\mathbf{Q},\tau,r,c$

Output: $R$

// list of regions

Function  _DivideRegions(_$\mathbf{Q}$ , $\tau$, $r$, $c$_)_:

/* Select the sub-region */

$\mathbf{Q}^{*}\longleftarrow\mathbf{Q}\mathrm{[r[0]:r[1],c[0]:c[1]]}$

if  _$(\mathrm{sum}(\mathbf{Q}^{*})
<\tau)\>||\>(\mathbf{Q}^{*}.\mathrm{shape}<(2,2))$_ then

return [[r, c]]

// base case

else

I $\leftarrow$ SplitRegions($\mathbf{Q}^{*}$, $r$, $c$)

// divide 4

R $\leftarrow\mathrm{[\>]}$

foreach  _$r,c\in\mathrm{I}$_ do

R.append(DivideRegions($\mathbf{Q}^{*}$, $\tau$, $r$, $c$))

end foreach

return R

end if

End Function

Algorithm 1 Algorithm for Subdivision

###  III-B High Resolution Crime Forecaster (HRCF)

Figure 3: We show HRCF architecture. In each time slot $t_{k}$, we extract
features with the Graph-ConvGRU operations. We pass these features to two
different MLP heads, $\mu$ and $\Sigma$. Each head produces the
$\mathbf{\mu}_{i}$ and $\mathbf{\Sigma}_{i}$ parameters of distribution in
each node.

This section gives details of each component in our model shown in figure 3
and their contributions to solving our problem.

A crime event correlates with abnormal events in nearby locations [8]. An
after-effect of a crime can trigger another crime in nearby areas [11]. We use
graph convolution to learn such relation due to its success of modelling
spatial-temporal series[19]. The idea of graph convolution is analogous to the
traditional 2D convolution. An image pixel is similar to a node in a graph,
where the filter size of 2D convolution determines the number of neighbors.
The 2D convolution takes the weighted average of pixel values of the central
node along with its structured grid neighbors. Similarly, graph convolution
takes the weighted average of the central node along with its unordered and
variable in size neighbors. Each node collects messages from the input signal
to its neighbors. Therefore, we can use convolution operations to carry the
information of a crime event in a region to nearby areas.

Mathematically, we motivate the graph convolution based on the steps shown in
[18]. In graph signal processing Fourier Transform takes the projection of a
graph signal $\mathbf{x}\in\mathbb{R}^{n}$ to orthonormal space of graph,
$\mathcal{F}(x)=\mathbf{U}^{T}\mathbf{x}=\tilde{\mathbf{x}}$, where
$\mathbf{U}^{T}\mathbf{U}=\mathbf{I}$. The inverse transform is also defined
as $\mathcal{F}^{-1}(\tilde{\mathbf{x}})=\mathbf{U}\tilde{\mathbf{x}}$. To
define the graph convolution an orthonormal basis must be created. Therefore,
the normalized graph Laplacian matrix,
$\mathbf{L}=\mathbf{I}_{n}-\mathbf{D}^{-1/2}\mathbf{A}\mathbf{D}^{-1/2}$, is
used for the mathematical representation of an undirected graph, where
$\mathbf{D}$ is the degree matrix of $\mathbf{A}$. Since the Laplacian is a
real symmetric positive semidefinite matrix, we can use the eigen
decomposition $\mathbf{L}=\mathbf{U}\mathbf{\Lambda}\mathbf{U}^{T}$, where
$\mathbf{U}\in\mathbb{R}^{n\times n}$ contains eigen vectors and
$\mathbf{\Lambda}$ is a diagonal matrix containing eigen values. Thus, with a
graph signal, $\mathbf{x}\in\mathbb{R}^{n}$ and a filter
$\mathbf{g}\in\mathbb{R}^{n}$ graph convolution is:

$\displaystyle\mathbf{x}\ast_{\mathcal{G}}\mathbf{g}$
$\displaystyle=\mathcal{F}^{-1}(\mathcal{F}(\mathbf{x})\odot\mathcal{F}(\mathbf{(}g))$
(10) $\displaystyle=\mathbf{U}(\mathbf{U}^{T}x\odot\mathbf{U}^{T}\mathbf{g})$
(11) $\displaystyle=\mathbf{U}\mathbf{g}_{\theta}\mathbf{U}^{T}\mathbf{x},$
(12)

where $\odot$ denotes the element-wise product and
$\mathbf{g}_{\theta}=\mathrm{diag}(\mathbf{U}^{T}\mathbf{g})$ is the learnable
filter. However, evaluating 12 is costly and note that we first need to
perform the eigen decomposition of $\mathbf{L}$, which is also costly
operation for large graphs. Thus, [23] parametrizes $\mathbf{g}_{\theta}$ as a
truncated expansion, up to order K-1 of Chebyshev polynomials $T_{k}$. As a
result, the graph filtering operation can be written as:

$\mathbf{g}_{\theta}\ast_{\mathcal{G}}\mathbf{x}=\sum_{k=0}^{K-1}\mathbf{\theta}_{k}T_{k}(\tilde{L})\mathbf{x},$
(13)

where $T_{k}(\tilde{L})\in\mathbb{R}^{n\times n}$ is the Chebyshev polynomial
of order k evaluated at the scaled Laplacian
$\tilde{L}=2L/\lambda_{\mathrm{max}}-I_{n}$, and
$\mathbf{\theta}\in\mathbb{R}^{K}$ is the vector of Chebyshev coefficients.
The $K$ value defines the number of hops we make while aggregating the
messages from the neighbors.

Graph Convolutional Neural networks have homophily and structural equivalence
biases, which we employ in crime prediction. We assume that structurally
similar nodes will show close behavior. Since graph convolutional networks
allow parameter sharing across the nodes in the graph, we can capture the
spatial dependencies for different patterns observed in other locations.

To capture the temporal relations we used the graph convolutions with deep
memory units proposed in [24]. Graph Convolutional Gated Recurrent Unit
(GCGRU) generalizes the Convolutional Gated Recurrent Unit (ConvGRU) model
[25] to graphs by replacing the Euclidian 2D convolution $\ast$ by the graph
convolution $\ast_{\mathcal{G}}$:

$\displaystyle z$
$\displaystyle=\sigma(\mathbf{W}_{xz}\ast_{\mathcal{G}}\mathbf{x}_{t}+\mathbf{W}_{hz}\ast_{\mathcal{G}}\mathbf{h}_{t-1}),$
$\displaystyle r$
$\displaystyle=\sigma(\mathbf{W}_{xr}\ast_{\mathcal{G}}\mathbf{x}_{t}+\mathbf{W}_{hr}\ast_{\mathcal{G}}\mathbf{h}_{t-1}),$
$\displaystyle\tilde{\mathbf{h}}$
$\displaystyle=\mathrm{tanh}(\mathbf{W}_{xh}\ast_{\mathcal{G}}+\mathbf{W}_{hh}\ast_{\mathcal{G}}(\mathbf{r}\odot\mathbf{h}_{t-1})),$
$\displaystyle\mathbf{h}_{t}$
$\displaystyle=\mathbf{z}\odot\mathbf{h}_{t-1}+(1-\mathbf{z})\odot\tilde{\mathbf{h}},$

where $\mathbf{W}_{h.}\in\mathbb{R}^{K\times d_{h}\times d_{h}}$ and
$\mathbf{W}_{x.}\in\mathbb{R}^{K\times d_{h}\times d_{x}}$ are the parameters
we learn. The hidden dimension, $d_{h}$, the input dimension, $d_{x}$, and $K$
determine number of parameters, which is independent of the number of nodes
$N$. The gates $\mathbf{z}$, $\mathbf{r}$, and $\tilde{\mathbf{h}}$ enabling
resetting and updating the stored information.

As show in figure 3, we stack GCGRU units and use as an encoder to encode the
input sequence. At each time slot $t$, each unit takes the previous hidden
state, $\mathbf{h}_{t-1}$ and input node feature, $\mathbf{x}_{t}$, to produce
the next state $\mathbf{h}_{t}$. Note that we apply these operations for every
node on the graph. Thus, in each time step, $t$, we feed the GCGRU unit at
each layer with $N$ different node features, $\mathbf{x}_{i,t}$, where the
subscript $i$ denotes the node index. Similarly, at each time step, $t$, GCGRU
unit outputs the hidden state, $\mathbf{h}_{i,t}$, for each node. As shown in
the problem definition, $\mathbf{x}_{i,t}\in\mathbb{R}^{L}$ are the event
vectors and $\mathbf{h}_{i,t}\in\mathbb{R}^{d_{h}}$ are the state vectors that
parametrize the likelihood model,
$l(x_{i,t},y_{i,t};\theta(\mathbf{h_{i,t}}))$. Each GCGRU output,
$\mathbf{h}_{i,t}$, passes to the MLP heads as shown in Figure 3. Each MLP
head is responsible for generating multivariate gaussian parameters shown in
equations 4-5 for each node:

$\displaystyle\mathbf{\mu}_{1}$
$\displaystyle=\sigma(\mathbf{W}^{T}_{\mu}\mathbf{h}_{1,t}+b_{\mu}),$
$\displaystyle\mathbf{v}_{1}$
$\displaystyle=\sigma(\mathbf{W}^{T}_{v}\mathbf{h}_{1,t}+b_{v}),$
$\displaystyle\dots$ $\displaystyle\mathbf{\mu}_{\mathrm{N}}$
$\displaystyle=\sigma(\mathbf{W}^{T}_{\mu}\mathbf{h}_{\mathrm{N},t}+b_{\mu}),$
$\displaystyle\mathbf{v}_{\mathrm{N}}$
$\displaystyle=\sigma(\mathbf{W}^{T}_{v}\mathbf{h}_{\mathrm{N},t}+b_{v}),$

where $\mathbf{W}^{T}_{.}\in\mathbb{R}^{d_{h}\times 2}$ and $b_{.}$ are the
weights we learn, $\sigma(.)$ is the sigmoid activation, and
$\mathbf{\mu}_{i}=[\mu_{i,1},\mu_{i,2}]$, $\mathbf{v}_{i}=[v_{i,1},v_{i,2}]$
are the parameter vectors. Since the multivariate distribution is
uncorrelated, we write the likelihood model as follows:

$\displaystyle l(x,y|\mathbf{\mu},\mathbf{\Sigma})$
$\displaystyle=\frac{\mathrm{exp}(\frac{-1}{2}(\mathbf{x}-\mathbf{\mu})^{T}\mathbf{\Sigma}^{-1}(\mathbf{x}-\mathbf{\mu}))}{2\pi|\mathbf{\Sigma}|^{1/2}}$
(14)
$\displaystyle=\frac{\mathrm{exp}(\frac{-1}{2}(\frac{(x-\mu_{1})^{2}}{v_{1}}+\frac{(y-\mu_{2})^{2}}{v_{2}}))}{2\pi(v_{1}v_{2})^{\frac{1}{2}}},$
(15)

which allows us to generate likelihoods for any location under the
distribution, as we show in the right of figure 3.

##  IV Experiments

This section compares our model performance with the baseline models on a real
and a synthetic dataset. We first describe the datasets with the statistics.
Next, we describe each dataset with the results of the experiments. Lastly, we
compare the performance of each model.

###  IV-A Data Description

####  IV-A1 The Chicago Crime Dataset

We collect the Chicago crime data between 2015 and 2019. The working area has
a longitude range of $[41.60,42.05]$ and a latitude range of $[-87.9,-87.5]$,
creating a rectangle with $50$km of height and $33$km of width. The rectangle
is non-euclidian due to the shape of the Earth, yet, we assumed an euclidian
rectangle. We partitioned the region into $50\times 33$ disjointed
geographical regions aiming to obtain $1\mathrm{km}\times 1\mathrm{km}$ sizes
of squares. As we described in the problem definition, we map crime events
into an individual geographical region. Figure 4(a) shows the heat map with
the grid shape of the crime distribution regardless of the crime type. We also
select the time resolution as $24$ hours. Thus, our target is to predict the
locations of any crime event in the partitioned regions for the next $24$
hours.

Moreover, we perform an exploratory data analysis 111You can find all of our
codes to perform analysis and experiments at github.com/sftekin/high-res-
crime-forecasting to observe spatial, temporal, and categorical covariates.
Spatially, we concluded that the crime events cluster in particular regions.
Temporally, the crime events are self-triggered, and there is a weekly
seasonality. Besides, before and during special days such as holidays,
weekends we observe similar patterns. Categorically, we perform
autocorrelation to features of different crime types to show that crimes
correlate with each other. In addition, the crime types; theft, burglary,
assault, deceptive practice, criminal damage, narcotics, battery, and robbery
forms the $\%90$ percent of the crime data. Thus, we filtered the data by
selecting these crime types.

We perform four experiments where each experiment consists of one year of
data. We split the data into ten months of train, one month of validation, and
one month of test in each experiment. We report the validation and test
scores.

(a)

(b)

Figure 4: We show the distribution of events for the Chicago crime data (a)
and the synthetic data (b).

####  IV-A2 Synthetic Dataset

We perform experiments on a synthetic dataset to simulate the performance of
our model even further. Our main goal is to create a gaussian distributed
spatial data that also has a temporal pattern. In addition, we mimic the crime
dataset by creating multiple categories that have self and cross-correlations.

First, we decided to give a total event count for each time step with a
temporal pattern. We model an AR process with $(1,0)$ parameters, where figure
5(a) shows the first 100 elements of this series. Second, we set the group
count as four and generated ten uniformly distributed density locations
between the range of $[0.2,0.8]$, as shown in figure 5(b). These locations are
the mean parameters of the uncorrelated multivariate Gaussian distributions,
which variance of them are $0.02,0.01,0.005,0.003$. We sampled from
distributions according to the ratios $0.1,0.2,0.3,0.4$. For instance, suppose
that the event count for an arbitrary day is $100$, the number of events
assigned for groups are $10,20,30,40$, respectively. Third, to create self and
cross relations, we create four different profiles and give numbers to each
distribution. In the first profile, distributions that have even indices can
generate events. The second profile is the opposite of the first profile. For
the third profile, indices divisible by four can generate events, and the
fourth profile is the opposite of the third. Moreover, after the ten-time
step, we switch the behaviors of profiles, where profile one behaves like
profile two and vice-versa. Accordingly, we created group relations both
temporally and categorically. Figure 4(b) shows the generated data
distribution.

###  IV-B HRCF Configurations

(a)

(b)

Figure 5: (a)The first 100 steps of AR series generated for synthetic data.
(b) Bi-variate Gaussian Distribution locations for each group Figure 6: We
show the predictions of HRCF model in different epochs. Validation Scores
---
| HRCF | ConvLSTM | ARIMA | RF | SVR | GPR
Date |  F1 |  Acc |  F1 |  Acc |  F1 |  Acc |  F1 |  Acc |  F1 |  Acc |  F1 |  Acc
2015 |  0.724 |  0.895 |  0.705 |  0.865 |  0.708 |  0.866 |  0.700 |  0.860 |  0.701 |  0.872 |  0.695 |  0.868
2016 |  0.728 |  0.891 |  0.714 |  0.864 |  0.717 |  0.865 |  0.727 |  0.873 |  0.716 |  0.875 |  0.703 |  0.865
2017 |  0.731 |  0.895 |  0.709 |  0.865 |  0.716 |  0.868 |  0.713 |  0.865 |  0.718 |  0.879 |  0.703 |  0.869
2018 |  0.720 |  0.894 |  0.704 |  0.868 |  0.705 |  0.867 |  0.707 |  0.869 |  0.698 |  0.873 |  0.692 |  0.869
Test Scores
| HRCF | ConvLSTM | ARIMA | RF | SVR | GPR
Date |  F1 |  Acc |  F1 |  Acc |  F1 |  Acc |  F1 |  Acc |  F1 |  Acc |  F1 |  Acc
2015 |  0.723 |  0.888 |  0.713 |  0.871 |  0.705 |  0.863 |  0.718 |  0.874 |  0.709 |  0.876 |  0.694 |  0.867
2016 |  0.709 |  0.881 |  0.698 |  0.863 |  0.718 |  0.876 |  0.693 |  0.855 |  0.697 |  0.870 |  0.684 |  0.864
2017 |  0.708 |  0.877 |  0.699 |  0.865 |  0.686 |  0.853 |  0.697 |  0.862 |  0.697 |  0.872 |  0.686 |  0.866
2018 |  0.720 |  0.884 |  0.708 |  0.870 |  0.712 |  0.869 |  0.716 |  0.872 |  0.708 |  0.876 |  0.693 |  0.869
TABLE I: We show model’s validation and test scores on Chicago crime dataset. Bold scores are the best. Date column shows the years the experiment belongs. | HRCF | ConvLSTM | ARIMA | RF | SVR | GPR
---|---|---|---|---|---|---
Set |  F1 |  Acc |  F1 |  Acc |  F1 |  Acc |  F1 |  Acc |  F1 |  Acc |  F1 |  Acc
Val |  0.484 |  0.775 |  0.470 |  0.738 |  0.344 |  0.611 |  0.387 |  0.677 |  0.341 |  0.784 |  0.300 |  0.660
Test |  0.491 |  0.781 |  0.475 |  0.742 |  0.345 |  0.585 |  0.398 |  0.692 |  0.356 |  0.780 |  0.308 |  0.679
TABLE II: We show model’s validation and test scores on synthetic dataset.
Bold scores are the best.

For the subdivision algorithm, we select the threshold value as $1000$ and
minimum region size as $(2,2)$ and obtain 203 regions which is also the number
of nodes in our graph. Our model uses $16$ input features total, $8$ for the
crime counts for each crime type, $2$ for the locations of nodes, and $6$ for
the calendar features such as weekends and holidays. We set the GCGRU layers
as three, where hidden dimensions of each layer $50,20,10$. The K value is $3$
in each layer, and we set the bias flag ”true” with the symmetric
normalization. We used the library of [26] to implement GCGRU. The number of
layers in MLP is $2$, and the hidden layer contains $64$ nodes. We set the
input sequence length as 10 with a batch size of $5$.

For the training, we use a $0.003$ learning rate, with an early stop tolerance
of $5$. We increase the tolerance count by one when the validation loss does
not decrease at the end of the epoch. In every backward pass, we clip the
gradients by $10$ to prevent exploding gradient problem. Lastly, we used
$0.001$ as L2 loss to regularize the model parameters.

###  IV-C Baseline Models

We compare our model with the models belonging to three different categories.
(i) the conventional time series forecasting methods ARIMA, SVR; (ii)
conventional supervised learning algorithm RF and GPR; (iii) recurrent neural
network architecture ConvLSTM.

Note that ARIMA, SVR, RF, GPR are regression models; however, we make
classification whether a crime event happens or not. Thus, after we make a
regression, we select a threshold value for classification. We select the
threshold value that maximizes the difference between True Positive Rate (TPR)
and False Positive Rate (FPR). The details of the models are as follows:

  1. 1.

Auto-Regressive Integrated Moving Average (ARIMA):[27] We determine the
autoregressive, difference, and moving average parameters according to Akaike
Information Criterion (AIC). The parameters that maximize the AIC are
$(1,0,1)$. Since the model is only applicable to single time series, the model
predicts each driving series of particular cells.

  2. 2.

Support Vector Regression (SVR): [28] We choose an RBF kernel and select the
other parameters with grid search. We feed the previous ten-time step values
of the target series as input features to be fair with the graph model.
Similarly, we apply SVR to individual cells and make predictions for each
particular cell.

  3. 3.

Random Forest(RF): [29] Similarly, we select the parameters with grid-search
and use Mean Squared Error as the criterion. The previous ten-time step values
are the input features of the target series, and we apply the model for each
particular cell.

  4. 4.

Gaussian Process Regression (GPR): [30] We choose this model to compare with
our model better since both models make a gaussian assumption. Model fits
spatial data belonging to the former ten time-steps and regresses the
following events with 1650 dimensioned multivariate gaussian.

  5. 5.

Convolutional Long-Short Term Memory Units (ConvLSTM): [25] We chose this
model to compare our graph-based model with a grid-based structured model,
taking $50\times 33$ shaped input event matrices. We set the input window
length as ten and use the encoder-decoder structure as proposed in [25]. Like
in the graph model training, we use early stopping. Furthermore, we train the
model with both BCE and MSE loss and take the one with the highest score.

###  IV-D Performance Analysis and Results

Tables I and II show the validation and test scores of models for both
datasets. We used the F1 metric,
$2\frac{\mathrm{TPR}*\mathrm{FPR}}{\mathrm{TPR}+\mathrm{FPR}}$, where
$\mathrm{TPR}$ represents the precision and $\mathrm{FPR}$ represents the
recall value. F1 metric measures the overall model performance of how precise
and sensitive a model is. Specifically, we also present the accuracy of our
models since it is essential in crime prediction. We observe that our model
passes the baseline models up to $2-3\%$ for both validation and test scores
in both datasets. We perform a statistical significance test with a p-value of
$0.05$ comparing baseline results with the HRCF and observe that the HRCF
significantly performs better in all metrics. HRCF is not only sensitive to
crime events but also accurate. When we look at the score differences between
years, we can say that HRCF is more adaptive to the change in the dataset.

In real-life dataset results shown in Table I, we observe that classical
approaches offer comparable performances to deep learning architecture. We
provide two reasons for this observation. The first reason is that, as we
increase the resolution, we increase the sparsity in the data. Thus, we expect
to see similar performance from both classical and deep learning
architectures. The second reason is how individual series in particular cells
are auto-correlated. In the PACF graph of crime events, we observe that the
series have high correlation values in the first ten lags.

In the synthetic dataset results shown in Table II, we expect to see higher
performance from HRCF since we sampled the data from multiple Gaussian
distributions. However, the performance of the GPR model is low, and GPR also
assumes the data is coming from a Gaussian distribution. The reason is that
the GPR model is not adaptive to temporal changes and can only capture the
spatial covariates. From this perspective, we can say that HRCF behaves as a
GPR model that can capture both spatial and temporal covariates.

In figure 6, we show how the output of HRCF evolves between epochs. The model
learns generic bounds of crime locations with minor detail on the high crime
rate regions in the first epochs. Then the details on the predictions start to
appear in the 6th epoch. After the 12th epoch, the model makes a detailed
forecast. However, we observe that model binarizes the output predictions,
which means the probability distribution generates likelihoods close to $0$ or
$1$. We expect this behavior since we use the BCE loss that makes negative
predictions closer to $0$ and positive predictions to $1$. Furthermore, this
causes the PDF to assign close values in responsible regions. To assess the
generative property of our model on high resolution, we obtain predictions for
a $100\times 66$ resolution grid from the HRCF model trained on $50\times 33$.
We achieved $36.67$ validation and $36.02$ F1 scores on test sets, which are
$1\%$ higher than the ConvLSTM model.

##  V Conclusion

We studied the problem of high-resolution crime forecasting with a new
generative graph neural network architecture, HRCF. We introduced a
subdivision algorithm to perform balance sampling on the data to create
representative regions. We built our graph according to created regions,
parameterized the problem to a likelihood model, and obtained probability
density functions belonging to each region. We evaluated HRCF on a real-world
and synthetic dataset, and results showed that our model achieves better
performance than baseline models. For future work, first, we plan to discover
the version with different probability distributions. Second, it is promising
to explore dynamic graph creation with a separate graph structure for each
time step. Lastly, we applied HRCF on the crime prediction problem; however,
it is feasible to apply our model to any spatiotemporal data.

## References

  * [1] I. Ehrlich, “On the relation between education and crime,” National Bureau of Economic Research, Tech. Rep., 1975.
  * [2] J. Braithwaite _et al._ , _Crime, shame and reintegration_. Cambridge University Press, 1989.
  * [3] E. B. Patterson, “Poverty, income inequality, and community crime rates,” _Criminology_ , vol. 29, no. 4, pp. 755–776, 1991.
  * [4] R. B. Freeman, “The economics of crime,” _Handbook of labor economics_ , vol. 3, pp. 3529–3571, 1999.
  * [5] J. L. Toole, N. Eagle, and J. B. Plotkin, “Spatiotemporal correlations in criminal offense records,” _ACM Transactions on Intelligent Systems and Technology_ , vol. 2, no. 4, 2011.
  * [6] X. Wang, M. S. Gerber, and D. E. Brown, “Automatic crime prediction using events extracted from twitter posts,” in _International conference on social computing, behavioral-cultural modeling, and prediction_. Springer, 2012, pp. 231–238.
  * [7] M. S. Gerber, “Predicting crime using twitter and kernel density estimation,” _Decision Support Systems_ , vol. 61, pp. 115–125, 2014.
  * [8] H. Wang, D. Kifer, C. Graif, and Z. Li, “Crime rate inference with big data,” _Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ , vol. 13-17-Augu, pp. 635–644, 2016.
  * [9] K. J. Bowers, S. D. Johnson, and K. Pease, “Prospective hot-spotting: The future of crime mapping?” _British Journal of Criminology_ , vol. 44, no. 5, pp. 641–658, 2004.
  * [10] S. Chainey, L. Tompson, and S. Uhlig, “The Utility of Hotspot Mapping for Predicting Spatial Patterns of Crime,” _Security Journal_ , vol. 21, no. 1-2, pp. 4–28, 2008.
  * [11] G. O. Mohler, M. B. Short, P. J. Brantingham, F. P. Schoenberg, and G. E. Tita, “Self-exciting point process modeling of crime,” _Journal of the American Statistical Association_ , vol. 106, no. 493, pp. 100–108, 2011.
  * [12] G. Mohler, “Marked point process hotspot maps for homicide and gun crime prediction in Chicago,” _International Journal of Forecasting_ , vol. 30, no. 3, pp. 491–497, 2014. [Online]. Available: http://dx.doi.org/10.1016/j.ijforecast.2014.01.004
  * [13] N. Du, H. Dai, R. Trivedi, U. Upadhyay, M. Gomez-Rodriguez, and L. Song, “Recurrent Marked Temporal Point Processes,” pp. 1555–1564, 2016.
  * [14] J. Zhang, Y. Zheng, D. Qi, R. Li, and X. Yi, “DNN-Based Prediction Model for Spatio-Temporal Data,” 2016.
  * [15] J. Zhang, Y. Zheng, and D. Qi, “Deep spatio-temporal residual networks for citywide crowd flows prediction,” _31st AAAI Conference on Artificial Intelligence, AAAI 2017_ , pp. 1655–1661, 2017.
  * [16] B. Wang, D. Zhang, D. Zhang, P. J. Brantingham, and A. L. Bertozzi, “Deep Learning for Real Time Crime Forecasting,” pp. 33–36, 2017. [Online]. Available: http://arxiv.org/abs/1707.03340
  * [17] C. Huang, X. Wu, C. Zhang, D. Yin, J. Zhao, and N. V. Chawla, “MIST: A multiview and multimodal spatial-temporal learning framework for citywide abnormal event forecasting,” _The Web Conference 2019 - Proceedings of the World Wide Web Conference, WWW 2019_ , pp. 717–728, 2019.
  * [18] Z. Wu, S. Pan, F. Chen, G. Long, C. Zhang, and S. Y. Philip, “A comprehensive survey on graph neural networks,” _IEEE transactions on neural networks and learning systems_ , vol. 32, no. 1, pp. 4–24, 2020.
  * [19] A. Jain, A. R. Zamir, S. Savarese, and A. Saxena, “Structural-RNN: Deep learning on spatio-temporal graphs,” _Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition_ , vol. 2016-Decem, pp. 5308–5317, 2016.
  * [20] B. Wang, X. Luo, F. Zhang, B. Yuan, A. L. Bertozzi, and P. J. Brantingham, “Graph-Based Deep Modeling and Real Time Forecasting of Sparse Spatio-Temporal Data,” 2018. [Online]. Available: http://arxiv.org/abs/1804.00684
  * [21] J. Sun, M. Yue, Z. Lin, X. Yang, L. Nocera, G. Kahn, and C. Shahabi, “CrimeForecaster: Crime Prediction by Exploiting the Geographical Neighborhoods’ Spatiotemporal Dependencies,” _Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)_ , vol. 12461 LNAI, pp. 52–67, 2021.
  * [22] C. Wang, Z. Lin, X. Yang, J. Sun, M. Yue, and C. Shahabi, “HAGEN: Homophily-Aware Graph Convolutional Recurrent Network for Crime Forecasting,” 2021. [Online]. Available: http://arxiv.org/abs/2109.12846
  * [23] M. Defferrard, X. Bresson, and P. Vandergheynst, “Convolutional neural networks on graphs with fast localized spectral filtering,” _Advances in Neural Information Processing Systems_ , no. Nips, pp. 3844–3852, 2016.
  * [24] Y. Seo, M. Defferrard, P. Vandergheynst, and X. Bresson, “Structured sequence modeling with graph convolutional recurrent networks,” _Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)_ , vol. 11301 LNCS, no. 2013, pp. 362–373, 2018.
  * [25] X. Shi, Z. Chen, H. Wang, D. Y. Yeung, W. K. Wong, and W. C. Woo, “Convolutional LSTM network: A machine learning approach for precipitation nowcasting,” _Advances in Neural Information Processing Systems_ , vol. 2015-Janua, pp. 802–810, 2015.
  * [26] B. Rozemberczki, P. Scherer, Y. He, G. Panagopoulos, A. Riedel, M. Astefanoaei, O. Kiss, F. Beres, , G. Lopez, N. Collignon, and R. Sarkar, “PyTorch Geometric Temporal: Spatiotemporal Signal Processing with Neural Machine Learning Models,” in _Proceedings of the 30th ACM International Conference on Information and Knowledge Management_ , 2021, p. 4564–4573.
  * [27] J. Contreras, R. Espinola, F. J. Nogales, and A. J. Conejo, “Arima models to predict next-day electricity prices,” _IEEE transactions on power systems_ , vol. 18, no. 3, pp. 1014–1020, 2003.
  * [28] C.-C. Chang and C.-J. Lin, “Libsvm: a library for support vector machines,” _ACM transactions on intelligent systems and technology (TIST)_ , vol. 2, no. 3, pp. 1–27, 2011.
  * [29] L. Breiman, “Random forests,” _Machine learning_ , vol. 45, no. 1, pp. 5–32, 2001.
  * [30] C. Rasmussen, “Cki williams gaussian processes for machine learning,” 2006.