Ego-Network Transformer for Subsequence Classification in Time Series Data

Extensive research has been conducted on various classification problems involving time series [3, 4, 5, 6]. One commonly studied variant is known as time series classification [5, 4]. An example of such problem is shown in Fig. 2.

During the training phase, a machine learning model is trained using a set of training time series, along with their corresponding ground truth labels. In this particular example, the time series data consists of human activity recordings obtained from accelerometers. Each time series is assigned a label indicating whether the activity is classified as walking or running. Once a test time series $X$ is obtained, the model predicts the most likely class label for $X$.

Another closely related time series problem is known as semantic segmentation [6]. An example of a time series semantic segmentation problem involving human activity time series is depicted in Fig. 3.

Unlike the time series classification problem, in semantic segmentation, we no longer have a dataset consisting of multiple time series. Instead, we have a single training time series $T_{\text{train}}$ and a separate testing time series $T_{\text{test}}$. The training time series $T_{\text{train}}$ can be segmented into multiple regimes, and for the ground truth labels, we have the locations of the boundaries between the regimes and the corresponding “class” of each regime. During testing, the trained model needs to perform two tasks: 1) identify the segmentation boundaries and 2) classify each regime into the appropriate class.

Finally, the problem addressed in this paper is referred to as the subsequence classification problem, and an example of such a problem is illustrated in Fig. 4.

Similar to semantic segmentation, the subsequence classification problem involves a single training time series $T_{\text{train}}$ and a separate testing time series $T_{\text{test}}$. However, both $T_{\text{train}}$ and $T_{\text{test}}$ may contain background segments that are unrelated to the classes of interest. In Fig. 4, the relevant subsequences correspond to walking and running patterns, while the other subsequences are considered as background segments (e.g., standing still). During testing, predictions are made at the subsequence level, where the subsequences are generated using a sliding window approach. The machine learning model needs to determine whether a subsequence belongs to one of the relevant classes (e.g., walking or running) or if it is a background subsequence.

It is important to note that the example problems presented in this section focus on univariate time series. However, each of these problems can also be formulated and extended to handle multivariate time series data.

We focus our related works section on two topics: 1) $k$-nearest neighbor subsequence graph and 2) time series classification.

The notion of a $k$-nearest neighbor subsequence graph may not have been explicitly explored in the time series data mining community. However, a similar concept has been implicitly adopted in the form of the Matrix Profile [7, 8]. The Matrix Profile algorithm involves computing two meta time series for a given time series $T$: the Matrix Profile and the Matrix Profile Index. The Matrix Profile stores the distance (typically $z$-normalized Euclidean distance) between each subsequence and its nearest neighbor, while the Matrix Profile Index stores the identity of the nearest neighbor. Together, these two meta time series form a 1-nearest neighbor graph for all subsequences in $T$. This 1-nearest neighbor subsequence graph has been utilized in various time series data mining tasks, including motif discovery, anomaly detection, and segmentation [9, 10, 11, 12, 13].

The initial Matrix Profile algorithms, such as STOMP [14], have already demonstrated sufficient efficiency for large-scale time series. However, subsequent research has made significant progress in further reducing the computational time of the Matrix Profile. Approaches such as utilizing specialized hardware, approximation techniques, and improved anytime convergence have been adopted to enhance its efficiency [15, 16, 17, 18, 19]. Many of these techniques can be incorporated into our $k$-nearest neighbor construction algorithm. Nevertheless, as the first work in adopting the $k$-nearest neighbor graph for the subsequence classification problem, our primary focus is to demonstrate the benefits of using this graph in our proposed approach. Therefore, we have chosen to extend a more basic version of the Matrix Profile algorithm, such as STOMP [14], to avoid the additional complexity associated with these more advanced methods. Exploring the integration of these advanced techniques into our algorithm is an avenue for future work.

Over the years, numerous time series classification methods have been proposed [20, 1]. Recent benchmark papers [20, 1] have identified methods such as HIVE-COTE [21], ROCKET [22], and ResNet [23] to achieve state-of-the-art performance in time series classification. In our work, we have chosen to extend neural network-based methods, e.g., ResNet [23], due to their modular nature, which facilitates easy modification and integration into our approach as backbone models. The designs of our backbone time series representation learning models are inspired by various popular neural network architectures for modeling sequential data [24, 25, 26, 23, 27], as introduced in Section IV-B.

The proposed Transformer model is presented in Fig. 6. The input to the model consists of a focal subsequence denoted as $X_{\text{focal}}$, along with its nearest neighbor subsequences from the training time series $X_{0},\cdots,X_{k-1}$, and the corresponding labels of the neighbors $y_{0},\cdots,y_{k-1}$. Essentially, the inputs consist of the subsequences associated with the ego-network of the focal subsequence, where the ego-network is extracted from the $k$-nearest neighbor subsequence graph. The initial step involves extracting the intermediate representation of each subsequence using one of the backbone models discussed in Section IV-B. These representations are denoted as $H_{\text{focal}},H_{0},H_{1},\cdots,H_{k-1}$, where $H_{\text{focal}}$ corresponds to the representation of $X_{\text{focal}}$, and $H_{0},H_{1},\cdots,H_{k-1}$ correspond to the representations of $X_{0},X_{1},\cdots,X_{k-1}$, respectively.

Next, we incorporate the corresponding label for each neighbor subsequence by adding a learnable label embedding to its representation. Let $Y_{i}$ represent the label embedding for $y_{i}$, the label of the $i$th neighbor. The final subsequence representation for the neighbor is computed as $\hat{H}_{i}\leftarrow Y_{i}+H_{i}$. With the node representations of each subsequence prepared, we concatenate them together to form a set that includes all the node representations: $[H_{\text{focal}},\hat{H}_{0},\cdots,\hat{H}_{k-1}]$. Subsequently, we employ two layers of Transformer blocks (refer to Fig. 9) to aggregate information from each node in the set. After the Transformer blocks, we extract the representation corresponding to the focal subsequence. Finally, a linear layer is used to compute the logit for each class. We choose to use a Transformer-based model design to capture the ego-network, as opposed to other graph neural networks like GCN [31] or GAT [32], because it has been shown in [33] that Transformers are more effective compared to the alternatives.

The proposed method leverages the versatile and powerful $k$-nearest neighbor subsequence graph, as discussed in Section III, for the subsequence classification problem. This approach offers notable advantages over attending to all subsequences in the training data. By focusing only on the top $k$ nearest neighbors, the method achieves improved efficiency. This is particularly significant considering the space complexity of the Transformer block, which grows quadratically with the number of input items. For instance, if the training data consists of one million subsequences, storing the attention matrix alone would require over seven terabytes of memory.

We have explored four different neural network architectures as backbone models for extracting global representations from time series data. A global representation captures the information from the entire input time series. The four backbone models are:

• •

  The Long Short-Term Memory Network (LSTM) is a widely used type of Recurrent Neural Network (RNN) for modeling sequential data [24, 34, 27]. In our work, we adopt the design depicted in Fig. 7.a. The figure employs specific notations to describe different layers. For instance, \collectbox\BOXCONTENT1D conv,7/2,$n_{\text{in}}{\to}$64 represents a $1D$ convolutional layer with a filter size of 7, a stride size of 2, an input dimension of $n_{\text{in}}$, and an output dimension of 64. Similarly, \collectbox\BOXCONTENTbi-RNN,64${\to}$64 denotes a bidirectional RNN layer with an input dimension of 64 and an output dimension of 64. In our case, the two bi-RNN layers are implemented as bidirectional LSTM layers. Additionally, \collectbox\BOXCONTENTlinear,64${\to}$64 denotes a linear layer with an input dimension of 64 and an output dimension of 64.

  The input time series is first processed by the $1D$ convolutional layer to extract local patterns. The decision to select only the last time step is based on the understanding that it encapsulates the information from the entire input time series. However, it is worth noting that the first time step could also be chosen since the RNN layers are bidirectional. In the end, the output of the LSTM backbone model consists of a size 128 vector for each input time series.

• •

  The Gated Recurrent Unit Network (GRU) is another popular type of RNN architecture for modeling sequential data [25, 34, 27]. We employ an identical design to the LSTM backbone model (see Fig. 7.a), with the only difference being that the two bi-RNN layers are implemented as GRU layers instead of LSTM layers.

• •

  The Residual Network (ResNet) is a time series classification model inspired by the success of ResNet in computer vision [35, 23]. Extensive evaluations reported in [36] have demonstrated that ResNet is one of the most effective models for time series classification. Our design, depicted in Fig. 7.b, is based on the architecture proposed in [23]. In our notation, \collectbox\BOXCONTENTRBlock,64$\to$64 represents a residual block (refer to Fig. 8) with an input dimension of 64 and an output dimension of 64.

  The length of the output sequence from the residual blocks depends on the length of the input time series. When the sequence length is greater than one, we employ a global average pooling function to generate a global intermediate representation of the input time series. The output of this backbone model is a size 128 vector that represents each input time series.

• •

  The Transformer is a widely adopted alternative to RNNs for sequence modeling [26, 37, 27, 34, 38]. In our work, we adopt the architecture depicted in Fig. 7.c. Like the previously discussed backbone models, the initial layer comprises a $1D$ convolutional layer designed to capture local patterns. To incorporate positional information, we follow [26] and apply fixed positional encoding. This encoding is added to the output of the $1D$ convolutional layer. Furthermore, to enable effective learning of global representations for the input time series, we prepend a special token [start] to the beginning of the sequence.

  Next, the input sequence passes through four consecutive Transformer blocks, denoted as \collectbox\BOXCONTENTTBlock,8,64${\to}$64. In this notation, the number 8 refers to the attention heads, and the two 64 values represent the input and output dimensions, respectively. The design of the Transformer block is shown in Fig. 9. From the output sequence generated by the Transformer blocks, we extract the intermediate representation associated with the [start] token. This extracted representation serves as the global representation of the input time series, capturing the essential information from the entire sequence. This mechanism shares similarities with the [CLS] token used in prior Transformer models like BERT [39], highlighting its significance in capturing global context. Finally, the output of this backbone model is a size 128 vector that represents each input time series.

The detailed design of the residual block can be found in Fig. 8. This block consists of two passages: the main passage and the skip connection passage. The main passage processes the input sequence using three pairs of $1D$ convolutional-ReLU layers. The convolutional layers have filter sizes of seven, five, and three, sequentially, progressing from the input to the output. On the other hand, the skip connection passage may include an optional $1D$ convolutional layer with a filter size of one. This convolutional layer is only introduced to the skip connection when the input dimension and the output dimension of the residual block differ. The output of the main passage and the skip connection passage are combined through element-wise addition to form the final output of the block.

The design of the Transformer block is illustrated in Fig. 9, showcasing its structure and components. The Transformer block is composed of two stages: a multihead self-attention stage and a feed-forward stage. In the first stage, a multihead self-attention module is employed. This module allows the Transformer block to capture dependencies between different positions in the input sequence. The second stage involves a position-wise feed-forward network. This network applies two linear layers with a ReLU activation function to each position of the sequence obtained from the multihead self-attention module. This stage enables the Transformer block to incorporate non-linear transformations and enhance the representation of each position. Both stages incorporate skip connections, ensuring that the input is added to the output at each stage. This mechanism facilitates the flow of information from the input to the output, enabling the model to retain important information throughout the block. The Transformer block is responsible for modeling complex dependencies and enhancing the representation of the input sequence through self-attention and position-wise transformations.

We adopt layer normalization [40] for all normalization layers in our model. Layer normalization has proven to be effective and is commonly used with sequential data [40, 26]. By applying layer normalization, we can ensure stable and consistent normalization across different layers.

The training procedure for the proposed ego-network Transformer model is outlined in Algorithm 2. The algorithm takes the following inputs: the training time series $T$, the ground truth labels $Y$, the subsequence length $m$, and the number of neighbors $k$.

To begin, in line 2, Algorithm 1 is employed to construct the $k$-nearest neighbor graph $\mathcal{G}$. Next, in line 4, the number of samples $n_{\text{sample}}$ is calculated. This value corresponds to the minimal number of subsequences used for training in each epoch and is determined based on the number of subsequences required to cover the time series $T$. Using all subsequences would lead to redundancy due to overlap between subsequences. In line 5, $n_{\text{sample}}$ subsequences are randomly sampled from $T$ without replacement. The sampling process yields the sampled subsequences $\mathbf{X}_{\text{sample}}$, their associated ground truth labels $Y_{\text{sample}}$, and the indices of the subsequences $I_{\text{sample}}$. This random sampling approach enables the model to train on different shifts of essentially the same subsequences, thereby enhancing its robustness.

In line 7, the mini-batch for the iteration is prepared, consisting of the subsequence $\mathbf{X}_{\text{batch}}$, the corresponding ground truth labels $Y_{\text{batch}}$, and the indices $I_{\text{batch}}$. In line 8, by utilizing the $k$-nearest neighbor graph $\mathcal{G}$ and the indices $I_{\text{batch}}$, we obtain the indices of the $k$-neighbors, denoted as $\mathbf{I}_{\text{neighbor}}$, for each sample in the mini-batch. It is important to note that $\mathbf{I}_{\text{neighbor}}$ is a matrix of size $n_{\text{batch}}\times k$, where $\mathbf{I}_{\text{neighbor}}[i,j]$ contains the index of the $j$th neighbor for the $i$th sample in the mini-batch. In line 9, we extract the subsequences and labels for each neighbor based on the indices in $\mathbf{I}_{\text{neighbor}}$. Line 10 involves updating the parameters $\theta$ of the ego-network Transformer model $f_{\theta}$. Finally, in line 11, the trained model $f_{\theta}$ is returned as the output of the algorithm.

The inference procedure for the proposed Transformer model is presented in Algorithm 3. The algorithm accepts the following inputs: the test time series $T_{\text{test}}$, the training time series $T_{\text{train}}$, the training labels $Y_{\text{train}}$, the subsequence length $m$, and the number of neighbors $k$.

Similar to Algorithm 2, Algorithm 3 also constructs the $k$-nearest neighbor graph $\mathcal{G}$ in line 2, but with the difference that it finds the $k$-nearest neighbors from $T_{\text{train}}$ for each subsequence in $T_{\text{test}}$. From line 3 to line 6, the algorithm predicts the label for each subsequence $\mathbf{X}_{i}\in T_{\text{test}}$, where $i$ denotes the index associated with $\mathbf{X}_{i}$. In line 4, the index of the neighbors for the subsequence $\mathbf{X}_{i}$ is extracted from $\mathcal{G}$. In line 5, the subsequence and label for each neighbor are extracted from $T_{\text{train}}$ and $Y_{\text{train}}$. In line 6, the label for $\mathbf{X}_{i}$ is predicted and stored in $\hat{Y}_{\text{test}}[i]$. The predicted labels $\hat{Y}_{\text{test}}$ are returned in line 7.

It’s worth noting that although we introduced both Algorithm 2 and Algorithm 3 with univariate time series, both algorithms can also handle multivariate time series.

To ensure temporal consistency, we employ a sliding window technique to smooth the predicted label series. This post-processing method is both simple and effective. By following these steps, we obtain the smoothed label vector $Y_{\text{after}}$ from the input label vector $Y_{\text{before}}$ and a sliding window length $m$:

1. 1.

   Starting from the left and progressing towards the right, we identify the next onset for the relevant classes (i.e., non-background classes) in $Y_{\text{before}}$.

2. 2.

   If an onset is found at index $i_{\text{onset}}$, we determine the majority class within $Y_{\text{before}}[i_{\text{onset}}:i_{\text{onset}}+m]$.

3. 3.

   If the majority class identified in the previous step is denoted as $c$, we assign $c$ to $Y_{\text{after}}[i_{\text{onset}}:i_{\text{onset}}+m]$.

4. 4.

   Repeat steps 1–3 until reaching the end.

Fig. 10 provides a visual example illustrating the post-processing method with $m=3$. In this example, three onsets (onset 0, onset 1, and onset 2) are detected, and there are three classes (class 0 which represents the background, class 1, and class 2). For onset 0, the majority class within the window is class 1, so we set the corresponding values in $Y_{\text{after}}$ to class 1. Similarly, for onset 1 and onset 2, we assign the corresponding values in $Y_{\text{after}}$ as class 2 and class 0, respectively. This post-processing method improves the temporal consistency of the predicted labels. In the given example, the likely erroneous classification of class 1 at onset 2 is corrected. Please note that in our experiments, we determine the length of the sliding window using a validation dataset.

The 128 univariate datasets are from the UCR Archive [5], while the 30 multivariate time series datasets are from the UEA Archive [4]. Originally designed for time series classification (as depicted in Fig. 2), we have adapted these datasets to suit our problem setting (as shown in Fig. 4) by applying the following pre-processing steps:

1. 1.

   Splitting all instances in the dataset into training, validation, and test sets with a ratio of 6:2:2. Each instance is considered as a foreground segment.

2. 2.

   Generating the background segment for each foreground segment using a random walk generator, with its length being twice that of each foreground segment. For multivariate time series, the background segment is also multivariate.

3. 3.

   Splitting the background segment into two parts at a random position and concatenating each part to the beginning and end of the foreground segment. When connecting the foreground segments with the background segments, we carefully adjust the offset to avoid any noticeable step-shape artifacts around the connection points.

4. 4.

   Connecting all the expanded instances within each set (i.e., training, validation, and test sets) into continuous time series. Again, we adjust the offset of each instance to prevent the occurrence of step-shape artifacts.

5. 5.

   Creating the ground truth labels for each time series by assigning a class label to a subsequence when 60% or more of the subsequence consists of the foreground segment from that particular class.

Fig. 11 illustrates the first 1,700 training time series samples from the Crop dataset in UCR Archive. In Fig. 11.top, the foreground segments are not highlighted, making it challenging to visually distinguish them from the background. This demonstrates the difficulty of the subsequence classification task in the presence of background segments.

Because detecting the onset of an event (i.e., when a foreground segment has just occurred) is more important, we use the onset-based $F1$-score to measure performance. The difference from the traditional $F1$-score lies in how precision and recall are calculated. To calculate precision and recall, we first identify all the onsets (i.e., the beginning of a foreground class) in the predicted label $\hat{Y}_{\text{test}}$ and the ground truth label $Y_{\text{test}}$. For each onset in $\hat{Y}_{\text{test}}$, we check if the onset location contains a “correct” prediction or not. If the total number of onsets in $\hat{Y}_{\text{test}}$ is denoted as $n_{\text{total}}$ and the number of correctly predicted onsets as $n_{\text{correct}}$, the precision is computed as $\frac{n_{\text{correct}}}{n_{\text{total}}}$. We define a correct prediction as follows: Given an onset location $i$ in $\hat{Y}_{\text{test}}$, if there exists a location $j$ in $Y_{\text{test}}$ such that $\hat{Y}_{\text{test}}[i]=Y_{\text{test}}[j]$ and $|i-j|<0.1m$, where $m$ is the length of the median foreground segment. To compute the recall, we repeat the above steps by swapping the roles of $\hat{Y}_{\text{test}}$ and $Y_{\text{test}}$.

The experiments were conducted on multiple datasets, and in order to compare the overall performance of each method, it is necessary to summarize the performances across these datasets. For each compared method, we determined its ranking based on the $F1$-score achieved on each individual dataset. By averaging these rankings, we obtained the overall ranking for each method, which we report in this paper. Please note that due to space limitations, we only present the summarized results. For readers interested in the complete results, we refer them to [41].

There are two sets of baselines that we compared in this experiment. The first set of methods consists of $k$-nearest neighbor classifiers with different values of $k$. Specifically, we have the one-nearest neighbor (1NN), five-nearest neighbor (5NN), ten-nearest neighbor (10NN), and $k$-nearest neighbor where $k$ is determined using each dataset’s validation set. We use $z$-normalized Euclidean distance with the $k$-nearest neighbor classifiers. The second set of baseline methods are neural network-based methods, where we add a classification layer on top of each backbone model (i.e., LSTM, GRU, ResNet, and Transformer). These baselines are used to highlight the benefits of the proposed ego-network Transformer model.

The experimental results for UCR Archive and UEA Archive are presented in Table II and Table III, respectively. In each table, the first four rows contain the performance of the $k$-nearest neighbor methods, with and without the post-processing technique. Rows five to eight display the performance of the neural network-based methods. These include the baseline neural network methods with various backbone models, with and without the post-processing technique, as well as the ego-network Transformer with different backbone models, also with and without the post-processing technique. For the ego-network Transformer results, we provide the performance for both the five-nearest neighbor graph and the ten-nearest neighbor graph. The best method is highlighted in bold, while the second best is underlined in the tables.

First, we compare the performance of each method with and without the post-processing technique. It is evident that the post-processing technique enhances the performance of all methods. This implies that the post-processing technique is a simple yet effective method for improving the performance of most subsequence classification systems.

Next, let us compare the baseline $k$-nearest neighbor methods with the baseline neural network methods. In the UCR Archive (i.e., Table II), LSTM and GRU exhibit similar performance to the $k$-nearest neighbor baselines, while ResNet and Transformer outperform the $k$-nearest neighbor baselines. In the UEA Archive (i.e., Table III), all neural network methods surpass the performance of the $k$-nearest neighbor baselines. One possible explanation for this observation is that the UEA Archive comprises multivariate time series data. Even with less effective architectures (such as LSTM and GRU), the neural network methods still have an advantage due to their ability to learn the relative importance of different dimensions.

Lastly, we compare the ego-network Transformer methods with their baseline counterparts. The ego-network Transformer consistently improves performance in almost all cases, whether it utilizes a five-nearest neighbor graph or a ten-nearest neighbor graph. The only exception is when ResNet is used as the backbone model without the post-processing step in the UCR Archive (see Table II, row seven, first three columns). Nevertheless, the best performing method in both tables utilizes the proposed ego-network Transformer (with either the ResNet or Transformer backbones) along with the post-processing step.

To gain insights into the performance improvement brought by the proposed ego-network Transformer model in subsequence classification, we conducted a detailed analysis using the Dodgers Loop Sensor dataset [2]. This dataset consists of time series data generated by monitoring highway traffic near the Dodgers Stadium, and the task is to detect whether a baseball game is being hosted at the stadium or not. It is worth noting that this is a challenging dataset since the Dodgers Stadium also hosts other events like concerts [42], which may result in a similar amount of traffic around the stadium (i.e., false positives).

The length of the time series is 50,400, and we split it into training, validation, and test sets with a ratio of 6:2:2. After the split, there are 46 games in the training time series, 18 games in the validation time series, and 17 games in the test time series. We utilize the onset-based $F1$-score as the performance metric, and we always apply the post-processing technique to ensure temporal consistency. The experiment results are presented in Table IV, where the best performance is indicated in bold and the second best performance is underlined.

First, we focus on the performance of the $k$-nearest neighbor method with different values of $k$. We observe that the performance for $k=1$ and $k=2$ is identical (i.e., 0.15), while setting $k=3$ reduces the $F1$-score to zero. This finding indicates that the top two nearest neighbors play a more important role in determining the class of each test subsequence. Next, we examine the performance of different baseline backbone neural network methods, which mostly exhibit poor performance with zero $F1$-score. The only exception is the Transformer baseline, which outperforms the $k$-nearest neighbor classifier slightly. We suspect that their poor performance is due to the limited number of training examples for the positive class. However, when we combine each backbone model with the proposed ego-network Transformer, their performance improves dramatically. The incorporation of nearest neighbor information mitigates the data scarcity issue associated with this dataset and has the potential to be extended to other types of data.

The overall best model for this dataset is the combination of the ego-network Transformer with the Transformer backbone model. Therefore, we further investigate the relative importance of each nearest neighbor in the ego-network. To conduct this study, we evaluate the model after removing the $i$th nearest neighbor. Removing the first nearest neighbor results in a 72% reduction in performance, yielding an $F1$-score of 0.10. Removing the second nearest neighbor reduces the performance by 49% to an $F1$-score of 0.19. Finally, removing the third nearest neighbor leads to a 32% performance reduction, with an $F1$-score of 0.25. These results further confirm our assumption regarding the importance of the nearest neighbor graph when working with subsequences. Notably, these observations align with previous works in the Matrix Profile literature [8, 43, 28].