Learning from Highly Sparse Spatio-temporal Data

Authors: leyan  deng
defu  lian
chenwang  wu
enhong  chen
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 15:16:14

Abstract: Incomplete spatio-temporal data in real-world has spawned many research.
However, existing methods often utilize iterative message-passing across temporal and spatial dimensions, resulting in substantial information loss and high computational cost.
We provide a theoretical analysis revealing that such iterative models are not only susceptible to data sparsity but also to graph sparsity, causing unstable performances on different datasets.
To overcome these limitations, we introduce a novel method named One-step Propagation and Confidence-based Refinement (OPCR).
In the first stage, OPCR leverages inherent spatial and temporal relationships by employing sparse attention mechanism.
These modules propagate limited observations directly to the global context through one-step imputation, which are theoretically effected only by data sparsity.
Following this, we assign confidence levels to the initial imputations by correlating missing data with valid data.
This confidence-based propagation refines the seperate spatial and temporal imputation results through spatio-temporal dependencies.
We evaluate the proposed model across various downstream tasks involving highly sparse spatio-temporal data.
Empirical results indicate that our model outperforms state-of-the-art imputation methods, demonstrating its superior effectiveness and robustness.

Main paper: 
 introduction: 
 Spatio-temporal data, encompassing information distributed across both spatial and temporal dimensions, is prevalent in various domains [1] . In real world, the acquisition of spatio-temporal data often faces practical constraints, leading to missing observations. Incomplete data undermines the reliability and effectiveness of subsequent tasks, necessitating robust imputation techniques. However, the existing spatio-temporal works effort addresses temporal missing (i.e., point-level missing), which is usually caused by inevitable device failure. Beyond that, spatial missing (i.e., node-level missing) becomes a burning issue. For example, in a traffic scenario, the management will not deploy dense traffic sensors to reduce costs. Therefore, exploring spatially sparse data not only makes the best use of available data but also lowers the barriers to implementing spatio-temporal models in real scenarios. In view of the gap, Traffic4cast 2022 (T4C22) competition [2] presented sparse traffic data collected in real urban road networks. Specifically, the competition considered three cities, where sensors are deployed sparsely, i.e. spatial and point missing co-exist. T4C22 aims at generalizing limited data to entire city to predict global traffic dynamics.We first provide a theoretical analysis for general spatio-temporal iterative imputation model from PAC-learnability perspective. Then we find that iterative methods are constrained by the sparsity and structure of data. As the data scale and missing rate increase, the model requires more iterations. Additionally, with an increasing number of iterations, the model requires more training samples. Therefore, for highly sparse large-scale data, iterative methods suffer from information loss and error accumulation. To address these issues, we propose a sparse attention-based one-step imputation and confidence-based refinement approach. In the first stage, we propagate information from observed data to all missing data directly, leveraging inherent spatial and temporal correlations. In the second stage, we assign confidence-based propagation weights to the imputed results. Through confidencebased refinement, we eliminate the bias introduced by imputations from separate perspectives. This paper makes the following contributions.• We provide an limitation analysis for the popular iterative imputation from the PAClearnability perspective, which explains the error accumulation caused by multiple iterations.• Motivated by theoretical results, we propose a one-step propagation strategy to efficiently recover global information from limited observations. Then we assign confidence-based propagation weights to spatio-temporal interactions, refining the imputation results.• We apply our method to various downstream tasks, the experiments show that our model can learn sufficient information from limited observations than state-of-the-art baselines.Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?Answer: [Yes] Justification: We summarize the motivation and contribution of the paper.Guidelines:• The answer NA means that the abstract and introduction do not include the claims made in the paper. • The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 
related works: 
 There are many works exploring how to impute different types of sparse data. For tabular data, matrix factorization-based methods are widely popular. A recent work transformed tabular data imputation into link prediction in a bipartite graph, which benefited from the expressive power of graph neural networks (GNNs). For graph data, a simple idea is propagating known features to missing data through the graph structure. For example Feature propagation (FP) [3] iteratively aggregates neighboring node features and PCFI [4] further considered pseudo-confidence to propagate messages more accurately. It is clear that GNN can capture spatial relations better. In addition to GNN-based imputation model, SAT [5] and ITR [6] both additionally considered structural representations and structure reconstruction objective. However, these graph imputation problems focus on static graph and fixed missing data sets, which is incompatible with dynamic sparse spatio-temporal data.For time-series data, the existing approaches investigated the imputation performances of different sequence models. For example, BRITS [7] proposed a bidirectional Recurrent Neural Networks (RNN). SAITS [8] designed self-attention based model and jointly trained imputation and reconstruction objective. CSDI [9] proposed a conditional score-based diffusion model. However, these time-series imputation methods ignore intrinsic spatial dependencies in spatio-temporal data.For spatio-temporal data, existing research leverages topological information effectively. IGNNK [10] introduced a scalable inductive method trained by reconstructing random sub-graphs. GRIN [11] was the first to apply Graph Neural Networks (GNNs) to multivariate time-series imputation and proposed a graph-based recurrent neural network. Subsequently, SPIN [12] identified that auto-regressive models like GRIN are prone to error propagation. SPIN developed an end-to-end architecture utilizing intra-node and inter-node attention mechanisms to address this. However, when dealing with highly sparse large-scale data, propagating valid information through graph structures requires multiple iterations, leading to error accumulation and information loss. In addition, PriSTI [13] proposed a diffusion-based model. Nonetheless, PriSTI employs two separate attention modules to incrementally aggregate temporal and spatial dependencies, which leads to decoupling the spatio-temporal context. Additionally, PriSTI uses linear interpolation for coarse conditional information, which is inadequate for spatially missing data. Beyond attribute imputation, PoGeVon [14] also addresses the challenge of missing structural information in spatio-temporal data.3 Preliminaries Definition 3.1 (Spatio-temporal Series). Given a fixed graph G = (V, E, A), where V and E denote the set of N nodes and E edges, respectively; A ∈ R N ×N is the corresponding adjacency matrix. A spatio-temporal series of length T is represented by X ∈ R N ×T ×Fx , where F x denotes the number of feature dimensions. We represent each spatio-temporal point (ST point) with a tuple z = (v, t) and x v,t ∈ R Fx denotes the collected data of node v at time t.Definition 3.2 (Spatio-temporal Mask). For spatio-temporal series X, we use a binary mask M to indicate missing ST points, where m v,t = 0 if x v,t is missing, otherwise m v,t = 1. Note that, since a faulty device often miss all records, we ignore the availability of data in feature dimension. Thus, we can define a unique sparse spatio-temporal series X in terms of X and M , i.e.,EQUATIONDefinition 3.3 (Sparse Spatio-temporal Data Learning). The goal is to accomplish downstream tasks based on the incomplete data X. Without loss of generality, we consider the following objective functions for node-level task.EQUATIONwhere l(•, •) is an element-wise loss function that depends on specific downstream tasks. Here y v and ŷv are the ground truth and model's prediction for node v, respectively.For imputation task, the model aims to minimize the reconstruction error as follows.EQUATIONwhere T denotes the set of time steps and l(•, •) is an element-wise loss function.Question: Does the paper discuss the limitations of the work performed by the authors?Answer: [No] Justification:Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
theory assumptions and proofs: 
 Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?Answer: [Yes]• It should be clear whether the error bar is the standard deviation or the standard error of the mean. Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
theoretical analysis: 
 As we stated above, the iterative spatio-temporal imputation methods will suffer from information loss and error accumulation on extremely sparse large-scale data. In order to expose the limitations of iterative models, we provide a theoretical analysis in terms of PAC-learnability for node-level tasks.We use X ∈ X and Y ∈ Y to denote complete spatio-temporal series and node-level labels, and use M ∈ M to denote mask distribution. Let D be the fixed but unknown distribution over X × Y. We define the mixture distribution D of D and M using Eq. 1. Given a training set S = {( Xi , Y i )} m , we assume that all samples in S are i.i.d. according to D, denoted as S ∼ Dm . Let f ∈ F : X ×M → Y be a sparse spatio-temporal data learning model, the empirical risk over S and the corresponding generalization risk is defined as follows,Empirical risk : R S (f ) = 1 m m i=1 l(f ( Xi ), Y i ), Generalization risk : R D (f ) = E ( X,Y )∼ D l(f ( X), Y )Similarly, we denote empirical and generalization risk under complete data as RS (f ) and R D (f ). Definition 4.1 (PAC-Learnability [15] ). A concept class C is said to be probably approximately correct (PAC) learnable if there exist a learning algorithm A and a polynomial function poly(•, •, •, •) satisfying: for any ϵ, δ > 0 and any distribution D, the following holds for any sample size m ≥ poly(1/ϵ, 1/δ, n, size(c)):P S∼D m [R D (h S ) ≤ ϵ] ≥ 1 -δ.Most of sparse spatio-temporal data learning models have the following encoder-decoder architecture.The encoder f e learns all ST point representations from sparse data and the decoder f d outputs node-level predictions for specific downstream task.f d (f e ( X)) = ϕ 1 T t∈T f e ( X) t W d ,where W d represents the trainable weight matrix in decoder. In the encoder, the iterative models to learn the missing ST point representations work by continuously extracting valid information from its neighbors. The key differences between iterative models lie in how they define neighbors and how they aggregate messages from these neighbors.Let Z = {(v, t)|v ∈ V, t ∈ T }.For any ST point z ∈ Z, we denote the set of its neighboring ST points at the k-th iteration by N k z . According to the definition of neighbors, we can infer the path between any two ST points. Without loss of generality, for any z ∈ Z, we can formulate the k-th iteration as follows.h k z = ϕ   z ′ ∈N k z p k z ′ →z • h k-1 z ′   ,where h k z denotes the learned representation for ST point z after the k-th iteration. For messagepassing, the iterative models usually assign weight p k z ′ →z to messages from z ′ to z. We denote the distance of the path from ST point z to z ′ as d z→z ′ . Let Z o ⊆ Z to be the set of all observed ST points and Z m = Z\Z o . To ensure that the model has ability to recover all ST points, the number of iterations must satisfies K ≥ max z ′ ∈Zm min z∈Zo d z→z ′ . Therefore, multiple iterations are inevitable in highly sparse large-scale spatio-temporal data.We then establish the PAC-learnable guarantee for the iterative spatio-temporal imputation methods. First, let us immediately mask some mild assumptions that are easy to implement. Assumption 4.2. For the weight matrix in decoder, we assume its spectral norm satisfies ∥W d ∥ 2 ≤ B d , for any ST point z ∈ Z, we assume its feature vector satisfies ∥x z ∥ 2 ≤ B x . For the loss function, we assume l is an C l -lipschitz continuous and bounded by [0, 1]. For the activation function, we assume ϕ is C ϕ -lipschitz continuous with ϕ(0) = 0. For the mask distribution M, we assume that all ST points are randomly masked with a probability of ρ. Proposition 4.3. Let F be a K-iterations imputation model class, we assume its learned propagation weights are bounded by [0, γ]. If we draw a sample S of size m, for any f ∈ F, the following inequality holds.P S∼ Dm [R D (h S ) ≤ ϵ] ≥ 1 -δ with m ≥ log 1/δ 2ϵ-4ηCK-4(1-η)CK•ρ τ -4C l ℜm(F ) , where C = C l • γ K • C K+1 ϕ • (d max ) K • B x B d . Remark 4.4. Here 0 < η < 1 , d max = max z∈Z |N z | and τ = max z∈Z |{d z ′ →z < K|z ′ ∈ Z}|.Consider PAC-learnability under complete data, number of required samples needs to satisfy m ≥ log 1/δ 2(ϵ-2C l ℜm(F )) . Since ℜ m (F) represents Rademacher complexity of model class F, it is encouraging that the learnability of the model on sparse data is related to the one on complete data. Thus, we can estimate the impact of the missing data on the model performance. Obviously, the required sample size m is positively correlated with the missing ratio ρ and the number of model iterations K. Nevertheless, the structural sparsity in the spatio-temporal data itself limits the learnability of the iterative model in addition to the data sparsity. Specifically, τ is related to the number of k-hop neighbors of each ST point. Therefore, the sparser the spatio-temporal structure (i.e., smaller τ ), the greater the number of samples required. This theoretical result provides an interpretation for iterative model-induced error accumulation. Note that although we assume that all ST points are masked at random (MAR), this proof strategy can be generalized to other mask distribution M. 
methodology: 
 This section presents our proposed method, One-step Propagation and Confidence-based Refinement (OPCR), as illustrated in Fig. 1 . In the first stage, we independently learn intrinsic representations for ST points in both spatial and temporal dimensions. We then employ a sparse attention-based one-step propagation strategy to obtain two separate imputation results. In the second stage, we derive imputation confidence based on the learned correlations between ST points to address potential biases in these results. Finally, we perform confidence-based spatio-temporal propagation to refine the final predictions.Motivated by the aforementioned theoretical findings, we propose a one-step propagation method to avoid error accumulation and information loss commonly found in iterative methods. Specifically, as illustrated in Fig. 1 , we begin by independently learning intrinsic spatial and temporal representations for ST points. We capture correlations among ST points across different dimensions by adopting a sparse attention mechanism. This approach enables the limited information to be propagated directly to the global context as efficiently as possible. Q K V Q K V Figure 1:The framework of the proposed OPCR.We first address the significant spatial sparsity present in spatio-temporal data. To fully utilize limited observation, we learn the correlations between nodes using static spatial information. Leveraging these intrinsic dependencies, messages from all observations are propagated directly to the global context through a sparse attention mechanism. We utilize a L s -layers Graph Neural Network (GNN) [16] to learn the spatial representations of nodes from the graph structure. We initialize S 0 using the inherent static attributes of all nodes; then the layer-wise updation can be summarized as follows.S l = ϕ S l-1 W l 1 + D -1 AS l-1 W l 2 ,where W l 1 and W l 2 are the parameter matrix in the l-layer; D is the degree matrix of A. In order learn the spatial associations between nodes, we employ a self-attention mechanism [17] . We use node embeddings S = S Ls as both the key and query. We denote the set of available nodes by Ṽ ⊂ V. For any node u ∈ V, v ∈ Ṽ, the spatial self-attention is formulated as:EQUATIONα s u,v = exp(⟨q s u , k s v ⟩) v ′ ∈ Ṽ exp(⟨q s u , k s v ′ ⟩), where Q s , K s , V s t ∈ R N ×F represent the query, key, value of spatial self-attention; q s i , k s i and v s i,t stand for their i-the row; W s Q , W s K , W s V ∈ R F ×F are parameter matrices. For any ST point (v, t), we aggregate spatial messages coming from all observations weighted by learned attentions. The spatial dependencies-based imputation result can be computed as:EQUATIONAnother component is designed to learn temporal correlations. We adopt a temporal attention mechanism for the time-series data associated with each node. Unlike recurrent sequence models such as RNN or LSTM, Transformers are not inherently capable of learning sequence information [18] . We first introduce vanilla positional encoding [17] to capture this information. If real-world timestamps are available, we use a learnable embedding layer to encode these timestamps [19] .Combining positional encoding with timestamp encoding, for any node v ∈ V, the input to the temporal sparse attention module can be formulated as follows.X v = X v + P E(X v ) + M LP (U ), P E pos,2i = sin pos/10000 2i/d model P E pos,2i+1 = cos pos/10000 2i/d modelwhere X v is associated time-series of node v; U is the available real-world time information, such as the hour of the day.For any node v, X v serves as the key, query, and value in the temporal self-attention mechanism. For node v, similar to the spatial module, we denote the available time steps by Tv . Then the temporal attention score and the temporal aggregation are formulated as:EQUATION(α t t1,t2 ) v = exp(⟨q t v,t1 , k t v,t2 ⟩) t ′ 2 ∈ Tv exp(⟨q t v,t1 , k t v,t ′ 2 ⟩) , h t v,t = MLP t ′ ∈ Tv (α t t,t ′ ) v v t v,t ′ , where Q t v , K t v , V t v ∈ R T ×F represent the query, key, value of spatial self-attention; q t v,i , k t v,i and v t v,i stand for their i-the row; W t Q , W t K , W t V ∈ R F ×F are parameter matrices.Based on these two sparse attention modules, we propagate all available information to the global missing data in one step. We also give a PAC-Learnability analysis for the proposed method. P S∼ Dm [R D (h S ) ≤ ϵ] ≥ 1 -δ with m ≥ log 1/δ 2[ϵ-4ρC-2C l ℜm(F )] , where C = C l • C ϕ • B d • B v . Remark 5.2.It can be seen that the number of required samples is positively correlated with the sparsity ρ. Unlike iteration-based models, sparsity is the sole factor that constrains the performance of the sparse attention-based model when dealing with incomplete data. Consequently, the proposed one-step strategy is scalable to various spatio-temporal data of different sizes and structures.In the first stage, we reconstructed the missing representations based on inherent spatial and temporal information. However, these two independent modules decompose the global context. Integrating these results and refining them through spatio-temporal structure is a straightforward idea. To further propagate reliable information, we propose a confidence-based message-passing mechanism. Intuitively, there are correlations between any pairwise spatio-temporal points. Thus, the missing data will remove some dependencies. The larger the correlations between an ST point and other observations, the more plausible its recovery. Therefore, for any ST point (u, t), we can define the confidences of its spatial and temporal imputation results as:EQUATIONWe extract highly confident parts from separate imputation results in temporal and spatial dimensions. However, simple weighting ignores the global context in spatio-temporal data. Therefore, we propose to employ the learned confidences as propagation weights through the spatio-temporal dimension.For any ST point (u, t), we first define the set of its neighbors asN u,t = {(v, t)|v ∈ N u } ∪ {(v, t ′ )|t ′ ∈ T \t} ,where N u denotes the set of neighboring nodes of node u in the fixed graph G. Then the layer-wise message-passing for ST point (u, t) can be formulated asO l+1 u,t = MLP O l u,t ∥ (v,t ′ )∈Nu,t β v,t ′ • O l v,t ′ ,where O 0 u,t = h s u,t + h t u,t . During L layers, we finally recover representations for all ST points. Then the decoder is designed depend on different downstream tasks. 
experiments: 
 We evaluate our approach on three sets of real-world datasets for different downstream tasks, including imputation and prediction. More experimental details and time complexity analysis are provided in the appendix. The source code and datasets are available at https://github.com/dleyan/OPCR.We consider three sets of spatio-temporal datasets and summarize their statistics in Table 1 . It is evident that these datasets vary in terms of topology size. The T4C22 dataset primarily comprises spatially missing data, exhibiting an exceptionally high sparsity of up to 90%. To simulate incomplete data in realistic scenario, we design two policies to inject missing data into original datasets: 1) Point Missing, in which we follow the same setup of [12, 11] , randomly dropping ρ of the available data. 2) Spatial missing, in which we are inspired by the T4C22 dataset, randomly dropping 25% of the available data, then mask out ρ of the devices.We compare the proposed OPCR with various baselines designed for different data types.• Tabular Imputation. We consider three statistical methods for matrix imputation: 1) Mean, imputing missing data using the mean value at each time step. 2) Matrix Factorization (MF) [20] with rank = 10. 3) GRAPE [21] , a graph-based feature imputation method, which regards observations and features as two types of nodes in a bipartite graph, and the observed feature values as edges. • Graph Imputation. For spatial missing, we consider some node attributes imputation methods: 1) Feature Propagation (FP) [3] , iteratively propagating observed messages through graph structure. 2) PCFI [4] , further measuring the propagation confidence. • Time-series Imputation. To impute multivariate time-series, we consider: 1) BRITS [7] , a bidirectional RNN-based model. 2) SAITS [8] , a transformer-based model. 2) CSDI [9] , a diffusion-based model. • Spatio-temporal Data Imputation. We also consider some state-of-the-art methods for spatio-temporal data imputation. 1) IGNNK [10] , an inductive GNN-based model. 3) SPIN-H [12] , an efficient version of spatio-temporal attention based method. 3) PriSTI [13] , a conditional diffusion model. 4) PoGeVon [14] , solving a specific issue in which spatiotemporal data contains missing values in both node time series features and graph structures.For the imputation task, we consider mean absolute error (MAE) as evaluation metrics. All the experiments are run with 5 different random seeds. In each round, we inject ρ of missing data into the entire dataset using different masking policies. All models are trained on the sparse training set and evaluated on the corresponding sparse testing set.The experimental results of all models are summarized in Table 2 , where the missing rate ρ is set as 95%. There is a clear gap in the imputation performance on the traffic dataset between spatial-missing data and point-missing data, indicating that recovering spatial-missing data is a challenging issue. For the tabular and graph imputation baselines, their performance remains relatively consistent across datasets with spatial and point missing. This can be easily understood, as these baselines only utilize or fail to utilize spatial structure. The time-series imputation baselines are not suitable for spatial missing, as they solely rely on temporal information. In addition, it is difficult for them to model such a high-dimensional time series on large-scale datasets.For state-of-the-art (SOTA) spatio-temporal series imputation baseline SPIN-H, they are most suitable for small-scale data with point missing. Since they only propagate partial observation iteratively, larger topology and higher spatial missing rate imply a need for more iterations. Therefore, the error accumulation and information loss during iterative process lead to their poor performance. For the inductive baseline IGNNK, it converts the original task to smaller-scale spatio-temporal series via sampling sub-graphs. The effectiveness of IGNNK proves that there are correlations between all nodes, which is consistent with our motivation. However, this sampling strategy still ignores some of the valid information. Therefore, considering the problem of error accumulation in autoregressive methods, some diffusion-based models have been proposed, such as CSDI [9] and PriSTI [13] . It is still challenging for CSDI to model a high-dimensional time series in the large-scale dataset. However, it show performance improvement on the traffic dataset compared to other temporal baselines (i.e., BRITS and SAITS). For the spatio-temporal method PriSTI, it achieves better performances than SPIN-H on the traffic dataset with spatial missing. However, its performances are unstable on the large-scale datasets, especially the spatially missing data. PoGeVon [14] is proposed to deal with specific data where attribute-missing and structure-missing co-exist. Therefore, it show worse imputation performances than other spatio-temporal baselines. In addition, PoGeVon does not apply to the large-scale dataset because of its high computational complexity.As a result, our proposed OPCR outperforms all the baselines in most cases. Especially, on traffic dataset with spatial missing, OPCR exceeds the best baseline by 26% and 37%. on large-scale PVUS dataset, OPCR exceeds the best baseline by 11% and 24% under two settings. These experiments demonstrate the effectiveness and scalability of our proposed OPCR.To evaluate the effect of data sparsity on imputation performance, we simulate sparse data at various rate, ranging from 25% to 95%. Figures 2 and 3 report imputation performances on point missing data and spatially missing data, respectively. On the traffic dataset, it is clear that the imputation errors increase with the missing rate. Similar to the results in challenge for all models. On large-scale datasets, temporal baselines struggle to model extremely high-dimensional data and do not exhibit the same trends as observed in the traffic dataset. In addition, these models usually terminates training process early then result extremely poor imputation performances. For the inductive spatio-temporal baseline IGNNK, its overall performance show a significant improvement when the missing rate is reduced from 95% to 75%. This empirical results are due to IGNNK can not sample enough sub-graph data for training in highly-sparse data. For SPIN-H, its imputation error on the CER-E dataset is not exactly positively correlated with the missing rate, which is consistent with our theoretical findings. The diffusion-based method PriSTI achieves significant improvements over other baselines on the traffic dataset with spatial missing. However, PriSTI struggle to deal with large-scale dataset. For the proposed OPCR, we can observe that it outperforms baselines in most cases. Furthermore, the imputation performances of our method steadily improves with decreasing missing rates. This experimental result is consistent with the theoretical findings, confirming that the PAC learnability of the proposed OPCR is only constrained by data sparsity.For the T4C22 dataset, we follow the competition rules. We set the evaluation metric to a weighted cross-entropy loss for the congestion classification task, and MAE for the prediction task. All the models are equipped with the same downstream network and use the same training strategy. Table 3 presents the traffic performance comparison for two downstream tasks. Since we designed strong downstream models for both prediction tasks, the performance gap is insignificant. It can be seen that our proposed OPCR outperforms baselines across all experiments. There are also some findings in the traffic prediction experiments. SPIN-H performs poorly compared to graph imputation baselines (i.e., FP and PCFI). This is because the T4C22 dataset only considers short-term (i.e., 4 time steps) historical series, and its highly spatial sparsity results in slow propagation of valid information. To evaluate the effectiveness of different components of our proposed OPCR, we make comparisons between some model variants. To demonstrate the robustness of our model, we also conduct sensitivity analysis with respect to model's hyper-parameters. All models here are trained on the traffic datasets and large-scale datasets with 95% missing rate.Effectiveness of Each Component. We consider the following variants. The results of the ablation study are shown in Fig. 4 . First, we compare the spatial module and temporal module. Obviously, it is challenging for both variants to handle spatially missing data. On the large-scale dataset, the temporal module presents poorer performances compared to the spatial module. This result is easy to understand because the temporal module utilizes a narrower range of valid information. Second, combining temporal-based and spatial-based results yields superior performances compared to a single module. Finally, when comparing the complete model with all variants, it can be seen that confidence-based propagation also plays a vital role.Sensitivity w.r.t. Hyper-parameters. First, we consider the effect of hidden states, as shown in Fig. 5 . As the hidden states go from 16 to 256, the overall performance slowly increases and then fluctuates slightly. Therefore, we set the number of hidden states to 128. This result reflects the robustness of the proposed model. Then, we consider the sensitivity w.r.t. the number of layers in stage 2, as shown in Fig. 5 . The approximate best level can be reached when the number of layers is only 2. These experiments prove that our design motivation is that a shallow iterative propagation is enough to refine the complete recovery by the first stage. 
conclusion: 
 For the highly sparse spatio-temporal data learning problem prevalent in the real-world, the existing common scheme is iterative propagation-base imputation. However, such methods empirically suffer from error accumulation and high computational costs in large-scale data. Therefore, we first provide a PAC-learnability analysis for iterative imputation methods from the perspective of PAC-learnability, which theoretically demonstrates their limitations. Motivated by theoretical findings, we propose onestep propagation and confidence-based refinement (OPCR). In the first stage, we rapidly propagate useful information to all missing data through a sparse attention mechanism that makes full use of limited observations. To eliminate the bias caused by independent temporal and spatial modeling, we propose assigning confidence to imputation results and achieving more accurate spatio-temporal message-passing. We evaluate the imputation and prediction performances of the proposed OPCR on a dataset of different scales. The experimental results illustrate our approach outperforms the state-of-the-art imputation methods. There are several interesting future directions. First, it would be interesting to explore some downstream tasks without supervision. The second is to extend our theoretical analysis to non-random missing scenarios. 
acknowledgment: 
 The work was supported by grants from the National Natural Science Foundation of China (No. 92367110). 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [Yes]Justification: We point out that exploring spatially missing data can lower the barrier of some realistic applications, such as intelligent transportation.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA]Justification:Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [Yes]Justification: We have illustrated that some experiments on the traffic dataset follow SPIN.Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.• If this information is not available online, the authors are encouraged to reach out to the asset's creators. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review. 
 
 Appendix: We consider the following three sets of spatio-temporal datasets.• Traffic dataset [22] record traffic dynamics every 5 minutes in San Francisco Bay Area and LA County, respectively [11] .• Large-scale dataset [23] includes two larger-scale datasets. The sources of the PV-US dataset and the CER-E dataset are the simulated energy production by PV farms 1 and the CER Smart Metering Project2 , respectively. Both datasets are aggregated in 30 minutes.• T4C22 dataset [24] record traffic dynamics every 15 minutes from vehicle detectors in three cities, which is provided by Traffic4cast 2022 competition 3 .For the traffic dataset and PV-US dataset, we derive the adjacency from pairwise geographic distances [22, 25] . Without location information, the adjacency of the CER-E dataset is derived from similarity between historical series. For the T4C22 dataset, the available urban road networks can serve as adjacency.Considering memory consumption, for SPIN, we choose the efficient version SPIN-H as baseline.On the traffic dataset, we train all models with an RTX 3090 GPU (24GB RAM). On the large-scale dataset and the T4C22 dataset, we train them with a V100 GPU (16GB RAM). All the baselines have been implemented in PyTorch [26] . We use, whenever possible, the open-source code and configuration provided by the authors.For spatio-temporal data imputation task, we select windows of length 24. On the traffic datasets, we strictly follow the settings of SPIN 4 . We fix the maximum number of epochs to 300 and we use early stopping on the validation set with patience of 40 epochs. On the large-scale dataset, considering memory capacity and computational efficiency, we reduced the number of hidden states to 16 for some baselines (i.e., SPIN-H, CSDI, and PriSTI). We fix the maximum number of epochs to 200 and we use early stopping on the validation set with patience of 10 epochs.For traffic prediction task, we follow the competition settings. Since the original test dataset is unlabeled, we randomly select data from the training set for different days. Note that this partitioning strategy is aligns with the competition rules. We provided each model with the same downstream network and trained the models end-to-end. For congestion classification task, we train all the models for 20 epochs. For travel time prediction task, we train all the models for 50 epochs. We both select the best model with the minimum loss on the validation set for evaluation.We compare our proposed OPCR with SOTA iterative imputation baselines SPIN. We let the number of edges in G be E and the number of iterations for all models be L. According to [12] , the time complexity of SPIN scales with O L(N + E)T 2 and its efficient version SPIN-H scales with O (L(N + E)KT ), where K ≪ T .For our proposed OPCR, in the first stage, we propagate observations to missing data, thus we can reduce the time complexity from O N 2 + N T 2 to O (N 2 + N T 2 ) × ρ(1 -ρ) via sparse attention matrices. Considering the sparsity of the graph structure, it is reasonable to assume that E and N 2 × ρ(1 -ρ) are similar in magnitude. Moreover, since we learn spatial attention matrix from static node features and share it across all spatio-temporal series within a batch, the the computation remains efficient despite the introduction of attention-based confidence assignment. In the second stage, the time complexity of layer-wise updation is O ET + N T 2 . As we mentioned in Section 4, after one-step propagation, OPCR requires fewer iterations for refinement compared to SPIN. Therefore, our proposed method actually has greater computational efficiency and scalability.In addition, following [23] , we present the timings and memory consumption in the Table 4 . Compared to the spatio-temporal imputation baselines SPIN-H, our proposed model shows significant superiority in computational efficiency and memory usage. P S∼ Dm [R D (h S ) ≤ ϵ] ≥ 1 -δ with m ≥ log 1/δ 2ϵ-4ηCK-4(1-η)CK•ρ τ -4C l ℜm(F ) .Given an sparse training set S ∼ Dm , for any f ∈ F, we haveEQUATIONCorollary B.2. For any f ∈ F and any (X, Y ) ∈ X × Y, we mask all ST points at random with probability of ρ. We denote this mask distribution as M. Given a complete spatio-temporal series X and its sparse version X, we denote the node-level output of the model as Ŷ = f (X) and Ỹ = f ( X). The difference between the model's prediction error on complete data and sparse data have the following upper bound.E M ∼M L( Ỹ , Y ) -L( Ŷ , Y ) ≤ C • K k=1 ρ τ k-1 min + η • (1 -ρ τ k-1 max ) ,whereC = C l • γ K • C K+1 ϕ • (d max ) K • B X B d .Proof. Under assumptions, f is an encoder-decoder architecture, for any complete samples (X, Y ) and its sparse version ( X, Y ), we haveL( Ỹ , Y ) -L( Ŷ , Y ) = 1 N v∈V (l ( ỹv , y v ) -l ( ŷv , y v )) ≤ C l • 1 N v∈V ∥ ỹv -ŷv ∥ 2 (9) = C l • 1 N v∈V f d (f e ( X)) v -f d (f e (X)) v 2 .Here Eq.9 is due to the loss function l is C l -lipschitz continuous. As the assumption about decoder f d , we haveEQUATION)Here Eq.10 is due to the ϕ is C ϕ -lipschitz continous and Eq.11 is due to ∥W d ∥ 2 ≤ B d . Since the encoder f e is a K-iteration imputation model, we denote the ST point representations after k iterations by H k and Hk . We denote the set of recovered ST points after k iterations by N k o . For the number of iterations K, we assume that K exactly satisfies Z K o = Z and for any Z K-1 o ⊂ Z. Thus, we haveEQUATIONwhere Z = {(v, t)|v ∈ V, t ∈ T }. Then we have the following recursion:EQUATIONEQUATION≤ C ϕ • z∈Z k o   z ′ ∈ Ñ k z |ã k z ′ →z | • hk-1 z ′ -h k-1 z ′ 2 + z ′ ∈N \ Ñ k z |a z ′ →z | • h k-1 z ′ 2 + z ′ ∈ Ñ k z |ã k z ′ →z -a z ′ →z | • h k-1 z ′ 2  Here Eq.13 is due to that ϕ is C ϕ -lipschitz continuous. Eq.14 is due to ãkz ′ →z = 0 if z ′ ∈ N z \ Ñ k z .For ∀z ∈ Z and ∀z ′ ∈ N z , we assume that 0 < a z ′ →z ≤ γ. For ∀z ∈ Z, ∀z ′ ∈ N k z and ∀k ∈ [1, K], we assume that 0 < ãk z ′ →z ≤ γ and 0 < |a z ′ →z -ãk z ′ →z | ≤ γ ′ < γ. These assumptions are easy to implement because the model tends to use positive weights when aggregating neighboring ST points.For convenience, let 0 < η = γ ′ γ < 1, we haveEQUATIONEQUATIONFor the second term and the third term in Eq. 16, we haveEQUATIONHere τ k max = max z∈Z τ k z and τ k min = min z∈Z τ k z , whereEQUATIONTherefore, expanding the recursion in Eq. 16, we haveEQUATIONThen we can deriveEQUATIONSubstituting Eq.20 into Eq.12, we haveE M L( Ỹ , Y ) -L( Ŷ , Y ) ≤ C l • C ϕ • B d • 1 N T • E M z∈Z hK z -h K z 2 ≤ C l • C ϕ • B d • 1 N T • (γC ϕ d max ) K • N T B X • K k=1 ρ τ k-1 min + η • (1 -ρ τ k-1 max ) ≤ C l • γ K • C K+1 ϕ • (d max ) K • B X B d • K k=1 ρ τ k-1 min + η • (1 -ρ τ k-1 max ) . Let C = C l • γ K • C K+1 ϕ • (d max ) K • B X B d ,we finally derive the follows inequality.E M L( Ỹ , Y ) -L( Ŷ , Y ) ≤ C • K k=1 ρ τ k-1 min + η • (1 -ρ τ k-1 max ) .For the second term in Eq.8, R D (f ) -RS (f ) represents the generalization performance of f ∈ F over complete dataset. Model complexity measurements, such as VC-Dimension [27] , Rademacher complexity [28] and Covering number [29] are related to the generalization ability. Therefore, they can provide useful information about number of training samples m required for PAC-learnability under complete data. Rademacher complexity is frequently applied to investigate the generalization performances of GNN-based models. The Rademacher complexity-based generalization bound as given in [15] is: Lemma B.3. Let H be a function class mapping from X to [0, 1]. Then, for any δ > 0, with probability at least 1 -δ over the draw of an i.i.d. sample S of size m, for any h ∈ H, the following inequality holds.As our assumptions, the loss function l : R × Y → [0, 1] is C l -lipschitz continuous. Then we can derive the following corollary, which show that generalization gap is small when provided large enough training samples. Corollary B.4. Let F : X → [0, 1] be a function class for spatio-temporal data imputation. function class mapping from X to [0, 1]. Then, for any δ > 0, with probability at least 1 -δ over the draw of an i.i.d. sample S of size m, for any h ∈ H, the following inequality holds.P R D (f ) -RS (f ) ≥ ϵ ≤ e -2m(ϵ-2C l ℜm(F )) .Proof. Using Lemma B.3 and contraction lemma [15] , we haveR D (f ) ≤ RS (f ) + 2ℜ m (l • F) + log 1\δ 2m ≤ RS (f ) + 2C l ℜ m (F) + log 1\δ 2m .Therefore, we can rewrite this inequality then we have for any f ∈ FP R D (f ) -RS (f ) ≥ ϵ ≤ e -2m(ϵ-2C l ℜm(F )) .Using Corollary B.2 and B.4, we haveP R D (f ) -R S (f ) ≥ ϵ ≤ P R D (f ) -RS (f ) ≥ ϵ -R D (f ) -R D (f ) + RS (f ) -R S (f ) ≤ P R D (f ) -RS (f ) ≥ ϵ -2C • K k=1 ρ τ k-1 min + η • (1 -ρ τ k-1 max ) ≤ exp -2m ϵ -2C • K k=1 η -ηρ τ k-1 max + ρ τ k-1 min -2C l ℜ m (F) .Then we derive the number of required samples m:exp -2m ϵ -2C • K k=1 η -ηρ τ k-1 max + ρ τ k-1 min -2C l ℜ m (F) ≤ δ ⇒ exp 2m ϵ -2C • K k=1 η -ηρ τ k-1 max + ρ τ k-1 min -2C l ℜ m (F) ≥ 1 δ ⇒ 2m ϵ -2C • K k=1 η -ηρ τ k-1 max + ρ τ k-1 min -2C l ℜ m (F) ≥ log( 1 δ ) ⇒ m ≥ 1 2ϵ -4C • K k=1 η -ηρ τ k-1 max + ρ τ k-1 min -4C l ℜ m (F) • log 1 δ ⇒ m ≥ 1 2ϵ -4ηCK -4(1 -η)C • K k=1 ρ τ k-1 max -4C l ℜ m (F) • log 1 δ ⇒ m ≥ 1 2ϵ -4ηCK -4(1 -η)CK • ρ τ K-1 max -4C l ℜ m (F) • log 1 δFor convenience, we let τ = τ K-1 max .C Proof of Proposition 5.1Proof. Similar to proof of Proposition 5.1, we first derive the following upper bound for the difference between model performances under complete and sparse data. For any M ∈ M, we have1 N T • z∈Z hz -h z 2 = 1 N T • z∈Z ∥σ(ã z )V -σ(a z )V ∥ 2 ≤ 1 N T • z∈Z z ′ ∈Zo a z ′ →z z ′′ ∈Zo a z ′′ →z v z ′ - z ′ ∈Z a z ′ →z z ′′ ∈Z a z ′′ →z v z ′ 2 ≤ B v N T • z∈Z z ′ ∈Zo a z ′ →z z ′′ ∈Zo a z ′′ →z - a z ′ →z z ′′ ∈Z a z ′′ →z + 1 N T • z∈Z z ′ ∈Z\Zo a z ′ →z z ′′ ∈Z a z ′′ →z, where max z∈Z ∥v z ∥ 2 ≤ B v . Then we haveE M 1 N T • z∈Z hz -h z 2 ≤ B v N T • z∈Z E M   z ′ ∈Zo a z ′ →z • z ′′ ∈Z\Zo a z ′′ →z z ′′ ∈Zo a z ′′ →z • z ′′ ∈Z a z ′′ →z + z ′ ∈Z\Zo a z ′ →z z ′′ ∈Z a z ′′ →z   = 2B v N T • z∈Z E M z ′ ∈Z\Zo a z ′ →z z ′ ∈Z a z ′ →z ≤ 2B v • ρ Similar to proof of Proposition 4.3, P R D (f ) -R S (f ) ≥ ϵ ≤ exp (-2m [ϵ -4C l • C ϕ • B d • B v • ρ -2C l ℜ m (F)]) ⇒ P R D (f ) -R S (f ) ≥ ϵ ≤ exp (-2m [ϵ -4C • ρ -2C l ℜ m (F)]) ⇒ exp (-2m [ϵ -4C • ρ -2C l ℜ m (F)]) ≤ δ ⇒ 2m [ϵ -4C • ρ -2C l ℜ m (F)] ≥ log 1 δ ⇒ m ≥ log 1/δ 2 [ϵ -4C • ρ -2C l ℜ m (F)],whereC = C l • C ϕ • B d • B v .NeurIPS Paper Checklist38th Conference on Neural Information Processing Systems (NeurIPS 2024).https://www.nrel.gov/grid/solar-power-data.htmlhttps://www.ucd.ie/issda/data/commissionforenergyregulationcer/https://www.iarai.ac.at/traffic4cast/challenge/https://github.com/Graph-Machine-Learning-Group/spin 


Decision: The paper presents  a novel framework for spatio-temporal imputation, leveraging Probably Approximately Correct (PAC) theory to offer a unique perspective on error accumulation in iterative imputation models. The theoretical analysis is innovative, particularly in its application to sparse attention-based imputation models. The authors propose a one-step propagation and confidence-based refinement framework, which effectively addresses error accumulation and can be applied to both spatial and temporal missing data scenarios. This high-level approach offers new insights for the design of future imputation algorithms. The paper also explores the challenges of spatially sparse data, emphasizing the importance of utilizing available data efficiently and lowering barriers to implementing spatio-temporal models in real-world applications. Experimental results on several benchmark datasets demonstrate that the proposed OPCR framework outperforms existing baselines across various spatio-temporal tasks. The theoretical analysis of existing iterative message-passing methods is highlighted as a significant contribution, potentially inspiring future research in sparse data learning. Additionally, the paper is well-organized, clearly identifying the limitations of existing methods through theoretical analysis and motivating the proposal of an improved method. The focus on tackling high sparsity in spatio-temporal data is particularly relevant, given its importance in many downstream applications. Overall, the paper combines strong theoretical foundations with practical experimental validation, making it a valuable contribution to the field of spatio-temporal imputation. The paper should be publised as NeurIPS2024.

Reviews: review: paper_summary: paper_summary: This paper leverages the Probably Approximately Correct (PAC) theory to study the message-passing mechanism of spatial-temporal imputation. Inspired by the results of PAC, this paper introduces a One-step Propagation and Confidence-based Refinement (OPCR) model for spatial-temporal imputation. OPCR is comprised of a spatial and a temporal sparse attentions, and a confidence-based refinement module. Experimental results on several benchmark datasets show that OPCR could outperform several baselines.
strength_weakness: strength_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. 
2. The presentation needs further improvements, especially the theoretical part. Many details and claims need clarification, please see questions.
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].

[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] Provably Convergent Schrödinger Bridge with Applications to Probabilistic Time Series Imputation, ICML'2023
questions: questions: 1. What does "poly" mean in line 98?
2. Line 101-102 & 104-105, what does $\phi$ mean?
3. Line 106-107, why should the model need to have the ability to recover all ST points?
4. In Assumption 3.2, what do $B_d$ and $B_x$ mean?
limitations: limitations: N/A
paper_summary: paper_summary: This paper proposes a sparse attention-based one-step imputation and confidence-based refinement approach named One-step Propagation and Confidence-based Refinement (OPCR). The authors evaluate the proposed model across two downstream tasks involving highly sparse spatio-temporal data. The contributions of this paper are as follows:

1. The authors provide a theoretical analysis of a general spatio-temporal iterative imputation model from the perspective of PAC-learnability.

2. Motivated by the theoretical results, this paper introduces a sparse attention-based one-step propagation strategy. This strategy directly propagates information from limited observations to all missing data by leveraging inherent spatial and temporal relationships, resulting in two separate spatial and temporal imputation results. The authors then perform confidence-based spatio-temporal refinement to eliminate the bias introduced by the separate imputations by assigning confidence-based propagation weights to the imputation results.

3. Finally, experiments are conducted comparing several existing imputation methods with the proposed method on real-world datasets, demonstrating the effectiveness of the proposed method.
strength_weakness: strength_weakness: 1. In Section 4.1.2, the construction details of the input to the temporal sparse attention module are not described. Additionally, there are some typos in this paper. For example, the symbol \(H^0\) at line 196 is incorrectly written, the symbols $q^t_t$ and $k^t_k$ 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.

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.

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.
questions: questions: 1. In Figures 4 and 5, why is the MAE result of the SAITS ∞ in the PV-US and CER-E datasets?

2. What's the advantage of the proposed model compared with diffusion model-based methods?
limitations: limitations: Yes.
paper_summary: paper_summary: The paper addresses the issue of incomplete spatio-temporal data. It theoretically analyzes how existing iterative message-passing methods are susceptible to the impacts of data sparsity and graph sparsity. It proposes the One-step Propagation and Confidence-based Refinement (OPCR). In OPCR, the Sparse Spatial Attention module captures spatial information, while the Sparse Temporal Attention module focuses on dynamic temporal information. And, the Confidence Module in Confidence-based Iterative Refinement further refines these two types of information through spatio-temporal dependencies.
strength_weakness: strength_weakness: 1.	The paper uses PAC-learnability to analyze generalization risk. Have the author(s) considered using other mathematical tools, such as Rademacher complexity?
2.	Could the author(s) further discuss the potential strength of the proposed method in practical scenarios?
3.	There are some typo and grammatical errors. For instance, "seperate" on Line 13, "problem" on Line 29.
questions: questions: 1.	Have the author(s) considered using other mathematical tools to analyze generalization risk, such as Rademacher complexity?
2.	Could the author(s) further discuss the potential strength of the proposed method in practical scenarios?
limitations: limitations: yes
paper_summary: paper_summary: This paper proposes to address the challenge of learning from incomplete spatio-temporal data, which is prevalent in various real-world applications. Accordingly, this paper proposes a method named OPCR to handle data sparsity more effectively. Specifically, the method first directly utilizes spatial and temporal relationships to propagate limited observations to the global context through a sparse attention mechanism. After the initial propagation, confidence-based refinement is applied to refine the imputations, correlating the missing data with valid data to enhance the quality of the imputation. Experiments show that OPCR outperforms several baselines in various downstream tasks involving highly sparse spatio-temporal data.
strength_weakness: strength_weakness: W1. The presentation needs to be significantly improved. Many parts of the contents are vague and difficult to follow.

-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.

-The notations for the theory provided in Section 3 do not offer detailed explanations. I cannot find the definitions for many of them. For example, what is “poly()” in Definition 3.1? what is \mathcal{T}? what are Z_m, Z_o?

-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? 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.

W2. 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”.

W3. 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.

W4. Figure 1 is not informative at all. I cannot really understand which parts of the nodes and timestamps are utilized for sparse attention. Again, due to bad notations and presentation, I don’t really follow the paper.

W5. Some of the related studies are highly related, and thus should be included. For example, [1, 2].

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

[2] Networked Time Series Imputation via Position-aware Graph Enhanced Variational Autoencoders. KDD 2023
questions: questions: Please give more explanations on my comments in W1-W4.
limitations: limitations: The authors did not discuss the limitations or negative impact of their paper.

Comments: title: Thanks
need your comment
Welcome for more discussions
comment: To Reviewer Ctvj,

Thanks to your reply.

best

Area Chair
Thanks for the responses.

My major concerns about (1) comparison with SPIN and (2) comparison with recent baselines are mostly addressed in the rebuttal. I'll update my scores later during the discussion period.
To reviewer aMi7,

In response to the authors' comments, it is unclear in what respect they remain problematic. 
If you are going to keep the initial score, please explain in detail why.

best

Area Chair,
Thanks for your valuable time in reviewing and constructive comments, according to which we have tried our best to answer the questions and carefully revise the paper. We humbly hope our response has addressed your concerns. 

Considering your current rating, if you believe that our responses have satisfactorily addressed your concerns, we kindly request that you consider revising your final rating of our manuscript. If you have any additional concerns or comments that we may have missed in our responses, we would be most grateful for any further feedback from you to help us further enhance our work.
Thanks for your response. After reading it, I would like to keep my score.
Thank you for the detailed responses, it addressed most of my concerns.