Spectral CUSUM for Online Network Structure Change Detection

Detecting abrupt changes in the community structure of a network from noisy observations is a fundamental problem in statistics and machine learning. This paper presents an online change detection algorithm called Spectral-CUSUM to detect unknown network structure changes through a generalized likelihood ratio statistic. We characterize the average run length (ARL) and the expected detection delay (EDD) of the Spectral-CUSUM procedure and prove its asymptotic optimality. Finally, we demonstrate the good performance of the Spectral-CUSUM procedure and compare it with several baseline methods using simulations and real data examples on seismic event detection using sensor network data.

Automated summary

This paper proposes an online change detection algorithm called Spectral-CUSUM to detect unknown network structure changes using a generalized likelihood ratio statistic. The average run length (ARL) and the expected detection delay (EDD) of the Spectral-CUSUM procedure are characterized and its asymptotic optimality is proven. Finally, the good performance of the Spectral-CUSUM procedure is demonstrated and compared with several baseline methods on seismic event detection using sensor network data.