Research map / Video / Video segmentation and tracking
Learning from Highly Sparse Spatio-temporal Data
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes OPCR, a one-step sparse-attention propagation plus confidence-based spatio-temporal refinement for imputing highly sparse spatio-temporal data, with a PAC-learnability analysis of iterative imputation models.
Problem
Imputing and learning from highly sparse spatio-temporal data (point and node-level missingness), where iterative message-passing suffers information loss, error accumulation and high cost.
Approach
Replace iterative spatio-temporal message passing with one-step sparse attention that propagates observations directly to all missing points, then refine with attention-derived confidence weights propagated over spatio-temporal neighbors; supported by a PAC-learnability bound showing iterative models depend on graph sparsity as well as data sparsity.
Key results
- On spatially missing PEMS-BAY, OPCR exceeds the best baseline by 26% and 37% (MAE) per the paper's reported settings.
- At 95% point missing, OPCR achieves MAE 1.79 on PEMS-BAY and 2.80 on METR-LA, outperforming SPIN-H (1.84, 2.99).
- On the T4C22 prediction tasks, OPCR gives the best congestion classification on London and Madrid and... travel time on London (74.44) and Madrid (55.39).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use OPCR instead of the strongest reported baseline | spatio-temporal imputation · PEMS-BAY point missing (95%) | MAE: 1.84 ± 0.02 -> 1.79 ± 0.01 | Helped |
| use OPCR instead of the strongest reported baseline | spatio-temporal imputation · METR-LA point missing (95%) | MAE: 2.99 ± 0.03 -> 2.80 ± 0.02 | Helped |
| use OPCR instead of the strongest reported baseline | spatio-temporal imputation · PV-US point missing (95%) | MAE: 1.94 ± 0.06 -> 1.73 ± 0.06 | Helped |
| use OPCR instead of the strongest reported baseline | spatio-temporal imputation · CER-E point missing (95%) | MAE: 0.33 ± 0.09 -> 0.28 ± 0.00 | Helped |
| use OPCR instead of the strongest reported baseline | spatio-temporal imputation · PEMS-BAY spatial missing (95%) | MAE: 3.05 ± 0.20 -> 2.27 ± 0.07 | Helped |
| use OPCR instead of the strongest reported baseline | spatio-temporal imputation · METR-LA spatial missing (95%) | MAE: 4.51 ± 0.45 -> 3.20 ± 0.10 | Helped |
| use OPCR instead of the strongest reported baseline | spatio-temporal imputation · PV-US spatial missing (95%) | MAE: 2.73 ± 0.08 -> 2.01 ± 0.11 | Helped |
| use OPCR instead of the strongest reported baseline | spatio-temporal imputation · CER-E spatial missing (95%) | MAE: 0.29 ± 0.00 -> 0.28 ± 0.00 | Helped |
| use OPCR instead of the strongest reported baseline | traffic congestion classification · London | weighted cross-entropy loss: 0.8126 -> 0.8114 | Helped |
| use OPCR instead of the strongest reported baseline | traffic congestion classification · Madrid | weighted cross-entropy loss: 0.8514 -> 0.8444 | Helped |
| use OPCR instead of the strongest reported baseline | traffic congestion classification · Melbourne | weighted cross-entropy loss: 0.8552 -> 0.8519 | Helped |
| use OPCR instead of the strongest reported baseline | travel time prediction · London | MAE: 77.21 -> 74.44 | Helped |
Surprising findings
- Iterative SPIN-H's imputation error on CER-E is not monotonically correlated with missing rate, which the authors attribute to graph sparsity effects.
- Temporal-only and spatial-only variants show different strengths; the temporal module is weaker on large-scale data.
Limitations
- Theoretical analysis assumes missingness is random (MAR); non-random missing not covered.
- Paper's checklist answers 'No' for limitations; no dedicated limitations section.
- Only evaluated on random and spatially-sparse masking policies and on imputation/prediction tasks with supervision.
Experimental setup
Datasets: PEMS-BAY METR-LA PV-US CER-E T4C22 (London, Madrid, Melbourne)
Benchmarks: PEMS-BAY METR-LA PV-US CER-E T4C22
Metrics: MAE classification cross-entropy (weighted) travel time MAE
Baselines: Mean MF GRAPE FP PCFI BRITS SAITS CSDI IGNNK SPIN-H PriSTI PoGeVon
Builds on: SPIN GRIN PriSTI Feature Propagation PCFI
Closest papers by meaning
- Graph Structure Learning for Spatial-Temporal Imputation: Adapting to Node and Feature Scales (AAAI 2025 · similarity 0.91)
- RDPI: A Refine Diffusion Probability Generation Method for Spatiotemporal Data Imputation (AAAI 2025 · similarity 0.89)
- STD-PLM: Understanding Both Spatial and Temporal Properties of Spatial-Temporal Data with PLM (AAAI 2025 · similarity 0.87)
- Causal Deciphering and Inpainting in Spatio-Temporal Dynamics via Diffusion Model (NeurIPS 2024 · similarity 0.87)
- Causal Spatio-Temporal Prediction: An Effective and Efficient Multi-Modal Approach (NeurIPS 2025 · similarity 0.86)
- Glocal Information Bottleneck for Time Series Imputation (NeurIPS 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.