Learning from Highly Sparse Spatio-temporal Data
Authors: Leyan Deng
Chenwang Wu
Defu Lian
Enhong Chen
Venue: NeurIPS 2024 poster (2024)
Keywords: spatio-temporal data mining; incomplete data imputation
Primary area: deep_learning_architectures

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.

Learning from Highly Sparse Spatio-temporal Data
Leyan Deng', Defu Lian 1%+, Chenwang Wu', Enhong Chen 1 f School of Artificial Intelligence and Data Science, University of Science and Technology of China 8 School of Computer Science and Technology, University of Science and Technology China {dleyan, wcw1996) @mail. ustc. edw...dduccc. en, (liandefu, cheneh) euu.:eeuutututt.eeee.ooooo cn
Abstract
Incomplete spatio-temporal data in the real world has spawned much research. However, existing methods often utilize iterative message-passing across temporal and spatial dimensions, resulting in substantial information loss and high com- putational cost. We provide theoretical analysis revealing that such iterative models are susceptible to data and 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 employ- ing sparse attention mechanism. These modules propagate limited observations directly to the global context through one-step imputation, which is theoretically affected only by data sparsity. Following this, assign confidence levels the initial imputations by correlating missing data with valid data. This confidence- based propagation refines the separate spatial and temporal imputation results through spatio-temporal dependencies. We evaluate the proposed model across various downstream tasks involving highly sparse spatio-tempora data. Empirical results indicate that our model outperforms state-of-thee imputation methods, demonstrating its effectiveness and robustness.
1 Introduction
Spatio-temporal data, encompassing information distributed across both spatial and temporal dimen- sions, 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 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 neatio-tempora 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 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-bace one-step imputation and confidence-bais based refinement approach. In the first stage, we propagate information from observed
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

data to all missing data directly, leveraging inherent spatial and temporal correlations. In the second stage, we assign confidence-basee propagation weights the imputed results. Through confidence- based 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 PAC- learnability 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.
2
Related Works
There are many works exploring how to impute different types of sparse data. For tabular data, matrix factorization-basee methods are widely popular. A recent work transformed tabular data imputation into link prediction in 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) B iteratively aggregates neighboring node features and PCFI 44 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 se- quence models. For example, BRITS 77] proposed bidirectional Recurrent Neural Networks (RNN). SAITS 8 designed self self-attention based model and jointly trained imputation and reconstruction objective. CSDI [9] proposed a conditional score-based diffusion model. However, these time-series data.
imputation methods ignore intrinsic spatial dependencies in
For spatio-temporal data, existing research leverages topological information effectively. IGNNK [1] introduced scalable inductive method trained by reconstructing random sub-graphs. GRIN 11 was the first to apply Graph Neural Networks (GNNs) 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 eтror accumulation and information loss. In addition, PriSTI [13 proposed a diffusion-basee 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, PoGe Von [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, where V and È denote the set of N nodes and E edges, respectively; A E R is the corresponding adjacency matrix. A spatio-temporal series of length T is represented by X E NxTxx= where Fg denotes the number of feature dimensions. We represent each spatio-temporal point (ST point) with a tuple = (v, 1) and L.,, E P denotes the collected data of node v at time 1.
Definition 3.2 (Spatio-temporal Mask). For spatio-temporal series X, we use binary mask M to
indicate missing ST points, where my,t = if ar,,, is missing, otherwise m.,t = 1. Note that, since faulty device often miss all records, we ignore the availability of data in feature dimension. Thus,

---

we can define unique sparse spatio-temporal series X in terms of X and M, i.e.
X = X + M NoN o (1-M),
(1)
Definition 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.
C(Y,))
1 N
Σ VEV
Uyy.r 9v).
(2)
where .) is element-wise loss function that depends specific downstream tasks. Here ye and y, are the ground truth and model's s prediction for node v, respectively.
For imputation task, the model aims to minimize the reconstruction error as follows.
C(X,
1
E
mm,)) (( Lw,t);
(3)
M
DEVIET
where T denotes the set of time steps and I(:-)) -) an element-wise loss function.
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, provide theoretical analysis in terms of PAC-leamability for node-level tasks.
We use X X and Y Y to denote complete spatio-temporal series and node-level labels, and use M E M to denote mask distribution. Let 'D be the fixed but unknown distribution over X' x y We define the mixture distribution D of DD and M using Eq. Given training Š = (X,, Y)) mm we assume that all samples in Š are i...d. according to D, denoted as Š Dmm Let E F X M y be sparse spatio-temporal data learning model, the empirical risk over S and the corresponding generalization risk is defined as follows,
Empirical risk R&(f)
Σ ((((X), Y)) m7
1
m
Generalization risk Rf( = E(XY) ((((X). r)
Similarly, denote empirical and generalization risk under complete data as Rs(f) and RD(f).
Definition 4.1 (PAC-Learnabilityy (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 po satisfying: for any e, > 0 and any distribution D, the following holds for any sample size m poly(1/e, 1/6, n, size(c)):
PS-Dm
(Rp < 8-
Most of sparse spatio-temporal data learning models have the following encoder-decoder architecture. The encoder Se leams all ST point representations from sparse data and the decoder fa outputs node-level predictions for specific downstream task.
fa(f((X)) = ( [
1ET
where Wa 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 {(, t)lu V,t E T}. For any ST point Z, denote the set of its neighboring ST points the k-th iteration by No. According to the definition of neighbors, can infer the path

---

between any two ST points. Without loss of generality, for any 2 E 2, we can formulate the k-th iteration as follows.
Σ 1 h 1b N'ENE
12 = Φ
where h denotes the learned representation for ST point z after the k-th iteration. For message- passing, the iterative models usually assign weight - to messages from 2' to We denote the distance the path from ST point & to z' as dz-+z'. Let 2, Z to be the set of all observed ST points and 2,, Z To ensure that the model has ability recover all ST points, the number of iterations must satisfies K 2 max min d2-22' Therefore, multiple iterations are inevitable in s'E2m sE2.
highly sparse farge-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, assume its spectral norm satisfies Walla S Bg, for any ST point 2 E 2, we assume its feature vector satisfies || ll2 S. By. For the loss function, assume is an Cj-lipschitz continuous and bounded by [0, 1]. For the activation function, we assume & is Ca-lipschitz continuous with (0) = O. For the mask distribution M, we assume that all ST points are randomly masked with probability of p.
Proposition 4.3. Let F be K-iterations imputation model class, we assume its learned propagation weights are bounded by [0, 7). If we draw a sample of size m, for any J E F, the following inequality holds.
P BmD [Rg(h)) S 2
with
log 1/8
where C Ci 7 cC+1, (dmax) )K Ba
Remark 4.4. Here < r) < 1. dmax = max,ez W and T = max,gz (dd-== < K|z E Z Consider PAC-leamability under complete data, number of required samples needs to satisfy 2
log 1/6 2(e-20; (F).. Since (F) represents Rademacher complexity of model class F. it encouraging the model on sparse data related to the one on complete data. Thus, we estimate the impact of the missing data on the model performance. Obviously, the required sample size m is positively correlated with the missing ratio p 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, T is related to the number of k-hop neighbors of each ST point. Therefore, the sparser the spatio-temporal structure (i.e., smaller r), the greater the number of samples required. This theoretical result provides an interpretation for iterative model-induced error accumulation. Note that although assume that all ST points masked at random (MAR), this proof strategy can be generalized to other mask distribution M.
that the learnability
Methodology
This section presents our proposed method, One-step Propagation and Confidence-baseee Refinement (OPCR), as illustrated in Fig. [ In the first stage, we independently learn intrinsic representations for ST points in both spatial and temporal dimensions. We then employ 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.
5.1 Sparse Attention-bases One-step Propagation
Motivated by the aforementioned theoretical findings, we propose one-step propagation method to avoid error accumulation and information loss commonly found in iterative methods. Specifically, as illustrated in Fig. [ we begin by independently learning intrinsie spatial and temporal representations for ST points. We capture correlations among ST points across different dimensions by adopting sparse attention mechanism. This approach enables the limited information to be propagated directly to the global context as efficiently as possible.

---

Imput Spatie-temparal Data
One-tep Propugation
Confidenc--hated Refinement
My eteetion
Sedelaal
tepabiies
Micaage gaiiig
Obternal MTSS
K
Naiid MMaun
Waighted Sparte
trappraal Propagation
Texz
Structural Graph
Stracturat Basheodings
Time expleal tyukll
Figure 1:
The framework of the proposed OPCR.
5.1.1 Sparse Spatial Attention
We first address the significant spatial sparsity present in spatio-tempora 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 the global context through a sparse attention mechanism. We utilize a Læ-layers Graph Neural Network (GNN) [16] to learn the spatial representations of nodes from the graph structure. We initialize Sp using the inherent static attributes of all nodes; then the layer-wise updation can be summarized as follows.
S o (S-- w + D AAS D-'AS W:).
where i and W are the parameter matrix the I-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 5 Sz, as both the key and query. We denote the of available nodes by V/ c For any node u V, v E V, the spatial self-attention formulated as:
Q", K" Vi SSW,, SW X,W.,
(4)
exp( ki))
a Eved expppxxplg. kg))
where Q" K V E NXF represent the query, key, value of spatial self-attention; qf ky and vf, stand for their i-the row; W W W FxF are parameter matrices. For any ST point (v. t). we aggregate spatial messages coming from all observations weighted by learned attentions. The spatial dependencies-basee imputation result can be computed as:
h MLP (Eure aip Dir.))
(5)
5.1.2 Sparse Temporal Attention
Another 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 LSTM, Transformers are not inherently capable of learning sequence information We first introduce vanilla positional encoding [17] to capture this information. If real-world timestamps available, we use learnable embedding layer encode these timestamps [1]].
5

---

Combining positional encoding with timestamp encoding, for any node v E V. the input to the temporal sparse attention module can be formulated follows.
X X PE(X.) + MLP(U),
P PPpss,2 sin (pos/ / A
2 cos (0s0/10000 1:0000 //dmddel
where X 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 serves the key, query, and value in the temporal self-attention mechanism. For node t, similar to the spatial module, we denote the available time steps by T Then the temporal attention score and the temporal aggregation are formulated as:
Q K V = X.Wo X, X. X Wi
(6)
exp((db..) k ko
(a (e Enee. exp( ktt ko,1g)))
h/, MLP (E (0
where Q K V E RTXx represent the query, key, value of spatial self-attention; L kyy and oy stand for their i-the row; W3. W WV E FxF 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 PAC-Leamability analysis for the proposed method.
Proposition 5.1. Let F be sparse antention-based imputation model class. we draw sample $ of size m, for any J E F, the following inequality holds.
TP B~ Dm (Rg( S 1-
with m 2 21e-4pe- 20: where C = Ci C Ba B,.
log 1/6
Remark 5.2. It can be seen that the number of required samples is positively correlated with the sparsity p. Unlike iteration-basee models, sparsity is the sole factor that constrains the performance of the sparse attention-basee model when dealing with incomplete data. Consequently, the proposed one-step strategy is scalable to various peatooat data of different sizes and structures.
5.2 Confidence-based Iterative Refinement
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 straightforward idea. To further propagate reliable information, we propose 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, f), we can define the confidences of its spatial and temporal imputation results as:
EvED exp((ge. kg)) Evet. expl(g) k()) Evey exp((qt)) kg)) Ever exp((qt k()))
Bu,
We extract highly confident parts from separate imputation results in temporal and spatial dimensions. However, simple weighting ignores the global context spatio-temporal data. Therefore, we propose to employ the learned confidences propagation weights through the spatio-temporal dimension. For any ST point (u, t), we first define the set of its neighbors as
Na,t = {(u,t) f)le E N,) U ((,,t)) (

---

where Nu denotes the set of neighboring nodes of node in the fixed graph G. Then the layer-wiss wise message-passing for ST point (u, t) can be formulated
O
g++ u,t
MLP (o,,ell Σ (ULY)NN.. Bor O e.
where O hig t + h During L layers, we finally recover representations for all ST points. Then the decoder 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 httpt::/ http//g.ttttu..... com dleyan/ OPCR,
6.1 Datasets
We consider three sets of spatio-temporal datasets and summarize their statistics in Table I It is evident that these datasets vary in terms of topology size. The T4C22 dataset primarily comprises spatially missing data, exhibiting exceptionally high sparsity of up to 90%.
Table 1: Statistics of the datasets.
TRAFFIC PEMS-BAY
LARGE-SCALE PV-US CER-E
T4C22
METR-LA
LONDON
MADRID MELBOURNE
# NODES
325
207
5166
6435
59110
63397
49510
# EDGES
2369
1515
71446
51428
132414
121902
94871
# STEPS
52128
34272
8688
8688
10560
10464
10176
To simulate incomplete data in realistic scenario, design two policies to inject missing data into original datasets: 1) Point Missing, in which we follow the same setup of [12] [.] randomly dropping P of the available data. Spatial missing, in which dataset, randomly dropping 25% of the available data, then mask out of the devices.
inspired by the T4C22
6.2 Baselines
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 (2I) 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.
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.
Graph Imputation.
Time-series Imputation. impute multivariate time-series, we consider: 1) BRITS 77, bidirectional RNN-based model. 2) SAITS g transformer-based model. 2) CSDI 99. diffusion-bann based model.
Spatio-temporal Data Imputation. We also consider some state-of-the-art methods for spatio-temporal data imputation. 1) IGNNK [TO), an inductive GNN-based model. 3) SPIN-H [12], an efficient version of spatio-temporal attention based method. 3) PriSTI (13). conditional diffusion model. 4) PoGeVon [14] solving a specific issue in which spatio- temporal data contains missing values in both node time series features and graph structures.
6.3 Spatio-temporal Data Imputation Task
For the imputation task, we consider mean absolute error (MAE) as evaluation metrics. All the experiments are run with different random seeds. In each round, inject p of missing data into
7

---

Table 2: Imputation performances (in terms of MAE) on Traffic dataset and Large-scale dataset.
POINT MISSING
SPATIAL MISSING
MODEL
PEMS- BAY
METR-L.A
PV-US
CER-E
PEMS-BAY
METR-LAA
PV-US
CER-E
MEAN
0.00
10.28 - 0.02
1.31=0000
0.56 0.000
5.08 0.13
10.37 +: 0.21
8.43 0.28
0.56
4.01 0.01
MF
5.25 0.00
7.55
0.04
4.53 = 0.01
0.50 0.00
5.71 +: 0.07
7.61 + 0.11
12.47 0.24
0.57 0.01
GRAPE
0.02
6.75 4: 0.03
10.69 +: 0.22
0.34 +: 0.00
4.72 +: 0.02
6.78 - 0.03
11.67
+ 0.03
0.36 +: 0.00
FP
4.92 0.00
9.22 + 0.02
7.60 = 0.01
0.52 0.00
5.05 + 0.05
9.25 + 0.16
7.87
+ 0.13
0.52 + 0.02
PCFI
0.04
12.94 + 0.08
8.79 = 0.02
0.52 0.01
6.75 + 0.59
14.95 + 1.86
12.31
+ 0.30
0.50 +: 0.04
BRITS
2.58 +: 0.00
3.25 0.10
30.48 + 4.75
1.38
0.99
5.64 + 0.16
8.88 + 0.52
25.77 +: 9.00
1.15 + 0.28
SAITS
2.44 0.01
5.21 0.03
6.40 4.56
0.67 + 0.57
6.14 + 0.24
9.51 0.63
2.73 0.08
0.37 0.11
CSDI
0.04
3.48 + 0.09
7.51 = 2.30
0.49
0.02
3.76 + 0.75
4.51 + 0.45
8.97 + 1.93
0.47 + 0.02
IGNNK
2.61 0.01
4.37 0.00
7.86 = 0.02
0.38 + 0.00
4.70 + 0.13
6.85 + 0.27
11.43 + 0.06
0.46 + 0.00
SPIN-H H
1.84
2.99 +: 0.03
1.94 0.06
0.33 0.09
4.93 +: 0.04
7.62 + 0.06
2.63 +: 0.06
0.29 +: 0.00
POGEVON
5.68 0.01
8.86 0.01
5.73
1: 0.14
8.82 - 0.56
PRISTI
2.05 + 0.02
3.85 0.18
11.93 + 2.84
0.63 0.12
3,05 + 0.20
5.01
11.75 : 7.54
0.59 + 0.14
OPCR
1.79 0.01
2.80 2.000021100111111. 0.02
1.73
0.06
0.28
0.00
2.27
0.07
3.20 0.10 2.01 0.11
0..88 + 0.00
the entire dataset using different masking policies. All models are trained on the sparse training set and evaluated the corresponding sparse testing set.
6.3.1 Highly Sparse Data Imputation
The experimental results of all models are summarized in Table where the missing rate is set as 95%. There is clear gap in the imputation performance 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 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-scall scale datasets.
For sate-of-ttheart (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 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-basee models have been proposed, such as CSDI [9] and PriSTI [13) It is still challenging for CSDI to model a sigh-dimensional time series the large-scale 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. PoGe [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-tempone baselines. In addition, Von does not apply to the large-scale dataset because of its high computational complexity.
As 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.
6.3.2 Imputation with Increasing Missing Rate
To evaluate the effect of data sparsity on imputation performance, we simulate sparse data at various rate, ranging from 25% to 95%. Figures 2 3 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 Table 2 spatial missing poses a greater
8

---

Mosing
Stoskng
Misiing Navz
Figure 2: Imputation performance (in terms of MAE) with increasing point missing rate.
Basing Kals
Viuiing Fals
Vising Rals
Mausng Facto
Figure 3: Imputation performance (in terms of MAE) with increasing saptial missing rate.
challenge for all models. On large-scale datasets, temporal baselines struggle to model extremely nigh-dimensional data and do not exhibit the same trends 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 significant improvement when the missing rate is reduced from 95% to 75%. This empirical results are due IGNNK can not sample enough sub-graph data for training in highly-saarse 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 deal with large-scall 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.
6.4 Traffic Prediction Task
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.
Table 3: Traffic Prediction performances.
CONGESTION CLASSIFICATION
TRAVEL TIME PREDICTION
MODEL
LONDON MADRID MELBOURNE LONDON
MADRID MELBOURNE
FP
0.8126
0.8624
0.8635
84.56
68.17
31.48
PCFI
0.8159
0.8514
0.8552
105.61
61.06
31.43
SPIN-H
0.8335
0.8768
0.8795
77.21
59.24
31.36
OPCR
0.8114
0.8444
0.8519
74.44
55.39
31.54
6.5 Ablation Study
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-pann aapeer-arameters. 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. 1) Spatial module (S): Only use spatial module as encoder. 2) Temporal module (T): Only use temporal module as encoder. 3) W/O refingg inmment (W/O R): Ignore the confidence-based refinement.
kildin Layer Size
humbor
Figure 4: The effect of each component.
Figure 5: The effect hyper-parameters
The results of the ablation study are shown in Fig. First, we compare the spatial module and temporal module. Obviously, 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 easy understand because the temporal module utilizes a narrower range of valid information. Second, combining remporal-basee and apatial-basce results yields superior performances compared to a single module. Finally, when comparing the complete model with all variants, it can be seen that confidence-ber baadde propagation also plays vital role.
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, 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 that shallow iterative propagation is enough to refine the complete recovery by the first stage.
Sensitivity w.r.t
consider the sensitivity w.r.t. the number of layers in
7
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 PAC-learnability analysis for iterative imputation methods from the perspective of PAC-learnability. which theoretically demonstrates their limitations. Motivated by thcoretical findings, we propose one- step 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 apatio-temporal We evaluate the imputation and prediction performances of the proposed OPCR on dataset of different scales. The experimental results illustrate approach outperforms the state-of-the-ee imputation methods. There are several interesting future directions. First, 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).
10

---

References
[1] Gowtham Atluri, Anuj Karpatne, and Vipin Kumar. Spatio-temporal data mining: A survey of problems and methods. ACM Computing Surveys (CSUR), 51(4)) 41, 2018.
[2] Moritz Neun, Christian Eichenherger, Henry Martin, Markus Spanring, Rahul Siripurapu, Daniel Springer, Leyan Deng, Chenwang Wu, Defu Lian, Min Zhou, et al. Traffic4cast neurips 2022-predict dynamics along graph edges from sparse node data: Whole city traffic and eta from stationary vehicle detectors. In NeurlPS 2022 Competition Track, pages 251-278. PMLR, 2022.
[3] Emanuele Rossi, Henry Kenlay, Maria I Gorinova, Benjamin Paul Chamberlain, Xiaowen Dong, and Michael M Bronstein. On the unreasonable effectiveness of feature propagation in learning on graphs with missing node features. In Learning on Graphs Conference, pages 11-1. PMLR, 2022.
[4] Daeho Um, Jiwoong Park, Seulki Park, and Jin Young Choi. Confidence-based feature imputa- tion for graphs with partially known features. arXiv preprint arXiv:2305. 222222305566666 16618, 2023.
[5] Xu Chen, Siheng Chen, Jiangchao Yao, Huangjie Zheng, Ya Zhang, and Ivor W Tsang. Learning attribute-missin graphs. IEEE transactions on pattern analysis and machine intelligence, 44(2):740-77 757, 2020.
[6] Wenxuan Tu, Sihang Zhou, Xinwang Liu, Yue Liu, Zhiping Cai, En Zhu, Zhang Changwang, and Jieren Cheng. Initializing then refining: A simple graph attribute imputation network. In Proc. ICAI, pages 3494-3500, 2022.
[7] Wei Cao, Dong Wang, Jian Li, Hao Zhou, Lei Li, and Yitan Li. Brits: Bidirectional recurrent imputation for time series. Advances in neural information processing systems, 31, 2018
[8] Wenjie Du, David Côté, and Yan Liu. Saits: Self-attention-baat imputation for time series. Expert Systems with Applications,
2023.
[9] Yusuke Tashiro, Jiaming Song, Yang Song, and Stefano Ermon. Csdi: Conditional score-based diffusion models for probabilistic time series imputation. Advances in Neural Information Processing Systems, 2222404-24816 2021.
[10] Yuankai Wu, Dingyi Zhuang, Aurelie Labbe, and Lijun Sun. Inductive graph neural networks for spatiotemporal kriging. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 4478 4485, 2021.
[11] Cini Andrea, Marisca Ivan, Cesare Alippi, et al. Filling the g_ap_s: Multivariate time series imputation by graph neural networks. In ICLR 2022, pages 1-20. 2021.
[12] Ivan Marisca, Andrea Cini, and Cesare Alippi. Learning to reconstruct missing data from spatiotemporal graphs with sparse observations. Advances in Neural Information Processing Systems, 35:32069-32088 2022.
[13] Mingzhe Liu, Han Huang, Hao Feng, Leilei Sun, Bowen Du, and Yanjie Fu. Pristi: A conditional diffusion framework for spatiotemporal imputation. In 2023 IEFE 39th International Conference on Data Engineering (ICDE), pages 1927-1939. IEEE, 2023.
[14] Dingsu Wang, Yuchen Yan, Ruizhong Qiu, Yada Zhu, Kaiyu Guan, Andrew Margenot, and Hanghang Tong. Networked time series imputation via position-awar graph enhanced variational autoencoders. arXiv preprint arXiv:2305.18612. 2023.
[15] Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of machine learning. MIT press, 2018.
[16] Christopher Morris, Martin Ritzert, Matthias Fey, William Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe Weisfeiler and leman go neural: Higher-order graph neural networks. Proceedings of the AAAI conference on artificial intelligence, volume 33, pages 4602-4609, 2019.

---

[17] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention all you need. Advances in neural information processing systems, 30, 2017.
[18]
Qingsong Wen, Tian Zhou, Chaoli Zhang. Weiqi Chen, Ziqing Ma. Junchi Yan, and Liang Sun. Transformers in time series: survey. arXiv preprint arXtv:2202.07125, 2022.
[19] Haoyi Zhou, Shanghang Zhang. Jieqi Peng, Shuai Zhang, Jianxin Li, Hui Xiong, and Wancai Zhang. Informer: Beyond efficient transformer for long sequence time-series forecasting. In Proceedings of the AAAI conference on artificial intelligence, volume 35, pages 11106-11115, 2021.
[20] Andrzej Cichocki and Anh-Huy Phan. Fast local algorithms for large scale nonnegative matrix and tensor factorizations. IEICE transactions on fundanentals of electronics, communications and computer sciences, 92(3):708- 721, 2009.
[21] Jiaxuan You, Xiaobai Ma, Yi Ding, Mykel Kochenderfer, and Jure Leskovee. Handling missing data with graph representation learning. Advances in Neural Information Processing Systems, 33:19075--9087, 2020.
[22] Yaguang Li, Rose Yu, Cyrus Shahabi, and Yan Liu. Diffusion convolutional recurrent neural network: Data-driven traffic forecasting. arXiv preprint arXiv: 2017.
[23] Andrea Cini, Ivan Marisca, Filippo Maria Bianchi, and Cesare Alippi. Scalable spatiotemporal graph neural networks. In Proceedings of the AAAI conference on artificial intelligence, volume 37, pages 7218-7226, 2023.
[24] Moritz Neun, Christian Eichenberger, Henry Martin, Markus Spanring, Rahul Siripurapu. Daniel Springer, Leyan Deng, Chenwang Wu, Defu Lian, Min Zhou, et al. Traffic4cast at neurips 2022-predict dynamics along graph edges from sparse node data: Whole city traffic and eta from stationary vehicle detectors. arXiv preprint arXiv:2303.07758 2023.
[25] Zonghan Wu, Shirui Pan, Guodong Long, Jing Jiang, and Chenggi Zhang. Graph wavenet for deep spatial-temporal graph modeling. arXiv preprint arXiv:1906.00110 00120,, 2019.
[26] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, al. Pytorch: An imperative style, high-performance deep learning library. Advances in neural information processing systems, 32, 2019.
[27] Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred K Warmuth. Learnability and the vapmik-chervonenkis dimension. Journal of the ACM (JACM), 36(4):929-9)))))) 1989.
[28] Peter I. Bartlett and Shahar Mendelson. Rademacher and gaussian complexities: Risk bounds and structural results. Journal of Machine Learning Research, 3(Nov):463-482 2002.
[29] Ding-Xuan Zhou. The covering number in learning theory. Journal of Complexity, 18(3):399 2002.
12

---

A Experiment
A.1 Datasets
We consider the following three sets of spatio-temporal datasets.
Traffic dataset 22 record traffic dynamics every 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[an and the CER Smart Metering Project respectively. Both datasets are aggregated in 30 minutes.
T4C22 dataset [24] record traffic dynamies every 15 minutes from vehicle detectors in three cities, which is provided by Traffic4cast 2022 competition
For the traffic dataset and PV-US dataset, we derive the adjacency from pairwise geographic distances 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.
22
25
A.2
Experimental settings
Considering memory consumption, for SPIN, we choose the efficient version SPIN-H as baseline. On the traffic dataset, 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 PyTTrcch (26]. We use, whenever possible, the open-source code and configuration provided by the authors.
For spatio-temporal data imputation task, select windows of length 24. On the traffic datasets, strictly follow the settings SPIN We fix the maximum number of epochs to 300 and we use early stopping the validation with patience of 40 epochs. On the large-scall 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 and-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.
A.3 Time Complexity and Run-time Analysis
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²) and its efficient version SPIN-H scales with O (L(N- KT), where K T.
For our proposed OPCR, the first stage, we propagate observations to missing data, thus we can reduce the time complexity from O 2 + N72) to O NN2) ) x p(1 p)) via sparse attention matrices. Considering the sparsity of the graph structure, it reasonable to assume that E and 2 p(1 p) are similar in magnitude. Moreover, since we learn spatial attention matrix from static node features and share it across all spatio-temporal series within 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 O (ET + NT²). As we mentioned
'https//www.mrell.ppm
https: thub. www.aaaoooaeaeappaaaaaeaaeeeeeee Group/spin
13

---

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 231, we present the timings and memory consumption in the T Compared the spatio-temporal imputation baselines SPIN-H, our proposed model shows significant superiority in computational efficiency and memory usage.
Table 4: Timings and memory consumption.
PV-US
CER-E
MODEL
MEMORY
BATCH/S
BATCH SIZE
MEMORY
BATCH/S
BATCH SIZE
BRITS
11.20GB
2.84
16.53GB
1.97
32
SAITS
4.52GB
8.95
128
5.28GB
1.76
128
SPIN-H
14.22GB
2.88
18.00GB
3,46
2
PRISTI
14.22GB
1.40
17.52GB
1.01
OPCR
16.98GB
3.09
18.22GB
2.87
B Proof of Proposition 4.3
Proposition B.1. Assume that all ST points randomly masked with probability of p. Let F be K-iterations imputation model class. If we draw sample $ of size m, for any F, the following inequality holds.
TP BwDm (Ro(hs) S -
log 1/8 with m 2 Ze- CcC 10
Given an sparse training set 3 ~ DmH for any f E F, we have
Ry (f) - itg (f) - (R RD (f)+ RD
(f) [D)
Res [s) (t) ftg (n)
(8)
Corollary B.2. For any f E F and any (X,Y) E & V, mask all ST points random with probability of p. 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 Ý = ((X) and Y = -(.).. The difference between the model's prediction error complete data and sparse data have the following upper bound.
EM^M [[L L(Ý, Y) sC- Σ
A--1 + +n. 1..... 0--11
k-1
min
where C = Cg.ga K. ck+z (dmax) Bx Ba-
Proof. Under assumptions, f is an encoder-decoder architecture, for any complete samples (X, Y)
and its sparse version (X, Y), we have
- -
=
1
(T.. ) - (g.. vr))
N
BEV
< Ct
1. Dull2
(9)
N
AEA
= C. N
Σ
(X))) - -Fa(fe(X)))
AE
14

---

Here is due to the loss function / is C1-lipschitz continuous. As the assumption about decoder fa. we have
I( Y) 1(8,8)
S SC
Σ
N
DEV
T E 1o(X).,. - - So (X)))x,Wa))
C Σ
1ET
IET
1C C.
1
Σ NEV
Σ
fc((X)) - -f((X) Wd
(10)
NT
IET
1
<C.C2 NT
fe(X)u, - f(())
-lWall2
NEVIET
SC. C. Ba NT
ΣΣ DEVIET IET
1o(8) -
(11)
Here Eq 10 is due to the é is Ca-lipschitz continous and Eq 11 is due to |Wale < Ba- Since the encoder fa K -iiteration imputation model, we denote ST point representations after iterations by H and H We denote the of recovered ST points after h iterations by NRk For the number of iterations K, we assume that K exactly satisfies z Z and for any z C 2. Thus, we have
ΣΣ NT DEVIET
fe(() fx(X)
1
h
h
NT
h
(12)
NT
where 2 = (V Then we have the following recursion:
Σ
h
Σ
Σ
k-1 - E
Σ
1-1
d
az
zEZk
F'EN
''ENN
$ SC Σ
مx' h k-1
a
k-1
(13)
zE
1'EN!
E'NN
2
S CC.
Σ
Σ
a 3s
h
lk
Σ
(a
h k-1
(14)
=
SC..
L
h
k-1
Σ
1
k-
11
Σ
1a
|1b55111,
kk
N'
W'EA
Here Eq 13 is due to that di is -i-liscchiz continuous. Eq 14 is due to = 0 ''' ENSWA.
For V2 E Z and Vz' E Ns. we assume that 0 < drr n. For V2 E Z, 4. E Aa and Ak E K], we assume that ab. S y and < |azr=z - 5 <. These assumptions are easy to implement because the model tends to use positive weights when aggregating neighboring ST points.
15

---

For convenience, let 0 <ソ= 2 1, we have
Σ
=62g
S C
Σ
a +
:
R-
h
8-1
+
Σ
|az'
1
11 +
Σ
lay-
||
112
2
x'ENN
N'ENWN
E'E
CCs
Σ I
q.
h
h
Σ
7.
|
ll2
Σ
122
#c
s'ENs
S'ENT
(15)
<nCadmax
h
h
+70
Σ
Σ
|
Σ
11
1112
2E2
=E2
z'ENs
(16)
For the second term and the third term in Eq. T6 we have
EM
Σ
Σ
I
11
Σ z'EN,
n. | 1
SEZ
< EE
Σ
Σ
1
Σ
17 n. 1 1 1112
2
1E2
N'EN.W.
N'EN:
S dmax
p"min min
h
112 +1
p
k-1
Σ
n1 |
ZEZ
ZEZ
= dmaxx
0
1 p'min
+ 17 (1
max
(17)
#E2
Here k
max maxzez le and - minzez The where T = K='Idee0s S k,, E -
Actually, - represents the number of k-hop neighbors of ST point 2.
For Exez | we have
Σ ZEZ
h 112
Σ
Σ E'EN
k-1 a
12 h2
ZEZ
2
Σ
Σ
:EZ
MEN
CC Σ
Σ
k-1
0g'
2EZ
l''eN
SnC Σ Σ
|
-
111
x'E
S S7Codmaxx
Ih
k-1
*E2
< (rCodmnxx) kk.
122112
2EZ < (7C NTBx.
(18)
16

---

Therefore, expanding the recursion in Eq. 16
we have
EM
Σ
h
h
< EM
7 Codlmaxx
Σ
h
h
+ +7
Σ
Σ
|
112
Σ
17
11
11
=E2."
ZE2g
F'ENN Wo
z'EN.
< SoCdmaxx
EM
k-1
h
k-1
+ p min
k-1
+ 17 (1 - p=mux)
Σ
1
z'
L=EZ
ZE2
I <nCodmax EM
Σ
k=
+
p
x-1 pmina min
+ 17. (1 - p'mmz))
NT
L=
(19)
Then we can derive
EM
Σ
h
K
h
EM
h
LEEZ
=EE.
<naddmax EM
Σ
h
h 1
p mi
+n (1 (1-pinz)))
(T " .N
$ <yCCdmaax) NTBx
Σ
p min
k-1
+ 17 (1
(20)
Substituting Eq 20 into Eq 12 we have
EM LÍÝ - s Ci Co
Ba
EM
Σ LEEZ
h
NT
$ C. Co Ba NT (7Codmax)
NTBX
p min
+ 17 (1
K
S C1 2k ckktl (dmax) j.
Bx
0
min
+ 17 (1 - p k-
mmaxs
k=1
Let = -C .K cK+1, (dmax) K. Bx Ba, we finally derive the follows inequality.
EM -( Y)
SC p pmmin
+ (1 p² tind
For the second term in Eq R&p (f) Rs (f) represents the generalization performance of f F complete dataset. Model complexity measurements, such 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 required for PAC-Icarnabilis under complete data. Rademacher complexity is frequently applied to investigate the generalization performances of GNN-based models. The Rademacher complexity-bane based generalization bound as given [5] is:
Lemma B.3. Let a function class mapping from X to (0, 1). Then, for any > O, with probability least 1 - 8 over the draw of i..dd. sample S of size m. for any h E H. the following
17

---

inequality holds.
log 1/0
RD (h) S Rs (h) + 2mm (H)
2m
As our assumptions, the loss function L: R x y + [0, 1] is Ci-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, be a function class for spatio-temporal data imputation, function class mapping from X to [0, 11. Then, for any ā > O, with probability at least 1 - 8 over the draw of an i.idd sample of size m, for any H. the following inequality holds.
P P (5) Rt (1) 2)) Se 2m (.))
Proof. Using Lemma B.3 and contraction lemma we have
log 1,0
Ro (f) S Rs (J) + 28m (1 F)
2m
log 1'60
s Rs (f) + 2m (F)
2m
Therefore, we can rewrite this inequality then we have for any f E F
P ((Ro (1) Rs (1) 2 20) S 2m 20,
Using Corollary
B.2 and B.4
we have
p
(5) RD(
R
Rg (5) 2()
(1
IBD (f) its (f) 2 Rb (f) - RD (f) + (f) Rg (1)
K
< P
RD (f) - Rs (f)
2 c- - 2C
Σ
p
k- min
+ n (1 - p --1
maxe |]
k=1
17 np thm p= -0 (F) 1)
$ cxp
-2m
2C
Then we derive the number of required samples m:
K
1) 58
exp
2m
E 2C
npp
man
+ p k-1
pminn
- 2C (F)
1=1
K
+ exp
2m
E 2C
np tint
+ p R-1
20 (F)
IV
1=1
+ 2m
2C
1) np time time
+ p pitmml
2C(Rm(F) (F)
2 loog( (
1
I
-log V
26 4C Et=
1) pp
k-1
+ (FF
1-1
log
2c AICK - -4(1 - -nC
Ek Piina (CFRm(F)
1
1
3m> 2
logg V
20 4nCK 4(1 n)C
pr K-1
4CiR,n,
For convenience, we let
max
K-1
18

---

C Proof of Proposition 5.1
Proof. Similar to proof of Proposition 5.1 first derive the following upper bound for the difference between model performances under complete and sparse data. For any M E .,, we have
Σ h2
h2 ||2
NT
-
NT
0/'
0z'-22
0z
Uz!
NT
E
EE
O2
Ex
02
=EZ
J'EZ
B
0,'++3
02'-43
Σ
NT
ExnEZ az"+2
Ex"EZ 022
NT
Σ
22 0z"
ZEZ
Z'EZ,
2E2
22
where maX=Ez 1|2212 S Bu. Then we have
1
EM
h2
h2
NT
ZE2
02'-1"" (Er"EziZo 02"-12
B
Σ sE2
EM
+ Σ
0''+3
NT
#'EZo Σ EE"EZ d='-22) (ES (241+22)
Σ
ExnEz 0z'1
s'E2/2,
2B,
EvEZi2, 0z'+z
Σ
EM
NT
Σvez 02'
xE2
< 2B, P
Similar to proof of Proposition
4.3
R (f) - R2 (1) 2 e) S exp (-2m - 4Cp Co Ba B, . p- Re (F))
+ +P( RB (f) - R3 (f) 2() S exp (-2m (e - 4C p - 20 (F)))
exp (-2m (c
4C p- RC, (F)) s
2m (E 4C p Rm (F) > log
1/8
2 E 4C p 20 Rm (F)]
where C = Ct C. Bd B..
19

---

NeurIPS Paper Checklist
1. Claims
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 perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
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 not discussed in the paper.
The authors are encouraged to create 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 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 few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might 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 address problems of privacy and faimess.
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 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
20

---

Justification: Appendix
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: Reproducible code and Experimental settings.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reprodueibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
21

---

Answer: [Yes]
Justification: Reproducible code and Experimental settings.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.co cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https guwdes/ddeeeeee Cooeeeoodeesssseeeeee 7/nips.com / cassiicnncccyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Question:
Answer: [Yes]
Justification: Reproducible code and Experimental settings. Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: We run all the experiments with 5 different random seeds and present the results with mean standard deviation (std).
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
22

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: Experimental settings.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification:
We conform the NeurlPS Code of Ethics.
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 cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. 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 no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact 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.
23

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is 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 being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there 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 monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have 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 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 best faith effort.
12. Lieenses 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 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 URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.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, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of 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 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS 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.
25


Reviews:
[{"review_id": "cSwm8yz3Bl", "reviewer": "Reviewer_Ctvj", "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.", "questions": "1. What does \"poly\" mean in line 98?\n2. Line 101-102 & 104-105, what does $\\phi$ mean?\n3. Line 106-107, why should the model need to have the ability to recover all ST points?\n4. In Assumption 3.2, what do $B_d$ and $B_x$ mean?", "limitations": "N/A", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. Using Probably Approximately Correct (PAC) theory to analyze spatial-temporal imputation is an interesting direction.\n2. Spatial imputation is an interesting sub-topic of the spatial-temporal imputation.\n3. Experimental results on several benchmark datasets show that the proposed OPCR could outperform baselines.", "weaknesses": "1. In general, the proposed method is a little bit incremental. A simpler version of sparse spatial-temporal attention has been proposed by SPIN. \n2. The presentation needs further improvements, especially the theoretical part. Many details and claims need clarification, please see questions.\n3. The comparison baselines GRIN (2021) and SPIN (2022) are a little bit outdated. More recent baselines should be considered, such as [1,2,3].\n\n[1] PriSTI: A Conditional Diffusion Framework for Spatiotemporal Imputation, ICDE'2023\n[2] Networked Time Series Imputation via Position-aware Graph Enhanced Variational Autoencoders, KDD'2023\n[3] Provably Convergent Schrödinger Bridge with Applications to Probabilistic Time Series Imputation, ICML'2023", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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).\n\n\n> **[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.\n\nThanks for raising this fundamental issue. We would like to clarify the differences from SPIN and emphasize the contributions of the proposed method.\n\n**Differences.** The proposed method differs from SPIN in the following aspects:\n\n- 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.\n- 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.\n- 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.\n\n**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.\n\n- **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.\n- **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.\n\nWe reasonably believe that these contributions to the theoretical analysis of existing work and the algorithmic breakthroughs inspired by the theory are significant.\n\n> **[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].\n\nThanks 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.\n\n**References**\n\n[1] PriSTI: A Conditional Diffusion Framework for Spatiotemporal Imputation, ICDE'2023. \n\n[2] Networked Time Series Imputation via Position-aware Graph Enhanced Variational Autoencoders, KDD'2023. \n\n[3] Csdi: Conditional score-based diffusion models for probabilistic time series imputation. NeurIPS'2021.\n\n[4] Handling Missing Data with Graph Representation Learning. NeurIPS 2020.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "b4MeCYGFsR", "reviewer": "Reviewer_fc8s", "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:\n\n1. The authors provide a theoretical analysis of a general spatio-temporal iterative imputation model from the perspective of PAC-learnability.\n\n2. 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.\n\n3. Finally, experiments are conducted comparing several existing imputation methods with the proposed method on real-world datasets, demonstrating the effectiveness of the proposed method.", "questions": "1. In Figures 4 and 5, why is the MAE result of the SAITS ∞ in the PV-US and CER-E datasets?\n\n2. What's the advantage of the proposed model compared with diffusion model-based methods?", "limitations": "Yes.", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The theoretical analysis of the general spatio-temporal iterative imputation model from the PAC-learnability perspective provided in this paper is relatively innovative, explaining the error accumulation caused by multiple iterations. The authors also present a PAC-learnability analysis for sparse attention-based imputation models and provide detailed proofs for both theoretical analyses in the appendix.\n\n2. This paper proposes a novel one-step propagation and confidence-based refinement framework. This framework addresses the problems of error accusation and can be applied to spatial and temporal missing scenes. The high-level idea may provide novel insight for further imputation algorithm design.\n\n3. This paper explores spatially sparse data in the experiments, which helps to make full use of available data and lowers the barriers for implementing spatio-temporal models in real scenarios.", "weaknesses": "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.\n\n2. 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.\n\nReferences:\n\n[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.\n\n[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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Many thanks for your positive comments and constructive feedback. Please see the below responses to your comments.\n> **[Weakness 1.1]** In Section 4.1.2, the construction details of the input to the temporal sparse attention module are not described.\n\nThanks 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:\n$$\n\\bar{X_v} = X_v + PE(X_v) + MLP(U),\n$$\nwhere $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.\n$$\nPE_{(pos, 2i)} = sin(pos/10000^{2i/d_{model}}),\n$$\n\n$$\nPE_{(pos, 2i+1)} = cos(pos/10000^{2i/d_{model}}).\n$$\n\n\n> **[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.\n\nThanks for your careful review. We have corrected these typos and thoroughly checked the symbols in the revised version.\nSpecifically, 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 \n$$\nO_{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),\n$$\nwhere $O^0 = h_{v,t}^s + {h}_{v,t}^t$.\n\nFor the sparse attention-based confidence, we have revised inconsistent symbols and rewritten Eq.7 as follows. \n$$\n\\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>)} \n$$\n\n\n> **[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.  \n> **[Question 2]** What's the advantage of the proposed model compared with diffusion model-based methods?\n> \n\nThanks 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.\n\nNotably, we have conducted comparative experiments with CSDI [1] and PriSTI [2], please refer to the global rebuttal.\n\n> **[Question 1]** In Figures 4 and 5, why is the MAE result of the SAITS ∞ in the PV-US and CER-E datasets?\n\nThanks 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. \n\n**References**\n\n[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.\n\n[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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "0ahYSvSVEf", "reviewer": "Reviewer_g4JR", "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.", "questions": "1.\tHave the author(s) considered using other mathematical tools to analyze generalization risk, such as Rademacher complexity?\n2.\tCould the author(s) further discuss the potential strength of the proposed method in practical scenarios?", "limitations": "yes", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1.\tThe paper is well-organized, identifying limitations with existing methods through theoretical analysis and thereby motivating the proposal of an improved method for modeling spatio-temporal information. \n\n2.\tThe theoretical analysis of existing iterative message-passing methods is interesting and may inspire future research in the sparse data learning.\n\n3.\tA good one-step propagation strategy that can avoid error accumulation and provide a more efficient learning process.", "weaknesses": "1.\tThe paper uses PAC-learnability to analyze generalization risk. Have the author(s) considered using other mathematical tools, such as Rademacher complexity?\n2.\tCould the author(s) further discuss the potential strength of the proposed method in practical scenarios?\n3.\tThere are some typo and grammatical errors. For instance, \"seperate\" on Line 13, \"problem\" on Line 29.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Many thanks for your positive comments and constructive feedback. Please see the below responses to your comments.\n> **[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?\n> \n\nThanks 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.\n\n> **[Weakness 2 & Question 2]** Could the author(s) further discuss the potential strength of the proposed method in practical scenarios?\n\n\nThank you for your question. Our proposed method has three potential strengths:\n\n- **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.\n- **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.\n- **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.\n\n> **[Weakness 3]** There are some typo and grammatical errors. For instance, \"seperate\" on Line 13, \"problem\" on Line 29.\n> \n\nThanks for your careful review. We have modified and checked these typos and grammatical errors in the revised version.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "oHREknRGat", "reviewer": "Reviewer_aMi7", "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.", "questions": "Please give more explanations on my comments in W1-W4.", "limitations": "The authors did not discuss the limitations or negative impact of their paper.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 1, "contribution": 2, "strengths": "S1. Tackling spatio-temporal data with high sparsity is an important topic. It is critical to design effective method to tackle such a case, which has many downstream applications.\n\nS2. The paper offers a theoretical analysis on the advantages of the proposed method against existing models. The design proposed method is based on the derived theory.   \n\nS3. Experiments show that the proposed model achieves the best performance among several baselines in different settings and various spatio-temporal tasks.", "weaknesses": "W1. The presentation needs to be significantly improved. Many parts of the contents are vague and difficult to follow.\n\n-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.\n\n-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?\n\n-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?\n\nI don’t really follow the paper, as so many of the notations are not properly defined and explained.\n\nW2. 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”.\n\nW3. 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.\n\nW4. 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.\n\nW5. Some of the related studies are highly related, and thus should be included. For example, [1, 2].\n\n[1] Handling Missing Data with Graph Representation Learning. NeurIPS 2020\n\n[2] Networked Time Series Imputation via Position-aware Graph Enhanced Variational Autoencoders. KDD 2023", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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).\n> **[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.\n\nThanks 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.\n\n> **[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.\n\nWe 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:\n$$\n\\bar{X} = X + PE(X) + MLP(U),\n$$\nwhere $U$ is the available real-world time information, such as the hour of the day; $PE$ is the vanilla positional encoding as follows.\n$$\nPE_{(pos, 2i)} = sin(pos/10000^{2i/d_{model}}) ,\n$$\n\n$$\nPE_{(pos, 2i+1)} = cos(pos/10000^{2i/d_{model}}).\n$$\n\n\n> **[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?  \n> **[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”.  \n> **[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.\n\nThanks 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.\n\n- **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.\n- **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.\n- **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.\n\nBased on this, we address each of your questions as follows.\n\n***Q1: Are $S_l$ and $h^s_{v,t}$ the same thing?***\n\n$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)$.\n\n***Q2: Why the proposed belongs to “one-step propagation”.*** \n\nIn 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”.\n\n***Q3: Only the representations of nodes that have observed data are updated?***\n\nOnly 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.\n\n> **[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.\n\nThanks 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.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We sincerely thank all reviewers for taking the time to review our work. We appreciate that you find the problem is interesting and important (**Reviewer #Ctvj, #aMi7**), theory-inspired method is proposed (**Reviewer #g4JR, #aMi7**), the method is novel and efficient (**Reviewer #fc8s, #g4JR**), theoretical analysis is innovative (**Reviewer #Ctvj, #fc8s, #g4JR, #aMi7**), the paper is well organized (**Reviewer #g4JR**), with outstanding experimental results (**Reviewer #Ctvj, #fc8s, #aMi7**). Due to the limited space, the global response will answer the common questions, and the individual response will answer special questions.

**Q1: Concerns about more baselines.**
> **Reviewer #Ctvj**
> [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].
> **Reviewer #fc8s**
> [Weakness 2] Some diffusion model-based methods, such as CSDI [4] and PriSTI [1]
> **Reviewer #aMi7**
> [Weakness 5] Some of the related studies are highly related, and thus should be included. For example, [2, 5].

Following 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]. We present the imputation performances (in terms of MAE) of all methods in the METR-LA dataset with a missing ratio of 95% in the table below. It can be seen that the proposed OPCR is still significantly competitive on the two imputation tasks.

**Table 1. Imputation performance (in terms of MAE) of more baselines on METR-LA dataset.**
| Types | Methods | Spatial Missing | Point Missing |
| --- | --- | --- | --- |
| Tabular Data Imputation | GRAPE [4] | 6.78 | 6.73 |
| Time-series Imputation | CSDI [3] | 4.30 | 3.86 |
| Spatio-temporal Data Imputation | PoGeVon [2] |   10.14 | 9.47 |
| Spatio-temporal Data Imputation | PriSTI [1] | 5.01 | 3.90 |
| Spatio-temporal Data Imputation | **OPCR** | **4.22** | **3.15** |

**Q2: Concerns about confused notations.**
> **Reviewer #Ctvj**
> [Weakness 2] The presentation needs further improvements, especially the theoretical part. Many details and claims need clarification, please see questions.
> *[Question 1] What does "poly" mean in line 98?*
> *[Question 2] Line 101-102 & 104-105, what does 𝜙 mean?*
> *[Question 3] Line 106-107, why should the model need to have the ability to recover all ST points?*
> *[Question 4] In Assumption 3.2, what do 𝐵𝑑 and 𝐵𝑥 mean?*
> **Reviewer #aMi7**
> [Weakness 1.2] The notations for the theory provided in Section 3 do not offer detailed explanations.

We apologize for the confusing claims and notations. The detailed explanations of these claims and notations are as follows:
- **"poly":** The term “poly” in Definition 3.1 represents a polynomial function.
- **“$\phi$”:** The “$\phi$” denotes the activation function, which is assumed to be $C_{\phi}$-lipschitz continuous and bounded by $[0,1]$.
- **"Recover all ST points":** We apologize for the writing typos. The model needs to have the ability to recover all missing data, which is the goal of imputation tasks. We have clarified this point in the revised version.
- **"$B_d$, $B_x$":** For matrix $X$, we use $\lVert X\rVert_2$ to denote its spectral norm. For vector $x$, we use $\lVert x \rVert_2$ to denote its Euclidean norm. For any ST point $(v, t)$ in spatio-temporal dataset, we assume its collected feature vector $x_{v,t}$ satisfies $\lVert {x}_{v,t} \rVert_2 \leq B_x$. For the weight matrix $W_d$ in the decoder (line101-line102), we assume $\lVert W_d \rVert_2 \leq B_d$.
- **"$\mathcal{T}$":** Given a spatio-temporal series, we denote the set of nodes by $\mathcal{V}$ and the set of time steps by $\mathcal{T}$.
- **"$\mathcal{Z}_m$", "$\mathcal{Z}_o$":** We denote the set of all ST points as $\mathcal{Z}$. $\mathcal{Z}_o$ represents the set of all observed ST points and $\mathcal{Z}_m=\mathcal{Z} \backslash \mathcal{Z}_o$ represents the set of all missing ST points.
Thanks for your careful review. We have addressed each of your questions and have made corresponding modifications to the paper to improve clarity. 


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

Meta-review: 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.
Decision: Accept (poster)