Sequential change-point detection in high-dimensional Gaussian graphical models

Hossein Keshavarz, George Michailidis, Yves F. AtchadéJMLR 2020

TL;DR

This paper introduces a novel online algorithm for detecting abrupt changes in the structure of high-dimensional Gaussian graphical models (GGMs). This is crucial for real-time monitoring of complex systems like financial markets or sensor networks where relationships between variables can change rapidly. The algorithm offers a computationally efficient and statistically robust way to identify these changes with minimal delay.

What Problem Does This Paper Address?

Many real-world systems, from biological networks to financial markets, involve a large number of interacting variables whose relationships can evolve over time. Gaussian Graphical Models (GGMs) are powerful tools for representing these relationships, where the structure of the model is encoded in the precision matrix (inverse covariance matrix). While methods exist for detecting changes in these structures when all data is available beforehand (offline detection), the challenge of detecting these changes as they happen (online detection) in high-dimensional settings has remained largely unexplored. This is particularly important for applications requiring immediate alerts, such as fraud detection or system failure prediction, where delays can be costly. The paper addresses this gap by proposing a scalable online algorithm that can detect an unknown number of abrupt changes in the GGM's precision matrix with small delay.

Methods

The core of the proposed algorithm lies in comparing the conditional log-likelihood of nodes in the network before and after a potential change. The authors leverage a novel convex barrier function that magnifies deviations from the expected behavior under a stable regime. This function is applied to a test statistic derived from the pseudo-likelihood of the data.

Key methodological contributions include:

  • Sequential Detection: The algorithm processes data in a streaming fashion, making decisions as new observations arrive.
  • Convex Barrier Function: A non-negative, strongly convex function with a root at 1 is used to effectively detect deviations from the null hypothesis (no change). This function is crucial for magnifying the signal of change.
  • Pseudo-likelihood Approach: Instead of directly estimating the precision matrix, which is challenging in high dimensions, the algorithm relies on a pseudo-likelihood derived from conditional log-likelihoods.
  • Batch Updates: For the case where the pre-change precision matrix is unknown, the algorithm employs a mini-batch procedure to update its estimate, balancing computational efficiency with estimation accuracy.
  • Asymptotic Analysis: The paper provides theoretical guarantees for the algorithm's performance, including false alarm rates and detection power, under various conditions on network size, sparsity, and sample size.

Datasets

The paper utilizes both synthetic and real-world datasets for evaluation.

  • Synthetic Data: Generated GGMs with varying parameters (p, dmax, w, β, r, d) are used to test the algorithm's performance under different scenarios of network structure and change types (uniform, rank-r, localized).
  • Real-world Data: Daily log-returns of S&P 500 stocks from 2000-2016 are used to demonstrate the algorithm's applicability to financial time series data. A subset of 100 tickers was randomly chosen for experiments.

Key Insights and Ideas

  • The Power of Pseudo-likelihood for Online Detection: The paper demonstrates that a pseudo-likelihood approach, which is computationally more tractable than full likelihood in high dimensions, can be effectively adapted for online change-point detection in GGMs.
  • Convex Barrier Function as a Change Magnifier: The choice of a specific convex barrier function is critical. It effectively amplifies small deviations from the expected behavior under the null hypothesis, leading to improved detection power.
  • Robustness to Estimation Error: The theoretical analysis shows that the proposed algorithm is robust to small estimation errors in the pre-change precision matrix, a crucial property for practical applications where perfect knowledge is rare.
  • Scalability for High Dimensions: The algorithm is designed to handle high-dimensional networks, a significant challenge in many modern data analysis tasks.

Key Results

  • Theoretical Guarantees: The paper establishes asymptotic guarantees for the false alarm rate (PFA) and miss-detection probability (PMD) of the proposed algorithm, showing that it can achieve desired levels under certain regularity conditions.
  • Empirical Performance:
    • Synthetic Data: Experiments show that the miss-detection rate rapidly decays with increasing signal-to-noise ratio (SNR), window size (w), and network size (p). The algorithm demonstrates good performance across different types of changes (uniform, rank-r, localized).
  • Real-world Data (S&P 500): The algorithm successfully identifies change-points that align with significant market events, such as the 2008 financial crisis and the Ebola virus outbreak, demonstrating its practical utility. The detected changes are shown to correlate with periods of high return volatility.
  • Sensitivity Analysis: The algorithm's performance is found to be relatively insensitive to the choice of burn-in period and update frequency, suggesting its practical applicability.

Limitations and Future Work

  • Assumptions: The theoretical analysis relies on certain regularity conditions, such as the separation of change-points and the sparsity of the network. The paper acknowledges that the performance might be affected when these conditions are violated.
  • Localized Changes: The paper notes that the current approach might struggle to detect changes confined to very small sub-graphs.
  • Non-Gaussian Data: While the paper focuses on Gaussian graphical models, extending the methodology to non-Gaussian random fields (e.g., Ising models) is a promising direction for future research.
  • Optimal Barrier Function: Investigating optimal choices for the barrier function and establishing minimax lower bounds for separability between hypotheses are suggested as future research avenues.
  • Sequential Update of Precision Matrix: Exploring alternative methods for sequentially updating the pre-change precision matrix, such as regularized dual averaging (RDA), is also mentioned as a potential extension.

Summary updated

BibTeX
@article{keshavarz2020sequential,
  author = {Hossein Keshavarz and George Michailidis and Yves F. Atchadé},
  title = {{Sequential change-point detection in high-dimensional Gaussian graphical models}},
  journal = {J. Mach. Learn. Res.},
  year = {2020},
}
Figure