Real-Time Anomaly Detection in Edge Streams

• URL: http://arxiv.org/abs/2009.08452v3
• Date: Mon, 25 Apr 2022 04:30:45 GMT
• Title: Real-Time Anomaly Detection in Edge Streams
• Authors: Siddharth Bhatia, Rui Liu, Bryan Hooi, Minji Yoon, Kijung Shin and Christos Faloutsos
• Abstract summary: 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.
• Score: 49.26098240310257
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Given a stream of graph edges from a dynamic graph, how can we assign anomaly scores to edges in an online manner, for the purpose of detecting unusual behavior, using constant time and memory? Existing approaches aim to detect individually surprising edges. In this work, we propose MIDAS, which focuses on detecting microcluster anomalies, or suddenly arriving groups of suspiciously similar edges, such as lockstep behavior, including denial of service attacks in network traffic data. We further propose MIDAS-F, to solve the problem by which anomalies are incorporated into the algorithm's internal states, creating a `poisoning' effect that can allow future anomalies to slip through undetected. MIDAS-F introduces two modifications: 1) We modify the anomaly scoring function, aiming to reduce the `poisoning' effect of newly arriving edges; 2) We introduce a conditional merge step, which updates the algorithm's data structures after each time tick, but only if the anomaly score is below a threshold value, also to reduce the `poisoning' effect. Experiments show that MIDAS-F has significantly higher accuracy than MIDAS. MIDAS has the following properties: (a) it detects microcluster anomalies while providing theoretical guarantees about its false positive probability; (b) it is online, thus processing each edge in constant time and constant memory, and also processes the data orders-of-magnitude faster than state-of-the-art approaches; (c) it provides up to 62% higher ROC-AUC than state-of-the-art approaches.

Related papers

• ARES: Anomaly Recognition Model For Edge Streams [15.767494189633133]
  We introduce ARES, an unsupervised anomaly detection framework for edge streams.<n> ARES combines Graph Neural Networks (GNNs) for feature extraction with Half-Space Trees (HST) for anomaly scoring.<n>GNNs capture both spike and burst anomalous behaviors within streams by embedding node and edge properties in a latent space, while HST partitions this space to isolate anomalies efficiently.
  arXiv  Detail & Related papers  (2025-11-27T03:56:35Z)
• Federated Spatiotemporal Graph Learning for Passive Attack Detection in Smart Grids [2.721477719641864]
  This paper introduces a graph-centric, multimodal detector that fuses physical-layer and behavioral indicators over temporal windows to detect passive attacks.<n>The model achieves a testing accuracy of 98.32% per-timestep and 93.35% per-sequence at 0.15% FPR.
  arXiv  Detail & Related papers  (2025-09-29T08:52:30Z)
• Adaptive-GraphSketch: Real-Time Edge Anomaly Detection via Multi-Layer Tensor Sketching and Temporal Decay [0.12891210250935145]
  ADAPTIVE-GRAPHSKETCH is a lightweight and scalable framework for real-time anomaly detection in streaming edge data.<n>Our results show that ADAPTIVE-GRAPHSKETCH is practical and effective for fast, accurate anomaly detection in large-scale streaming graphs.
  arXiv  Detail & Related papers  (2025-09-15T06:57:35Z)
• Enhancing Web Service Anomaly Detection via Fine-grained Multi-modal Association and Frequency Domain Analysis [8.860339665670255]
  Anomaly detection is crucial for ensuring the stability and reliability of web service systems. Existing anomaly detection methods use logs and metrics to detect anomalies. We propose a novel anomaly detection method named FFAD to address these two issues.
  arXiv  Detail & Related papers  (2025-01-28T12:00:45Z)
• ORCHID: Streaming Threat Detection over Versioned Provenance Graphs [11.783370157959968]
  We present ORCHID, a novel Prov-IDS that performs fine-grained detection of process-level threats over a real time event stream. ORCHID takes advantage of the unique immutable properties of a versioned provenance graphs to iteratively embed the entire graph in a sequential RNN model. We evaluate ORCHID on four public datasets, including DARPA TC, to show that ORCHID can provide competitive classification performance.
  arXiv  Detail & Related papers  (2024-08-23T19:44:40Z)
• Multitask Active Learning for Graph Anomaly Detection [48.690169078479116]
  We propose a novel MultItask acTIve Graph Anomaly deTEction framework, namely MITIGATE. By coupling node classification tasks, MITIGATE obtains the capability to detect out-of-distribution nodes without known anomalies. Empirical studies on four datasets demonstrate that MITIGATE significantly outperforms the state-of-the-art methods for anomaly detection.
  arXiv  Detail & Related papers  (2024-01-24T03:43:45Z)
• Streaming Anomaly Detection [7.60882697435906]
  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.
  arXiv  Detail & Related papers  (2023-01-30T18:59:51Z)
• G-CMP: Graph-enhanced Contextual Matrix Profile for unsupervised anomaly detection in sensor-based remote health monitoring [9.835993421463515]
  In the wild, anomaly detection approaches are challenged by noise, label scarcity, high dimensionality, explainability and wide variability in operating environments. We propose a novel, self-supervised graph-based approach for temporal anomaly detection that works on context graphs generated from the CMP distance matrix. Our proposed method demonstrated better recall, alert rate and generalisability.
  arXiv  Detail & Related papers  (2022-11-29T11:48:50Z)
• Are we certain it's anomalous? [57.729669157989235]
  Anomaly detection in time series is a complex task since anomalies are rare due to highly non-linear temporal correlations. Here we propose the novel use of Hyperbolic uncertainty for Anomaly Detection (HypAD) HypAD learns self-supervisedly to reconstruct the input signal.
  arXiv  Detail & Related papers  (2022-11-16T21:31:39Z)
• Unveiling Anomalous Edges and Nominal Connectivity of Attributed Networks [53.56901624204265]
  The present work deals with uncovering anomalous edges in attributed graphs using two distinct formulations with complementary strengths. The first relies on decomposing the graph data matrix into low rank plus sparse components to improve markedly performance. The second broadens the scope of the first by performing robust recovery of the unperturbed graph, which enhances the anomaly identification performance.
  arXiv  Detail & Related papers  (2021-04-17T20:00:40Z)
• Fast and Accurate Anomaly Detection in Dynamic Graphs with a Two-Pronged Approach [49.25767340466445]
  We propose AnomRank, an online algorithm for anomaly detection in dynamic graphs. AnomRank uses a two-pronged approach defining two novel metrics for anomalousness. We show theoretically and experimentally that the two-pronged approach successfully detects two common types of anomalies.
  arXiv  Detail & Related papers  (2020-11-26T01:38:27Z)
• TadGAN: Time Series Anomaly Detection Using Generative Adversarial Networks [73.01104041298031]
  TadGAN is an unsupervised anomaly detection approach built on Generative Adversarial Networks (GANs) To capture the temporal correlations of time series, we use LSTM Recurrent Neural Networks as base models for Generators and Critics. To demonstrate the performance and generalizability of our approach, we test several anomaly scoring techniques and report the best-suited one.
  arXiv  Detail & Related papers  (2020-09-16T15:52:04Z)

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.