  Time series classification is an important data mining task that has received
a lot of interest in the past two decades. Due to the label scarcity in
practice, semi-supervised time series classification with only a few labeled
samples has become popular. Recently, Similarity-aware Time Series
Classification (SimTSC) is proposed to address this problem by using a graph
neural network classification model on the graph generated from pairwise
Dynamic Time Warping (DTW) distance of batch data. It shows excellent accuracy
and outperforms state-of-the-art deep learning models in several few-label
settings. However, since SimTSC relies on pairwise DTW distances, the quadratic
complexity of DTW limits its usability to only reasonably sized datasets. To
address this challenge, we propose a new efficient semi-supervised time series
classification technique, LB-SimTSC, with a new graph construction module.
Instead of using DTW, we propose to utilize a lower bound of DTW, LB_Keogh, to
approximate the dissimilarity between instances in linear time, while retaining
the relative proximity relationships one would have obtained via computing DTW.
We construct the pairwise distance matrix using LB_Keogh and build a graph for
the graph neural network. We apply this approach to the ten largest datasets
from the well-known UCR time series classification archive. The results
demonstrate that this approach can be up to 104x faster than SimTSC when
constructing the graph on large datasets without significantly decreasing
classification accuracy.
