PaperlayerView exact revision on arXiv

Source-linked AI summary

MIDAS: Microcluster-Based Detector of Anomalies in Edge Streams

Siddharth Bhatia, Bryan Hooi, Minji Yoon, Kijung Shin, Christos Faloutsos

arXiv:1911.04464v5cs.LGcs.AI

TL;DR

Existing graph-anomaly methods often target static graphs or individually surprising edges, while suspicious activity can arrive as groups of similar edges in a dynamic stream. MIDAS detects these microclusters online using constant time and memory, with theoretical false-positive guarantees. The paper reports 42%-48% higher AUC accuracy and 162-644 times faster processing than baseline approaches.

  • Problem

    Existing approaches focus on static graphs or individually surprising edges, while dynamic edge streams call for online microcluster detection.

    Source: Introduction · p. 1

  • Method

    MIDAS applies a streaming hypothesis-testing approach to detect microcluster anomalies in edge streams using constant time and memory.

    Source: Introduction · p. 1, Conclusion · p. 7

  • Results

    42%-48% higher AUC accuracy and 162-644 times faster processing than baseline approaches are reported for MIDAS.

    Source: Conclusion · p. 8

  • Takeaways & Limitations

    MIDAS detects microcluster anomalies while providing theoretical guarantees on false-positive probability.

    Source: Conclusion · p. 7

    The false-positive guarantees rely on the assumption that the current time tick's mean edge-arrival rate matches the mean before that tick.

    Source: Hypothesis Testing Framework · p. 3

Abstract

from arXiv · show

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. 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 162-644 times faster than state-of-the-art approaches; (c) it provides 42%-48% higher accuracy (in terms of AUC) than state-of-the-art approaches.

Introduction

Graph anomaly detection has largely focused on static graphs, while dynamic edge streams require real-time, constant-memory detection. MIDAS targets suddenly arriving microclusters rather than individually surprising edges, with theoretical false-positive guarantees and strong reported speed and accuracy.

Motivation

  • Dynamic graphs can have temporal characteristics that static-graph methods may miss.Many proposed graph-anomaly approaches had focused on static graphs.Source: Introduction · p. 1
  • Many dynamic-graph methods aggregate edges into snapshots, whereas real-time detection calls for judging an edge as it arrives.The paper also motivates constant memory because the vertex set may grow during the stream.Source: Introduction · p. 1

Streaming Microcluster Detection

  • MIDAS detects suddenly arriving groups of suspiciously similar edges, or microcluster anomalies, in edge streams.Examples include denial-of-service attacks and lockstep behavior.Source: Introduction · p. 1
  • MIDAS processes each edge in constant time and constant memory.This supports online processing as the stream grows.Source: Introduction · p. 1

Theoretical Guarantees

  • The paper reports theoretical guarantees on MIDAS's false-positive probability.The guarantees are based on a principled hypothesis-testing framework.Source: Introduction · p. 1

Effectiveness

  • 42%-48% higher AUC accuracy and 162-644 times faster processing than baseline approaches are reported for MIDAS.The reported speed and accuracy ranges summarize the experiments.Source: Introduction · p. 1

Related Work

Prior graph-anomaly work covers static graphs, graph snapshots, and edge streams, with methods targeting different anomalous entities. Among edge-stream approaches that score individual edges, the paper identifies microcluster detection and false-positive guarantees as gaps.

Static graphs

  • Static-graph anomaly detection can be classified by which entities, such as nodes, edges, or subgraphs, are identified as anomalous.The section points to Akoglu, Tong, and Koutra (2015) for an extensive survey.Source: Related Work · p. 1
  • Static-graph methods detect anomalous nodes, subgraphs, or edges using features, connectivity patterns, or reconstruction and encoding costs.Examples include egonet-based node features, anomalous dense subgraphs, and edges with high reconstruction error.Source: Related Work · pp. 1–2

Graph streams

  • Graph-snapshot methods include incremental matrix factorization for anomalous nodes, synchronized dense groups for subgraphs, and sudden unexpected edges or PageRank changes for events.The cited examples include Sun, Tao, and Faloutsos (2006), Beutel et al. (2013), Jiang et al. (2016), Eswaran et al. (2018), and Yoon et al. (2019).Source: Related Work · p. 2

Edge streams

  • Edge-stream anomaly work is categorized into anomalous-node, anomalous-subgraph, and anomalous-edge detection.Examples include sudden egonet changes, dense subtensors formed over short periods, and edge scores based on occurrence, preferential attachment, or mutual neighbors.Source: Related Work · p. 2

Anomalous edge detection

  • Edge-stream methods that output a score per edge are applicable to the task, but the compared methods neither target microclusters nor provide false-positive guarantees.The paper identifies Ranshous et al. (2016) and Eswaran and Faloutsos (2018) as the relevant edge-stream methods.Source: Related Work · p. 2

Problem

The problem is to score incoming edges in a time-evolving graph stream without assuming the vertex set is known in advance. The desired detector finds bursts sharing repeated nodes or edges, offers false-positive control, and maintains constant update time and memory.

Related approaches

  • Table 1 compares relevant edge-stream anomaly-detection approaches.Source: Table 1 · p. 2

Problem definition

  • Each arriving edge is a source, destination, and occurrence-time tuple, and the vertex set may grow during the stream.The example is a network-traffic connection between IP addresses.Source: Problem · p. 2

Problem setting

  • The graph may be directed or a multigraph, and edges may arrive simultaneously.An undirected edge can be represented as two simultaneous directed edges.Source: Problem · p. 2

Desired properties

  • The detector should identify suddenly appearing bursts of activity that share repeated nodes or edges as microclusters.Source: Problem · p. 2
  • For a user-specified probability level, the algorithm should be adjustable to keep false-positive probability at or below that level.The desired guarantees rely on data-distribution assumptions that the authors aim to keep weak.Source: Problem · p. 2
  • Memory use and update time should remain constant as the stream length and graph's node count grow.Source: Problem · p. 2

Proposed Algorithm

The paper presents MIDAS as a streaming hypothesis-testing approach that uses streaming data structures to obtain false-positive probability guarantees.

Overview

  • MIDAS combines streaming data structures with a hypothesis-testing framework to provide false-positive probability guarantees.Source: Overview · p. 3

2. Detection and Guarantees:

MIDAS uses streaming counts and a hypothesis-testing framework to score edge bursts as microcluster anomalies. Its decision procedure bounds false-positive probability, while MIDAS-R extends scoring to temporal and spatial relationships between edges.

2. Detection and Guarantees:

  • MIDAS maintains approximate total and current-tick counts with Count-Min Sketches, resetting the current-count sketch when the stream advances to the next tick.The total-count sketch retains counts across ticks, while the current-count sketch tracks edges in the current tick.Source: Streaming Data Structures · p. 3

MIDAS: Streaming Hypothesis Testing Approach

  • The test uses a chi-squared statistic to compare the current edge count with its expected count under the assumption that the current and past mean edge rates match.The method avoids assuming a particular per-tick distribution or strict stationarity; approximate current and total counts come from Count-Min Sketches.Source: Hypothesis Testing Framework · p. 3, Streaming Data Structures · p. 3

Detection and Guarantees

  • Using the adjusted statistic with the chi-squared 1−ϵ/2 quantile as threshold guarantees a false-positive probability of at most ϵ.The decision procedure combines Count-Min Sketch approximation guarantees with properties of a chi-squared random variable.Source: Detection and Guarantees · p. 4

Incorporating Relations

  • MIDAS-R scores each edge, its source, and its destination, then combines the three scores by taking their maximum to capture spatially related anomalies.It can also give recent edges a diminishing weight by reducing counts by a fixed fraction α at each time tick.Source: Incorporating Relations · pp. 4–5

Time and Memory Complexity

  • Memory is O(wb) and per-update time is O(w), where w and b are the sketch's hash-function and bucket counts.These bounds are independent of data size for memory; all update steps other than sketch operations take constant time.Source: Time and Memory Complexity · p. 5

Experiments

Experiments compare MIDAS and MIDAS-R with SEDANSPOT on dynamic-graph datasets, evaluating accuracy, scalability, and real-world anomaly detection. The reported results show higher accuracy and precision, faster processing, and detection of security-related events and a microcluster missed by SEDANSPOT.

Experimental Setup

  • Experiments use DARPA, TwitterSecurity, and TwitterWorldCup; MIDAS and MIDAS-R use CMS structures, with two hash functions and 2,719 buckets.The reported setup uses ν = 0.001 and sets MIDAS-R's temporal decay factor α to 0.5.Source: Q2. Scalability · p. 5, Experimental Setup · p. 5

Q1. Accuracy

  • MIDAS-R achieves AUC 0.95, a 48% accuracy improvement over the baseline at 215× faster speed; MIDAS achieves AUC 0.91, a 42% improvement at 644× faster speed.The experiments compare against SEDANSPOT on DARPA.Source: Q2. Scalability · p. 5, Figure 2 · p. 6, Figure 3 · p. 6
  • 0.97 average precision is reported for MIDAS-R, 29% more precise than SEDANSPOT; MIDAS scores 0.95 versus the baseline's 0.75.The authors report that both MIDAS variants outperform SEDANSPOT on accuracy and precision metrics.Source: Figure 3 · p. 6, Q1. Accuracy · p. 6

Q2. Scalability

  • MIDAS and MIDAS-R scale linearly with edge count; both process 4M edges within 0.5 second.MIDAS processes 4.4M DARPA edges within 1µs each, while MIDAS-R processes 4.3M within 1µs each.Source: Figure 4 · p. 6, Q2. Scalability · p. 6, Figure 5 · p. 7
  • 162×, 460×, and 644× faster than SEDANSPOT are reported for MIDAS-R on TwitterWorldCup and MIDAS on TwitterWorldCup and DARPA, respectively.On TwitterSecurity, MIDAS-R is 177× faster and MIDAS is 509× faster; on DARPA, MIDAS-R is 215× faster.Source: Q2. Scalability · p. 6, Table 2 · p. 7

Q3. Real-World Effectiveness

  • MIDAS and MIDAS-R anomalies on TwitterSecurity coincide with major world-news events, while SEDANSPOT misses some events and produces high scores unrelated to true events.The daily timeline aggregates edges by taking the maximum anomalousness score per day.Source: Figure 6 · p. 7, Q3. Real-World Effectiveness · p. 7
  • MIDAS-R detects a within-one-day group of suspiciously similar TwitterSecurity edges that SEDANSPOT misses.In the Figure 7 example, single and double edges represent 444 and 888 edges between nodes, respectively.Source: Figure 7 · p. 7, Q3. Real-World Effectiveness · p. 7

Conclusion

The conclusion presents MIDAS and MIDAS-R as streaming detectors for microcluster anomalies, with constant time and memory, false-positive guarantees, and reported accuracy and speed gains.

  • MIDAS detects microcluster anomalies in a streaming approach requiring constant time and memory.Source: Conclusion · p. 7
  • Theorem 1 provides guarantees on MIDAS’s false positive probability.Source: Conclusion · p. 7
  • MIDAS outperforms baseline approaches by 42%-48% accuracy (in terms of AUC) and processes data 162−644 times faster.Source: Conclusion · p. 8

Related papers

Loading 1911.04464v5…