  Multivariate time series (MTS) imputation is a widely studied problem in
recent years. Existing methods can be divided into two main groups, including
(1) deep recurrent or generative models that primarily focus on time series
features, and (2) graph neural networks (GNNs) based models that utilize the
topological information from the inherent graph structure of MTS as relational
inductive bias for imputation. Nevertheless, these methods either neglect
topological information or assume the graph structure is fixed and accurately
known. Thus, they fail to fully utilize the graph dynamics for precise
imputation in more challenging MTS data such as networked time series (NTS),
where the underlying graph is constantly changing and might have missing edges.
In this paper, we propose a novel approach to overcome these limitations.
First, we define the problem of imputation over NTS which contains missing
values in both node time series features and graph structures. Then, we design
a new model named PoGeVon which leverages variational autoencoder (VAE) to
predict missing values over both node time series features and graph
structures. In particular, we propose a new node position embedding based on
random walk with restart (RWR) in the encoder with provable higher expressive
power compared with message-passing based graph neural networks (GNNs). We
further design a decoder with 3-stage predictions from the perspective of
multi-task learning to impute missing values in both time series and graph
structures reciprocally. Experiment results demonstrate the effectiveness of
our model over baselines.
