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.

通过对给定图每个顶点进行单一噪声测量，利用基于罕见激活点的聚类位置的本地化信号来检测信号是否恒定或是否存在罕见激活点，找到稀疏切割等问题。我们开发了图傅里叶扫描统计量作为一个可行的放松器来处理 GLR 统计量，并进行了性质分析。在理论和模拟方面证明了图傅里叶扫描统计量优于全局平均和基于顶点门限值的 Naïve 测试程序的实用性