Streaming Anomaly Detection

• URL: http://arxiv.org/abs/2301.13199v1
• Date: Mon, 30 Jan 2023 18:59:51 GMT
• Title: Streaming Anomaly Detection
• Authors: Siddharth Bhatia
• Abstract summary: We first propose MIDAS which uses a count-min sketch to detect anomalous edges in dynamic graphs in an online manner. We then extend the count-min sketch to a Higher-Order sketch to capture complex relations in graph data. Using this sketch, we propose four streaming methods to detect edge and subgraph anomalies.
• Score: 7.60882697435906
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Anomaly detection is critical for finding suspicious behavior in innumerable systems. We need to detect anomalies in real-time, i.e. determine if an incoming entity is anomalous or not, as soon as we receive it, to minimize the effects of malicious activities and start recovery as soon as possible. Therefore, online algorithms that can detect anomalies in a streaming manner are essential. We first propose MIDAS which uses a count-min sketch to detect anomalous edges in dynamic graphs in an online manner, using constant time and memory. We then propose two variants, MIDAS-R which incorporates temporal and spatial relations, and MIDAS-F which aims to filter away anomalous edges to prevent them from negatively affecting the internal data structures. We then extend the count-min sketch to a Higher-Order sketch to capture complex relations in graph data, and to reduce detecting suspicious dense subgraph problem to finding a dense submatrix in constant time. Using this sketch, we propose four streaming methods to detect edge and subgraph anomalies. Next, we broaden the graph setting to multi-aspect data. We propose MStream which detects explainable anomalies in multi-aspect data streams. We further propose MStream-PCA, MStream-IB, and MStream-AE to incorporate correlation between features. Finally, we consider multi-dimensional data streams with concept drift and propose MemStream. MemStream leverages 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 a theoretical bound on the size of memory for effective drift handling. In addition, we allow quick retraining when the arriving stream becomes sufficiently different from the training data. Furthermore, MemStream makes use of two architecture design choices to be robust to memory poisoning.

Related papers

• A Mirror Descent-Based Algorithm for Corruption-Tolerant Distributed Gradient Descent [57.64826450787237]
  We show how to analyze the behavior of distributed gradient descent algorithms in the presence of adversarial corruptions. We show how to use ideas from (lazy) mirror descent to design a corruption-tolerant distributed optimization algorithm. Experiments based on linear regression, support vector classification, and softmax classification on the MNIST dataset corroborate our theoretical findings.
  arXiv  Detail & Related papers  (2024-07-19T08:29:12Z)
• Context Recovery and Knowledge Retrieval: A Novel Two-Stream Framework for Video Anomaly Detection [48.05512963355003]
  We propose a two-stream framework based on context recovery and knowledge retrieval. For the context recovery stream, we propose a U-Net which can fully utilize the motion information to predict the future frame. For the knowledge retrieval stream, we propose an improved learnable locality-sensitive hashing. The knowledge about normality is encoded and stored in hash tables, and the distance between the testing event and the knowledge representation is used to reveal the probability of anomaly.
  arXiv  Detail & Related papers  (2022-09-07T03:12:02Z)
• Improved Multi-objective Data Stream Clustering with Time and Memory Optimization [0.0]
  This paper introduces a new data stream clustering method (IMOC-Stream) It uses two different objective functions to capture different aspects of the data. The experiments show the ability of our method to partition the data stream in arbitrarily shaped, compact, and well-separated clusters.
  arXiv  Detail & Related papers  (2022-01-13T17:05:56Z)
• SreaMRAK a Streaming Multi-Resolution Adaptive Kernel Algorithm [60.61943386819384]
  Existing implementations of KRR require that all the data is stored in the main memory. We propose StreaMRAK - a streaming version of KRR. We present a showcase study on two synthetic problems and the prediction of the trajectory of a double pendulum.
  arXiv  Detail & Related papers  (2021-08-23T21:03:09Z)
• Sketch-Based Anomaly Detection in Streaming Graphs [89.52200264469364]
  Given a stream of graph edges from a dynamic graph, how can we assign anomaly scores to edges and subgraphs in an online manner? Our method is the first streaming approach that incorporates dense subgraph search to detect graph anomalies in constant memory and time.
  arXiv  Detail & Related papers  (2021-06-08T16:10:36Z)
• MemStream: Memory-Based Anomaly Detection in Multi-Aspect Streams with Concept Drift [20.143379054091536]
  We propose MemStream, a streaming multi-aspect anomaly detection framework. We leverage the power of a denoising autoencoder to learn representations and a memory module to learn the dynamically changing trend in data. Experimental results show the effectiveness of our approach compared to state-of-the-art streaming baselines.
  arXiv  Detail & Related papers  (2021-06-07T17:54:57Z)
• Real-Time Anomaly Detection in Edge Streams [49.26098240310257]
  We propose MIDAS, which focuses on detecting microcluster anomalies, or suddenly arriving groups of suspiciously similar edges. We further propose MIDAS-F, to solve the problem by which anomalies are incorporated into the algorithm's internal states. Experiments show that MIDAS-F has significantly higher accuracy than MIDAS.
  arXiv  Detail & Related papers  (2020-09-17T17:59:27Z)
• MSTREAM: Fast Anomaly Detection in Multi-Aspect Streams [33.20161160552062]
  MSTREAM can detect unusual group anomalies as they occur in a dynamic manner. It is evaluated over the KDDCUP99, CICIDS-DoS, UNSW-NB 15 and CICIDS-DDoS datasets.
  arXiv  Detail & Related papers  (2020-09-17T17:59:16Z)
• Contextual-Bandit Anomaly Detection for IoT Data in Distributed Hierarchical Edge Computing [65.78881372074983]
  IoT devices can hardly afford complex deep neural networks (DNN) models, and offloading anomaly detection tasks to the cloud incurs long delay. We propose and build a demo for an adaptive anomaly detection approach for distributed hierarchical edge computing (HEC) systems. We show that our proposed approach significantly reduces detection delay without sacrificing accuracy, as compared to offloading detection tasks to the cloud.
  arXiv  Detail & Related papers  (2020-04-15T06:13:33Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.