Time-series imputation

Overview

Sensors drop out, so some entries of a multivariate series are missing. The task is to reconstruct them, using the series' own past and future and, where available, the relations between channels 2108.00298 §1. The paper assumes that the missingness is stationary and mostly missing at random, and it puts no limit on the number or length of missing blocks 2108.00298 §3. It distinguishes two evaluation settings. In-sample imputation trains and tests on the same sequence. Out-of-sample imputation trains and tests on disjoint sequences 2108.00298 §3. The survey uses the same two settings and describes imputation as a task head on a spatial-temporal encoder, trained without clean values for the gaps, so it needs a surrogate objective such as synthetic missing values 2307.03759 §3.1.

The invariant GRIL keeps is that observed entries are not changed. Only the gaps receive predictions. GRIL enforces this with a fill operator that keeps the observed values and uses the model output only where the mask is zero 2108.00298 §4, eq. 8. The GASF method does not state this rule. Its reported errors cover the missing points only, and its full-series error is higher in every row 1506.00327 tab. 2. If you use it, apply the same fill step so observed values stay as they are. That is a recommendation of this page, not a claim from the paper.

The survey gives no masking scheme for evaluation 2307.03759 §3.1. GRIL's masks are the paper's own choices: random block drops and 25% point masking 2108.00298 §5. The GASF paper uses another protocol. Missing points are simulated by setting them to zero, and 20% of training points are zeroed 1506.00327 §4.1. Compare methods only under the same masking protocol, and do not read the two papers' numbers against each other.

Variants

Graph recurrent imputation (GRIL)

A bidirectional recurrent network runs once forward and once backward in time. Its GRU gates are message-passing layers over a sensor graph. Each step imputes twice, first from the hidden state and then from the one-hop neighbours, and a final MLP combines the two directions 2108.00298 §4, eq. 3-11. The paper's message operator is diffusion convolution 2108.00298 §5 app. A. Card: Filling the Gaps: Multivariate Time Series Imputation by Graph Neural Networks. The survey lists the same model, under the name GRIN, in its imputation section 2307.03759 §7.1.

Reported results (author-reported, mean of 5 runs):

• Out-of-sample on AQI-36: MAE 12.08 against 14.50 for BRITS 2108.00298 tab. 1.
• Point-missing PEMS-BAY: MAE 0.67 against 1.47 for BRITS 2108.00298 tab. 2.
• Block-missing METR-LA: MAE 2.03 against 2.34 for BRITS 2108.00298 tab. 2.
• Synthetic particle data with a fixed charge: MAE 0.0500 against 0.1203 2108.00298 tab. 6.

BRITS is the paper's main baseline. It has no card in this wiki, so it is named here only, and no content is taken from it.

Notes for implementers, from the card's "Paper vs code" section:

• The paper calls the model GRIL. The released code calls it GRIN. The decoder in the code has projections the paper's equations do not write down, and it adds node embeddings the paper's eq. 11 omits 2108.00298 §4 gril.py.
• The paper cuts edges beyond about 40 km. The code keeps edges whose kernel weight is at least 0.1 and sets no distance cutoff 2108.00298 app. B.1 utils.py.
• The code uses dense N×N supports at every step. The paper gives O(E) for a sparse implementation and O(N²) for a dense one, and it reports no runtime figures 2108.00298 app. C.3 spatial_conv.py.
• The graph is assumed fixed over time. The paper gives no adaptation for dynamic graphs 2108.00298 §3.

Gramian angular field denoising autoencoder (GASF)

The series is rescaled to [0,1] and turned into a Gramian angular summation field (GASF). This is an n \times n image whose cell (i, j) is the cosine of the sum of two angles, one per time step 1506.00327 §2.1. A single-hidden-layer denoising autoencoder with 500 sigmoid units learns to rebuild clean GASF images from corrupted ones 1506.00327 §4.1. At imputation time, the gaps are set to zero, the autoencoder repairs the image, and the values are read back from its diagonal. The inverse used there, \cos\phi = \sqrt{(\cos 2\phi + 1)/2}, holds only for [0,1] scaling 1506.00327 §4. Card: Imaging Time-Series to Improve Classification and Imputation. The paper's main subject is classification. Imputation is one section of it.

Reported results (author-reported, MSE averaged over 10 runs, five UCR series):

• Interpolation MSE, which counts only the missing points: ECG 0.01196 for GASF against 0.02301 for the raw-series autoencoder 1506.00327 tab. 2.
• The paper reports reductions of 12.18% to 48.02% across the five series 1506.00327 §4.2.
• Full-series MSE is higher with GASF in all five rows, for example ECG 0.01148 against 0.01001 1506.00327 tab. 2.

Notes for implementers:

• The corruption is zeros, so a real zero in the data cannot be told apart from a removed point unless a mask is kept. The test-time corruption rate is not stated 1506.00327 §4.1.
• Which minimum and maximum set the rescaling range is not stated. Store them per series to undo the scaling 1506.00327 §4.
• The image has one cell per pair of time steps, so memory grows with the square of the series length 1506.00327 §2.1.
• Four of the five series in tab. 2 are also in the autoencoder's training list. The held-out series is "7 Misc" 1506.00327 §4.1.
• No official code was found for this paper, so the sketch below follows the paper's equations.

When to use which

Implementation sketch

The GRIL core is the fill step and the masked loss. The GASF core is a repair of an image followed by a read-back of the diagonal. Both sketches follow the papers' equations, not their code. The papers' own pseudocode is not reproduced.

# Keep observed entries, fill gaps with the model's prediction  [§4, eq. 8]
# Inputs: X (values), M (1 = observed), Y (prediction), all (T, N, d)
def fill(Y, X, M):
    return M * X + (1 - M) * Y

# Loss: MAE on originally observed entries only  [app. A]
# Hide an extra 5% of observed inputs during training  [app. A]
def training_loss(model, X, M, W):
    M_in = M * bernoulli(0.95)              # (T, N, d)
    out = model(X, M_in, W)                 # prediction for every entry
    return mean(abs(M * (X - out)))         # computed on M, not on M_in

For GRIL, model is the bidirectional network described above, and W is the fixed adjacency built from sensor distances. The paper's kernel is exp(-dist^2 / gamma), cut at a threshold 2108.00298 app. B.1, eq. 12.

# Gramian angular summation field of one series, values in [0, 1]  [§2.1]
def gasf(z):
    phi = arccos(z)                          # angle per time step
    return cos(phi[:, None] + phi[None, :])  # cell (i, j) = cos(phi_i + phi_j)

# Impute gaps with a GASF denoising autoencoder  [§4, §4.1]
# Inputs: x (n,), observed mask m (n,) with 1 = observed, trained dae
# Output: x with gaps filled, observed points unchanged
def impute_gasf(x, m, dae):
    # Scale to [0, 1]. The paper does not say which values set the range;
    # this sketch uses the observed points  [§4]
    lo, hi = min(x[m]), max(x[m])
    z = (x - lo) / (hi - lo)                 # (n,) in [0, 1]
    # Gaps are zeroed, as in the training corruption  [§4.1]
    z = where(m, z, 0)                       # (n,)
    # Repair the GASF image; diagonal cell (i, i) holds cos(2 phi_i)  [§4]
    img = dae(gasf(z))                       # (n, n)
    # Invert the diagonal: cos(phi) = sqrt((cos(2 phi) + 1) / 2)  [§4]
    z_hat = sqrt((diagonal(img) + 1) / 2)    # (n,)
    # Undo the scaling and keep observed values  [§4] [arxiv:2108.00298 §4]
    x_hat = z_hat * (hi - lo) + lo           # (n,)
    return where(m, x, x_hat)

Contradictions

• Synthetic varying-charge setting, text against table. The text says BRITS is "more accurate" in the varying-charge setting [arxiv:2108.00298 app. C.1]. The table shows GRIL ahead in both settings: MAE 0.0530 against 0.1089 for BRITS with varying charge 2108.00298 tab. 6. The card reads the sentence as "BRITS does better with varying than with fixed charge". Trust the table. This page does not resolve it.
• No shared baseline. GRIL is compared with BRITS on multivariate data. The GASF paper compares only with raw-series autoencoding, on univariate UCR series 1506.00327 §4.1, tab. 2. Their numbers measure different things and cannot be ranked against each other.

The survey reports no results of its own, so it cannot conflict with GRIL's numbers 2307.03759 §1. It calls the model GRIN, where the paper calls it GRIL 2307.03759 §7.1 2108.00298 §4. The name is the same model.

Papers

• Imaging Time-Series to Improve Classification and Imputation: encodes series as GASF, GADF and MTF images. Its imputation section trains a denoising autoencoder on GASF images and reports lower interpolation MSE than raw-series autoencoding on five UCR series.
• Filling the Gaps: Multivariate Time Series Imputation by Graph Neural Networks: introduces GRIL, a bidirectional graph-recurrent imputer. It reports lower MAE than BRITS on AQI, traffic, smart-meter and synthetic data.
• A Survey on Graph Neural Networks for Time Series: Forecasting, Classification, Imputation, and Anomaly Detection: a survey with no experiments. It defines imputation as a task with a head and a surrogate objective, names the in-sample and out-of-sample settings, and lists benchmark missing ratios.