MemStream: Memory-Based Streaming Anomaly Detection

Siddharth Bhatia, Arjit Jain, Shivin Srivastava, Kenji Kawaguchi, Bryan Hooi

Abstract

Given a stream of entries over time in a multi-dimensional data setting where concept drift is present, how can we detect anomalous activities? Most of the existing unsupervised anomaly detection approaches seek to detect anomalous events in an offline fashion and require a large amount of data for training. This is not practical in real-life scenarios where we receive the data in a streaming manner and do not know the size of the stream beforehand. Thus, we need a data-efficient method that can detect and adapt to changing data trends, or concept drift, in an online manner. In this work, we propose MemStream, a streaming anomaly detection framework, allowing us to detect unusual events as they occur while being resilient to concept drift. We leverage the power of a denoising autoencoder to learn representations and a memory module to learn the dynamically changing trend in data without the need for labels. We prove the optimum memory size required for effective drift handling. Furthermore, MemStream makes use of two architecture design choices to be robust to memory poisoning. Experimental results show the effectiveness of our approach compared to state-of-the-art streaming baselines using 2 synthetic datasets and 11 real-world datasets.

Introduction

In real-world applications like network security or financial monitoring, data arrives as a continuous stream rather than a static batch. This environment presents two significant hurdles for anomaly detection: concept drift and data efficiency. Concept drift occurs when the statistical properties of "normal" behavior change over time, rendering static models obsolete. Furthermore, streaming scenarios often lack large labeled training sets, requiring models that can learn and adapt on the fly.

MemStream addresses these challenges by combining a denoising autoencoder with an explicit, FIFO-updated memory module. This framework achieves state-of-the-art accuracy while remaining robust against "memory poisoning"—the accidental inclusion of malicious data into the model's reference set.

Methodology

MemStream's architecture is built around two primary components that work in tandem to process incoming data points $x^t$ at time $t$.

Denoising Autoencoder (DAE)

The DAE serves as a robust feature extractor. By training the network to reconstruct data from corrupted versions of the input, it learns the fundamental structure of the data. This prevents the model from becoming overly flexible and inadvertently learning to reconstruct anomalies well.

Explicit Memory Module ($M$)

The memory module is a buffer that stores the embeddings ($z^t$) of recent data points deemed to be normal. The system follows a three-step workflow for every incoming record:

  1. Scoring: The embedding of a new record is compared to its $K$-nearest neighbors (K-NNs) within the memory. An anomaly score is calculated based on the distance to these neighbors.
  2. Filtering: To prevent memory poisoning, a record is only added to the memory if its anomaly score falls below a predefined threshold ($\beta$).
  3. Updating: The memory employs a First-In-First-Out (FIFO) replacement policy. As new normal data enters, the oldest entries are discarded, allowing the model to naturally adapt to concept drift by discarding stale patterns.
The MemStream architecture: (i) calculating the discounted anomaly score via K-NN search in memory, and (ii) updating the memory module using a FIFO policy based on a threshold check.

Experimental Evaluation

The authors evaluated MemStream against 11 state-of-the-art baselines across 13 datasets, including 2 synthetic datasets designed to simulate complex drift and 11 real-world benchmarks from cybersecurity and medical domains.

Performance and Drift Resilience

MemStream consistently outperformed competitors. For instance, on the NSL-KDD dataset, it achieved an AUC-PR of 0.959, significantly higher than the next best baseline (DILOF at 0.822).

A key strength is its resilience to drift. In synthetic experiments, MemStream demonstrated the ability to "spike" its anomaly score immediately when a drift occurred and then quickly recalibrate its memory to the new normal distribution. This is a critical advantage over static or slow-adapting models whose performance degrades permanently after a shift.

Anomaly scores generated by MemStream on synthetic data containing various types of concept drift. The model successfully flags anomalies and adapts to new normal patterns.

Theoretical Insights

Beyond empirical results, the paper offers theoretical justifications for its design:

  • Optimal Memory Size: The authors prove that memory size is a trade-off. Too much memory retains "stale" data, while too little lacks the variety to recognize legitimate normal behavior.
  • Embedding Dimensions: They demonstrate that the embedding dimension ($D$) should be less than or equal to the input dimension ($d$). If $D > d$, anomalies could potentially "hide" in the higher-dimensional space.
  • Self-Recovery: The system can recover from accidental poisoning. Because the scoring uses $K$-nearest neighbors, a poisoned entry eventually becomes an outlier within the memory itself as more true normal data arrives, and it is eventually flushed out by the FIFO policy.

Conclusion

MemStream provides a robust, efficient solution for anomaly detection in high-dimensional data streams. While highly effective, future work could explore more sophisticated memory management beyond simple FIFO, such as weighted importance for historical patterns, and further optimize hyperparameters like the update threshold ($\beta$) for varying drift speeds.

Summary updated

Abstract

Given a stream of entries over time in a multi-dimensional data setting where concept drift is present, how can we detect anomalous activities? Most of the existing unsupervised anomaly detection approaches seek to detect anomalous events in an offline fashion and require a large amount of data for training. This is not practical in real-life scenarios where we receive the data in a streaming manner and do not know the size of the stream beforehand. Thus, we need a data-efficient method that can detect and adapt to changing data trends, or concept drift, in an online manner. In this work, we propose MemStream, a streaming anomaly detection framework, allowing us to detect unusual events as they occur while being resilient to concept drift. We leverage the power of a denoising autoencoder to learn representations and a memory module to learn the dynamically changing trend in data without the need for labels. We prove the optimum memory size required for effective drift handling. Furthermore, MemStream makes use of two architecture design choices to be robust to memory poisoning. Experimental results show the effectiveness of our approach compared to state-of-the-art streaming baselines using $2$ synthetic datasets and $11$ real-world datasets.
BibTeX
@inproceedings{bhatia2022memstream,
  author = {Siddharth Bhatia and Arjit Jain and Shivin Srivastava and Kenji Kawaguchi and Bryan Hooi},
  title = {{MemStream: Memory-Based Streaming Anomaly Detection}},
  booktitle = {The Web Conference},
  year = {2022},
  doi = {10.1145/3485447.3512221},
}
Figure