An official website of the United States government
Given a sequence of random graphs, we address the problem of online monitoring and detection of changes in the underlying data distribution. To this end, we adopt the Random Dot Product Graph (RDPG) model which postulates each node has an associated latent vector, and inner products between these vectors dictate the edge formation probabilities. Existing approaches for graph change-point detection (CPD) rely either on extensive computation, or they store and process the entire observed time series. In this paper we consider the cumulative sum of a judicious monitoring function, which quantifies the discrepancy between the streaming graph observations and the nominal model. This reference distribution is inferred via spectral embeddings of the first few graphs in the sequence, and the monitoring function can be updated in an efficient, online fashion. We characterize the distribution of this running statistic, allowing us to select appropriate thresholding parameters that guarantee error-rate control. The end result is a lightweight online CPD algorithm, with a proven capability to flag distribution shifts in the arriving graphs. The novel method is tested on both synthetic and real network data, corroborating its effectiveness in quickly detecting changes in the input graph sequence.
more »
« less
Correlation-aware Online Change Point Detection
Change point detection aims to identify abrupt shifts occurring at multiple points within a data sequence. This task becomes particularly challenging in the online setting, where different types of changes can occur, including shifts in both the marginal and joint distributions of the data. In this paper, we address these challenges by tracking the Riemannian geometry of correlation matrices, allowing Riemannian metrics to compute the geodesic distance as an accurate measure of correlation dynamics. We introduce Rio-CPD, a non-parametric, correlation-aware online change point detection framework that integrates the Riemannian geometry of the manifold of symmetric positive definite matrices with the cumulative sum (CUSUM) statistic for detecting change points. Rio-CPD employs a novel CUSUM design by computing the geodesic distance between current observations and the Fréchet mean of prior observations. With appropriate choices of Riemannian metrics, Rio-CPD offers a simple yet effective and computationally efficient algorithm. Experimental results on both synthetic and real-world datasets demonstrate that Rio-CPD outperforms existing methods on detection accuracy, average detection delay and efficiency.
more »
« less
- Award ID(s):
- 2229876
- PAR ID:
- 10661415
- Publisher / Repository:
- Proceedings of the 34th ACM Conference on Information and Knowledge Management (CIKM’25)
- Date Published:
- Format(s):
- Medium: X
- Location:
- Seoul, Korea
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Change point detection is widely used for finding transitions between states of data generation within a time series. Methods for change point detection currently assume this transition is instantaneous and therefore focus on finding a single point of data to classify as a change point. However, this assumption is flawed because many time series actually display short periods of transitions between different states of data generation. Previous work has shown Bayesian Online Change Point Detection (BOCPD) to be the most effective method for change point detection on a wide range of different time series. This paper explores adapting the change point detection algorithms to detect abrupt changes over short periods of time. We design a segment-based mechanism to examine a window of data points within a time series, rather than a single data point, to determine if the window captures abrupt change. We test our segment-based Bayesian change detection algorithm on 36 different time series and compare it to the original BOCPD algorithm. Our results show that, for some of these 36 time series, the segment-based approach for detecting abrupt changes can much more accurately identify change points based on standard metrics.more » « less
-
We show that compact Riemannian manifolds, regarded as metric spaces with their global geodesic distance, cannot contain a number of rigid structures such as (a) arbitrarily large regular simplices or (b) arbitrarily long sequences of points equidistant from pairs of points preceding them in the sequence. All of this provides evidence that Riemannian metric spaces admit what we term loose embeddings into finite-dimensional Euclidean spaces: continuous maps that preserve both equality as well as inequality. We also prove a local-to-global principle for Riemannian-metric-space loose embeddability: if every finite subspace thereof is loosely embeddable into a common R^N , then the metric space as a whole is loosely embeddable into R^N in a weakened sense.more » « less
-
A brain–computer interface (BCI) provides a direct communication pathway between the human brain and external devices, enabling users to control them through thought. It records brain signals and classifies them into specific commands for external devices. Among various classifiers used in BCI, those directly classifying covariance matrices using Riemannian geometry find broad applications not only in BCI, but also in diverse fields such as computer vision, natural language processing, domain adaption, and remote sensing. However, the existing Riemannian-based methods exhibit limitations, including time-intensive computations, susceptibility to disturbances, and convergence challenges in scenarios involving high-dimensional matrices. In this paper, we tackle these issues by introducing the Bures–Wasserstein (BW) distance for covariance matrices analysis and demonstrating its advantages in BCI applications. Both theoretical and computational aspects of BW distance are investigated, along with algorithms for Fréchet Mean (or barycenter) estimation using BW distance. Extensive simulations are conducted to evaluate the effectiveness, efficiency, and robustness of the BW distance and barycenter. Additionally, by integrating BW barycenter into the Minimum Distance to Riemannian Mean classifier, we showcase its superior classification performance through evaluations on five real datasets.more » « less
-
This paper considers the change point detection problem under dependent samples. In particular, we provide performance guarantees for the MMD-CUSUM test under exponentially α, β, and fast ϕ-mixing processes, which significantly expands its utility beyond the i.i.d. and Markovian cases used in previous studies. We obtain lower bounds for average-run-length (ARL) and upper bounds for average-detection-delay (ADD) in terms of the threshold parameter. We show that the MMD-CUSUM test enjoys the same level of performance as the i.i.d. case under fast ϕ-mixing processes. The MMD-CUSUM test also achieves strong performance under exponentially α/β-mixing processes, which are significantly more relaxed than existing results. The MMD-CUSUM test statistic adapts to different settings without modifications, rendering it a completely data-driven, dependence-agnostic change point detection scheme. Numerical simulations are provided at the end to evaluate our findings.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript
- Conference Paper:
- The DOI is not currently available.
