Learning from Highly Sparse Spatio-temporal Data

Thanks for your careful reviews and insightful suggestions. We greatly appreciate your feedback. Please see the below responses to your comments (see global response to your questions about more baselines and confused notations).

[Weakness 1.1] The introduction section presents most of the contents that should be separately discussed in the related work section, while the related work section is missing.

Thanks for your suggestions. In the revised version, we have reorganized the paper to make it clearer. Specifically, we have streamlined the introduction to focus only on the background and significance of the spatio-temporal data imputation, briefly analyze the limitations of existing methods, and finally overview of our work. In addition, we have discussed related work in a separate section, including graph imputation, time-series imputation, and spatio-temporal data imputation, as well as comparing our method with them to highlight our advancements and contributions.

[Weakness 1.3.2] In section 4.1.2, what is \hat{X}, which does not appear anywhere previously? I don’t really follow the paper, as so many of the notations are not properly defined and explained.

We appreciate the constructive feedback. For the sparse temporal attention module in Sec. 4.1.2, we consider timestamp encoding and positional encoding to introduce sequence information. Specifically, the input $\bar X$ can be formulated as:

$$\bar{X} = X + PE(X) + MLP(U),$$

where $U$ is the available real-world time information, such as the hour of the day; $PE$ is the vanilla positional encoding as follows.

$$PE_{(pos, 2i)} = sin(pos/10000^{2i/d_{model}}) ,$$ $$PE_{(pos, 2i+1)} = cos(pos/10000^{2i/d_{model}}).$$

[Weakness 1.3.1] In section 4.1.1, the update in GNN equation uses S_l, but then h_^{s}_{v,t} is used to denote the equation. Are they the same thing?
[Weakness 2] It is not clear to me why the proposed belongs to “one-step propagation”. Stacking GNN layers implicitly means several iterations of propagation, which is how section 4.1.1 presents. Besides, the temporal self-attention has nothing to do with “propagation”.
[Weakness 3] It is not clear to me how sparse spatial attention works. The GNN equation and Figure 1 indicates that the original graph structure is utilized. However, in equation 4, it is mentioned only “available nodes” are selected to perform self-attention. In this case, only the representations of nodes that have observed data are updated? How exactly this module functions is not clear.

Thanks for your comments. The sparse spatial attention module may not be expressed clearly enough. Let us first clarify this module and then answer your questions one by one.

• Using multi-layers GNN: In Lines 150 to 155, $L_s$-layers GCN was utilized to learn static node spatial features from topology structure, and the learned static spatial features are the output $S_{L_s}$. Formally, this part does not belong to the sparse spatial attention that is dedicated to capturing dynamic spatial information. To avoid confusion, we will add a new section before Sec. 4.1.1, titled Learning of Static Spatial and Temporal Features, and move this part and our response to your [Weakness 1.3.2] to this section.
• The core of sparse spatial attention module: The sparse spatial attention module captures the comprehensive correlations of nodes based on the static node spatial features learned by $L_s$-layer GCN, i.e., the input node embedding $S$ of this module is $S_{L_s}$. Then, $S$, $S$, and $X_t$ serve as query, key, and value, respectively, to learn the spatial dependencies-based representation ${h}^{s}_{v,t}$ of each ST point $(v,t)$ that lacks features.
• The object of attention mechanism: We need to obtain representation of the missing point $(v, t)$, while the observed point keeps the original feature unchanged. Then, according to Eq. 5, the attention mechanism acts between the missing points and the observed points, and finally, the weighted observed point representations are used to update the missing point representation.

Based on this, we address each of your questions as follows.

Q1: Are $S_l$ and $h^s_{v,t}$ the same thing?

$S_l$ and $h^s_{v,t}$ are not equivalent. $S_l$ denotes the learned static node spatial feature by $L_s$-layers GCN. ${h}^{s}_{v,t}$ denotes the learned dynamic representation by spatial attention module for ST point $(v,t)$.

Q2: Why the proposed belongs to “one-step propagation”.

In dynamic spatio-temporal data learning, we focus on the propagation at each time step, i.e., the steps of dynamic propagation. The node spatial features learned by multi-layer GCN are static and shared across all time steps, which are not counted in the dynamic propagation. The dynamic process is reflected in the two proposed attention modules; each unobserved node receives information from all observations once, which is achieved by one matrix multiplication, so we refer this strategy as “one-step propagation”.

Q3: Only the representations of nodes that have observed data are updated?

Only the representations of the missing data are updated by aggregating the representation of all observed data based on the attention weights between the missing data and observed data. As for the observed data, their representations use the original feature representation and are not updated.

[Weakness 4] Figure 1 is not informative at all. I cannot really understand which parts of the nodes and timestamps are utilized for sparse attention.

Thanks for your valuable feedback. We have updated Figure 1 to include additional annotations, as shown in Fig. 1 in the rebuttal-submitted PDF. Specifically, for the sparse spatial attention module, we first learn the sparse attention matrix from structural embeddings $S$ using all observed nodes. At each time step $t$, we propagate observed nodes' information to missing data with attention-based weight.

Many thanks for your positive comments and constructive feedback. Please see the below responses to your comments.

[Weakness 1 & Question 1] The paper uses PAC-learnability to analyze generalization risk. Have the author(s) considered using other mathematical tools, such as Rademacher complexity?

Thanks for this valuable feedback. Other tools, such as Rademacher complexity, are usually closely related to the model structure, and are therefore model-specific mathematical tools. However, our work aims to investigate the impact of missing data on the learning ability of (general) models and to seek breakthroughs in theoretically inspired methods based on these insights, which can be facilitated by the PAC-Learnability theory rather than model-specific theory. The motivation for this theoretical analysis is that the influencing factors caused by missing data, as revealed through the general models, are universal and not confined to any specific model. This broad applicability can inspire improvements to various models (rather than specific models). It is undeniable that studying the generalization error (or convergence rate) of specific models is also of significant importance and will be the direction of our future work.

[Weakness 2 & Question 2] Could the author(s) further discuss the potential strength of the proposed method in practical scenarios?

Thank you for your question. Our proposed method has three potential strengths:

• Lowering the data threshold: Our method addresses both device failure (point missing) and device unavailability (spatial missing) in spatio-temporal data imputation. Learning from spatial missing data allows for the generalization of local observations to global data, which can reduce research costs in various fields.
• Correlation mining: Our approach provides inherent spatial and temporal context for message-passing rather than just propagating information along the spatiotemporal structure. This allows for easier encapsulation of static spatio-temporal information.
• Parallel recovery: Our one-step propagation aggregates all observations to target data, enabling parallel processing of missing data in practical scenarios. This avoids the low computational efficiency of iterative imputation methods, which makes it particularly suitable for large-scale datasets.

[Weakness 3] There are some typo and grammatical errors. For instance, "seperate" on Line 13, "problem" on Line 29.

Thanks for your careful review. We have modified and checked these typos and grammatical errors in the revised version.

Many thanks for your positive comments and constructive feedback. Please see the below responses to your comments.

[Weakness 1.1] In Section 4.1.2, the construction details of the input to the temporal sparse attention module are not described.

Thanks for your question. For the temporal sparse attention module, we consider timestamp encoding and positional encoding to introduce sequence information. Specifically, for any node $v \in \mathcal V$, the input $\bar X_v$ can be formulated as:

$$\bar{X_v} = X_v + PE(X_v) + MLP(U),$$

where $X_v$ is the associated time-series of node $v$; $U$ is the available real-world time information, such as the hour of the day; $PE$ is the vanilla positional encoding as follows.

$$PE_{(pos, 2i)} = sin(pos/10000^{2i/d_{model}}),$$ $$PE_{(pos, 2i+1)} = cos(pos/10000^{2i/d_{model}}).$$

[Weakness 1.2] Additionally, there are some typos in this paper. For example, the symbol (H^0) at line 196 is incorrectly written, the symbols 𝑞𝑡𝑡 and 𝑘𝑘𝑡 in Equation 7 are irregular and inconsistent with the corresponding symbols in Equation 6, and some symbols in the two formulas under line 195 lack descriptions.

Thanks for your careful review. We have corrected these typos and thoroughly checked the symbols in the revised version. Specifically, in Section 4.2, to avoid confusion, we replace "$H$" with "$O$" to denote the learned representations in the second stage. Then, the layer-wise updation can be formulated as

$$O_{v,t}^{l+1} = \text{MLP} \left( O_{v,t}^{l} || \sum_{(v',t')\in {N_{v,t}}} \beta_{v't'} \cdot O_{v',t'}^l \right),$$

where $O^0 = h_{v,t}^s + {h}_{v,t}^t$.

For the sparse attention-based confidence, we have revised inconsistent symbols and rewritten Eq.7 as follows.

$$\beta_{vt} = \frac{\sum_{k\in \tilde{V}}\exp (<q_v^s, k_k^s>)}{\sum_{k\in V}\exp (<q_v^s, k_k^s>)} + \frac{\sum_{k\in \tilde{T_v}}\exp (<q_{v,t}^t, k_{v,k}^t>)}{\sum_{k\in T}\exp (<q_{v,t}^t, k_{v,k}^t>)}$$

[Weakness 2] Some diffusion model-based methods, such as CSDI [1] and PriSTI [2], can propagate information from observed data to missing data directly without multiple iterations. It would be better to clarify the advantages of the proposed model compared to these methods.
[Question 2] What's the advantage of the proposed model compared with diffusion model-based methods?

Thanks for making this important question. Similar to other temporal methods, CSDI treats spatio-temporal data as multivariate time-series and ignores spatial structure. PriSTI introduces diffusion models to spatio-temporal imputation. They use two separate attention modules to incrementally aggregate temporal and spatial dependencies. However, this design decouples the spatio-temporal context and then ignores intrinsic interactions between spatial and temporal dimensions. In addition, PriSTI applies linear interpolation to the time series of each node to initially construct coarse conditional information. However, in spatially missing data, this strategy cannot provide effective information.

Notably, we have conducted comparative experiments with CSDI [1] and PriSTI [2], please refer to the global rebuttal.

[Question 1] In Figures 4 and 5, why is the MAE result of the SAITS ∞ in the PV-US and CER-E datasets?

Thanks for your question. The temporal imputation methods, such as SAITS and BRITS, treat spatio-temporal series as multivariate time series. These models struggle to effectively learn from large-scale spatio-temporal data, which is the high-dimensional time series. Under the early stopping settings, both SAITS and BRITS often terminate training process early, resulting in extremely high MAE values. To more clearly compare other methods, we have truncated the results of BRITS and SAITS in Fig. 2 and Fig. 3. We have replaced "∞" with accurate MAE results in the revised version. Please refer to Fig. 2 and Fig. 3 in the rebuttal-submitted PDF.

References

[1] Tashiro Y, Song J, Song Y, et al. Csdi: Conditional score-based diffusion models for probabilistic time series imputation[J]. Advances in Neural Information Processing Systems, 2021, 34: 24804-24816.

[2] Liu M, Huang H, Feng H, et al. Pristi: A conditional diffusion framework for spatiotemporal imputation[C]//2023 IEEE 39th International Conference on Data Engineering (ICDE). IEEE, 2023: 1927-1939.

Thanks for your careful reviews and insightful comments. We greatly appreciate your feedback. Please see the below responses to your comments (see global response to your questions about more baselines and confused notations).

[Weakness 1] In general, the proposed method is a little bit incremental. A simpler version of sparse spatial-temporal attention has been proposed by SPIN.

Thanks for raising this fundamental issue. We would like to clarify the differences from SPIN and emphasize the contributions of the proposed method.

Differences. The proposed method differs from SPIN in the following aspects:

• SPIN propagates information from neighboring spatial-temporal points to the target ST point, while our sparse attention mechanism makes full use of global observations (i.e., fully connected graph) to recover every missing data, which may capture more information.
• SPIN propagates in an iterative manner, while we directly propagate observations to missing data without any intermediary, which avoids the information loss and high computational cost caused by iterative propagation.
• SPIN applies the sparse attention mechanism only in shallow layers. In deep layers, it assumes that most missing data has been filled and then employs dense attention mechanisms, which may lead to error accumulation, especially in large-scale datasets with high sparsity. Instead, our method only uses observations to recover all missing data in the first stage, ensuring consistent and accurate handling of sparse data.

Contributions. Our contributions might not have been well received, and we restate and emphasize them. Specifically, our contributions lie in the theoretical analysis of imputation methods, as well as the breakthrough of theory-inspired methods.

• Our first contribution is in theoretically analyzing which factors impact the performance of the imputation task. Most existing imputation methods usually rely on iterative message-passing in the temporal and spatial dimensions. However, their feasibility is based on their experience in engineering practice, and there is a lack of theoretical analysis. To this end, this paper aims to bridge the gap between theoretical analysis and empirical practice, and provide a theoretical analysis for general spatio-temporal iterative imputation models from the PAC-learnability perspective. The theoretical results reveal the impact of data sparsity and structural sparsity, as well as the need for more iterations for model performance. Notably, PAC-learnability-based analysis is not coupled to the specific model, and such general insights can inspire improvements to various models.
• Our second contribution is the imputation method OPCR that we have developed, which has been shown to outperform the baselines regarding point missing and spatial missing tasks (Sec. 5.3 & 5.4). This is achieved by designing one-step imputation to avoid iterative error accumulation, and modeling spatio-temporal dependencies to refine the imputation results with confidence. Although the proposed method seems simple (i.e., reducing the number of layers and considering propagation over the fully connected graph), it is carefully designed based on comprehensive considerations of theoretical results, spatio-temporal dependence modeling, and computational complexity. We believe our method is quite useful.

We reasonably believe that these contributions to the theoretical analysis of existing work and the algorithmic breakthroughs inspired by the theory are significant.

[Weakness 3] The comparison baselines GRIN (2021) and SPIN (2022) are a little bit outdated. More recent baselines should be considered, such as [1,2,3].

Thanks for the valuable suggestions. Per your suggestions, we have added more baselines for comparison, including the tabular imputation method GRAPE [4], the time-series imputation method CSDI [3], the spatio-temporal imputation methods PoGeVon [2], and PriSTI [1]. Please see the global rebuttal.

References

[1] PriSTI: A Conditional Diffusion Framework for Spatiotemporal Imputation, ICDE'2023.

[2] Networked Time Series Imputation via Position-aware Graph Enhanced Variational Autoencoders, KDD'2023.

[3] Csdi: Conditional score-based diffusion models for probabilistic time series imputation. NeurIPS'2021.

[4] Handling Missing Data with Graph Representation Learning. NeurIPS 2020.