Online score statistics for detecting clustered change in network point processes

Rui Zhang, Haoyun Wang, Yao XieSequential 2023 · DOI

TL;DR

This paper introduces a novel "scan score statistic" for efficiently detecting sudden changes in the behavior of complex event networks, modeled by multivariate Hawkes processes. The method is computationally efficient, doesn't require estimating post-change parameters, and demonstrates strong performance on both simulated and real-world data, including social media trends and stock market events.

What Problem Does This Paper Address?

Detecting "change points" – moments when the underlying patterns in sequential data shift – is crucial in many fields, from finance to public health. When dealing with complex systems like social networks or financial markets, events are not independent; they influence each other over time and space. The multivariate Hawkes process is a powerful model for capturing these interdependencies. However, online (real-time) detection of changes in these complex, interconnected systems is challenging. Traditional methods often struggle with the high dimensionality, temporal dependencies, and the need to estimate unknown parameters of the system after a change occurs, which can be slow and computationally expensive. This paper tackles the problem of efficiently and accurately detecting such changes in network event data in real-time, specifically when the change affects a localized "cluster" within the network.

Methods

The core of this paper is the scan score statistic. This approach leverages score statistics, which are derived from the first-order derivatives of the log-likelihood function. Unlike methods that require estimating unknown post-change parameters (like the Generalized Likelihood Ratio or GLR), score statistics only rely on the pre-change parameters, making them computationally efficient for online detection.

The authors extend this to network data by:

  1. Defining score statistics for each potential interaction (influence) between nodes in the network.
  2. Grouping nodes into "clusters" (subgraphs) and computing aggregated score statistics within these clusters.
  3. Employing a "scanning" strategy: They compute these cluster-specific statistics over time and identify the maximum statistic across all clusters at each time step. This maximum forms the scan score statistic.
  4. Deriving the asymptotic distribution of this scan statistic, which allows for self-normalization and efficient approximation of key performance metrics like the false alarm probability and average run length.
  5. Developing an efficient procedure using importance sampling to accurately calibrate the detection threshold and control the false discovery rate.

Datasets

The paper uses both simulated and real-world datasets for evaluation:

  • Simulated Data: Used to verify theoretical results on the average run length (ARL) and false alarm rate (FAR).
  • Real-world Data:
    • Memetracker Data: Tracks phrases (memes) across websites to study information diffusion. Three specific datasets related to "Barack Obama's election," and the "Summer Olympics in Beijing" were used.
  • Stock Price Data: Closing prices and trading volumes of index-type stocks (SPY, QQQ, DIA, EFA, IWM) were used to construct events representing high/low returns and high trading volume. This created a network of 15 nodes.

Key Insights and Ideas

  • Score Statistics for Efficiency: The paper highlights that score statistics are a powerful tool for online change detection because they bypass the need to estimate unknown post-change parameters, significantly improving computational efficiency.
  • Clustering for Localization: By dividing the network into clusters and computing scan statistics within them, the method can not only detect a change but also potentially localize it to a specific part of the network.
  • Self-Normalization for Robustness: The derived asymptotic distribution of the scan statistic allows for self-normalization, making the detection procedure more robust to variations in the data.
  • Practical Threshold Calibration: The use of importance sampling for determining the detection threshold is a practical contribution, enabling effective control of false alarms and false discoveries.

Key Results

  • Computational Efficiency: The proposed method is significantly faster than traditional GLR methods, as demonstrated in Table 5 (3.789 seconds vs. 20.47-72.97 seconds for processing 50,000 time units).
  • Detection Performance: The method shows good performance in detecting changes in both simulated and real-world datasets. For instance, it successfully detected changes in public opinion related to the "Obama" election and events in the stock market.
  • ARL Verification: Table 2 shows that the approximated ARLs derived from the proposed method align well with simulated ARLs, validating the theoretical framework.
  • False Alarm Control: The method provides a way to control instantaneous false alarm probabilities and false discovery rates, as discussed in Sections 4.2.1 and Appendix A.

Limitations and Future Work

  • Cluster Definition: The performance of the scan statistic can depend on how clusters are defined. In cases where a change occurs on a single edge and clusters don't accurately capture this local topology, the score-based method might perform worse than GLR (as noted in the comparison with GLR in Section 5.1).
  • False Discovery Rate Localization: While the paper discusses controlling the false discovery rate, future work is suggested to provide a more detailed discussion on localizing the unknown change, with some initial results presented in Appendix A.
  • Window Length Choice: Remark 4.2 notes that the choice of window length w is important for detecting smaller changes and can influence the expected detection delay. Further investigation into optimal w selection could be beneficial.

Summary updated

Abstract

AbstractWe consider online monitoring of the network event data to detect local changes in a cluster when the affected data stream distribution shifts from one point process to another with different parameters. Specifically, we are interested in detecting a change point that causes a shift of the underlying data distribution that follows a multivariate Hawkes process with exponential decay temporal kernel, whereby the Hawkes process is considered to account for spatiotemporal correlation between observations. The proposed detection procedure is based on scan score statistics. We derive the asymptotic distribution of the statistic, which enables the self-normalizing property and facilitates the approximation of the instantaneous false alarm probability and the average run length. When detecting a change in the Hawkes process with nonvanishing self-excitation, the procedure does not require estimating the postchange network parameter while assuming the temporal decay parameter, which enjoys computational efficiency. We further present an efficient procedure to accurately determine the false discovery rate via importance sampling, as validated by numerical examples. Using simulated and real stock exchange data, we show the effectiveness of the proposed method in detecting change while enjoying computational efficiency.Keywords: Change point detectiongraph scanning statisticsscore statisticsSUBJECT CLASSIFICATIONS: Primary 62L10Secondary 62G1062G32 ACKNOWLEDGMENTThe authors thank the anonymous referees, an Associate Editor, and the Editor for their constructive comments that improved the quality of this article.DISCLOSUREThe authors have no conflicts of interest to report.Figure A.1. A network with 20 clusters in a line.Display full sizeAdditional informationFundingThis work is partially supported by an NSF CAREER CCF-1650913, and NSF DMS-2134037, CMMI-2015787, CMMI-2112533, DMS-1938106, and DMS-1830210.
BibTeX
@inproceedings{zhang2023online,
  author = {Rui Zhang and Haoyun Wang and Yao Xie},
  title = {{Online score statistics for detecting clustered change in network point processes}},
  booktitle = {Sequential},
  year = {2023},
  doi = {10.1080/07474946.2022.2164307},
}
Figure