Changepoint Detection over Graphs with the Spectral Scan Statistic

James Sharpnack, Aarti Singh, Alessandro Rinaldo
Proceedings of the Sixteenth International Conference on Artificial Intelligence and Statistics, PMLR 31:545-553, 2013.

Abstract

We consider the change-point detection problem of deciding, based on noisy measurements, whether an unknown signal over a given graph is constant or is instead piecewise constant over two induced subgraphs of relatively low cut size. We analyze the corresponding generalized likelihood ratio (GLR) statistic and relate it to the problem of finding a sparsest cut in a graph. We develop a tractable relaxation of the GLR statistic based on the combinatorial Laplacian of the graph, which we call the spectral 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 few graph topologies. Finally, we demonstrate both theoretically and by simulations that the spectral scan statistic can outperform naive testing procedures based on edge thresholding and χ^2 testing.

Cite this Paper

BibTeX
@InProceedings{pmlr-v31-sharpnack13b, title = {Changepoint Detection over Graphs with the Spectral Scan Statistic}, author = {Sharpnack, James and Singh, Aarti and Rinaldo, Alessandro}, booktitle = {Proceedings of the Sixteenth International Conference on Artificial Intelligence and Statistics}, pages = {545--553}, 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/sharpnack13b.pdf}, url = {https://proceedings.mlr.press/v31/sharpnack13b.html}, abstract = {We consider the change-point detection problem of deciding, based on noisy measurements, whether an unknown signal over a given graph is constant or is instead piecewise constant over two induced subgraphs of relatively low cut size. We analyze the corresponding generalized likelihood ratio (GLR) statistic and relate it to the problem of finding a sparsest cut in a graph. We develop a tractable relaxation of the GLR statistic based on the combinatorial Laplacian of the graph, which we call the spectral 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 few graph topologies. Finally, we demonstrate both theoretically and by simulations that the spectral scan statistic can outperform naive testing procedures based on edge thresholding and χ^2 testing.} }
Endnote
%0 Conference Paper %T Changepoint Detection over Graphs with the Spectral Scan Statistic %A James Sharpnack %A Aarti Singh %A Alessandro Rinaldo %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-sharpnack13b %I PMLR %P 545--553 %U https://proceedings.mlr.press/v31/sharpnack13b.html %V 31 %X We consider the change-point detection problem of deciding, based on noisy measurements, whether an unknown signal over a given graph is constant or is instead piecewise constant over two induced subgraphs of relatively low cut size. We analyze the corresponding generalized likelihood ratio (GLR) statistic and relate it to the problem of finding a sparsest cut in a graph. We develop a tractable relaxation of the GLR statistic based on the combinatorial Laplacian of the graph, which we call the spectral 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 few graph topologies. Finally, we demonstrate both theoretically and by simulations that the spectral scan statistic can outperform naive testing procedures based on edge thresholding and χ^2 testing.
RIS
TY - CPAPER TI - Changepoint Detection over Graphs with the Spectral Scan Statistic AU - James Sharpnack AU - Aarti Singh AU - Alessandro Rinaldo 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-sharpnack13b PB - PMLR DP - Proceedings of Machine Learning Research VL - 31 SP - 545 EP - 553 L1 - http://proceedings.mlr.press/v31/sharpnack13b.pdf UR - https://proceedings.mlr.press/v31/sharpnack13b.html AB - We consider the change-point detection problem of deciding, based on noisy measurements, whether an unknown signal over a given graph is constant or is instead piecewise constant over two induced subgraphs of relatively low cut size. We analyze the corresponding generalized likelihood ratio (GLR) statistic and relate it to the problem of finding a sparsest cut in a graph. We develop a tractable relaxation of the GLR statistic based on the combinatorial Laplacian of the graph, which we call the spectral 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 few graph topologies. Finally, we demonstrate both theoretically and by simulations that the spectral scan statistic can outperform naive testing procedures based on edge thresholding and χ^2 testing. ER -
APA
Sharpnack, J., Singh, A. & Rinaldo, A.. (2013). Changepoint Detection over Graphs with the Spectral Scan Statistic. Proceedings of the Sixteenth International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 31:545-553 Available from https://proceedings.mlr.press/v31/sharpnack13b.html.

Related Material