  We consider the problem of deciding, based on a single noisy measurement at
each vertex of a given graph, whether the underlying unknown signal is constant
over the graph or there exists a cluster of vertices with anomalous activation.
This problem is relevant to several applications such as surveillance, disease
outbreak detection, biomedical imaging, environmental monitoring, etc. Since
the activations in these problems often tend to be localized to small groups of
vertices in the graphs, we model such activity by a class of signals that are
supported over a (possibly disconnected) cluster with low cut size relative to
its size. We analyze the corresponding generalized likelihood ratio (GLR)
statistics and relate it to the problem of finding a sparsest cut in the graph.
We develop a tractable relaxation of the GLR statistic based on the
combinatorial Laplacian of the graph, which we call the graph Fourier scan
statistic, and analyze its properties. We show how its performance as a testing
procedure depends directly on the spectrum of the graph, and use this result to
explicitly derive its asymptotic properties on a few significant graph
topologies. Finally, we demonstrate theoretically and with simulations that the
graph Fourier scan statistic can outperform naive testing procedures based on
global averaging and vertex-wise thresholding. We also demonstrate the
usefulness of the GFSS by analyzing groundwater Arsenic concentrations from a
U.S. Geological Survey dataset.
