  Given a stream of graph edges from a dynamic graph, how can we assign anomaly
scores to edges and subgraphs in an online manner, for the purpose of detecting
unusual behavior, using constant time and memory? For example, in intrusion
detection, existing work seeks to detect either anomalous edges or anomalous
subgraphs, but not both. In this paper, we first extend the count-min sketch
data structure to a higher-order sketch. This higher-order sketch has the
useful property of preserving the dense subgraph structure (dense subgraphs in
the input turn into dense submatrices in the data structure). We then propose 4
online algorithms that utilize this enhanced data structure, which (a) detect
both edge and graph anomalies; (b) process each edge and graph in constant
memory and constant update time per newly arriving edge, and; (c) outperform
state-of-the-art baselines on 4 real-world datasets. Our method is the first
streaming approach that incorporates dense subgraph search to detect graph
anomalies in constant memory and time.
