LB-SimTSC: An Efficient Similarity-Aware Graph Neural Network for
  Semi-Supervised Time Series Classification
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.
Wenjie Xi, Arnav Jain, Li Zhang, Jessica Lin
LB-SimTSC: An Efficient Similarity-Aware Graph Neural Network for Semi-Supervised Time Series Classification

###### Abstract

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.

1
Footnote 1: These authors contributed equally.

Copyright © 2023, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

## Introduction

Time series classification is an important research area and attracts a great amount of attention [22]. In practice, due to the difficulty and high cost of obtaining labeled data, there might only be a few labeled instances per class for training. This becomes one of the greatest challenges in time series classification, and motivates researchers to investigate semi-supervised solutions [23]. Recently, zha et al. [24] proposed SimTSC, which combines batch Graph Convolution Network (GCN) [10] with Dynamic Time Warping (DTW), a commonly used distance measure that allows non-linear alignments in time. DTW has been shown to be more robust than other distance measures like Euclidean Distance in tasks such as classification and similarity search [1]. Specifically, SimTSC builds a graph from the DTW distance matrix; each node corresponds to a time series instance to be classified, and the edge is generated through DTW distance. SimTSC is versatile for three reasons. First, it only requires a batch dynamic subgraph and does not need the complete graph for the entire data to be stored in the GPU for training. Second, compared with the classic graph generation process, which simply uses the k-nearest neighbors (k-NN) to generate a static graph, SimTSC uses a graph via local k-NN generated from batch data, which allows the information in labeled data to be efficiently passed to the unlabeled data. Third, SimTSC is able to learn a warping-aware representation by inheriting the advantages of using DTW [19].

Despite the advantages, SimTSC is not scalable for large data. To construct the graph, SimTSC requires the full pairwise computation of DTW distances, a process with a high computational cost of \(O(L^{2})\), where L is the time series instance length. For example, for the famous _StartLightCurves_ dataset, which contains 9,236 time series of length 1,024, DTW takes around two days to calculate the distances between all pairs. Furthermore, since DTW computation uses dynamic programming, it is not parallelizable with GPU computations. While several techniques have been proposed to speed up DTW computation, they cannot be applied in this case since they work by pruning unnecessary computations for the similarity search problem, whereas SimTSC requires the full pairwise distance matrix for training.

To address this problem, we propose a new efficient graph based time series classification technique, **L**ower **B**ound **S**imilarity-aware **T**ime Series (LB-SimTSC) with a new efficient graph construction approach. Instead of computing the pairwise distance matrix using DTW, we propose to use a lower-bounding distance for DTW, which is much cheaper to compute. In particular, we adapt LB_Keogh, a popular lower bound for DTW [11], with \(O(L)\) time complexity. For the _StartLightCurves_ dataset, it would only take about 30 minutes to compute all pairwise distances using LB_Keogh instead of 2 days. The idea of lower bound is originally proposed to speed up the 1-NN similarity search problem by providing a reasonable, efficient-to-compute approximation of the actual distance and allowing us to prune some candidates from con
sideration. It is not designed as a similarity measure by itself. However, we observe that LB_Keogh matrix can be used as a replacement for DTW to provide the guidance needed by GCN and help GCN learn a similar warping-aware representation. We demonstrate through empirical evaluation that using the approximation matrix can achieve similar performance as the original SimTSC, with reduced running time by two orders of magnitude.

In summary, our contribution is as follows:

* In this paper, we investigate an important and challenging problem of semi-supervised time series classification with only a few labeled samples.
* We propose a new efficient graph-based time series classification technique, LB-SimTSC, with a new graph construction module that takes only linear time.
* Our experimental results show that our proposed LB-SimTSC achieves similar performance with SimTSC, but with much faster graph construction for large data.
* Our work demonstrates that it is possible to leverage a much more efficient lower bound distance-based graph to guide GCN, while still maintaining the same ability as using the more expensive DTW distance.

## Related Work

**Graph-based Time Series Classification** Most existing graph-based time series classification methods either require actual graphs (e.g., transportation) as an input or do not consider semi-supervised settings with few labels in each class [1]. The most closely related work is SimTSC [13]. SimTSC constructs a graph from the DTW pairwise matrix, where each node represents a time series, and the connection between nodes represents their similarity. The computation of the matrix is very time-consuming for large data. Our proposed method LB-SimTSC takes an alternative approach to address the efficiency bottleneck by utilizing LB_Keogh, a lower bound of DTW, to construct the graph. LB-SimTSC significantly reduces the graph construction time from quadratic to linear in the length of instances. It is thus more scalable for large datasets while maintaining comparable performance as SimTSC.

**Lower Bound of DTW** Lower bound of DTW is introduced to speed up time series similarity search. Since lower bounding measures are often much cheaper to compute than DTW, they are often used to approximate the minimum distance between a pair of sequences. Such approximation allows the quick elimination of certain unqualified candidates without computing the actual distances in similarity search. Driven by the need for efficient DTW-based similarity search, many lower bounding distance measures such as LB_Yi, LB_Kim, and LB_Keogh [22, 1, 13] have been proposed. Among them, LB_Keogh [13] is simple to compute and remains one of the most competitive and tightest lower bounds for DTW-based query tasks.

To the best of our knowledge, we are the first to explore the direction of using a lower bounding measure for graph construction for graph-based semi-supervised time series classification models.

## Problem Formulation

In this paper, we study a time series semi-supervised classification problem with the transductive setting [13], where test data without labels can be seen during training time. Consider a training data \(\mathcal{X}^{train}\) consisting of an time series instances \(X_{i}\) of length \(L\), with only a small \(n^{\prime}\) instances \(\mathcal{X}^{labeled}=[X_{1},X_{2},\cdots,X_{n^{\prime}}]\) with known labels \(Y^{labeled}=[y_{1},y_{2},\cdots,y_{n^{\prime}}]\) where \(y_{i}\in\{1,\cdots,C\}\) classes, and \(\mathcal{X}^{unlabeled}\) data without labels. During training, our proposed model is trained on \(\mathcal{X}^{labeled}\) and \(Y^{labeled}\) with \(\mathcal{X}^{unlabeled}\). Our goal is to train a model that correctly predicts the labels of test data \(\mathcal{X}^{test}\).

## Methodology

Fig. 1 shows the overall framework of the proposed method. The framework consists of three steps: **1) Batch Sampling**. Given a dataset \((\mathcal{X},\mathbf{Y})\), we first form a batch consisting of an equal number of labeled and unlabeled data \(\mathcal{X}^{B}\). **2) LB_Keogh Lower Bound Graph Construction**. We compute a pairwise lower bound distance matrix with respect to \(\mathcal{X}^{B}\) to generate a batch LB-graph \(G^{B}\) that describes the approximate warping-aware (dis)similarity between pairs of instances within each batch. The feature vector is obtained from the backbone network. **3) Graph Convolution and Classification** The feature vector is passed through Graph

Figure 1: Overall framework of LB-SimTSC.
Convolution Network (GCN) [10] to aggregate the features across the generated \(G^{B}\). Then the obtained node embedding is passed through a fully connected neural network and performs the classification task.

There are two main advantages of the framework: We can pass the label information from labeled instances to unlabeled instances through batched data. In addition, the GCN aggregates the information of similar instances under warping captured by the generated batch LB-graph \(G^{B}\) and achieves the preservation of warping-aware similarity on the instance level in the latent space.

Batch SamplingTo form a batch \(\mathcal{X}^{B}\) of size \(m\), we sample \(m/2\) number of instances from labeled data \((\mathcal{X}^{labeled},Y^{labeled})\), and \(m/2\) number of instances from unlabeled data \(\mathcal{X}^{unlabeled}\). In this step, we ensure that each class has equal samples to avoid imbalance in the learning process. The batch data will be used to compute the embedding and the proposed batch LB-Graph.

Lb_Keogh Graph ConstructionWe introduce our proposed LB_Keogh Graph (LB-Graph) construction in this subsection.

LB_Keogh [1] is originally proposed as a lower bound to prune unnecessary computations of DTW when performing similarity search. It is much cheaper to compute than the actual DTW distance, but still maintains the ability to allow warping when comparing two time series.

Given two time series instances \(X_{i}\) and \(X_{j}\) from batch \(\mathcal{X}^{B}\), LB_Keogh creates an envelope consisting of one upper bound and one lower bound time series. As shown in Eq. 1, for each timestamp \(k\):

\[\begin{split} u_{i,k}&=\max([X_{i,k-r},X_{i,k-r+1}, \cdots,X_{i,k+r}])\\ l_{i,k}&=\min([X_{i,k-r},X_{i,k-r+1},\cdots,X_{i,k+r }])\end{split} \tag{1}\]

where \(r\) is the allowed range of warping. Then the LB_Keogh distance \(d^{LB}\) between instance \(X_{i}\) and \(X_{j}\) is calculated by Eq. 2:

\[d^{LB}(X_{i},X_{j})=\sqrt{\sum_{k=1}^{L}\left\{\begin{array}{ll}(X_{j,k}-u_{ i,k})^{2},&ifX_{j,k}>u_{i,k}\\ (X_{j,k}-l_{i,k})^{2},&ifX_{j,k}<l_{i,k}\\ 0,&otherwise\end{array}\right.} \tag{2}\]

The pairwise LB_Keogh matrix \(D_{LB}\) given a batch \(\mathcal{X}^{B}\) is hence defined as

\[D_{LB}(i,j)=d^{LB}(X_{i},X_{j}),\quad X_{i}\in\mathcal{X}^{B},X_{j}\in \mathcal{X}^{B}. \tag{3}\]

Graph Construction from \(D_{LB}\)We next generate the graph \(G^{B}(V,E)\) from \(D_{LB}\). We perform a two-step approach to compute the edges.

We first convert the LB_Keogh distance to similarity by:

\[A_{i,j}=\frac{1}{\exp{(\alpha D_{i,j})}}. \tag{4}\]

where \(\alpha\) is scaling parameter.

Then we generate a sparse graph based on \(A\). For each row \(A_{i}=[A_{i,1},\ldots,A_{i,m}]\) in \(A\), we select \(K\) candidates to form the sparse adjacency matrix. Specifically, to form a vector \(Q_{i}\), we select random \(K\) candidates with zero LB_Keogh distance, which indicates that the shapes of these instances fall within the enveloped area (i.e. they are likely to be similar to \(X_{i}\)). If there are fewer than \(K\) candidates with zero distance, then we pick \(K\) instances with the smallest LB_Keogh distances.

To incorporate this idea, we compute a sparse adjacency matrix \(\bar{A}_{i,j}\) by:

\[\bar{A}_{i,j}=\left\{\begin{array}{ll}1/K,&j\sim\mathcal{Q}_{i}\quad \&\quad|\mathcal{Q}_{i}|\geq K;\\ A_{i,j},&A_{i,j}\in\arg\text{TopK}(A_{i})\quad\&\quad|\mathcal{Q}_{i}|<K;\\ 0,&\text{otherwise}.\end{array}\right. \tag{5}\]

where \(\mathcal{Q}_{i}=\{k|D_{i,k}=0\}\), and we randomly pick \(K\) samples from \(\mathcal{Q}_{i}\).

Now we are ready to build the batch graph \(G^{B}(V,E)\) where \(|V|=m\), and the weights between node \(i\) and node \(j\) is defined as:

\[E_{i,j}=\frac{\bar{A}_{i,j}}{\sum_{b=1}^{m}\bar{A}_{i,b}}. \tag{6}\]

The overall LB graph construction algorithm is summarized in Algorithm 1.

```
1:Input:\(\mathcal{X}^{B}\): batch data, \(r\): warping range, \(\alpha\): scaling factor, \(K\): number of top neighbors
2:Output:\(G^{B}\): the graph of the current batch /* Compute \(D_{LB}\) via Eqn. 3 */
3:\(D\)=ComputePairwiseLB(\(X_{batch}\)) /* Compute \(A\) via Eqn. 4 */
4:for each \(D_{i,j}\) in \(D\)do
5:\(A_{i,j}=1/\exp(\alpha D_{i,j})\)
6:endfor
7: /* Compute \(G^{B}\) via Eqn. 5 and Eqn. 6. */
8:\(G^{B}=\text{GenerateGraph}(A,K)\)
9:return\(G^{B}\)
```

**Algorithm 1** LB-Graph Construction

Graph Convolution and ClassificationGiven a backbone network \(f(.)\), we compute the feature embedding network \(z=f(\mathcal{X}^{B})\). Then the embedding \(z\) is passed through a series of graph convolutional network (GCN) layers and used to perform classification. Particularly,

\[z^{l}=GCN(G^{B},z^{l-1})\]

\[o=Softmax(z^{l}).\]

where \(l\) is the number of layers in this case. In our work, we use the same backbone network as SimTSC [14], which is a ResNet [1] with three residual blocks.

Figure 2: A visual intuition of the lower envelope (blue dotted line) and upper envelope (green dotted line) of a sample time series (gray solid line) generated by LB_Keogh.
### Advantages of LB-SimTSC

Compared with SimTSC [13], our proposed method has two advantages. First, we construct batch LB_Keogh graph, which can be seen as an alternative but efficient solution to measure warping similarity. Compared to the original DTW distance computation, which is expensive via dynamic programming or recursion, LB_Keogh is simple and only requires \(O(L)\) time complexity. Second, from Eqn 2, we can see that \(D_{LB}\) is highly parallelizable, thus more suitable to implement in GPU.

Moreover, GCN does not require exact weights to perform aggregate information to propagate label information. Therefore, although LB_Keogh matrix \(D_{LB}\) containing zero values provides a less accurate warping measure than DTW, all of these instances fall into the envelop area and share some degree of warping similarity. Thus, a random subset of zero value in \(D_{LB}\) is sufficient to guide the training and propagate labels. In our experiments, we find that the empirical performance of LB-SimTSC is statistically comparable with the performance of SimTSC.

## Experimental Evaluation

In this section, we evaluate both efficiency and performance of our proposed LB-SimTSC.

DatasetsOur evaluation will focus on demonstrating the efficiency of LB-SimTSC, as well as the ability to achieve competitive performance even with few labels available. We choose all large datasets from the UCR classification archive [1]. Specifically, we choose datasets with sequence lengths greater than 500, and the number of instances greater than 2000. A total of ten datasets are included. We follow the same dataset generation protocol as SimTSC, whereas we first split every dataset into training set (80%) and test set dataset (20%). We randomly sample \(\beta\) instances for each class from the training data to form \(\mathcal{X}^{labeled}\) and \(Y^{labeled}\). The remaining training data is used as \(\mathcal{X}^{unlabeled}\). We test six different settings \(\beta=\{5,10,15,20,25,30\}\). We report the classification accuracy for each case.

HyperparametersWe keep all the settings of the baselines, consistent with the original paper. For our model, we fix the warping range \(r\) to be 5% of time series length, and empirically set the scaling factor \(\alpha\) to 11. All other settings are consistent with SimTSC.

Experiment 1: Comparing with 1NN-DTWWe compare with the 1-Nearest Neighbor classifier under Dynamic Time Warping Distance (1NN-DTW). 1NN-DTW is a well-known baseline in time series classification [1] and still performs well even with only few labeled data available [13].

Table 1 shows the classification accuracy of 1NN-DTW and our model on the 10 datasets. Our model wins 8 or 9 out of 10 in most cases, and ties with 1NN-DTW when \(\beta=5\). To further illustrate the superiority of the accuracy of our model, we perform the one-sided Wilcoxon signed-rank test. The p-values of the Wilcoxon test between two models on all \(\beta\) settings are 0.246, 0.042, 0.042, 0.043, 0.043, 0.024 and 0.042, respectively. Among them, except for \(\beta=5\), the rest of the p-values are all less than 0.05. Thus we conclude that our model is significantly better than 1NN-DTW across all settings except 5 labels, which is consistent with the observation in SimTSC. This is potential because the extreme small-sample situation is easier for the classical 1-NN method but more difficult for deep learning to get good performance.

Experiment 2: Comparing with SimTSCSimTSC [13] is the closest related work. We compare computational time for graph construction, which is the major bottleneck in overall computation cost. For both methods, to ensure a fair comparison, we follow the same implementation process described in [13] via pre-computing the similarity matrix for the entire dataset first, then performing sampling for each batch. For our model, LB-SimTSC, we use Python to implement the graph construction process. For SimTSC, since their graph construction code in C is not executable on our computer, we use an equivalent C++ implementation to estimate their running time. We report the actual running time for both methods.

\begin{table}
\begin{tabular}{l c c c c c c} \hline \hline  & \multicolumn{2}{c}{5 labels} & \multicolumn{2}{c}{10 labels} & \multicolumn{2}{c}{15 labels} \\ \hline Datasets & 1NN-DTW & LB\_SimTSC & 1NN-DTW & LB\_SimTSC & 1NN-DTW & LB\_SimTSC \\ \hline Perda & 0.540 & **0.793** & 0.531 & **0.826** & 0.545 & **0.816** \\ Perdb & 0.672 & **0.813** & 0.603 & **0.806** & 0.628 & **0.807** \\ NIFECTECT & **0.665** & 0.662 & 0.704 & **0.743** & 0.710 & **0.830** \\ NIFECTECT & **0.757** & 0.689 & 0.758 & **0.798** & 0.817 & **0.856** \\ UWGLAll & **0.779** & 0.447 & **0.824** & 0.549 & **0.856** & 0.622 \\ Phoneme & 0.185 & **0.255** & 0.204 & **0.330** & **0.209** & **0.346** \\ Mailfa & **0.944** & 0.508 & 0.900 & **0.635** & **0.571** & 0.960 \\ MSST & 0.784 & **0.871** & 0.796 & **0.853** & 0.834 & **0.908** \\ MSST & **0.790** & 0.775 & 0.519 & **0.891** & 0.834 & **0.916** \\ SLC & 0.559 & **0.970** & **0.653** & **0.939** & 0.763 & **0.546** \\ \hline wins & **5** & **5** & **1** & **9** & **2** & **8** \\ p-value & 0.246 & **-** & 0.042 & **-** & 0.042 & **-** \\ \hline \hline \end{tabular}
\end{table}
Table 1: Accuracy scores LB-SimTSC (ours) and 1NN-DTW on ten large datasets. The p-value is calculated using the Wilcoxon signed-rank test (one-sided).

\begin{table}
\begin{tabular}{l c c c c c} \hline \hline Datasets & Length & Instance & SimTSC & LB-SimTSC & Faster \\ \hline Perda & 500 & 4921 & 3.826 & **0.127** & **30s** \\ FordB & 500 & 4446 & 3.310 & **0.099** & **33x** \\ NIFECTECT1 & 750 & 3765 & 4.622 & **0.082** & **56x** \\ NIFECTECT2 & 750 & 3765 & 4.678 & **0.081** & **58x** \\ UWGLAll & 945 & 4478 & 10.385 & **0.126** & **62x** \\ Phoneme & 1024 & 2110 & 2.841 & **0.029** & **96x** \\ Mallat & 1024 & 2400 & 3.716 & **0.036** & **104x** \\ MSST & 1024 & 2525 & 4.014 & **0.041** & **96x** \\ MSRT & 1024 & 2925 & 5.045 & **0.058** & **86x** \\ SLC & 1024 & 9236 & 46.240 & **0.566** & **82x** \\ \hline Total & & & & 88.676 & **1.247** & **71x** \\ \hline \hline \end{tabular}
\end{table}
Table 2: Comparison of graph construction time
Table 2 shows the graph construction time in hours for SimTSC and LB-SimTSC on the ten datasets. We can observe that even when we use the slower implementation (Python) for the graph construction module of our model and the much faster implementation (MATLAB) for SimTSC, our model is still 71x faster than SimTSC in total time, and up to 104x faster on one dataset. For the time required to complete all graph construction, our approach reduces it from 3 days 16 hours to only 75 minutes. Note that an increase in time series length or number of instances makes the speed gap of our method more significant than that of SimTSC. The large time saving of our model makes our approach desirable for semi-supervised TSC on large data with few labels.

We also compare the accuracy to demonstrate that LB-SimTSC still achieves competitive performance. To eliminate randomness in deep learning training, we run both methods three times and report the average accuracy. Table 3 shows the classification accuracy of SimTSC and our model. The number of wins of SimTSC is slightly more than ours in all settings. To show the difference in accuracy between the two models, we perform the two-sided Wilcoxon signed-rank test. The p-values between SimTSC and LB-SimTSC are 0.492, 0.375, 0.375, 0.232, 0.695 and 0.492, respectively. All the p-values are less than 0.05, meaning our model does not have a significant difference in accuracy from SimTSC.

## Conclusion

In this paper, we study efficient semi-supervised time series classification with few labeled samples. We propose a new efficient graph-based time series classification, LB-SimTSC, with a new graph construction module that takes only linear time. Our proposed method resolves the scalability issue of constructing graphs from large datasets while maintaining the ability to allow time warping when comparing two time series. The experimental results on ten large datasets from the UCR archive show that our model achieves two orders of magnitude of speedup on graph construction without significant loss of classification accuracy compared to SimTSC. Furthermore, our work is the first to explore using a more efficient lower bounding-based graph to guide GCN while still maintaining the same ability as the more expensive DTW-based SimTSC.
