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:
- Defining score statistics for each potential interaction (influence) between nodes in the network.
- Grouping nodes into "clusters" (subgraphs) and computing aggregated score statistics within these clusters.
- 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.
- 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.
- 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
wis important for detecting smaller changes and can influence the expected detection delay. Further investigation into optimalwselection could be beneficial.
Summary updated