Detecting Activations over Graphs using Spanning Tree Wavelet Bases

James Sharpnack, Aarti Singh, Akshay Krishnamurthy
Proceedings of the Sixteenth International Conference on Artificial Intelligence and Statistics, PMLR 31:536-544, 2013.

Abstract

We consider the detection of clusters of activation over graphs under Gaussian noise. This problem appears in many real world scenarios, such as the detecting contamination or seismic activity by sensor networks, viruses in human and computer networks, and groups with anomalous behavior in social and biological networks. Despite the wide applicability of such a detection algorithm, there has been little success in the development of computationally feasible methods with provable theoretical guarantees. To this end, we introduce the spanning tree wavelet basis over a graph, a localized basis that reflects the topology of the graph. We first provide a necessary condition for asymptotic distinguishability of the null and alternative hypotheses. Then we prove that for any spanning tree, we can hope to correctly detect signals in a low signal-to-noise regime using spanning tree wavelets. We propose a randomized test, in which we use a uniform spanning tree in the basis construction. Using electrical network theory, we show that the uniform spanning tree provides strong guarantees that in many cases match our necessary condition. We prove that for edge transitive graphs, k-nearest neighbor graphs, and ε-graphs we obtain nearly optimal performance with the uniform spanning tree wavelet detector.

Cite this Paper

BibTeX
@InProceedings{pmlr-v31-sharpnack13a, title = {Detecting Activations over Graphs using Spanning Tree Wavelet Bases}, author = {Sharpnack, James and Singh, Aarti and Krishnamurthy, Akshay}, booktitle = {Proceedings of the Sixteenth International Conference on Artificial Intelligence and Statistics}, pages = {536--544}, year = {2013}, editor = {Carvalho, Carlos M. and Ravikumar, Pradeep}, volume = {31}, series = {Proceedings of Machine Learning Research}, address = {Scottsdale, Arizona, USA}, month = {29 Apr--01 May}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v31/sharpnack13a.pdf}, url = {https://proceedings.mlr.press/v31/sharpnack13a.html}, abstract = {We consider the detection of clusters of activation over graphs under Gaussian noise. This problem appears in many real world scenarios, such as the detecting contamination or seismic activity by sensor networks, viruses in human and computer networks, and groups with anomalous behavior in social and biological networks. Despite the wide applicability of such a detection algorithm, there has been little success in the development of computationally feasible methods with provable theoretical guarantees. To this end, we introduce the spanning tree wavelet basis over a graph, a localized basis that reflects the topology of the graph. We first provide a necessary condition for asymptotic distinguishability of the null and alternative hypotheses. Then we prove that for any spanning tree, we can hope to correctly detect signals in a low signal-to-noise regime using spanning tree wavelets. We propose a randomized test, in which we use a uniform spanning tree in the basis construction. Using electrical network theory, we show that the uniform spanning tree provides strong guarantees that in many cases match our necessary condition. We prove that for edge transitive graphs, k-nearest neighbor graphs, and ε-graphs we obtain nearly optimal performance with the uniform spanning tree wavelet detector.} }
Endnote
%0 Conference Paper %T Detecting Activations over Graphs using Spanning Tree Wavelet Bases %A James Sharpnack %A Aarti Singh %A Akshay Krishnamurthy %B Proceedings of the Sixteenth International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2013 %E Carlos M. Carvalho %E Pradeep Ravikumar %F pmlr-v31-sharpnack13a %I PMLR %P 536--544 %U https://proceedings.mlr.press/v31/sharpnack13a.html %V 31 %X We consider the detection of clusters of activation over graphs under Gaussian noise. This problem appears in many real world scenarios, such as the detecting contamination or seismic activity by sensor networks, viruses in human and computer networks, and groups with anomalous behavior in social and biological networks. Despite the wide applicability of such a detection algorithm, there has been little success in the development of computationally feasible methods with provable theoretical guarantees. To this end, we introduce the spanning tree wavelet basis over a graph, a localized basis that reflects the topology of the graph. We first provide a necessary condition for asymptotic distinguishability of the null and alternative hypotheses. Then we prove that for any spanning tree, we can hope to correctly detect signals in a low signal-to-noise regime using spanning tree wavelets. We propose a randomized test, in which we use a uniform spanning tree in the basis construction. Using electrical network theory, we show that the uniform spanning tree provides strong guarantees that in many cases match our necessary condition. We prove that for edge transitive graphs, k-nearest neighbor graphs, and ε-graphs we obtain nearly optimal performance with the uniform spanning tree wavelet detector.
RIS
TY - CPAPER TI - Detecting Activations over Graphs using Spanning Tree Wavelet Bases AU - James Sharpnack AU - Aarti Singh AU - Akshay Krishnamurthy BT - Proceedings of the Sixteenth International Conference on Artificial Intelligence and Statistics DA - 2013/04/29 ED - Carlos M. Carvalho ED - Pradeep Ravikumar ID - pmlr-v31-sharpnack13a PB - PMLR DP - Proceedings of Machine Learning Research VL - 31 SP - 536 EP - 544 L1 - http://proceedings.mlr.press/v31/sharpnack13a.pdf UR - https://proceedings.mlr.press/v31/sharpnack13a.html AB - We consider the detection of clusters of activation over graphs under Gaussian noise. This problem appears in many real world scenarios, such as the detecting contamination or seismic activity by sensor networks, viruses in human and computer networks, and groups with anomalous behavior in social and biological networks. Despite the wide applicability of such a detection algorithm, there has been little success in the development of computationally feasible methods with provable theoretical guarantees. To this end, we introduce the spanning tree wavelet basis over a graph, a localized basis that reflects the topology of the graph. We first provide a necessary condition for asymptotic distinguishability of the null and alternative hypotheses. Then we prove that for any spanning tree, we can hope to correctly detect signals in a low signal-to-noise regime using spanning tree wavelets. We propose a randomized test, in which we use a uniform spanning tree in the basis construction. Using electrical network theory, we show that the uniform spanning tree provides strong guarantees that in many cases match our necessary condition. We prove that for edge transitive graphs, k-nearest neighbor graphs, and ε-graphs we obtain nearly optimal performance with the uniform spanning tree wavelet detector. ER -
APA
Sharpnack, J., Singh, A. & Krishnamurthy, A.. (2013). Detecting Activations over Graphs using Spanning Tree Wavelet Bases. Proceedings of the Sixteenth International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 31:536-544 Available from https://proceedings.mlr.press/v31/sharpnack13a.html.

Related Material