Subgraph detection using eigenvector L1 norms

When working with network datasets, the theoretical framework of detection the-ory for Euclidean vector spaces no longer applies. Nevertheless, it is desirable to determine the detectability of small, anomalous graphs embedded into background networks with known statistical properties. Casting the problem of subgraph de-tection in a signal processing context, this article provides a framework and empir-ical results that elucidate a “detection theory ” for graph-valued data. Its focus is the detection of anomalies in unweighted, undirected graphs throughL1 properties of the eigenvectors of the graph’s so-called modularity matrix. This metric is ob-served to have relatively low variance for certain categories of randomly-generated graphs, and to reveal the presence of an anomalous subgraph with reasonable re-liability when the anomaly is not well-correlated with stronger portions of the background graph. An analysis of subgraphs in real network datasets confirms the efficacy of this approach.