Ego-Network Transformer for Subsequence Classification in Time Series Data

Chin-Chia Michael Yeh, Huiyuan Chen, Yujie Fan, Xin Dai, Yan Zheng, Vivian Lai, Junpeng Wang, Zhongfang Zhuang, Liang Wang, Wei Zhang, Eamonn J. Keogh

Abstract

Subsequence classification involves identifying specific events within continuous, noisy time series streams. Traditional deep learning models often struggle with this task, sometimes underperforming relative to simple $k$-nearest neighbor ($k$-NN) classifiers. This paper introduces the Ego-Network Transformer, a hybrid architecture that represents time series snippets as nodes in a $k$-NN graph. By applying a Transformer to aggregate information from a snippet's "ego-network"—its immediate neighbors in shape-space—the model combines the representational power of deep learning with the robust similarity-matching of $k$-NN. Evaluated across 158 datasets, the Ego-Network Transformer significantly outperforms standard neural networks and $k$-NN baselines, demonstrating particular efficacy in real-world scenarios like traffic event detection.

Introduction

Most time series classification research relies on pre-segmented, "clean" datasets where each snippet belongs to a single class. However, real-world data typically arrives as a continuous stream where relevant "foreground" events are buried within a dominant "background" signal. For example, a highway sensor primarily records routine traffic, only occasionally capturing distinct events like accidents or stadium-related surges.

This "subsequence classification" task presents two primary challenges. First, models must distinguish between specific classes while simultaneously identifying whether a relevant event is occurring at all. Second, researchers have observed a "Simple Baseline Paradox": sophisticated deep learning models are frequently outperformed by basic $k$-NN classifiers using Euclidean distance. The Ego-Network Transformer aims to bridge this gap by integrating the strengths of both approaches.

Methodology

The Ego-Network Transformer treats subsequences as nodes within a graph, leveraging local neighborhood information to refine classifications.

1. Ego-Network Representation

For any "focal" subsequence, the model identifies its $k$-nearest neighbors across the training set based on shape similarity, calculated using z-normalized Euclidean distance. This focal snippet and its neighbors constitute an "ego-network."

2. Hybrid Architecture

The model utilizes a two-stage process:

  • Backbone Embeddings: A backbone model (such as ResNet, LSTM, or a standard Transformer) converts raw time series snippets into high-dimensional vector embeddings.
  • Ego-Network Transformer: Rather than attending to every subsequence in a stream—which would result in $O(n^2)$ complexity—the model uses a Transformer block to attend specifically to the focal snippet's $k$ neighbors. It integrates the neighbors' embeddings and their known class labels to refine the prediction for the focal snippet.

3. Computational Efficiency

To ensure the approach is practical for large datasets, the authors extended the STOMP algorithm. This allows for the efficient construction of $k$-NN graphs by accelerating the computation of Matrix Profiles, reducing the complexity from a naive brute-force approach. During training and testing, the complexities are $O(k^2)$ and $O(k)$ respectively, where $k \ll n$.

4. Temporal Consistency

Because adjacent subsequences in a sliding window overlap significantly, the model employs a majority-voting smoothing step. This post-processing reduces "flickering" predictions—rapidly oscillating false positives or negatives—ensuring temporal consistency in the output stream.

Experimental Evaluation

The model was evaluated against a massive suite of 158 datasets, including 128 univariate datasets from the UCR Archive and 30 multivariate datasets from the UEA Archive. To simulate real-world conditions, these datasets were adapted into subsequence tasks by embedding foreground segments into synthetic background noise generated via random walks.

Case Study: Dodger Loop Sensor

A critical real-world test involved the Dodger Loop Sensor dataset, which requires detecting baseball games from highway traffic data near Dodger Stadium in Los Angeles. This task is particularly difficult due to the high ratio of background noise to foreground events.

Key Results and Insights

  • Broad Superiority: The Ego-Network Transformer outperformed baseline models on 104 out of 158 datasets. While the architecture is flexible, ResNet and Transformer backbones generally provided the strongest results.
  • Significant Gains in Real-World Tasks: In the Dodger Stadium case study, a standard Transformer baseline achieved an F1-score of only 0.18. The Ego-Network Transformer boosted this to 0.37, a substantial improvement in detection accuracy.
  • The Power of Neighbors: Ablation studies highlighted the importance of the graph structure. Removing the nearest neighbor from the ego-network resulted in a 72% performance drop in the case study, confirming that shape-space neighbors provide a vital prior for classification.
  • Data Scarcity Resilience: The ego-network approach proved especially effective when training data was scarce. By leveraging the similarity graph, the model could effectively "verify" its features against known examples even with limited positive samples.

Conclusion and Future Work

The Ego-Network Transformer demonstrates that incorporating $k$-NN priors into a deep learning framework significantly enhances subsequence classification. By restricting attention to local ego-networks, the model achieves both high accuracy and computational efficiency.

Future research may explore the use of approximate graph construction algorithms (like SCAMP) to further improve scalability. Additionally, for multivariate data, investigating "sub-dimensional" nearest neighbors—comparing snippets based on a subset of sensors—could provide more nuanced similarity matching in complex systems.

Summary updated

BibTeX
@inproceedings{yeh2023ego,
  author = {Chin-Chia Michael Yeh and Huiyuan Chen and Yujie Fan and Xin Dai and Yan Zheng and Vivian Lai and Junpeng Wang and Zhongfang Zhuang and Liang Wang and Wei Zhang and Eamonn J. Keogh},
  title = {{Ego-Network Transformer for Subsequence Classification in Time Series Data}},
  booktitle = {IEEE Big Data},
  year = {2023},
  doi = {10.1109/bigdata59044.2023.10386283},
}
Figure