📊 statistics

Change-Point Detection With Multivariate Repeated Measures

This paper proposes a new graph-based method for detecting change-points in high-dimensional nonparametric data with repeated measurements or local group structures by effectively integrating both within- and between-individual information, while providing analytical significance approximations and establishing statistical consistency.

Original authors: Serim Han, Jingru Zhang, Hoseung Song

Published 2026-09-11

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Serim Han, Jingru Zhang, Hoseung Song

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the vast, noisy stream of data that defines modern life, from the rhythm of a heartbeat to the flow of traffic through a city, there are moments when the underlying pattern suddenly shifts. Scientists call these moments change-points. Identifying them is crucial because a shift in the data often signals a real-world event: a disease outbreak, a change in climate, or a sudden alteration in human behavior. For decades, researchers have developed tools to spot these shifts, but most of these tools were built for simple, single-line data or for situations where each observation stands alone. They struggle when data comes in clusters, such as when a single person is measured repeatedly over time, or when groups of observations are tightly linked to one another. In these complex scenarios, the standard approach has been to flatten the data, averaging out the repeated measurements into a single number. While this simplifies the math, it often throws away the very details that matter most—the subtle variations within the group that signal a change is happening.

A team of researchers has now developed a new method to find these hidden shifts without losing the rich detail of repeated measurements. Published in a paper by Serim Han, Jingru Zhang, and Hoseung Song, the work introduces a graph-based technique that treats data like a map of connections rather than a list of numbers. Instead of averaging out the repeated observations, the new method looks at how the individual measurements relate to one another both within a single person and between different people. Imagine a forest where you are trying to detect a change in the ecosystem. The old way might involve counting the average number of leaves on a tree and ignoring the specific branches. The new approach, however, maps the connections between every single leaf, noticing when the pattern of how leaves touch or cluster together changes, even if the total leaf count remains the same. By building a network that respects the natural grouping of the data, the researchers created a test that can spot changes driven by shifts in the average, shifts in the spread of the data, or shifts in the internal structure of the groups themselves.

The researchers tested their method against a wide variety of simulated scenarios, including data that looked like random noise, data with sudden jumps in location, and data where the variability within groups changed. They compared their new tool to several existing methods, including those that rely on machine learning and others that use distance measurements. The results showed that while existing methods were good at finding changes between different people, they often failed completely when the change happened within the repeated measurements of a single person. The new method, however, successfully detected these internal shifts with high accuracy. It performed just as well as the best existing tools when the changes occurred between people, proving that it is a versatile tool that does not sacrifice one type of detection for another. The team also developed a way to calculate the statistical significance of their findings without needing to run thousands of slow computer simulations, making the method fast enough to handle very large datasets.

To see if the method worked in the real world, the authors applied it to a massive dataset of taxi trips in New York City. They looked at daily drop-off counts across a grid of the city over a period of more than a year, treating each day as a repeated measurement within a weekly cycle. The new method identified four distinct periods where the taxi patterns changed significantly. These changes aligned perfectly with major holidays and seasonal events: the Lunar New Year in early February, Spring Break in late March, Halloween in late October, and Christmas in mid-December. Other methods used for comparison missed some of these events or only detected changes during specific seasons. The new approach was able to pinpoint the exact weeks when the city's rhythm shifted, demonstrating its ability to find meaningful signals in complex, real-world data.

The study also established that the method is mathematically sound, proving that as the amount of data grows, the method becomes increasingly reliable at finding the true moment of change. The researchers showed that their estimates of where the change occurred converge on the actual location, giving confidence that the tool is not just finding random noise. By preserving the structure of repeated measurements and using a network of connections to detect shifts, this new framework offers a more complete picture of how data changes over time. It allows scientists to see not just that something has changed, but how the internal relationships within the data have shifted, opening the door to more accurate detection in fields ranging from healthcare monitoring to environmental science.

Technical Summary: Change-Point Detection With Multivariate Repeated Measures

Problem Statement
Change-point detection (CPD) in high-dimensional, nonparametric settings has seen significant advances through graph-based methods. However, existing literature largely overlooks data structures involving repeated measurements or local group dependencies. In many real-world applications, such as healthcare monitoring or longitudinal studies, observations are collected as sequences of repeated measures for each individual (e.g., $\ell$ measurements per time point $i$ ). Standard approaches typically either average these repeated measures, risking the loss of within-individual variability, or treat them as independent features, ignoring their inherent correlation. Consequently, standard CPD methods often fail to detect meaningful signals arising specifically from changes in local structures or within-individual patterns.

Methodology
The authors propose a novel graph-based framework designed to detect change-points in sequences with repeated measurements by simultaneously leveraging within-individual and between-individual information.

Graph Construction: The method constructs a similarity graph $G$ (specifically a 9-MST) on all $n \times \ell$ observations. This graph is decomposed into two disjoint subgraphs:
- $G_{out}$ : Edges connecting nodes from different individuals.
- $G_{in}$ : Edges connecting nodes belonging to the same individual.
Test Statistics: The authors define three scan statistics based on edge counts within these subgraphs:
- $Z_{out, w}(t)$ : A weighted statistic sensitive to location shifts in between-individual connectivity.
- $Z_{out, d}(t)$ : A difference statistic sensitive to scale changes in between-individual connectivity.
- $Z_{in}(t)$ : A statistic capturing changes in within-individual connectivity.
Orthogonalization and Combination: To address the correlation between $Z_{out, d}(t)$ and $Z_{in}(t)$ , the authors construct an orthogonalized within-individual statistic, $\tilde{Z}_{in}(t)$ , which removes the linear dependence on $Z_{out, d}(t)$ . The final test statistic is a max-type combination:
$M(t) = \max \{ Z_{out, w}(t), |Z_{out, d}(t)|, |\tilde{Z}_{in}(t)| \}$
The scan statistic is the maximum of $M(t)$ over a specified window.
Inference and Asymptotics:
- Analytical Approximations: Instead of relying solely on computationally expensive permutation tests, the authors derive the limiting distributions of the scan statistics as Gaussian processes. They provide analytical approximations for $p$ -values using Woodroofe's and Siegmund's methods.
- Skewness Correction: To improve accuracy, particularly near the boundaries of the sequence or in high-dimensional settings where convergence to normality is slow, the authors apply a skewness correction to the tail probability approximations.
- Consistency: The paper establishes the consistency of the proposed test and the convergence of the estimated change-point location to the true location under fixed change-point alternatives.

Key Results
The performance of the proposed method (denoted as $M$ ) was evaluated through extensive simulations and a real-world data analysis:

Simulation Studies: The method was tested against generalized edge-count methods ( $S_b$ ), Fréchet change-point detection, and machine learning-based approaches (changeforest, changekNN) under multivariate Gaussian, log-normal, and Gaussian mixture distributions.
- Within-Individual Changes: The proposed method $M$ consistently detected changes driven by within-individual differences (Setting 2), a scenario where competing methods (including those aggregating data or treating measures as independent) largely failed.
- Between-Individual Changes: $M$ remained competitive with state-of-the-art methods in detecting between-individual location and scale changes.
- Robustness: The method maintained high power across various dimensions ( $d=40, 50$ ) and change-point locations (centered and off-center).
Real Data Application: The method was applied to New York City taxi trip data (JFK pickups), treating daily drop-off counts as repeated measurements within 60 weekly observations.
- The proposed test identified four significant change-points corresponding to major events: Lunar New Year, Spring Break, Halloween, and Christmas.
- Competing methods detected fewer of these events or identified changes only in specific seasonal periods, whereas $M$ successfully captured the full spectrum of structural changes by utilizing both within-week and between-week variations.

Significance and Claims
The paper claims that the proposed method offers a significant advancement by effectively utilizing the full information structure in repeated measurement data. Its primary contributions are:

Novelty: It extends the framework of graph-based statistics with repeated measures introduced by Zhang et al. (2022) to the change-point detection scenario, explicitly combining within-individual and between-individual information to detect change-points in repeated measures.
Efficiency: By deriving analytical $p$ -value approximations with skewness correction, the method enables efficient computation for large datasets without the prohibitive cost of permutation testing.
Power: The method demonstrates superior power in detecting changes driven by local group structures (within-individual variability), a gap in existing literature, while maintaining robustness for standard between-individual shifts.
Theoretical Guarantees: The work provides rigorous theoretical foundations, including limiting distributions and consistency results for both the test and the change-point estimator.

The authors conclude that the framework is particularly effective when within-individual differences are present, offering a more comprehensive approach to change-point detection in complex, structured data sequences.

More like this