Series2Graph: Graph-based Subsequence Anomaly Detection for Time Series

Abstract

Subsequence anomaly detection in long sequences is an important problem with applications in a wide range of domains. However, the approaches proposed so far in the literature have severe limitations: they either require prior domain knowledge used to design the anomaly discovery algorithms, or become cumbersome and expensive to use in situations with recurrent anomalies of the same type. In this work, we address these problems, and propose an unsupervised method suitable for domain agnostic subsequence anomaly detection. Our method, Series2Graph, is based on a graph representation of a novel low-dimensionality embedding of subsequences. Series2Graph needs neither labeled instances (like supervised techniques) nor anomaly-free data (like zero-positive learning techniques), and identifies anomalies of varying lengths. The experimental results, on the largest set of synthetic and real datasets used to date, demonstrate that the proposed approach correctly identifies single and recurrent anomalies without any prior knowledge of their characteristics, outperforming by a large margin several competing approaches in accuracy, while being up to orders of magnitude faster. This paper has appeared in VLDB 2020.

References in corpus (6)

• From time series to complex networks: the visibility graph
• Nonlinear time-series analysis revisited
• Collective Anomaly Detection based on Long Short Term Memory Recurrent Neural Network
• Return of the Lernaean Hydra: Experimental Evaluation of Data Series Approximate Similarity Search
• The Lernaean Hydra of Data Series Similarity Search: An Experimental Evaluation of the State of the Art
• ParIS+: Data Series Indexing on Multi-Core Architectures

Cited by in corpus (7)

• dCAM: Dimension-wise Class Activation Map for Explaining Multivariate Data Series Classification
• Dumpy: A Compact and Adaptive Index for Large Data Series Collections
• Matrix Profile Goes MAD: Variable-Length Motif And Discord Discovery in Data Series
• Scalable Data Series Subsequence Matching with ULISSE
• Comprehensible Counterfactual Explanation on Kolmogorov-Smirnov Test
• Data Series Indexing Gone Parallel
• Fast Data Series Indexing for In-Memory Data