Matched filtering for subgraph detection in dynamic networks
June 28, 2011
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 sequences, 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 separation using a real background graph based on a computer network.