A Spectral Framework for Anomalous Subgraph Detection

Abstract—A wide variety of application spaces are concerned with data in the form of relationships or connections between entities, which are commonly represented as graphs. Within these diverse areas, a common problem of interest is the detection of a subset of entities that are anomalous with respect to the rest of the data. While the detection of such anomalous subgraphs has received a substantial amount of attention, no application-agnostic framework exists for analysis of signal detectability in graph-based data. In this paper, we describe a spectral framework that enables such analysis. Leveraging tools from community detection, we show that this framework has natural metrics for signal and noise power, and propose several algo-rithms that leverage these properties. Detection and identification performance are presented for a number of signal and noise models, and the trends observed confirm intuition gleaned from other signal processing areas. We demonstrate the utility of the proposed techniques in detecting small, highly anomalous subgraphs in two real datasets. Index Terms—Graph theory, signal detection theory, spectral analysis, residuals analysis, principal components analysis I