Hubness Change Point Detection

Ikumi Suzuki, Kazuo Hara, Eiji MurakamiAAAI 2025 · DOI

Introduction

Change point detection (CPD) is a critical task in time-series analysis, aimed at identifying the exact moments when the underlying distribution of a signal changes. Applications range from industrial fault detection to environmental monitoring. Traditional CPD methods are often categorized into model-based approaches, which assume a specific data distribution, and model-free approaches, which compare data windows directly. However, many existing model-free methods suffer from high computational costs or struggle with high-dimensional data due to "hubness"—a phenomenon where certain points become disproportionately frequent nearest neighbors, distorting similarity metrics.

This paper, presented at AAAI-25, introduces Hub-CPD, a novel model-free algorithm that leverages hubness as a diagnostic tool rather than a nuisance. By measuring the effectiveness of hubness-suppression techniques, Hub-CPD identifies distribution shifts with high accuracy and efficiency.

Methodology: Residual Normalization and the Rayleigh Score

The core of Hub-CPD is a three-step process designed to transform time-series data into a geometric signal of change.

  1. Preprocessing: Raw time-series data is transformed into high-dimensional vectors using a sliding window approach (Hankel matrix).
  2. Residual Normalization (ResNorm): Given two datasets $D$ and $D'$ (representing "before" and "after" windows), the algorithm finds the $k$-nearest neighbors in $D'$ for each point in $D$. It calculates a local centroid and computes a residual vector, which is then normalized to unit length.
  3. Uniformity Testing: If $D$ and $D'$ share the same distribution, the normalized residuals should be uniformly distributed on a unit hyper-sphere. Hub-CPD uses the Rayleigh score—the norm of the mean of these vectors—to quantify this. A low score suggests uniformity (no change), while a high score indicates clustering (a distribution shift).
Visualization of Residual Normalization (ResNorm) for different distribution shifts.

As shown in the figure above, when a significant difference exists between datasets ($diff=1.0$), the normalized residuals cluster, leading to a higher Rayleigh score. Conversely, when distributions are identical ($diff=0.0$), the points spread out uniformly. This process can be iterated ($r$ times) to amplify subtle differences.

Experimental Results

The authors evaluated Hub-CPD against state-of-the-art methods like RuLSIF and KL-CPD across synthetic and real-world datasets, including hydraulic system and gas sensor data.

Sensitivity and Accuracy

Hub-CPD demonstrates high sensitivity to both mean shifts ($\mu$) and variance shifts ($\sigma$). The Rayleigh score increases monotonically as the magnitude of the shift grows, providing a clear signal for detection.

Rayleigh score sensitivity to shifts in mean ($\mu$) and standard deviation ($\sigma$).

In real-world tests on gas sensor data, Hub-CPD achieved a state-of-the-art average AUC of 0.952. Its performance was particularly robust on heavy-tailed distributions (e.g., t-distributions), where the local normalization step effectively mitigated the impact of outliers.

Computational Efficiency

One of the most striking advantages of Hub-CPD is its speed. In benchmarks using hydraulic system data, Hub-CPD processed the signal in approximately 0.5 seconds, whereas the popular KL-CPD method required over 212 seconds. This efficiency makes it highly suitable for real-time monitoring applications.

Conclusion and Future Work

Hub-CPD represents a paradigm shift in high-dimensional CPD by utilizing the geometry of hubness to detect distribution changes. While the method is highly effective, its performance is sensitive to hyperparameters such as the number of neighbors ($k$) and the number of iterations ($r$). Future research will focus on automating the selection of these parameters to enhance the algorithm's robustness across diverse data types.

Summary updated

BibTeX
@inproceedings{suzuki2025hubness,
  author = {Ikumi Suzuki and Kazuo Hara and Eiji Murakami},
  title = {{Hubness Change Point Detection}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.1609/aaai.v39i12.33376},
}
Figure