Abstract
The advantage of graph-based anomaly detection is that the relationships between elements can be analyzed for structural oddities that could represent activities such as fraud, network intrusions, or suspicious associations in a social network. Traditionally, methods for discovering anomalies have ignored information about the relationships between people, e.g., who they know, or who they call. One approach to handling such data is to use a graph representation and detect normative patterns and anomalies in the graph. However, current approaches to detecting anomalies in graphs are computationally expensive and do not scale to large graphs. In this work, we describe methods for scalable graph-based anomaly detection via graph partitioning and windowing, and demonstrate its ability to efficiently detect anomalies in data represented as a graph.