Explainable Spatio-Temporal Graph Neural Networks
Spatio-temporal graph neural networks (STGNNs) have gained popularity as a
powerful tool for effectively modeling spatio-temporal dependencies in diverse
real-world urban applications, including intelligent transportation and public
safety. However, the black-box nature of STGNNs limits their interpretability,
hindering their application in scenarios related to urban resource allocation
and policy formulation. To bridge this gap, we propose an Explainable
Spatio-Temporal Graph Neural Networks (STExplainer) framework that enhances
STGNNs with inherent explainability, enabling them to provide accurate
predictions and faithful explanations simultaneously. Our framework integrates
a unified spatio-temporal graph attention network with a positional information
fusion layer as the STG encoder and decoder, respectively. Furthermore, we
propose a structure distillation approach based on the Graph Information
Bottleneck (GIB) principle with an explainable objective, which is instantiated
by the STG encoder and decoder. Through extensive experiments, we demonstrate
that our STExplainer outperforms state-of-the-art baselines in terms of
predictive accuracy and explainability metrics (i.e., sparsity and fidelity) on
traffic and crime prediction tasks. Furthermore, our model exhibits superior
representation ability in alleviating data missing and sparsity issues. The
implementation code is available at: https://github.com/HKUDS/STExplainer.
Jiabin Tang, Lianghao Xia, Chao Huang
# Explainable Spatio-Temporal Graph Neural Networks

###### Abstract.

Spatio-temporal graph neural networks (STGNNs) have gained popularity as a powerful tool for effectively modeling spatio-temporal dependencies in diverse real-world urban applications, including intelligent transportation and public safety. However, the black-box nature of STGNNs limits their interpretability, hindering their application in scenarios related to urban resource allocation and policy formulation. To bridge this gap, we propose an Explainable Spatio-Temporal Graph Neural Networks (STExplainer) framework that enhances STGNNs with inherent explainability, enabling them to provide accurate predictions and faithful explanations simultaneously. Our framework integrates a unified spatio-temporal graph attention network with a positional information fusion layer as the STG encoder and decoder, respectively. Furthermore, we propose a structure distillation approach based on the Graph Information Bottleneck (GIB) principle with an explainable objective, which is instantiated by the STG encoder and decoder. Through extensive experiments, we demonstrate that our STExplainer outperforms state-of-the-art baselines in terms of predictive accuracy and explainability metrics (_i.e._, sparsity and fidelity) on traffic and crime prediction tasks. Furthermore, our model exhibits superior representation ability in alleviating data missing and sparsity issues. The implementation code is available at: [https://github.com/HKUDS/STExplainer](https://github.com/HKUDS/STExplainer).

Spatio-Temporal Data Mining; Graph Neural Networks; Urban Computing; Explainable AI +
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.

+
Footnote †: c)hao Huang is the corresponding author.
for improved deployment of spatio-temporal models in real-world scenarios. Human-interpretable explanations can assist decision-makers in effectively utilizing spatio-temporal models for various downstream tasks, including urban planning, intelligent transportation systems, and emergency resource scheduling. To address this crucial gap, we propose the development of explainability models specifically tailored for STGNNs. However, existing graph explainability models primarily focus on classification tasks, such as BA-Shapes, BA-Community, and BA-Cycles(Coles, 2018), and there is currently a lack of ground-truth datasets available for spatio-temporal explainability. Therefore, we need to tackle the following key questions to advance the field of spatio-temporal explainability:

**Q1:** How can the explainability of STGNN be defined?

**Q2:** How to endow STGNN with spatial and temporal explainability to provide insights underlying cross-region and time dependencies?

**Q3:** How to evaluate the performance of STGNN in terms of explainability in the absence of ground-truth labels?

**Contribution.** In this study, we address the aforementioned challenges by presenting Explainable Spatio-Temporal Graph Neural Networks (STExplainer). Our framework offers scalability, interpretability, and generalization capabilities. We achieve this by breaking down the STG into separate spatial and temporal graphs and employing a unified spatio-temporal graph attention network to encode the spatial and temporal dynamics. Furthermore, we integrate spatio-temporal positional information into the STG decoder layer. In our approach, we define explainability as the ability to identify influential spatial and temporal subgraphs that have a significant impact on predictive results. To accomplish this, we propose utilizing the spatio-temporal Graph Information Bottleneck (GIB) with a structure-distilled explainable objective. We employ variational approximation to make the objective tractable and instantiate the variational bounds with our proposed STG encoder and decoder. To evaluate the performance of STGNN in terms of explainability without the availability of ground-truth, we adapt two metrics, _Sparsity_ and _Fidelity_, to suit the explainable evaluation of STGNN.

In summary, our work makes the following contributions:

* To the best of our knowledge, we present the first systematic investigation into the explainability of STGNN, specifically focusing on identifying the most influential spatial and temporal subgraphs in relation to the prediction results.
* We propose a novel explainable framework STExplainer, which integrates the structure-distilled graph information bottleneck principle with a unified spatio-temporal attentive encoder and decoder to enhance the explainability and generalization of STGNN.
* In our proposed STExplainer framework, we employ the spatio-temporal graph information bottleneck principle with a structure-distilled explainable objective to control the information flow and characterize it with a unified STGNN. We utilize graph attention networks and a position-aware information fusion layer to encode both interpretable and generalizable STG representations.
* We conduct extensive experiments across various settings to evaluate the performance of STExplainer in terms of predictive accuracy and explainability. Comparisons over various datasets demonstrate that our model outperforms state-of-the-art baselines.

## 2. Preliminaries

**Spatio-Temporal Graph Forecasting.** In Spatio-Temporal Graph (STG) forecasting, we analyze a scenario with \(N\) nodes representing regions and \(T\) time steps. The spatio-temporal graph \(\mathcal{G}=(\mathcal{V},\mathcal{E},\mathbf{A},\mathbf{X})\) is formed, where \(\mathcal{V}\) denotes the set of \(N\) nodes representing regions, \(\mathcal{E}\) represents the edges recorded by the adjacency matrix \(\mathbf{A}\in\mathbb{R}^{N\times N}\), and \(\mathbf{X}\in\mathbb{R}^{T\times N\times F}\) is the feature matrix associated with attributes like traffic volumes or crime occurrences. Here, \(F\) represents the feature dimensions, and \(T\) represents the time steps. With these definitions in place, we can formally define the task of spatial-temporal graph forecasting as follows:

**Problem Statement**. In STG forecasting, the goal is to learn a predictive function denoted as \(f\). This function aims to predict specific attributes of the spatio-temporal graph in the next \(L^{\prime}\) time steps, given the previous \(L\) historical observations.

\[\mathbf{Y}_{t:t+L^{\prime}-1}=f(\mathcal{G}(\mathcal{V},\mathcal{E},\mathbf{ A},\mathbf{X}_{t-Lt-1})) \tag{1}\]

\(\mathbf{X}\in\mathbb{R}^{T\times N\times F}\) is the historical observations with \(F\) feature dimensions from time step \(t-L\) to \(t-1\). \(\mathbf{Y}\in\mathbb{R}^{L^{\prime}\times N\times F^{\prime}}\) represents the predictions with \(F^{\prime}\) feature dimensions for the next \(L^{\prime}\) time steps.

**Explainable Graph Neural Networks.** The research community has recently been captivated by the field of explainable Artificial Intelligence (XAI) for Graphs, which focuses on providing reliable and interpretable explanations to enhance the trustworthiness of black-box Graph Neural Network (GNN) models. The primary objective of XAI for Graphs is to foster a sense of trust and enable effective utilization of these models by human users (Sutskever et al., 2017). Motivated by previous studies on the explainability of canonical graphs (Coles, 2018), we propose to enhance the explainability of STGNN by searching for subgraph \(\mathcal{G}_{S}\) based on the STG \(\mathcal{G}\) and the ground-truth label Y:

\[\mathcal{G}_{S}=\operatorname*{arg\,max}_{\mathcal{G}_{S}}I(\mathbf{Y}, \mathcal{G}_{S})=H(\mathbf{Y})-H(\mathbf{Y}|\mathcal{G}_{S}) \tag{2}\]

where \(I(\cdot)\) denotes the mutual information function, \(H(\cdot)\) represents the information entropy, \(\mathcal{G}_{S}=(\mathcal{V}_{S},\mathcal{E}_{S},\mathbf{A}_{S},\mathbf{X}_{S})\) represents the subgraph of \(\mathcal{G}\) with the sub-node set \(\mathcal{V}_{S}\), the sub-edge set \(\mathcal{E}_{S}\), the sub-adjacency matrix \(A_{S}\) and the sub-feature matrix \(\mathbf{X}_{S}\). The model is optimized to find subgraph \(\mathcal{G}_{S}\) which makes the most prominent contribution to predictions made by model \(f\), which helps humans comprehend the black-box GNN model \(f\) intuitively. Next, we introduce the definition of two categories of explainability approaches on graphs, _i.e._, _post-hoc_ and _intrinsic_, as follows.

(i) **Post-hoc.** With the GNN model \(f\), the _post-hoc_ model aims to learn an explainability function \(\Gamma\) to identify the subgraph \(\mathcal{G}_{S}\) contributing to the performance of \(f\) the most:

\[\mathcal{G}_{S}=\Gamma(\mathcal{G},\mathbf{Y},f)\quad\text{s.t.}\max_{ \mathcal{G}_{S}}I(\mathbf{Y},\mathcal{G}_{S}) \tag{3}\]

(ii) **Intrinsic.** Distinct from _post-hoc_ methods, the goal of _intrinsic_ approaches is to learn a unified model \(f^{\prime}\) to simultaneously predict the target graph signals and identify the subgraph \(\mathcal{G}_{S}\) that impacts the model \(f^{\prime}\) the most, which is defined as below:

\[\hat{\mathbf{Y}},\mathcal{G}_{S}=f^{\prime}(\mathcal{G})\quad\text{s.t.}\min \mathcal{L}(\mathbf{Y},\hat{\mathbf{Y}})\land\max_{\mathcal{G}_{S}}I(\mathbf{ Y},\mathcal{G}_{S}) \tag{4}\]
where \(\mathcal{L}\) denotes a specific loss function supervising the predictive task on graphs, and \(\hat{\Upsilon}\) presents the predicted results of the model. We summarize the notations frequently used in our paper in Table 1.

## 3. Methodology

In this section, we provide a detailed description of the technical aspects and theoretical analysis of our STExplainer framework. Our framework encompasses a unified STGNN encoder that employs spatio-temporal graph attention networks to reason about spatio-temporal dependencies. Additionally, we propose the structure-distilled Graph Information Bottleneck (GIB) for STG to select explainable subgraph structures benefiting the downstream forecasting. The overall architecture of STExplainer is illustrated in Figure 1.

### Spatio-Temporal Graph Attention Networks

#### 3.1.1. **Spatial Relation Learning**

Inspired by GNN's strength of reasoning the complicated correlations (Srivastava et al., 2015; Wang et al., 2016; Wang et al., 2017), especially in spatio-temporal modeling (Srivastava et al., 2015; Wang et al., 2016), we propose a unified GNN encoder which adapts graph attention networks (Wang et al., 2016) to capture the spatio-temporal dependencies. Following (Wang et al., 2016), we could employ a unified GNN-based framework to capture spatio-temporal dependencies on a unified spatio-temporal graph structure \(\mathbf{A}\in\mathbb{R}^{TN\times TN}\). To avoid the enormous time complexity of STG learning, we decouple the joint graph into a temporal graph and a spatial graph. Primarily, STG feature matrix \(\mathbf{X}\in\mathbb{R}^{T\times N\times F}\) is embeded into a \(d\)-dimensional latent space with the fully connected layer:

\[\mathbf{X}^{(0)}=\mathbf{X}\cdot\mathbf{W}^{(0)}+\mathbf{b}^{(0)} \tag{5}\]

where \(\mathbf{X}^{(0)}\in\mathbb{R}^{T\times N\times d}\) represents initial embeddings of the STG. \(\mathbf{W}^{(0)}\in\mathbb{R}^{F\times d}\), \(\mathbf{b}^{(0)}\in\mathbb{R}^{d}\) denote the weight and bias matrices. Furthermore, to individually encode spatial and temporal dynamics with our GAT, \(\mathbf{X}^{(0)}\) is converted to spatial embeddings \(\mathbf{X}^{(s)}=\{\mathbf{x}^{(s)}_{j}\in\mathbb{R}^{d_{s}},1\leq j\leq N\}\) employing linear transformation by:

\[\mathbf{x}^{(s)}_{j}=\sum_{i=1}^{T}\mathbf{X}^{(0)}_{i,j,:}\mathbf{W}^{(s)}_{ i}+\mathbf{b}^{(s)} \tag{6}\]

where \(\mathbf{W}^{(s)}\in\mathbb{R}^{T\times d\times d_{s}}\) and \(\mathbf{b}^{(s)}\in\mathbb{R}^{d_{s}}\) indicate weight and bias parameters. In this stage, we utilize the spatial subgraph in the STG \(\mathcal{G}\), which is defined by \(\mathcal{G}^{(s)}=(\mathcal{V}^{(s)},\mathcal{E}^{(s)},\mathbf{A}^{(s)}, \mathbf{X}^{(s)})\), where \(\mathbf{A}^{(s)}\in\mathbb{R}^{N\times N}\) denotes the spatial adjacency matrix recording the spatial node-wise correlations. Regarding the spatial graph reasoning, we employ GAT with stacked multi-head graph attention layers, where the \(K\)-head graph attention layer is defined as below:

\[\begin{split}\mathbf{h}^{(s)}_{j}=\sum_{k=1}^{K}\sum_{j\prime} \sum_{\mathcal{N}(j)\cup\{j\}}\alpha^{k}_{j,j^{\prime}}\cdot\mathbf{W}^{k} \mathbf{x}^{(s)}_{j^{\prime}}\\ \alpha_{j,j^{\prime}}=\frac{\exp(\sigma(\vec{a}^{\top}[ \mathbf{W}\mathbf{x}^{(s)}_{j}+\mathbf{W}\mathbf{x}^{(s)}_{j^{\prime}}]))}{ \sum_{j^{\prime}\in\mathcal{N}(j)\cup\{j\}}\exp(\sigma(\vec{a}^{\top}[ \mathbf{W}\mathbf{x}^{(s)}_{j}+\mathbf{W}\mathbf{x}^{(s)}_{j^{\prime}}]))} \end{split} \tag{7}\]

where \(\mathcal{N}(j)\) represents the set of neighbors of the \(j\)-th region according to \(\mathbf{A}^{(s)}\), \(\vec{a}\in\mathbb{R}^{d_{s}}\) represents the weight vector, \(\mathbf{W}\in\mathbb{R}^{d_{s}\times d_{s}}\) indicates the weight parameters, and \(\sigma(\cdot)\) denotes the LeakyReLU activation function. With multiple GAT layers, we gain the extracted spatial embeddings \(\mathbf{H}^{(s)}=\{\widehat{h}^{(s)}_{j}\in\mathbb{R}^{d_{s}},1\leq j\leq N\}\). Then we transform \(\mathbf{H}^{(s)}\) into the spatio-temporal embedding space to get \(\mathbf{H}^{\prime(s)}\in\mathbb{R}^{T\times N\times d}\) utilizing fully-connected layer with weight matrix \(\mathbf{W}^{(1)}\in\mathbb{R}^{T\times d\times d_{s}}\) and bias parameters \(\mathbf{B}^{(1)}\in\mathbb{R}^{T\times d}\) as:

\[\mathbf{H}^{\prime(s)}_{i,j,:}=\mathbf{W}^{(1)}_{i}\cdot\mathbf{h}^{(s)}_{j}+ \mathbf{B}^{(1)}_{i} \tag{8}\]

#### 3.1.2. **Temporal Relation Learning**

We follow the similar relation learning paradigm to model the temporal graph \(\mathcal{G}^{(t)}=(\mathcal{V}^{(t)},\mathcal{E}^{(t)},\mathbf{A}^{(t)}, \mathbf{X}^{(t)})\), where \(\mathbf{A}^{(t)}\in\mathbb{R}^{T\times T}\) indicates the temporal adjacency matrix revealing the correlations among time steps, and \(\mathbf{X}^{(t)}=\{\widetilde{x}^{(t)}_{i}\in\mathbb{R}^{d_{t}},1\leq i\leq T\}\) represents the temporal feature matrix. \(\mathbf{X}^{(t)}\) is transformed from \(\mathbf{H}^{\prime(s)}\) by utilizing the similar fully connected layer as Eq 6. To model the temporal dynamics, stacked multi-head GAT layers defined analogously as Eq 7 are utilized to generate the temporal feature matrix \(\mathbf{H}^{(t)}=\{\widehat{h}^{(t)}_{i}\in\mathbb{R}^{d},1\leq i\leq T\}\). Eventually, we transform the temporal features \(\mathbf{H}^{(t)}\) into the final spatio-temporal embedding matrix \(\mathbf{H}=\mathbf{H}^{\prime(t)}\in\mathbb{R}^{T\times N\times d}\) adopting the similar transformation function as Eq 8. So, we summarize how to construct spatial and temporal graphs as follows: (i) **spatial graph (\(\mathbf{A}^{(s)}\)):** Spatial graph represents the correlations between spatial units. For the two common types of spatio-temporal prediction, _i.e._, graph-based and grid-based (Ghahramani et al., 2017), we can construct graphs using a threshold Gaussian kernel (Srivastava et al., 2015) and considering neighboring regions as neighbors (Srivastava et al., 2015; Wang et al., 2016), respectively. (ii) **temporal graph (\(\mathbf{A}^{(t)}\)):** Temporal graph represents the correlations between temporal representations at different time steps. Formally, if the historical time step is \(T\), we have temporal graph \(A^{(t)}\in\mathbb{R}^{T\times T}\) and \(A^{(t)}_{i,j}=1\) for arbitrary \(i,j\). This means that we assume that every time step influence others originally. Applying GAT for message passing on the temporal graph is equivalent to existing works (Srivastava et al., 2015) that utilize self-attention to capture temporal correlations.

#### 3.1.3. **Position-Aware STG Prediction**

To enhance the modeling of spatio-temporal contexts in the model inference phase of our STExplainer, we propose to inject spatial and temporal positional embeddings into the foregoing STG relational embeddings \(\mathbf{H}\). In specific, multiple free-form embeddings are leveraged by our STExplainer: the region representations \(\mathbf{E}^{(s)}\in\mathbb{R}^{N\times d}\), the _time of day_ embeddings \(\mathbf{E}^{(ToD)}\in\mathbb{R}^{T\times d}\), and the _day of week_ embeddings \(\mathbf{E}^{DoW}\in\mathbb{R}^{T\times d}\). For implementation, we randomly initialize a tensor

\begin{table}
\begin{tabular}{c|c} \hline
**Notions** & **Description** \\ \hline \(\mathbf{X}\in\mathbb{R}^{TN\times N}\) & Original STG feature matrix. \\  & Initialized STG embeddings. \\ \(\mathbf{X}^{(0)}=(\mathbf{x}^{(0)}_{i}\in\mathbb{R}^{d_{s}},1\leq j\leq N)\) & Spatial feature matrix. \\ \(\mathbf{H}^{(0)}=(\mathbf{x}^{(0)}_{i}\in\mathbb{R}^{d_{s}},1\leq j\leq N)\) & Enstructed spatial embedding. \\ \(\mathbf{H}^{(0)}=(\mathbf{x}^{(0)}_{i}\in\mathbb{R}^{d_{s}},1\leq j\leq N)\) & Enstructed spatial embedding. \\ \(\mathbf{H}^{(0)}=(\mathbf{x}^{(0)}_{i}\in\mathbb{R}^{d_{s}},1\leq j\leq N)\) & Enstructed spatial embedding. \\ \(\mathbf{H}^{(0)}=(\mathbf{x}^{(0)}_{i}\in\mathbb{R}^{d_{s}},1\leq j\leq N)\) & Enstructed spatial embedding. \\ \(\mathbf{H}^{(0)}=(\mathbf{x}^{(0)}_{i}\in\mathbb{R}^{d_{s}},1\leq j\leq N)\) & Enstructed spatial embedding. \\ \(\mathbf{H}^{(0)}=(\mathbf{x}^{(0)}_{i}\in\mathbb{R}^{d_{s}},1\leq j\leq N)\) & Enstructed spatial embedding. \\ \(\mathbf{H}^{(0)}=(\mathbf{x}^{(0)}_{i}\in\mathbb{R}^{d_{s}},1\leq j\leq N)\) & Enstructed spatial embedding. \\ \(\mathbf{H}^{(0)}=(\mathbf{x}^{(0)}_{i}\in\mathbb{R}^{d_{s}},1\leq j\leq N)\) & The final output feature matrix of the proposed STG encoder. \\ \(\mathbf{G}^{(0)}=(\mathbf{x}^{(0)}_{i}\in\mathbb{R}^{N\times N},\) & Spatial graph with spatial adjacency matrix \(A^{(0)}\in\mathbb{R}^{N\times N}\). \\ \(\mathbf{E}^{(0)}=(\mathbf{x}^{(0)}_{i}\in\mathbb{R}^{N\times N},\) & Temporal graph with temporal embedding matrix \(A^{(0)}
\(E^{(s)}\in\mathbb{R}^{N\times D}\), and the value of the tensor could be updated during back propagation (i.e., learnable). As to temporal positional embeddings, we randomly initialize a _time of day_ tensor \(E_{\text{all}}^{(ToD)}\in\mathbb{R}^{288\times D}\) and a _day of week_ tensor \(E_{\text{all}}^{(DoW)}\in\mathbb{R}^{7\times D}\), where 288 denotes a day has 288 time steps (for 5 min interval) and 7 denotes a week has 7 days. The input _time of day_ and _day of week_ index of the STG query _time of day_ and _day of week_ tensors to obtain temporal positional embeddings. Then, STExplainer makes predictions as follows:

\[\mathbf{Y}=\mathbf{MLP}_{1}(\mathbf{H}\|\mathbf{E}^{(s)}\|\mathbf{E}^{(ToD)} \|\mathbf{E}^{(DoW)}\|\mathbf{MLP}_{2}(\mathbf{X})) \tag{9}\]

where \(\|\) denotes concatenation, \(\mathbf{MLP}_{1}(\cdot)\) and \(\mathbf{MLP}_{2}(\cdot)\) denote two multi-layer perceptrons for making final predictions and leveraging low-level features \(\mathbf{X}\), respectively. \(\mathbf{Y}\) denotes the predictions for future STG attributes using the position-aware STG embeddings.

### Spatio-Temporal Explainability with GIB

#### 3.2.1. GIB-based Explainable Structure Distillation

The Graph Information Bottleneck (GIB) technique is designed to compress graph-structured data into low-dimensional representations that exhibit strong correlation with downstream labels. These compressed representations capture a subset of the original information while effectively accounting for the labels in subsequent tasks. As a result, GIB has gained recognition as an explainable model in certain literature, such as (Zhu et al., 2017; Wang et al., 2018). The underlying principle of GIB is to optimize the embeddings by minimizing the following objective:

\[\min_{\mathbb{P}(\mathbf{Z}_{X}|\mathcal{G})}-I(Y,\mathbf{Z}_{X})+\beta I( \mathcal{G},\mathbf{Z}_{X}) \tag{10}\]

The hidden representations of the graph feature matrix \(\mathbf{X}\) are denoted as \(\mathbf{Z}_{X}\). While the conventional GIB generates low-dimensional representations that capture the reasoning behind downstream labels, these dense hidden embeddings are often challenging for humans to comprehend. This limitation significantly restricts the applicability of using the conventional GIB for model interpretation.

In order to address the objective of developing explainable spatio-temporal graph (STG) models, as outlined in Eq 2, we draw inspiration from (Zhu et al., 2017) and propose the structure-distilled GIB approach. This approach applies the Information Bottleneck (IB) principle to distilled subgraph Structures, enabling the acquisition of a small subset of interpretable STG structures. Specifically, the objective of our structure-distilled GIB is defined as follows:

\[\min_{\mathbb{P}(\mathcal{G}|\mathcal{G})}-I(\mathbf{Y},\mathcal{G}_{S})+ \beta\cdot I(\mathcal{G},\mathcal{G}_{S}) \tag{11}\]

The subgraph \(\mathcal{G}_{S}=(\mathcal{V}_{S},\mathcal{E}_{S},A_{S},\mathbf{X}_{S})\) represents the distilled subgraph obtained from the conditional probability distribution given the original graph \(\mathcal{G}\). In real-world scenarios, the graph structures play a crucial role in spatio-temporal graphs and are easier for humans to interpret as a rationale for model inference. Therefore, we prioritize the use of subgraph structures for interpretation purposes and simplify the objective presented in Equation 11 by defining the subgraph as \(\mathcal{G}_{S}=(\mathcal{V}_{S},\mathcal{E}_{S},A_{S},\mathbf{X})\).

#### 3.2.2. Variational Bounds for Structure-Distilled GIB

Since the mutual information terms \(I(\mathbf{Y},\mathcal{G}_{S})\) and \(I(\mathcal{G},\mathcal{G}_{S})\) are intractable, we resort to using variational bounds to estimate each term in the objective. For the lower bound of the first term \(I(\mathbf{Y},\mathcal{G}_{S})\), we can utilize the fact that \(\operatorname{KL}[\mathbb{P}(\mathbf{Y}|\mathcal{G}_{S}),\mathbb{Q}_{1}( \mathbf{Y}|\mathcal{G}_{S})]\geq 0\), where \(\mathbb{Q}_{1}(\mathbf{Y}|\mathcal{G}_{S})\) represents an arbitrary distribution of \(\mathbf{Y}\) given \(\mathcal{G}_{S}\). Thus, we obtain:

\[I(\mathbf{Y},\mathcal{G}_{S})=\mathbb{E}_{\mathbf{Y},\mathcal{G}_{S}}[\log \frac{\mathbb{P}(\mathbf{Y}|\mathcal{G}_{S})}{\mathbb{P}(\mathbf{Y})}]\geq \mathbb{E}_{\mathbf{Y},\mathcal{G}_{S}}[\log\mathbb{Q}_{1}(\mathbf{Y}| \mathcal{G}_{S})] \tag{12}\]

The expression \(\log\mathbb{Q}_{1}(\mathbf{Y}|\mathcal{G}_{S})\) also represents the variational approximation of \(\mathbb{P}(\mathbf{Y}|\mathcal{G}_{S})\), which can be modeled using neural networks within an end-to-end framework. Specifically, by \(\log\mathbb{Q}_{1}(\mathbf{Y}|\mathcal{G}_{S})\) aims to predict the results based on the subgraph \(\mathcal{G}_{S}\). Regarding the upper bound of the second term \(I(\mathcal{G},\mathcal{G}_{S})\), we can establish that \(\operatorname{KL}[\mathbb{P}(\mathcal{G}_{S}),\mathbb{Q}_{2}(\mathcal{G}_{S}) ]\geq 0\) holds true. We can formalize it as follows:

\[I(\mathcal{G},\mathcal{G}_{S})=\mathbb{E}_{\mathcal{G},\mathcal{G}_{S}}[\log \frac{\mathbb{P}(\mathcal{G}_{S}|\mathcal{G})}{\mathbb{P}(\mathcal{G}_{S})}] \leq\mathbb{E}_{\mathcal{G}}[\operatorname{KL}(\mathbb{P}(\mathcal{G}_{S}| \mathcal{G})\|\mathbb{Q}_{2}(\mathcal{G}_{S}))] \tag{13}\]

Figure 1. The overall framework of the proposed STExplainer framework is as follows: the STG is decoupled into spatial and temporal graph structures to capture spatio-temporal features. These structures are then fed into the structure-distilled GIB module with the ST-Edge Encoder, resulting in spatial and temporal graph edge representations. Additionally, ST-Edge Sampling is employed to obtain explainable spatial and temporal graph structures. Finally, ST-GAT is utilized to encode spatial and temporal dependencies on the explainable structures, ultimately producing the final results.
\(\mathbb{Q}_{2}(\mathcal{G}_{S})\) is the variational approximation for the marginal distribution \(\mathbb{P}(\mathcal{G}_{S})\). The ultimate objective for Eq 11 is defined as:

\[\min_{\mathbb{P}(\mathcal{G}_{S}|\mathcal{G})}-\mathbb{E}_{\mathbf{Y },\mathcal{G}_{S}}[\log\mathbb{Q}_{1}(\mathbf{Y}|\mathcal{G}_{S})]+\beta \mathbb{E}_{\mathcal{G}}[\mathrm{KL}(\mathbb{P}(\mathcal{G}_{S}|\mathcal{G}) \|\mathbb{Q}_{2}(\mathcal{G}_{S}))] \tag{14}\]

### Spatio-Temporal GIB Characterization

To minimize the upper bound in Eq 14 for our structure-distilled GIB, it is necessary to characterize the distributions \(\mathbb{P}(\mathcal{G}_{S}|\mathcal{G})\), \(\mathbb{Q}_{1}(\mathbf{Y}|\mathcal{G}_{S})\) and \(\mathbb{Q}_{2}(\mathcal{G}_{S})\).

i) \(\mathbb{P}(\mathcal{G}_{S}|\mathcal{G})\): To extract the influential subgraph \(\mathcal{G}_{S}\) from the original graph \(\mathcal{G}\), we incorporate randomness into the instantiated networks. In particular, we begin by embedding the spatio-temporal graphs \(\mathcal{G}^{(s)}\) and \(\mathcal{G}^{(t)}\) using a unified STGNN encoder. This process yields the spatio-temporal node representations \(\mathbf{H}^{(s)}=\{\widetilde{h}^{(s)}_{j}\in\mathbb{R}^{d_{s}}\}\) and \(\mathbf{H}^{(t)}=\{\widetilde{h}^{(t)}_{i}\in\mathbb{R}^{d_{t}}\}\). Next, we employ the concatenation operator \(|\) and an MLP \(\mathcal{F}_{\Theta}\) with parameters \(\Theta\) to encode the spatio-temporal edge representation. This encoding step is defined as:

\[\widetilde{h}^{(s)}_{uu}=\mathcal{F}_{\Theta^{(s)}}(\widetilde{h} ^{(s)}_{u}|\widetilde{h}^{(s)}_{u}),\mathrm{s.t.},u\in\mathcal{N}(v)\] \[\widetilde{h}^{(t)}_{uu}=\mathcal{F}_{\Theta^{(t)}}(\widetilde{h} ^{(t)}_{u}|\widetilde{h}^{(t)}_{u}),\mathrm{s.t.},u\in\mathcal{N}(v) \tag{15}\]

where \(\mathcal{N}(v)\) denotes the neighbor set of node \(v\). Subsequently, we employ the Gumbel-Softmax reparameterization trick (Gumbel and Softmax, 1957; Gumbel and Softmax, 1957) to compute the spatio-temporal probabilities \(p^{(s)}_{uu}\) and \(p^{(t)}_{uu}\) for each edge in a differentiable manner. This enables us to have:

\[p^{(s)}_{uu}=\sigma((\widetilde{h}^{(s)}_{uu}+g)/\tau),\quad p^{(t)}_{uu}= \sigma((\widetilde{h}^{(t)}_{uu}+g)/\tau) \tag{16}\]

where \(g\) is a set of i.i.d. samples drawn from a Gumbel(0,1) distribution, and \(\tau\) is the temperature parameter that controls the smoothness of the resulting distribution. Consequently, we obtain the spatio-temporal explainable subgraph structures \(\mathbf{A}^{(s)}_{S}\) and \(\mathbf{A}^{(t)}_{S}\):

\[\mathbf{A}^{(s)}_{S}=\alpha^{(s)}\odot A^{(s)},\quad\alpha^{(s)}_ {uu}\sim\mathrm{Bern}(p^{(s)}_{uu})\] \[\mathbf{A}^{(t)}_{S}=\alpha^{(t)}\odot A^{(t)},\quad\alpha^{(t)}_ {uu}\sim\mathrm{Bern}(p^{(t)}_{uu}) \tag{17}\]

The symbol \(\odot\) is the element-wise product. \(\alpha^{(s)}\) and \(\alpha^{(t)}\) are the spatio-temporal subgraph selectors used to extract the explainable subgraphs. Consequently, the instantiation of the spatio-temporal term \(\mathbb{P}(\mathcal{G}_{S}|\mathcal{G})\) is as follows:

\[\mathbb{P}(\mathcal{G}^{(s)}_{S}|\mathcal{G}^{(s)})=\prod_{u,u\in \mathcal{V}^{(s)}}\mathbb{P}(\alpha^{(s)}_{uu}|p^{(s)}_{uu})\] \[\mathbb{P}(\mathcal{G}^{(t)}_{S}|\mathcal{G}^{(t)})=\prod_{u,u\in \mathcal{V}^{(t)}}\mathbb{P}(\alpha^{(t)}_{uu}|p^{(t)}_{uu}) \tag{18}\]

**ii) \(\mathbb{Q}_{1}(\mathbf{Y}|\mathcal{G}_{S})\)**: The goal of this variational approximation is to infer the spatio-temporal dynamics based solely on the extracted spatio-temporal explainable subgraphs. To achieve this, we utilize the proposed spatio-temporal graph attention network (ST-GAT) architecture, which consists of the same set of learnable parameters as introduced in Section 3.1. It is important to note that when calculating \(\mathbb{Q}_{1}(\mathbf{Y}|\mathcal{G}_{S})\), our ST-GAT performs message propagation exclusively along the sampled explainable edges and nodes.

**iii) \(\mathbb{Q}_{2}(\mathcal{G}_{S})\)**: Regarding the prior distribution \(\mathbb{Q}_{2}(\mathcal{G}_{S})\), we have the following formalizations for the spatial and temporal graphs:

\[\mathbb{Q}_{2}(\mathcal{G}^{(s)}_{S})=\sum_{\mathcal{G}^{(t)}} \mathbb{P}(\mathcal{G}^{(s)},\mathcal{G}^{(s)}_{S})=\sum_{\mathcal{G}^{(t)}} \mathbb{P}(\mathcal{G}^{(s)}_{S}|\mathcal{G}^{(s)})\mathbb{P}(\mathcal{G}^{(s)})\] \[\mathbb{Q}_{2}(\mathcal{G}^{(t)}_{S})=\sum_{\mathcal{G}^{(t)}} \mathbb{P}(\mathcal{G}^{(t)},\mathcal{G}^{(t)}_{S})=\sum_{\mathcal{G}^{(t)}} \mathbb{P}(\mathcal{G}^{(t)}_{S}|\mathcal{G}^{(t)})\mathbb{P}(\mathcal{G}^{(t)}) \tag{19}\]

Following (Gumbel and Softmax, 1957), for the given spatio-temporal graphs \(\mathcal{G}^{(s)}\) with \(n^{(s)}\) edges, we sample prior spatio-temporal selectors \(\alpha^{\prime(s)}\) and \(\alpha^{\prime(t)}\), which is defined as below:

\[\alpha^{\prime(s)}\sim\mathrm{Bern}(r^{(s)}),\alpha^{\prime(t)} \sim\mathrm{Bern}(r^{(t)})\] \[\mathbb{Q}_{2}(\mathcal{G}^{(s)}_{S})=\sum_{\mathbf{n}}\mathbb{P}( \alpha^{\prime(s)}|n^{(s)})\mathbb{P}(n^{(s)})\] \[\mathbb{Q}_{2}(\mathcal{G}^{(t)}_{S})=\sum_{\mathbf{n}}\mathbb{P}( \alpha^{\prime(t)}|n^{(t)})\mathbb{P}(n^{(t)}) \tag{20}\]

The selector \(\alpha^{\prime}_{uu}=1\) indicates that the edge \((v,u)\in\mathcal{E}\) in graph \(\mathcal{G}\). The hyperparameters \(r^{(s)}\) and \(r^{(t)}\) are used for sampling. Since \(\mathbb{P}(n^{(s)})\) and \(\mathbb{P}(n^{(t)})\) are constants and independent of \(\alpha^{\prime(s)}\) and \(\alpha^{\prime(t)}\), we can simplify the expression, and ultimately we obtain:

\[\mathbb{Q}_{2}(\mathcal{G}^{(s)}_{S})=\mathbb{P}(n^{(s)})\prod_{u,u= 1}^{n}\mathbb{P}(\alpha^{\prime(s)}_{uu})\] \[\mathbb{Q}_{2}(\mathcal{G}^{(t)}_{S})=\mathbb{P}(n^{(t)})\prod_{u,u= 1}^{n}\mathbb{P}(\alpha^{\prime(t)}_{uu}) \tag{21}\]

### Model Optimization

In our STExplainer framework, we optimize towards the objective of structure-distilled GIB as defined in Equation 14. To infer the downstream labels \(\mathbf{Y}\) using the explainable subgraph \(\mathcal{G}_{S}\), we utilize different loss functions depending on the specific spatio-temporal prediction tasks. For instance, when predicting future traffic volumes, we employ the Huber loss (Gumbel and Softmax, 1957).

\[\mathcal{L}_{0}(\mathbf{Y},\hat{\mathbf{Y}})=\mathcal{H}(\mathbf{Y},\hat{ \mathbf{Y}})=\begin{cases}\frac{1}{2}(\mathbf{Y}-\hat{\mathbf{Y}}),&\left| \mathbf{Y}-\hat{\mathbf{Y}}\right|\leq\delta\\ \delta\big{(}\mathbf{Y}-\hat{\mathbf{Y}}\big{|}-\frac{1}{2}\delta),&otherwise \end{cases} \tag{22}\]

where \(\delta\) denotes the hyperparameter for threshold. For the crime prediction, we instead utilize the mean absolute error (MSE) loss following (Gumbel and Softmax, 1957) and have the following loss: \(\mathcal{L}_{0}(\mathbf{Y},\hat{\mathbf{Y}})=\left\|\mathbf{Y}-\hat{\mathbf{Y}} \right\|_{2}^{2}\). For the second item in the upper-bound GIB objective (Eq 14), we employ specific loss functions for the spatial and temporal explainable subgraphs, respectively.

(23) \[\mathcal{L}_{\text{S-GIB}}=\mathbb{E}_{\mathcal{G}^{(s)}}[ \mathrm{KL}(\mathbb{P}(\mathcal{G}^{(s)}_{S}|\mathcal{G}^{(s)})\|\mathbb{Q}_{2 }(\mathcal{G}^{(s)}_{S}))]\] \[\qquad\qquad\qquad=\sum_{(u,u)\in\mathcal{E}^{(s)}}p^{(s)}_{uu} \log\frac{p^{(s)}_{uu}}{r^{(s)}}+(1-p^{(s)}_{uu})\log\frac{1-p^{(s)}_{uu}}{1-r^{(s)}}+C\] \[\mathcal{L}_{\text{T-GIB}}=\mathbb{E}_{\mathcal{G}^{(t)}}[ \mathrm{KL}(\mathbb{P}(\mathcal{G}^
Combining the above loss functions, the optimization for our STExplainer framework is to minimize the below jointly-training objective, with weighing hyperparameters \(\lambda_{1},\lambda_{2}\).

\[\mathcal{L}=\mathcal{L}_{0}+\lambda_{1}\mathcal{L}_{\text{S-GB}}+\lambda_{2} \mathcal{L}_{\text{T-GB}} \tag{24}\]

## 4. Experiments

To evaluate the performance of STExplainer in terms of predictive accuracy and explainability, we conduct extensive experiments on three real-world traffic datasets and two crime datasets by answering questions: **RQ1**: How does STExplainer perform while predicting future traffic volume and crimes compared to various state-of-the-art baselines? **RQ2**: How does the STExplainer framework compare to different state-of-the-art explainable models in terms of quantitative explainability? **RQ3**: How do key components contribute to the performance of STExplainer framework? **RQ4**: How does the STExplainer framework perform in terms of generalization and robustness? **RQ5**: What is the influence of various hyperparameter settings on the predictive accuracy of STExplainer?

**RQ6**: What visual explanations can be provided by the STExplainer?

### Experimental Settings

#### 4.1.1. **Datasets and Evaluation Protocols.**

The experiments are conducted on both graph-based traffic prediction tasks and grid-based crime prediction tasks, utilizing five real-world datasets. The statistics of our experimental datasets are summarized in Table 3.

**Traffic Prediction.** The model evaluation is firstly conducted using three widely used traffic datasets: PeMS04, PeMS07, and PeMS08 (Feng et al., 2017; Wang et al., 2018; Wang et al., 2018; Wang et al., 2018; Wang et al., 2018). They were collected by the California Performance of Transportation (PeMS) and have a time interval of 5 minutes, covering different time ranges. To ensure a fair comparison, we split the datasets into training, validation, and testing sets in a 6:2:2 ratio. The evaluation of the models is performed using three metrics: _Mean Absolute Error (MAE)_, _Root Mean Squared Error (RMSE)_, and _Mean Absolute Percentage Error (MAPE)_.

**Crime Prediction.** We also investigate the effectiveness of our model in spatio-temporal prediction using crime datasets: NYC Crime and CHI Crime. These datasets, collected from New York City and Chicago, respectively, capture crime incidents on a daily basis and are constructed with a spatial partition unit of \(3km\times 3km\). Following the approach adopted in recent literature (Wang et al., 2018; Wang et al., 2018), we generate the training and testing sets in a ratio of 7:1. In the training set, crime records from the last month are used for validation purposes. We utilize the MAE and MAPE as our evaluation metrics.

**Metrics for Explainability Analysis.** Given the absence of ground-truths specifically designed for spatio-temporal explainability, we adopt metrics commonly used in the context of explainability for GNNs, namely _Sparsity_ and _Fidelity_(Zhou et al., 2018). To accommodate the spatio-temporal nature of our tasks, we make modifications to the _Fidelity_ metric, tailored for autoregressive tasks.

\[Fidelity+^{(s)t}=\frac{1}{Q}\sum_{i=1}^{Q}(|f(\mathcal{G}_{i}^{(s)t})-f( \mathcal{G}_{i}^{(s)t1-m_{i}})|) \tag{25}\]

The modified _Fidelity_ metric, denoted as \(Fidelity+^{(s)t}\), is utilized to measure the explainability of the Spatio-Temporal Graph (STG) framework. In this context, \(Q\) represents the number of spatial and temporal graphs, \(f\) represents the trained predictive spatio-temporal function, \(\mathcal{G}_{i}^{(s)t}\) represents the i\({}^{th}\) original spatial\(\backslash\)temporal graph, and \(m_{i}\) indicates the i\({}^{th}\) extracted explainable subgraph. Consequently, \(\mathcal{G}^{(s)t\backslash 1-m_{i}}\) refers to the masked spatial\(\backslash\)temporal graph based on the complementary subgraph structure \(1-m_{i}\). Furthermore, the _Sparsity_ metric is redefined in the context of spatio-temporal graphs to capture the level of explainability.

\[Sparsity+^{(s)t}=\frac{1}{Q}\sum_{i=1}^{Q}(1-\frac{|m_{i}|}{|M_{i}|}) \tag{26}\]

where \(Sparsity+^{(s)t}\) indicates spatial/temporal _Sparsity_ of explainable subgraphs, \(|m_{i}|\) and \(|M_{i}|\) represent the number of important nodes based on the explainable subgraph and the original graph.

#### 4.1.2. **Compared Baseline Methods**

We compare STExplainer to methods, which can be categorized into two classes, to validate its performance in terms of both accuracy and explainability.

**Predictive Accuracy:** For the evaluation of our STExplainer on traffic datasets, we compare it with 18 baselines that fall into 5 different categories. Similarly, for the evaluation on crime datasets, we adopt 12 baselines categorized into 5 different categories.

_Traffic Prediction:_ (1) **Conventional Statistical Methods**: HA (Han et al., 2017), VAR (Han et al., 2017); (2) **Attention Methods**: ASTGCN (Krishnam et al., 2018), DSTGANN (Krishnam et al., 2018); (3) **Neural Differential Equation Models**: STG-ODE (Feng et al., 2017), STGCNC (Wang et al., 2018), STGCNN (Wang et al., 2018); (4) **GNN-based Methods**: DCRNN (Krishnam et al., 2018), STGCN (Wang et al., 2018), GWN (Wang et al., 2018), STGCN (Krishnam et al., 2018), STGCNN (Krishnam et al., 2018), Z-GCNETs (Wang et al., 2018), TAMP-52GCNets (Wang et al., 2018), GMSDR (Krishnam et al., 2018), FOGS (Krishnam et al., 2018); (5) **Variant of STExplainer**: STExplainer-CGIB (STExplainer with Conventional GIB) _Crime Prediction:_ (1) **Conventional Statistical Methods**: HA (Han et al., 2017), SVM (Krishnam et al., 2018); (3) **CNN-based Approach**: ST-ResNet (Wang et al., 2018); (4) **Hybrid Spatio-Temporal Models**: ST-MetaNet (Wang et al., 2018), STDN (Wang et al., 2018); (4) **Attention Methods**: DeepCrime (Krishnam et al., 2018), STrans (Krishnam et al., 2018); (5) **GNN-based Models**: DCRNN (Krishnam et al., 2018), STGCN (Krishnam et al., 2018), GMAN (Han et al., 2017), ST-SHN (Wang et al., 2018), DMSTGCN (Krishnam et al., 2018).

**Predictive Explainability:** To evaluate the predictive explainability of our approach, we employ four baselines, which can be grouped into two categories. (1) **Post-hoc Methods**: GNNExplainer (Han et al., 2017), PGExplainer (Han et al., 2017), GraphMask (Wang et al., 2018); (2) **Intrinsic Approach**: the STExplainer-CGIB (STExplainer with Conventional GIB).

#### 4.1.3. **Hyperparameter Settings.**

Our STExplainer is implemented using PyTorch and PyTorch Geometric library, with Adam optimizer, a learning rate of \(1e^{-3}\), and a decay ratio of 0.5. We utilize two GAT layers with 16 heads for spatial and temporal encoding, with dimensions of 64 and 128, respectively. The prior probabilities \(r^{(s)}\) and \(r^{(t)}\) are scheduled with a decay ratio of 0.1 and a decay interval of 10 epochs. We employ an annealing strategy for \(\lambda_{1}\) and \(\lambda_{2}\) in the loss function to gradually change from 0 to 1 as the epoch increases. For traffic forecasting, we predict the next 12 time steps based on the past 12 time steps, while for crime prediction, we use 30 days of historical records to predict the next 1 day.

### Prediction Accuracy Comparison (RQ1)

Table 2 showcases the performance comparison results between our STExplainer and state-of-the-art baselines on three traffic datasets. Additionally, Table 4 presents the comparison results for crime
prediction, emphasizing the best-performing model in each dataset. Based on these results, we have the following observations:

* **Overall Superiority of STExplainer.** Our STExplainer consistently outperforms state-of-the-art baselines in both tasks. This is attributed to its effective architecture, utilizing an STG attentive encoder and decoder with a position-aware fusion layer. Additionally, the incorporation of explainable structure-distilled Graph Information Bottleneck (GIB) helps filter out irrelevant information and noise, improving accuracy and interpretability.
* **Comparing to State-of-the-arts.** Compared to attention-based models like ASTGCN, DSTAGNN, DeepCrime, and STTrans, our STExplainer achieves significant improvements in predictive performance. The explainable GIB principle filters task-irrelevant structural correlations, allowing attentive information to propagate over influential subgraphs. The spatio-temporal GIB demonstrates generalization and robustness, extracting task-relevant information from sparse crime data. The performance gap with GNN-based approaches (FOGS, GMSDR, TAMP-S2GCNets, Z-GCNETs, DMSTGCN, ST-SHN, GMAN) highlights the effectiveness of using graph attention mechanisms to alleviate the over-smoothing effects while modeling complex spatial and temporal correlations. Furthermore, comparing our STExplainer with the variant STExplainer-CGIB, which surpasses most baselines, further confirms the effectiveness of our framework. The GIB principle, instantiated by unified STG attention networks, plays a crucial role in improving performance.
* **Visualization of predictions.** We further visualize the predictive results on PEMS04, demonstrating the comparison between our STExplainer and two competitive baselines, namely STGODE and GMSDR, along with the ground-truth results. The visual comparison, depicted in Figure 3, highlights the superiority of our STExplainer. It excels in predicting inflection points that involve sharp jitter changes due to its capability to filter out task-irrelevant information, capturing essential spatio-temporal dynamics, and providing more accurate results.

### Model Explainability Evaluation (RQ2)

In this subsection, we quantitatively analyze the spatio-temporal explainability of our STExplainer. We use modified metrics, namely "Sparsity" and "Fidelity", to evaluate the spatial and temporal graphs. The comparison results on PEMS04 are shown in Figure 2. To ensure a fair comparison, we employ _post-hoc_ frameworks to explain STGNN models using the same STG encoder and decoder. Higher scores in "Sparsity" and "Fidelity" indicate better predictive explainability, aiming to extract smaller, impactful spatio-temporal subgraphs. The STExplainer framework, incorporating explainable information bottleneck, achieves the best explainable performance

\begin{table}
\begin{tabular}{c|c c c c c c c c c c c c c c c c c} \hline \hline \multirow{2}{*}{Model} & \multirow{2}{*}{HA} & \multirow{2}{*}{VAR} & \multirow{2}{*}{DRNN} & \multirow{2}{*}{STGCN} & \multirow{2}{*}{GWN} & \multicolumn{2}{c}{AST} & \multicolumn{2}{c}{STS} & \multicolumn{2}{c}{Stem} & \multicolumn{2}{c}{Z-} & \multicolumn{2}{c}{TAMP-} & \multicolumn{2}{c}{STAP-} & \multicolumn{2}{c}{STAP-} & \multicolumn{2}{c}{STExplainer} \\  & & & & & & GCN & GCN & GNN & & GCN & S2GCNets & & & NCDE & GNN & & CGIB & \\ \hline \multirow{6}{*}{GCNETs} & MAE & 38.03 & 24.54 & 21.22 & 21.16 & 24.89 & 22.93 & 25.11 & 19.83 & 19.83 & 20.84 & 19.50 & 19.74 & 20.49 & 19.74 & 19.21 & 19.30 & 19.14 & **18.57** \\  & RMSE & 92.94 & 38.61 & 33.44 & 34.89 & 39.66 & 35.22 & 33.86 & 33.80 & 32.26 & 31.88 & 32.82 & 31.61 & 31.74 & 32.13 & 31.16 & 31.09 & 31.46 & 30.77 & **30.14** \\  & MAPF(\%) & 27.88 & 17.24 & 14.17 & 13.83 & 17.29 & 16.56 & 13.90 & 16.10 & 12.97 & 13.02 & 13.77 & 12.78 & 13.22 & 14.15 & 13.05 & 12.76 & 12.70 & 12.91 & **12.13** \\ \cline{2-15}  & MAE & 45.12 & 50.22 & 52.52 & 25.23 & 25.33 & 26.40 & 24.26 & 22.23 & 22.37 & 22.07 & 22.99 & 21.77 & 21.84 & 22.27 & 21.28 & 20.53 & 21.42 & 20.55 & **20.00** \\  & RMSE & 65.64 & 75.63 & 36.61 & 39.34 & 37.40 & 41.50 & 37.87 & 90.36 & 34.66 & 35.55 & 38.00 & 37.54 & 35.17 & 35.42 & 34.94 & 34.83 & 33.84 & 34.51 & 35.12 & 33.45 \\  & MAPF(\%) & 45.31 & 22.22 & 11.97 & 10.73 & 12.01 & 9.20 & 9.12 & 9.21 & 9.21 & 10.14 & 9.25 & 9.24 & 9.86 & 8.95 & 8.80 & 9.01 & 8.61 & **8.51** \\ \cline{2-15}  & MAE & 34.86 & 19.19 & 16.82 & 17.50 & 18.28 & 18.25 & 17.13 & 15.91 & 15.95 & 16.64 & 16.81 & 15.76 & 13.66 & 13.65 & 15.75 & 15.45 & 15.67 & 14.87 & **14.59** \\ \cline{2-15}  & RMSE & 22.94 & 29.83 & 26.79 & 27.90 & 30.05 & 28.06 & 28.54 & 25.22 & 25.97 & 25.11 & 25.98 & 25.84 & 29.42 & 28.14 & 27.47 & 24.07 & **23.91** \\ \cline{2-15}  & MAPF(\%) & 24.07 & 13.10 & 10.92 & 11.29 & 12.15 & 11.64 & 10.96 & 10.90 & 10.60 & 10.62 & 10.01 & 10.15 & 10.28 & 9.88 & 9.92 & 9.94 & 10.26 & **9.80** \\ \hline \hline \end{tabular}
\end{table}
Table 2. Performance comparison of different methods on PEMS4, 7, 8 datasets.

\begin{table}
\begin{tabular}{c c c c c} \hline \hline Dataset & Type & Volume \# Interval & * Nodes & * Time Span & * Features \\ \hline PeMSD4 & Graph & Traffic & 5 min & 307 & 01/2018 - 02/2018 & 1 \\ PeMSD7 & Graph & Traffic & 5 min & 883 & 05/2017 - 08/2017 & 1 \\ PeMSD8 & Graph & Traffic & 5 min & 170 & 07/2016 - 08/2016 & 1 \\ NNC Crime & Grid & Crime & 1 day & 256 & 01/2014 - 12/2015 & 4 \\ CHI Crime & Grid & Crime & 1 day & 168 & 01/2016 - 12/2017 & 4 \\ \hline \hline \end{tabular}
\end{table}
Table 3. Statistical information of the experimental datasets.

Figure 2. Overall explainability comparison of STExplainer.
compared to state-of-the-art approaches. This validates the effectiveness of injecting explainability into our unified STGNN architecture with the IB principle. Among the _post-hoc_ methods, PGExplainer outperforms others for STGNN models, providing effective global explanations. However, the performance gap between our _intrinsic_ models with STExplainer framework and _post-hoc_ methods highlights our inherent superiority in providing faithful explanations for spatio-temporal GNN architecture.

### Ablation Study (RQ3)

We investigate the effectiveness of the proposed modules by designing variants of our STExplainer: i) "-CGIB": We replace the explainable GIB principle with the conventional one to compare different ways of controlling bottleneck information. ii) "-w/o SIB" and "-w/o TIB": We remove the explainable GIB-based GAT encoder in spatial and temporal modeling, respectively, and use canonical GAT instead. iii) "-drop 0.5", "-drop 0.3", and "-drop 0.0": We randomly drop edges of the spatio-temporal graphs with different probabilities, instead of utilizing the explainable spatio-temporal GIB. We analyze the results on PEMS04 and 08, which are shown in Figure 4. Through these experiments, we make the following discoveries:

* Regarding the "-CGIB" variant, the performance improvements achieved by our STExplainer demonstrate the superiority of the explainable structure-distilled GIB over the conventional one in controlling the flow of structural information during inference. This is attributed to the significance and sensitivity of graph structure in graph neural network models.
* The application of explainable GIB demonstrates its effectiveness in capturing important spatial and temporal dependencies, as evidenced by the variants "-w/o SIB" and "-w/o TIB". The influence of spatial and temporal GIB on the framework's performance depends on the credibility and noise levels present in the original spatial and temporal graph structures. In this regard, we argue that the fully connected temporal graph often contains more task-irrelevant structural noise that needs to be filtered out.
* When examining the variants "-drop 0.5", "-drop 0.3", and "-drop 0.0", a noticeable performance gap becomes apparent. This gap arises because random edge dropping cannot differentiate between task-relevant and task-irrelevant edges in the graph structure. It is worth noting that "-drop 0.5" and "-drop 0.3" outperform "-drop 0.0" in terms of better generalization. This outcome validates the necessity of edge dropping and motivates us to develop more accurate and efficient strategies for edge drop in the future.

### Generalization and Robustness Study (RQ4)

The inherent ability of GIB to extract task-relevant and prediction-influential spatio-temporal information allows us to further validate the generalization and robustness of our STExplainer. To achieve this, we address two specific data quality issues.

**Performance _w.r.t_ Data Missing.** In real-world spatio-temporal scenarios, data missing challenges often arise due to sensor failure and privacy policies. To assess the performance of our STExplainer in such cases, we randomly drop traffic volumes on each node with proportions of 10%, 30%, and 50% for traffic prediction. It is important to note that the data drop between nodes is independent. The results on PEMS04 are presented in Table 5, where "-" indicates that the model fails in this situation. The results demonstrate that our STExplainer is capable of filtering out random noise introduced by data drop, showcasing its generalization and robustness. We compare our STExplainer with three competitive baselines, namely STGODE, GMSDR, and STG-NCDE. We observe that the performance of STGODE and GMSDR sharply decreases with an increasing proportion of dropped data. However, our STExplainer shows its robustness by achieving better performance in adapting to data missing scenarios compared to STG-NCDE.

**Performance _w.r.t_ Data Sparsity.** In practical scenarios, e.g., crime prediction, spatio-temporal signals across the observed space often exhibit sparsity, with many regions or nodes having zero values. This poses a challenge for achieving better generalization and robustness of the model. To address this, we categorize regions in crime prediction tasks based on historical region density. We compare the predictive results of our STExplainer with baselines on density ranges "0-0.25" and "0.25-0.5", as depicted in Figure 5. The notable performance gap underscores the capability of our STExplainer framework to extract task-relevant information from sparse data, resulting in improved predictive performance. This is particularly noteworthy as our STExplainer outperforms methods specifically tailored for crime prediction, e.g., STtrans and ST-SHN.

Figure 4. Ablation experiments of our STExplainer.

Figure 5. Performance comparison on sparse regions.

\begin{table}
\begin{tabular}{c|c c c c c c c|c c c} \hline \hline \multirow{2}{*}{model} & \multicolumn{6}{c|}{PESM04} \\ \cline{2-13}  & \multicolumn{3}{c|}{missing 10\%} & \multicolumn{3}{c|}{missing 30\%} & \multicolumn{3}{c|}{missing 50\%} \\ \cline{2-13}  & MAE & RMSE & MAVE & MAE & RMSE & MAVE & MAE & RMSE & MAVE \\ \hline STGODE & 23.97 & 35.41 & 19.13 & 45.02 & 59.48 & 29.54 & - & - & - \\ GASDE & 21.69 & 34.06 & 13.81 & 25.02 & 38.45 & 15.01 & 10.51 & 131.64 & 47.31 \\ ST-NCDE & 19.36 & 31.28 & 12.79 & 14.01 & 31.30 & 13.04 & 19.98 & 32.09 & 13.48 \\ STExplainer & 19.12 & 30.84 & 12.61 & 19.34 & 31.20 & 12.86 & 19.92 & 32.05 & 13.27 \\ \hline \hline \end{tabular}
\end{table}
Table 5. Performance comparison against data missing.
### Hyperparameter Investigation (RQ5)

We are conducting a hyperparameter investigation by varying specific hyperparameters while keeping others at their default values. We focus on four significant hyperparameters: head numbers (\(K\)), prior probability (\(r\)), spatial dimension (\(d^{(s)}\)), and temporal dimension (\(d^{(t)}\)). The results of our experiments on PEMS04 are displayed in Figure 6. Here are our detailed experiments and observations: i) **Head numbers** (\(K\)): We vary the number of heads in the spatio-temporal GAT encoder from the range of \(2,2^{2},2^{3},2^{4}\). We find that the model with \(2^{4}\) heads achieves the best performance. Increasing the number of heads enables the model to capture spatio-temporal correlations from multiple dimensions. ii) **Spatial and temporal dimensions** (\(d^{(s)}\), \(d^{(t)}\)): We search for the optimal spatial and temporal dimensions in the spatio-temporal GAT encoder within the range of \(2^{4},2^{5},2^{6},2^{7}\). We find that \(d^{(s)}=2^{6}\) and \(d^{(t)}=2^{7}\) serve as the best settings. iii) **Prior probability** (\(r\)): The prior probability \(r\) represents the spatio-temporal prior probability in Equation 23. We explore the search range of "fix 0.5", "0.9-0.3", "0.9-0.5", "0.9-0.7", where "fix 0.5" indicates fixing \(r\) at 0.5, and the last three options involve controlling \(r\) to decay from 0.9 as the epoch increases.

### Model Interpretation Case Study (RQ6)

We conduct an investigation into the explanations provided by our STExplainer in identifying important subgraphs and analyzing their spatio-temporal patterns. To achieve this, we employ a method of obtaining explainable subgraphs by discarding edges with low edge weights. Subsequently, we employ extensive visualization techniques to gain a deeper understanding of the relationships.

**Spatio-Temporal Pattern Explanations:** In the left side of Figure 7 (a), our STExplainer identifies node 28 as being more related to node 57 compared to nodes 242 and 243. This relationship is also apparent in the adjacent time series diagram, where node 28 and node 57 exhibit similar time trend patterns with comparable peaks and valleys. The thickness of the arrow connecting the nodes represents the edge weights encoded by the GB principle. Furthermore, in the right side of Figure 7 (a), we observe that node 47 is considered to be weakly correlated with node 36 and other nodes. This is evident from the highlighted peaks, valleys, and rising time points in the adjacent time series plot. Both figures demonstrate that our STExplainer provides explanations that accurately reflect spatio-temporal trend patterns across time and locations.

**Spatial Semantics Explanation:** Due to the unavailability of coordinate information in the PEMS04, PEMS07, and PEMS08 datasets, we focus on exploring the precise semantic information provided by explanations on the CHI Crimes dataset. Figure 7 (b) visually present our findings, where interconnected regions exhibit similar regional functionality, particularly in terms of shared Point of Interest (POI) information. For example, regions 118 and 129, as well as regions 141 and 142, display comparable POI characteristics, implying functional resemblance. Conversely, region 119 stands out as relatively isolated due to its primarily oceanic nature and lack of substantial POI information. These findings underscore the significance of explainability and the prediction effectiveness.

## 5. Conclusion

In this study, we emphasize the significance of explainability in spatio-temporal graph neural networks. To address this, we propose a novel framework called STExplainer that not only predicts future spatio-temporal signals accurately but also provides transparent explanations. Our framework incorporates GIB-based structure distillation with an explainable objective and employs variational approximation for tractability. Additionally, we introduce a unified STG encoder and decoder that generate explainable, generalizable, and robust STG representations. Through extensive experiments, we demonstrate the superiority of our STExplainer in terms of predictive accuracy, explainability, generalization, and robustness. Our results surpass existing state-of-the-art methods in both predictive accuracy and explainability. In future work, we plan to investigate effective approaches for integrating explainability into global spatial information propagation mechanisms, such as hypergraph neural networks, using an _intrinsic_ explainable approach.

Figure 6. Hyperparameter study of the proposed STExplainer.

Figure 7. Case study of our STExplainer.