Technical Summary: Learning Higher-Order Structure from Incomplete Spatiotemporal Data

1. Problem Formulation

The paper addresses the challenge of spatiotemporal imputation in sensor networks, specifically focusing on scenarios where missing data is not uniformly random but follows structured patterns. Standard benchmarks often assume uniform-random cell dropout, yet real-world deployments exhibit coherent failures such as:

• Cell-MAR: Scattered missing cells.
• Block-MAR: Contiguous time-block outages (e.g., 30-minute calibration windows).
• Sensor-Kriging: Whole-sensor blackouts (e.g., cabinet failures or new installations with no history).

Existing methods, including low-rank tensor completion and pairwise graph-Laplacian smoothing, often fail in these regimes. They assume missing values can be reconstructed from nearby observed cells. However, when gaps cluster in time, space, or along entire sensors, pairwise priors cannot capture higher-order group-level coherence (e.g., flow conservation at a freeway merge involving three or more lanes, or shared calibration drift across a cluster of sensors). The classical graph Laplacian penalizes differences between pairs, inadvertently taxing coherent group motion that the underlying physical constraints allow.

The core problem is to recover a latent matrix $X^* \in \mathbb{R}^{N \times T}$ from noisy, incomplete observations $Y_{obs}$ where the missingness mask $M$ creates structured absences that violate the assumptions of standard imputation protocols.

2. Methodology: Multi-Scale Hypergraph Laplacians (MSHL)

The authors propose MSHL, a two-stage framework designed to learn higher-order structure from incomplete observations while maintaining safety guarantees when such structure is not identifiable.

Stage 1: Discovery (Structure Learning)

The Discovery stage constructs a Multi-Scale Hypergraph $\hat{\mathcal{H}}$ from incomplete data.

• Linear Backbone: It begins with an Inverse-Propensity-Weighted (IPW) Tikhonov estimator. This linear backbone uses a pairwise graph Laplacian ($\mathcal{L}_G$) for spatial smoothing and a temporal Laplacian ($\mathcal{L}_T$). The IPW factor debiases the empirical loss to account for non-uniform missingness rates.
• Candidate Generation: To identify higher-order groups without ground truth, MSHL uses two complementary signals:
  1. Prior Topology: Enumerates hyperedges based on physical adjacency (e.g., top-$K$ neighbors). This signal is robust to whole-sensor blackouts where no observation exists.
  2. Residual Correlations: Computes correlations on the residuals of the pairwise pre-fit. This signal captures latent group patterns (e.g., demand clusters) not aligned with physical adjacency but is robust to scattered missingness where topology-based joint observations are sparse.
• Scale Selection: The framework employs a Lepski-style observation-only selector. It evaluates candidates across multiple hyperedge sizes ($s=2, \dots, S_{max}$) using structural scores (average residual correlation and leave-one-out MSE improvement). A per-scale complexity penalty $\rho(s-2)$ prevents over-selection at large scales. This selector adapts to the "best fixed scale" up to a logarithmic factor without requiring prior knowledge of the regime.
• Multi-Scale Laplacian: The selected hypergraph $\hat{\mathcal{H}}$ is converted into a spatial operator $\mathcal{L}_H$ using scale-invariant weighting ($w_s = 1/\binom{s}{2}$). This ensures that hyperedges of different sizes contribute equally to the regularization energy per pair, preventing bias toward larger or smaller groups.

Stage 2: Refinement (Neural Correction)

The Refinement stage adds a Hypergraph-Conditioned Residual Network (HCRN) to correct nonlinear residuals that the linear backbone cannot capture.

• Architecture: A small Multi-Layer Perceptron (MLP) takes as input the observed residual values of a target sensor's co-members within the discovered hypergraph. Crucially, the input features are structurally orthogonal to the target cell's own value to prevent trivial identity solutions.
• Safety Mechanism (Deferment): The network is trained with a Huber loss on observed cells. The design ensures that the zero correction is always a feasible configuration. If a sensor has no observed co-members (e.g., in sensor-kriging regimes), the feature vector contains no informative signals, and the network naturally defers to the linear estimate.
• Guarantee: The refinement provides a one-sided guarantee. The worst-case error of the refined estimator is bounded by the generalization gap of the linear estimator plus a vanishing term, ensuring the correction never catastrophically degrades performance.

3. Key Contributions

1. Multi-Scale Hypergraph Estimator with Provable Scale Adaptation: The paper introduces a hypergraph Laplacian with scale-invariant weighting and a Lepski-style selector that adapts to the optimal interaction scale up to a logarithmic factor. It utilizes two candidate sources (topology and residuals) with exponentially separated recovery rates to cover the full deployment spectrum.
2. One-Sided Refinement Guarantee with Built-in Deferment: The HCRN is designed such that the worst-case inflation over the linear estimator vanishes at the parametric rate. It automatically defers when no informative residual features are available, making it safe to enable by default.
3. End-to-End Theory and Regime-Level Validation: The authors prove representation, discovery, scale-selection, and refinement guarantees. Empirically, the method is validated on two real traffic networks (PEMS-BAY and METR-LA) across three missingness regimes and five missing rates, demonstrating robustness where competing methods collapse.

4. Experimental Results

The evaluation compares MSHL against five baselines (Sensor-mean, kNN-spatial, LETC, WDGTC, and a pairwise-only ablation Tikh-graph) across 30 conditions (2 datasets $\times$ 3 regimes $\times$ 5 rates).

• Performance: MSHL improves upon the pairwise-graph baseline (Tikh-graph) in 22 out of 30 conditions and ties in the remaining 8 within sampling noise. It never underperforms the baseline.
• Regime Robustness:
  • Block-MAR: MSHL achieves the largest gains (up to 23% MAE reduction on PEMS-BAY at low missing rates) because it can span gaps using group-level coherence when pairwise neighbors are jointly missing.
  • Sensor-Kriging: MSHL gracefully degrades to the linear backbone (matching Tikh-graph) when whole sensors are missing, whereas tensor-based methods (WDGTC) collapse to zero rows or global means.
  • Cell-MAR: MSHL consistently outperforms tensor and deep graph methods, avoiding the convergence failures seen in alternating optimization approaches at high missing rates.
• Hyperparameter Sensitivity: The method is robust to hyperparameter choices. A single configuration works across all regimes and datasets, with the scale selector automatically ramping down to pairwise-only fits when higher-order structure is not identifiable.
• Qualitative Analysis: Visualizations show that MSHL preserves diurnal cycles and rush-hour patterns without spatial over-smoothing or temporal artifacts. In sensor-kriging, the smoothing of held-out sensors is attributed to the necessary information loss of the linear backbone, not method failure.

5. Significance and Claims

The paper claims that missing data should be treated as evidence of structure to discover, not merely as isolated entries to fill.

• Beyond Pairwise Priors: The work demonstrates that higher-order group-conservation patterns (e.g., flow conservation) are distinct signals that pairwise graph priors cannot encode. MSHL successfully extracts these signals from incomplete data.
• Safety in Deployment: The primary significance lies in the graceful deferment mechanism. Unlike methods that may produce nonsensical outputs when their structural assumptions are violated, MSHL is "safe by construction." It improves estimates where higher-order structure is identifiable and reverts to a safe linear estimate otherwise.
• Evaluation Protocol: The authors argue that standard benchmarks using uniform-random dropout create a "deployment gap." Their evaluation protocol, stressing regime robustness across structured missingness, reveals that methods tuned to random dropout often fail in real-world structured scenarios.
• Limitations: The authors acknowledge that the framework assumes missingness is ignorable (MAR), whereas real sensors may fail due to signal saturation (non-ignorable). Additionally, the current non-learned selector and weights ensure provable guarantees but limit the discovery of unforeseen structures.

In conclusion, MSHL offers a principled approach to spatiotemporal imputation that combines structured priors with learned corrections, ensuring reliability in the specific conditions where current benchmarks are silent.