Papers › SEDANSPOT: Detecting Anomalies in Edge Streams
SEDANSPOT: Detecting Anomalies in Edge Streams
Dhivya Eswaran, Christos Faloutsos
Given a stream of edges from a time-evolving (un)weighted (un)directed graph, we consider the problem of detecting anomalous edges in near real-time using sublinear memory. We propose SEDANSPOT, a principled randomized algorithm, which exploits two tell-tale signs of anomalous edges: they tend to (i) occur as bursts of activity and (ii) connect parts of the graph which are sparsely connected. SEDANSPOT has the following desirable properties: (a) Burst resistance: It provably downsamples edges from bursty periods of network traffic, (b) Holistic scoring: It takes into account the whole (sampled) graph while scoring the anomalousness of an edge, giving diminishing importance to far-away neighbors, (c) Efficiency: It supports fast updates and scoring and hence can be efficiently maintained over stream; further, it can detect anomalous edges in sublinear space and constant time per edge. Through experiments on real-world data, we demonstrate that SEDANSPOT is 3× faster and 270% more accurate (in terms of AUC) than the state-of-the-art.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Tasks
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections