# Deep Spatio-Temporal Graph Attention Network for Street-Level 110 Call Incident Prediction
## 4 Problem Statement
### Spatial Embedding  
A GAT is a type of graph neural network that incorporates the attention mechanism. This allows the GAT to simultaneously capture both node features and topological structure features, while also differentiating the importance of various neighboring nodes. This approach addresses a key limitation of GCNs, which treat all the neighboring nodes as having equal importance [47]. The working principle of the GAT involves several key steps: feature aggregation with attention, attention coefficients calculation, feature update and multi-head attention.  
At first, the GAT utilizes a single-layer feedforward neural network as its alignment mechanism to determine the attention scores between node pairs. This approach allows for the calculation of the relative importance of the connections between the nodes in the graph.  
\[scores_{ij}^{l}=LeakyReLU\left(\omega^{T}\left[h_{i}^{l}\middle|\middle|h_{j}^{ l}\right]\right) \tag{1}\]  
where \(h_{i}^{l}\) and \(h_{j}^{l}\) indicate the hidden representations of the node \(v_{i}\) and \(v_{j}\) in the \(l^{th}\) layer, \(v_{j}\) is the neighbor of \(v_{i}\), \(\left|\right|\) represents the operation of concatenation, \(\omega\in R^{2\times M}\) is a learnable weight,\({}^{T}\) denotes the transposition operation, and \(LeakyReLU\) is a non-linear activation function.  
In this step, the GAT restricts its computation to masked attention, focusing solely on each node's immediate, first-order neighbors through the use of localized attention mechanisms. Then, the GAT uses the following equation to normalize the attention scores:  
\[\alpha_{ij}=softmax_{j}\big{(}scores_{ij}\big{)}=\frac{exp\big{(}scores_{ij} \big{)}}{\sum_{k\in N_{i}}exp\big{(}scores_{ik}\big{)}} \tag{2}\]  
where \(v_{j}\) and \(v_{k}\) are the neighboring nodes of node \(v_{i}\).  
Figure 5: Operational process of the dual graph method: (**a**) a simplified real-world street network, the numbers represent street segment identifiers; and (**b**) the transformed network, the numbers next to the nodes correspond to the street segments in Figure (**a**).  
After obtaining the normalized attention coefficients \(\alpha_{ij}\), these values are utilized to compute a weighted linear combination of the associated features. This combined result is then passed through a non-linear activation function \(\sigma\), producing the final output features:  
\[\overrightarrow{h_{i}^{\prime}}=\sigma\left(\sum_{j\in N_{i}}\alpha_{ij}W \overrightarrow{h_{j}}\right) \tag{3}\]  
To enhance the stability of the learning process, a multi-head attention mechanism can be incorporated, building upon the self-attention process. In this approach, \(K\) independent attention mechanisms are applied to perform the transformation described in Equation (3). The resulting features from each attention head are then concatenated to produce the final output feature representation.  
\[\overrightarrow{h_{i}^{\prime}}=\begin{array}{c}K\\ k=1\end{array}\sigma\left(\sum_{j\in N_{i}}\alpha_{ij}^{k}W\overrightarrow{h_ {j}}\right) \tag{4}\]  
where \(\mid\mid\) represents the concatenation, \(\alpha_{ij}^{k}\) represents the normalized attention coefficient generated by the k-th attention mechanism \(\alpha^{k}\), and \(W^{k}\) denotes the corresponding weight matrix.  
Upon completing the sequence of operations outlined, the GAT produces the final output, which is the embedding representation of a given node within the overall graph structure. The embedding encapsulates not only the spatial attributes of the node but also the impact of its neighboring nodes. It integrates information derived from the graph's overall structure and the features of adjacent nodes, providing a comprehensive representation.