Anomaly detection for random graphs using distributions of vertex invariants

Anomaly detection is a longstanding problem with many applications in signal processing. We consider anomaly detection on graphs, a subject which has not previously had treatment in such depth. Our approach is inspired largely by previous work, where anomaly detection in an acoustic signal is accomplished by measuring and comparing the distribution of localized measurements to those available from a non-anomalous signal. In similar spirit, we proceed by comparing distributions of vertex invariants to those obtained from non-anomalous graphs. Specifically, we consider homogeneous Erdös-Rényi random graphs (where each vertex is connected independently with equal probability p) to be non-anomalous, and compare them to four classes of heterogeneous alternatives (where a subset of the vertices are connected according to a different process). Our contributions are (1) a novel method of incorporating information from vertex invariants for anomaly detection on graphs, (2) a principled approach to fusing information from an arbitrary number of such statistics, and (3) evaluation on several types of anomalous graphs. We demonstrate superior performance to available state-of-the-art approaches against the specific type of anomalies optimized for, and further demonstrate superior generalization to an entire class of anomalies.