Subgraph detection using graph signals

In this paper we develop statistical detection theory for graph signals. In particular, given two graphs, namely, a background graph that represents an usual activity and an alternative graph that represents some unusual activity, we are interested in answering the following question: To which of the two graphs does the observed graph signal fit the best? To begin with, we assume both the graphs are known, and derive an optimal Neyman-Pearson detector. Next, we derive a suboptimal detector for the case when the alternative graph is not known. The developed theory is illustrated with numerical experiments.

I. Introduction

Graphs are mathematical objects that may be used to explain relationships among datasets. Vertices of the graph represent different elements of the dataset, whereas the edges of the graph explain the dependence between these elements. Some examples of such graph-structured data include transportation networks, gene networks, brain networks, social networks, to name a few. Processing signals supported on graphs is an emerging area of research [1], [2] that has recently received a lot of attention.