Matched filtering for subgraph detection in dynamic networks

Graphs are high-dimensional, non-Euclidean data, whose utility spans a wide variety of disciplines. While their non-Euclidean nature complicates the application of traditional signal processing paradigms, it is desirable to seek an analogous detection framework. In this paper we present a matched filtering method for graph se-quences, extending to a dynamic setting a previous method for the detection of anomalously dense subgraphs in a large background. In simulation, we show that this temporal integration technique enables the detection of weak subgraph anomalies than are not detectable in the static case. We also demonstrate background/foreground separa-tion using a real background graph based on a computer network. Index Terms — community detection, dynamic graphs, graph al-gorithms, matched filtering, signal detection theory 1