Fast and Accurate Anomaly Detection in Dynamic Graphs with a Two-Pronged Approach

• URL: http://arxiv.org/abs/2011.13085v1
• Date: Thu, 26 Nov 2020 01:38:27 GMT
• Title: Fast and Accurate Anomaly Detection in Dynamic Graphs with a Two-Pronged Approach
• Authors: Minji Yoon, Bryan Hooi, Kijung Shin, Christos Faloutsos
• Abstract summary: 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.
• Score: 49.25767340466445
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Given a dynamic graph stream, how can we detect the sudden appearance of anomalous patterns, such as link spam, follower boosting, or denial of service attacks? Additionally, can we categorize the types of anomalies that occur in practice, and theoretically analyze the anomalous signs arising from each type? In this work, we propose AnomRank, an online algorithm for anomaly detection in dynamic graphs. AnomRank uses a two-pronged approach defining two novel metrics for anomalousness. Each metric tracks the derivatives of its own version of a 'node score' (or node importance) function. This allows us to detect sudden changes in the importance of any node. We show theoretically and experimentally that the two-pronged approach successfully detects two common types of anomalies: sudden weight changes along an edge, and sudden structural changes to the graph. AnomRank is (a) Fast and Accurate: up to 49.5x faster or 35% more accurate than state-of-the-art methods, (b) Scalable: linear in the number of edges in the input graph, processing millions of edges within 2 seconds on a stock laptop/desktop, and (c) Theoretically Sound: providing theoretical guarantees of the two-pronged approach.

Related papers

• SLADE: Detecting Dynamic Anomalies in Edge Streams without Labels via Self-Supervised Learning [24.41015179377796]
  We propose SLADE (Self-supervised Learning for Anomaly Detection in Edge Streams) for rapid detection of dynamic anomalies in edge streams. In dynamic anomaly detection across four real-world datasets, SLADE outperforms nine competing methods.
  arXiv  Detail & Related papers  (2024-02-19T08:19:26Z)
• ADA-GAD: Anomaly-Denoised Autoencoders for Graph Anomaly Detection [84.0718034981805]
  We introduce a novel framework called Anomaly-Denoised Autoencoders for Graph Anomaly Detection (ADA-GAD) In the first stage, we design a learning-free anomaly-denoised augmentation method to generate graphs with reduced anomaly levels. In the next stage, the decoders are retrained for detection on the original graph.
  arXiv  Detail & Related papers  (2023-12-22T09:02:01Z)
• Graph Anomaly Detection with Unsupervised GNNs [19.772490600670363]
  We design GLAM, an end-to-end graph-level anomaly detection model based on graph neural networks (GNNs) We also propose a new pooling strategy for graph-level embedding, called MMD-pooling, that is geared toward detecting distribution anomalies which has not been considered before.
  arXiv  Detail & Related papers  (2022-10-18T01:59:58Z)
• 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)
• 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)
• Line Graph Neural Networks for Link Prediction [71.00689542259052]
  We consider the graph link prediction task, which is a classic graph analytical problem with many real-world applications. In this formalism, a link prediction problem is converted to a graph classification task. We propose to seek a radically different and novel path by making use of the line graphs in graph theory. In particular, each node in a line graph corresponds to a unique edge in the original graph. Therefore, link prediction problems in the original graph can be equivalently solved as a node classification problem in its corresponding line graph, instead of a graph classification task.
  arXiv  Detail & Related papers  (2020-10-20T05:54:31Z)
• 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)

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.