Detecting Activations over Graphs using Spanning Tree Wavelet Bases
This addresses a computationally feasible detection method with theoretical guarantees for general graph topologies, which is incremental as it builds on existing graph signal processing but offers new randomized tests.
The paper tackles the problem of detecting piecewise constant activations on graphs under Gaussian noise, providing a universal necessary condition for distinguishability and introducing a spanning tree wavelet basis that achieves near-optimal performance in low signal-to-noise regimes for various graph types.
We consider the detection of activations over graphs under Gaussian noise, where signals are piece-wise constant over the graph. Despite the wide applicability of such a detection algorithm, there has been little success in the development of computationally feasible methods with proveable theoretical guarantees for general graph topologies. We cast this as a hypothesis testing problem, and first provide a universal necessary condition for asymptotic distinguishability of the null and alternative hypotheses. We then introduce the spanning tree wavelet basis over graphs, a localized basis that reflects the topology of the graph, and prove that for any spanning tree, this approach can distinguish null from alternative in a low signal-to-noise regime. Lastly, we improve on this result and show that using the uniform spanning tree in the basis construction yields a randomized test with stronger theoretical guarantees that in many cases matches our necessary conditions. Specifically, we obtain near-optimal performance in edge transitive graphs, $k$-nearest neighbor graphs, and $ε$-graphs.