Asymptotic Distribution-Free Change-Point Detection for Modern Data Based on a New Ranking Scheme

Doudou Zhou, Hao ChenIEEE Trans. Information Theory 2025 · DOI

TL;DR

This paper introduces RING-CPD, a novel method for detecting changes in data distributions, particularly effective for complex, high-dimensional, and non-Euclidean data. By leveraging graph-induced ranks, RING-CPD offers a robust and asymptotically distribution-free approach, overcoming limitations of existing methods that struggle with heavy-tailed data and outliers.

What Problem Does This Paper Address?

Identifying shifts in data distributions, known as change-point detection (CPD), is crucial across many fields, from finance to healthcare. While traditional methods work well for simple, low-dimensional data, they falter when faced with modern datasets characterized by high dimensionality or complex structures like networks. Existing nonparametric methods, though more robust, often require strong assumptions about data moments (like the existence of a second moment, which is violated by heavy-tailed data) or are computationally intensive. This paper aims to bridge this gap by developing a robust, efficient, and assumption-free method for change-point detection in these challenging modern data scenarios.

Methods

The core innovation of RING-CPD lies in its use of graph-induced ranks. Instead of directly using raw data or distances, the method first constructs a sequence of similarity graphs (e.g., k-Nearest Neighbor Graphs or k-Minimum Spanning Trees) based on pairwise similarities between observations. These graphs are then used to define a graph-induced rank matrix. This matrix captures similarity information in a way that is more robust to outliers and heavy-tailed distributions than direct distance measures.

The method then derives scan statistics based on this rank matrix. These statistics are designed to detect deviations from the null hypothesis of no change. A key theoretical contribution is proving that these scan statistics are asymptotically distribution-free under the null hypothesis. This means that their behavior can be approximated without needing to know the exact underlying data distribution, simplifying their practical application. The paper also provides analytic approximations for tail probabilities, enabling Type-I error control.

Datasets

The paper evaluates RING-CPD on several real-world datasets:

  • Functional connectivity network dataset: Used for detecting seizures, where functional connectivity networks are represented as weighted graphs.
  • Digit images dataset (MNIST): Used to test the method's performance on non-Euclidean data by differentiating similar digit pairs.
  • New York City Taxi dataset: Utilized for detecting changes in travel patterns, where daily taxi trip data is represented using kernel density estimation.

The paper does not introduce new benchmark datasets but rather applies its method to existing, well-known datasets to demonstrate its practical utility.

Key Insights and Ideas

  • Ranks are powerful for robustness: By shifting from direct distances to ranks derived from similarity graphs, the method gains significant robustness against heavy-tailed distributions and outliers, which are common in real-world data.
  • Graphs unlock high-dimensional and non-Euclidean data: The graph-based approach naturally handles data structures that are difficult for traditional methods, such as networks and high-dimensional feature spaces.
  • Asymptotic distribution-free property is key: This theoretical guarantee simplifies the application of the method, as practitioners don't need to estimate complex nuisance parameters related to the data distribution.
  • k-NNG and k-MST are flexible graph choices: The method's performance is evaluated using different graph constructions, showing its adaptability. The paper also discusses the impact of the parameter 'k' (number of neighbors or MSTs) on performance.

Key Results

  • Strong performance in simulations: RING-CPD consistently outperforms or matches existing methods (like GET, MET, SWR, DM, ED, C2N, S3) across various scenarios, including light-tailed, heavy-tailed, and mixed distributions, and for different types of changes (location, scale, mixed). It shows particular strength in detecting changes in heavy-tailed distributions.
  • Effective on real-world data: The method successfully identifies seizures in functional connectivity data, detects changes in MNIST digit images, and pinpoints significant shifts in NYC taxi travel patterns, often aligning with known events like holidays or breaks.
  • Robustness to outliers and heavy tails: Empirical results demonstrate that RING-CPD maintains good power even when data is contaminated with outliers or follows heavy-tailed distributions, a significant advantage over many distance-based methods.
  • Computational efficiency: While not the primary focus, the paper notes that graph construction can be computationally intensive, but efficient algorithms exist, and the rank-based approach avoids some of the pitfalls of direct distance calculations in high dimensions.

Limitations and Future Work

  • Choice of 'k': The optimal choice of 'k' for graph construction remains an open question. While the paper suggests a data-driven approach, further research is needed to formalize this.
  • Theoretical assumptions: The theoretical guarantees rely on certain conditions on the similarity graph (Conditions 1-6). While these are shown to hold for common graph types, their strict verification for all possible graphs is complex.
  • Extension to kernel/distance weighting: The paper proposes extending the method to directly use kernel values or distances (KING-CPD, DING-CPD) instead of ranks, which could offer different trade-offs and is a promising avenue for future research.
  • Further theoretical analysis: The paper mentions that the analytical approximations of tail probabilities can be improved by skewness correction, and further work could explore more refined approximations.

Summary updated

BibTeX
@article{zhou2025asymptotic,
  author = {Doudou Zhou and Hao Chen},
  title = {{Asymptotic Distribution-Free Change-Point Detection for Modern Data Based on a New Ranking Scheme}},
  journal = {IEEE Trans. Information Theory},
  year = {2025},
  doi = {10.1109/tit.2025.3575858},
}
Figure