Multiple change-point detection via bottom-up scanning

arXiv:2609.31116 · stat.ME · Submitted 2026-09-25 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Statistics. The day in statistics: methods, theory and the inference under them.

Tom: We're looking at the paper: "Multiple change-point detection via bottom-up scanning".

Jane: Here's the gist of the paper. Multiple change-point detection via bottom-up scanning aims to identify time points at which the underlying distribution changes in high-dimensional sequences We propose gBottomup, a graph-based bottom-up framework for multiple change-point detection in high-dimensional settings Simulation results demonstrate that gBottomup performs reliably across a range of structural configurations and is particularly effective in frequent change-point settings, where existing top-down procedures may lose sensitivity Runtime experiments indicate favorable computational performance relative to graph-based top-down alternatives.

Tom: Problem Definition and Motivation Change-point detection seeks to identify distributional changes in data and estimate their locations, which is relevant across various domains such as medical condition monitoring, genomics, finance, and social networks The offline multiple change-point detection problem involves partitioning the entire sequence into several distinct segments based on a sequence of change-points where the distribution changes between segments.

Jane: Classical methods often rely on restrictive parametric assumptions, prompting the development of nonparametric approaches like kernel-based methods or E-Divisive method.

Tom: gBottomup Framework Components The proposed gBottomup framework consists of three distinct phases for change-point detection Phase 1 (Local Merging) partitions the sequence into short initial segments and screens adjacent pairs through repeated provisional merge followed by a test using local graph-based statistic over several levels.

Title and authors: Tom: So we're looking at this paper titled Multiple change-point detection via bottom-up scanning. Jane, what does that title actually suggest to you?

Jane: Well, it suggests a specific way of looking at the problem, focusing on building up solutions from the bottom of the data sequence—or perhaps from smaller segments upward. It sounds like they are trying a different approach than what we usually see in these kinds of change-point studies.

Tom: Exactly. And it's by Jinhyeok Park, Hyeyoung Maeng, and Hoseung Song. I've seen their work on graph-based detection before, so I’m curious how they build this bottom-up structure compared to those top-down methods we often look at.

Lu: What interests me is the specific methodology they are proposing here. They are using a graph-based framework that constructs a hierarchical segmentation by proposing merges of adjacent segments. That implies they aren't just looking for one split point at a time, but building up the structure across the whole sequence first.

Meng: From an engineering standpoint, I wonder how computationally heavy this is compared to those top-down graph methods we usually deploy in production environments. We need something that scales well when we have thousands of data points and multiple potential breaks.

Lalam: I see a lot of focus on high-dimensional sequences here, which is where things get tricky because the number of dimensions can make similarity graphs really complex to manage. I’m picking up on the idea that they are aiming for something nonparametric, which means they aren't locked into a specific mathematical test statistic upfront.

Jane: So, if I had to put it simply, this paper is proposing a new way—a bottom-up scan—to find where the underlying data distribution shifts in high-dimensional sequences. It’s about building up the picture incrementally rather than trying to find all the breaks at once.

The paper's summary: Tom: Right, so they start by defining this offline multiple change-point detection problem, which is just partitioning a whole sequence into several distinct segments where the distribution changes between those segments. They are aiming to estimate both how many change points there are and exactly where they occur.

Jane: And they address the problem that existing methods can struggle when structural breaks are packed very closely together. If the breaks are dense, top-down procedures might get lost in the noise, but this paper aims to keep that sensitivity even when those changes happen right next to each other.

Lu: They propose gBottomup as their framework. It has three main phases: first local merging, then hierarchical merging to build a nested candidate hierarchy, and finally model selection using an extended pseudo-modified Bayesian information criterion called ep-mBIC.

Meng: The number of change points is estimated in phase three by pruning the candidates using this ep-mBIC and an Early Stopped Backward Elimination algorithm. I need to know how robust that pruning step is, because if we have a huge candidate set, we can't afford slow evaluations at scale.

Lalam: What’s interesting about their structure is how Phase one uses a local graph-based statistic over several levels, and the unmerge rule combines absolute significance with relative local heterogeneity to adaptively refine those initial partitions <ref:2609.31116#pg2>. That sounds like it has some built-in self-correction for the early stages.

Tom: It’s that adaptive refinement in phase one that I find mechanically interesting. They are essentially setting a local merging ratio, ρlocal, which controls how aggressively they merge segments initially, and then checking significance at five levels based on a partition length L.

Jane: So the core idea is starting fine and progressively merging segments while making sure we test for actual change points using these local graph statistics and that adaptive rule. It’s about preserving local boundary information that might otherwise get washed out by large early merges.

The paper's improvements: Tom: So the paper highlights a few key advantages over existing methods. First, they emphasize its robustness against missing true boundaries, which is ensured by an unmerge rule where every evaluation of a true boundary returns keep under certain conditions.

Jane: That’s a big deal for real data. It means if we miss a break entirely, the algorithm doesn't just silently merge that boundary away when it moves to larger scales; it has a local protection property. They check two criteria: absolute heterogeneity and relative heterogeneity of the boundary compared to its immediate neighbors.

Lu: From a modeling perspective, they claim this framework is fully nonparametric and not tied to a specific test statistic. This gives them flexibility because they can plug in different graph-based or nonparametric statistics, as long as those statistics yield comparable results across windows and admit suitable filtering and model selection criteria.

Meng: I’m still concerned about the computational cost. The text mentions the cost for evaluating a window with w observations is O of w squared log w for some steps. How does that compare to the top-down graph-based approaches they't comparing against? We need concrete numbers on how much faster it actually runs on realistic data volumes.

Lalam: On that front, I see they are tuning parameters like k, the graph parameter, based on empirical scaling rules dependent on window sample size n. This adaptation ensures the ep-mBIC remains comparable across candidate sets during final model selection by using this rule to set k appropriately for phase one and two or phase three evaluation.

Jane: So what it means for someone listening to this is that they get a system that handles frequent change-points much better than older top-down methods, especially when those breaks are clustered together. It’s designed to maintain detection power in those dense settings.

Conclusion: Tom: So to wrap up on the Multiple change-point detection via bottom-up scanning paper, this framework is presented as a reliable, nonparametric approach for high-dimensional multivariate data analysis. The simulation results show it performs well across various structural configurations.

Jane: It seems the main implication is that for applications like genomics or finance where changes are frequent, this method offers a stable way to get reliable change points without losing sensitivity when breaks are close together.

Lu: It’s a bottom-up construction that preserves local boundary information by starting fine and merging upward, which is a key design feature. They also stress that it remains stable even when both the mean and covariance structure of the data change simultaneously.

Meng: For deployment, I just see it as practical if we can nail down those scaling costs and make sure the pruning step using ep-mBIC is conservative enough to avoid discarding real breaks under heavy load.

Lalam: I’m confident that this framework provides a solid foundation for future work, especially since it’s fully nonparametric and not tied to a single test statistic. It keeps the door open for other types of statistics we can plug in later.

Tom: Yeah, so to summarize, they built gBottomup to handle high-dimensional change points by scanning from the bottom up through local merging and hierarchical merging, which is effective even when breaks are clustered together.

Jane: That’s a good summary. So the core message here is that this new approach offers dependable performance in challenging situations where other methods might lose track of those closely spaced distributional shifts.

KAIST · Ewha Womans University · Durham University

stat.ME

Submitted: 2026-09-25

Updated: 2026-11-08

Code: https://github.com/zinhyeok/gBottomup

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 97/100

The gist: Multiple change-point detection via bottom-up scanning aims to identify time points at which the underlying distribution changes in high-dimensional sequences We propose gBottomup…

Key concepts

Local Merging
This initial phase partitions the data into short segments and tests adjacent pairs for merging. It uses a local graph-based statistic combined with rules to decide whether two adjacent segments should be combined, allowing the process to adaptively refine the initial partition.
Hierarchical Merging
This phase iteratively merges remaining segments from the bottom up to build a nested structure of candidate change points. It uses global ranking and greedy merging, selecting boundaries based on scores that stay below a certain threshold to create a hierarchy of potential breaks.
Unmerge Rule
This rule ensures robustness by checking two criteria: absolute significance and relative local heterogeneity. This prevents the algorithm from incorrectly merging true change points, as it requires the boundary to show stronger heterogeneity than its immediate neighbors.
ep-mBIC
This is an extended pseudo-modified Bayesian information criterion used in Phase 3 to prune candidate change points. It helps select the final set by evaluating evidence for a distributional change at each point, ensuring a conservative selection process.

Terminology

Summary

Multiple change-point detection via bottom-up scanning aims to identify time points at which the underlying distribution changes in high-dimensional sequences We propose gBottomup, a graph-based bottom-up framework for multiple change-point detection in high-dimensional settings Simulation results demonstrate that gBottomup performs reliably across a range of structural configurations and is particularly effective in frequent change-point settings, where existing top-down procedures may lose sensitivity Runtime experiments indicate favorable computational performance relative to graph-based top-down alternatives. p. 0

Where the paper says it

Simulation results demonstrate that gBottomup performs reliably across a range of structural configurations and is particularly effective in frequent change-point settings, where existing top-down procedures may lose sensitivity. Runtime experiments indicate favorable computational performance relative to graph-based top-down alternatives.

Problem Definition and Motivation

Change-point detection seeks to identify distributional changes in data and estimate their locations, which is relevant across various domains such as medical condition monitoring, genomics, finance, and social networks The offline multiple change-point detection problem involves partitioning the entire sequence into several distinct segments based on a sequence of change-points where the distribution changes between segments. Classical methods often rely on restrictive parametric assumptions, prompting the development of nonparametric approaches like kernel-based methods or E-Divisive method. p. 1

Where the paper says it

Classical change-point detection methods often rely on specified model structures and distributional assumptions. Parametric methods, as surveyed by Chen et al.

gBottomup Framework Components

The proposed gBottomup framework consists of three distinct phases for change-point detection

** Phase 1 (Local Merging) partitions the sequence into short initial segments and screens adjacent pairs through repeated provisional merge followed by a test using local graph-based statistic over several levels. The unmerge rule combines absolute significance with relative local heterogeneity to adaptively refine partitions This phase controls the degree of early merging via the Local Merging ratio ρlocal. p. 0

Where the paper says it

To address this challenge, we propose gBottomup, a graph-based bottom-up framework for multiple change-point detection in high-dimensional settings. gBottomup constructs a hierarchical segmentation by proposing merges of adjacent segments and verifying them through an unmerge rule that combines absolute significance with relative local heterogeneity, thereby adaptively refining partitions and estimating the number of change-points.

5 levels are set for the initial partition length L. p. 6
Where the paper says it

To orient the reader, Algorithm 1 summarizes the full pipeline before the per-phase details are introduced. Algorithm 1 gBottomup Require: sequence {Xt} T t=1; segment length L; ratios ρlocal, ρmerge; penalty constant c; significance level α Ensure: estimated change-point set τˆ 1: partition {Xt} into N = ⌊T /L⌋ segments of length L ▷ initial partition B 2: Phase 1: provisional-merge, verified via unmerge (Algorithm 2) ▷ hlocal levels; Eq.

8 levels are set for hlocal, which is defined in Eq. p. 8
Where the paper says it

As described in Section 2. 1, this provisional merge-and-verify procedure is repeated for hlocal levels, where hlocal is defined in Eq.

(5). **

** Phase 2 (Hierarchical Merging) iteratively merges the remaining segments in a bottom-up manner to construct a nested candidate hierarchy. p. 6

Where the paper says it

In Phase 1 (Local Merging), the sequence is partitioned into short initial segments, and disjoint adjacent pairs are screened by repeated provisional merge followed by a test using local graph-based statistic over several levels. In Phase 2 (Hierarchical Merging), the remaining segments are iteratively merged in a bottom-up manner to construct a nested candidate hierarchy.

This phase uses global ranking and greedy merge, selecting boundaries whose scores do not exceed the empirical ρmerge-quantile. p. 6
Where the paper says it

Algorithm 1 gBottomup Require: sequence {Xt} T t=1; segment length L; ratios ρlocal, ρmerge; penalty constant c; significance level α Ensure: estimated change-point set τˆ 1: partition {Xt} into N = ⌊T /L⌋ segments of length L ▷ initial partition B 2: Phase 1: provisional-merge, verified via unmerge (Algorithm 2) ▷ hlocal levels; Eq. (5) 3: Phase 2: greedy merge (Algorithm 3), verified via unmerge ▷ until |B| = 1, obtain τ˜ 4: Phase 3: τˆ ← ES-BE(˜τ ) with ep-mBIC (Algorithm 5) ▷ prune 5: return τˆ Throughout the procedure, candidate boundaries are assessed using the generalized edge7

4 iterations are used in the hierarchical merging procedure. p. 0
Where the paper says it

We illustrate the proposed method through an analysis of a S&P 500 dataset. Keywords: Frequent change-points, Nonparametrics, Graph-based methods, Hierarchical merging, High-dimensional data ∗Corresponding authors.

**

** Phase 3 (Model Selection) prunes the candidate change-point set using an extended pseudo-modified Bayesian information criterion, ep-mBIC. p. 5

Where the paper says it

Chen (2019), the proposed method starts from a fine initial partition and proceeds through two phases, Local Merging and Hierarchical Merging, to construct a robust set of candidate change-points which are then pruned using a BIC-type model-selection criterion. Figure 2: Detection frequency of gBottomup under the same setting as Figure 1.

The eAS statistic evaluates the evidence for a distributional change at each candidate point using observations in the two neighboring segments. p. 7
Where the paper says it

Unlike traditional scan statistics, which maximize S [a,b] (t) over all candidate split points t ∈ [a, b), our algorithm evaluates the statistic only at internal boundaries ν, induced by the current segmentation. Specifically, let B = [a, ν] and B′ = [ν + 1, b] be two adjacent segments of the current segmentation.

Early-Stopped Backward Elimination (ES-BE) is used to select the final subset of change-points. p. 3
Where the paper says it

We refer to such situations as frequent change-point settings, in which consecutive change-points are closely spaced and form a highly clustered pattern. In these settings, top-down procedures may struggle because an early split over a large interval can mask nearby interior changes.

5 steps are used in the ES-BE algorithm. p. 5
Where the paper says it

First, by operating from fine-scale segments upward, it is specifically designed to preserve sensitivity in frequent change-point settings, where existing top-down graph-based procedures may lose detection power. As a preview, Figure 2 reports the detection frequencies of gBottomup under the same frequent meanchange setting used in Figure 1.

**

Mechanism for Robustness

The method's robustness against missing true boundaries is ensured by the unmerge rule in Algorithm 2 Proposition 1 establishes a local protection property of this rule, stating that under certain conditions, every evaluation of a true change-point boundary returns KEEP. This property is achieved by checking two criteria: Criterion 1 (Absolute heterogeneity), which tests significance in isolation at level α, and Criterion 2 (Relative heterogeneity), which ensures the boundary exhibits stronger heterogeneity than its immediate local surroundings. p. 9

Where the paper says it

The pair is then evaluated against the following two criteria: if either is satisfied, the provisional merge is canceled and the corresponding boundary is retained (we refer to this outcome as KEEP); otherwise, the two segments remain merged (MERGE). Criterion 1 (Absolute heterogeneity) We test whether the internal boundary within Wkeep is significant in isolation at level α: S(Wkeep) > χ2 2,1−α .

Parameter Tuning and Performance

The procedure involves four tuning parameters: the graph parameter k, the penalty constant c, and the merging parameters ρlocal and ρmerge The graph parameter k is chosen based on empirical scaling rules dependent on window sample size n. Calibration studies determined the optimal values of c = 2, ρlocal = 0. p. 6

Where the paper says it

To orient the reader, Algorithm 1 summarizes the full pipeline before the per-phase details are introduced. Algorithm 1 gBottomup Require: sequence {Xt} T t=1; segment length L; ratios ρlocal, ρmerge; penalty constant c; significance level α Ensure: estimated change-point set τˆ 1: partition {Xt} into N = ⌊T /L⌋ segments of length L ▷ initial partition B 2: Phase 1: provisional-merge, verified via unmerge (Algorithm 2) ▷ hlocal levels; Eq.

3, and ρmerge = 0. p. 6
Where the paper says it

To orient the reader, Algorithm 1 summarizes the full pipeline before the per-phase details are introduced. Algorithm 1 gBottomup Require: sequence {Xt} T t=1; segment length L; ratios ρlocal, ρmerge; penalty constant c; significance level α Ensure: estimated change-point set τˆ 1: partition {Xt} into N = ⌊T /L⌋ segments of length L ▷ initial partition B 2: Phase 1: provisional-merge, verified via unmerge (Algorithm 2) ▷ hlocal levels; Eq.

2 across four models. p. 1
Where the paper says it

(2006) and Malladi et al. (2013) consider models with linear structures and Gaussian noise.

The computational cost for evaluating a window containing w observations is O(w squared log w). p. 3
Where the paper says it

, 2008; Frick et al. , 2014) offers global optimality at a higher computational cost.

Real-Data Application

The method was applied to a high-dimensional panel of daily S&P 500 constituent returns covering the COVID-19 period The comparison included gMulti(G.WBS), gMulti(G. p. 3

Where the paper says it

These schemes follow a top-down strategy that begins with the full sequence, identifies a candidate change-point over a large interval, and recursively applies the same procedure to the resulting sub-intervals. Zhang and Chen (2021) recently combined this paradigm with graph-based statistics, incorporating them into the WBS and SBS frameworks to propose gMulti(G.

SBS), and E-Divisive, excluding KCP due to calibration constraints. p. 1
Where the paper says it

, 2008; Arlot et al. , 2019; Song and Chen, 2024) detect changes by mapping the data into a high-dimensional feature space andMatteson and James (2014) proposed the E-Divisive method based on empirical divergence measures.

Figure 5 shows that gBottomup and the two graph-based top-down methods each estimate five change-points, while E-Divisive returns the same two boundaries under both values of h. p. 5
Where the paper says it

As a preview, Figure 2 reports the detection frequencies of gBottomup under the same frequent meanchange setting used in Figure 1. In contrast to the top-down procedures, which lose sensitivity inside the dense cluster, the proposed method shows high detection frequencies at all five closely spaced change-points.

The estimated locations for gBottomup align with identifiable events such as the February 24–25 boundary coinciding with sharp repricing of COVID-19 risk. p. 6
Where the paper says it

To orient the reader, Algorithm 1 summarizes the full pipeline before the per-phase details are introduced. Algorithm 1 gBottomup Require: sequence {Xt} T t=1; segment length L; ratios ρlocal, ρmerge; penalty constant c; significance level α Ensure: estimated change-point set τˆ 1: partition {Xt} into N = ⌊T /L⌋ segments of length L ▷ initial partition B 2: Phase 1: provisional-merge, verified via unmerge (Algorithm 2) ▷ hlocal levels; Eq.

Conclusion

In conclusion, gBottomup is the first bottom-up framework for nonparametric multiple change-point detection in high-dimensional multivariate data The simulation results show that the proposed method delivers reliable performance across a range of structural configurations, with particular advantages in frequent change-point settings where existing top-down procedures may lose sensitivity. p. 0

Where the paper says it

Simulation results demonstrate that gBottomup performs reliably across a range of structural configurations and is particularly effective in frequent change-point settings, where existing top-down procedures may lose sensitivity. Runtime experiments indicate favorable computational performance relative to graph-based top-down alternatives.

By starting from a fine initial partition and progressively merging adjacent segments, the method preserves local boundary information that would otherwise be obscured by early large-scale splits. p. 5
Where the paper says it

Chen (2019), the proposed method starts from a fine initial partition and proceeds through two phases, Local Merging and Hierarchical Merging, to construct a robust set of candidate change-points which are then pruned using a BIC-type model-selection criterion. Figure 2: Detection frequency of gBottomup under the same setting as Figure 1.

p. 5
Where the paper says it

Chen (2019), the proposed method starts from a fine initial partition and proceeds through two phases, Local Merging and Hierarchical Merging, to construct a robust set of candidate change-points which are then pruned using a BIC-type model-selection criterion. Figure 2: Detection frequency of gBottomup under the same setting as Figure 1.

The framework is fully nonparametric and not tied to a specific test statistic. p. 5
Where the paper says it

In contrast to the top-down procedures, which lose sensitivity inside the dense cluster, the proposed method shows high detection frequencies at all five closely spaced change-points. Second, the framework is fully nonparametric and not tied to a specific test statistic.

The proposed method remains stable when both the mean and covariance structure change simultaneously. p. 0
Where the paper says it

We illustrate the proposed method through an analysis of a S&P 500 dataset. Keywords: Frequent change-points, Nonparametrics, Graph-based methods, Hierarchical merging, High-dimensional data ∗Corresponding authors.

References

Arlot, S., Celisse, A., and Harchaoui, Z. p. 1

Where the paper says it

In response, various nonparametric methods have been proposed. For instance, kernel-based approaches (Harchaoui et al.

(2019). A kernel multiple change-point algorithm via model selection. p. 6
Where the paper says it

In Phase 3 (Model Selection), the resulting candidate change-points are pruned using a BICtype criterion to obtain the final estimate. To orient the reader, Algorithm 1 summarizes the full pipeline before the per-phase details are introduced.

J. Mach. Learn. Res., 20:1–56

Baranowski, R., Chen, Y., and Fryzlewicz, P. p. 3

Where the paper says it

, 2012) achieves linear computational complexity, its performance depends on the choice of penalty. Alternatively, interval-generation methods such as Wild Binary Segmentation (WBS) (Fryzlewicz, 2014), Narrowest-Over-Threshold (NOT) (Baranowski et al.

p. 3
Where the paper says it

, 2012) achieves linear computational complexity, its performance depends on the choice of penalty. Alternatively, interval-generation methods such as Wild Binary Segmentation (WBS) (Fryzlewicz, 2014), Narrowest-Over-Threshold (NOT) (Baranowski et al.

p. 3
Where the paper says it

, 2012) achieves linear computational complexity, its performance depends on the choice of penalty. Alternatively, interval-generation methods such as Wild Binary Segmentation (WBS) (Fryzlewicz, 2014), Narrowest-Over-Threshold (NOT) (Baranowski et al.

(2019). Narrowest-over-threshold detection of multiple change points and change-point-like features. p. 0
Where the paper says it

and Hoseung Song∗ † Department of Industrial and Systems Engineering, KAIST. September 28, 2026 Abstract We study nonparametric multiple change-point detection for high-dimensional sequences, aiming to identify time points at which the underlying distribution changes.

J. R. Stat. Soc. Ser. B Stat Methodol. p. 0
Where the paper says it

1 arXiv:2609. 31116v1 [stat.

p. 0
Where the paper says it

1 arXiv:2609. 31116v1 [stat.

, 81:649–672

Bosc, M., Heitz, F., Armspach, J.-P., Namer, I., Gounot, D., and Rumbach, L. (2003). Automatic change detection in multimodal serial mri: application to multiple sclerosis lesion evolution. p. 1

Where the paper says it

1 Introduction Change-point detection aims to identify distributional changes in data and estimate their locations. Such problems arise in a wide range of application domains, including medical condition monitoring (Bosc et al.

NeuroImage, 20:643–656

Chen, H. and Chu, L. p. 2

Where the paper says it

1 Graph-based top-down approaches Among nonparametric approaches, graph-based methods have emerged as effective tools for detecting distributional changes in multivariate and high-dimensional data (Song and Chen, 2022; Chen and Chu, 2023). Their main idea is to represent similarity relationships among observations through a graph and then to assess whether the graph structure changes across a candidate split point.

(2023). Graph-based change-point analysis. p. 0
Where the paper says it

We illustrate the proposed method through an analysis of a S&P 500 dataset. Keywords: Frequent change-points, Nonparametrics, Graph-based methods, Hierarchical merging, High-dimensional data ∗Corresponding authors.

Annu. Rev. Stat Appl., 10:475–499

Chen, H. and Zhang, N. p. 1

Where the paper says it

, 2005; Malladi et al. , 2013), genomics (Zhang et al.

(2015). Graph-based change-point detection. p. 0
Where the paper says it

While many existing methods perform well when change-points are well-separated, their performance can deteriorate when structural breaks are densely clustered. To address this challenge, we propose gBottomup, a graph-based bottom-up framework for multiple change-point detection in high-dimensional settings.

Ann. Stat., 43:139–176

Chu, L. and Chen, H. p. 1

Where the paper says it

Classical change-point detection methods often rely on specified model structures and distributional assumptions. Parametric methods, as surveyed by Chen et al.

p. 1
Where the paper says it

Classical change-point detection methods often rely on specified model structures and distributional assumptions. Parametric methods, as surveyed by Chen et al.

p. 1
Where the paper says it

Classical change-point detection methods often rely on specified model structures and distributional assumptions. Parametric methods, as surveyed by Chen et al.

p. 1
Where the paper says it

Classical change-point detection methods often rely on specified model structures and distributional assumptions. Parametric methods, as surveyed by Chen et al.

p. 1
Where the paper says it

Classical change-point detection methods often rely on specified model structures and distributional assumptions. Parametric methods, as surveyed by Chen et al.

(2019). Asymptotic distribution-free change-point detection for multivariate and non-euclidean data. p. 4
Where the paper says it

These alternatives to top-down search are effective, but existing approaches rely on parametric assumptions in both univariate and high-dimensional settings. We propose gBottomup, a graph-based bottom-up framework for multiple change-point detection in high-dimensional multivariate data.

Ann. Stat., 47:382–414

Frick, K., Munk, A., and Sieling, H. (2014). Multiscale change point inference. p. 0

Where the paper says it

Multiple change-point detection via bottom-up scanning Jinhyeok Park Department of Industrial and Systems Engineering, KAIST. Hyeyoung Maeng∗ Department of Statistics, Ewha Womans University, Department of Mathematical Sciences, Durham University.

J. R. Stat Soc. Ser. B Stat Methodol., 76:495–580

Friedman, J. H. and Rafsky, L. C. (1979). Multivariate generalizations of the wald-wolfowitz and smirnov two-sample tests. p. 1

Where the paper says it

(2013) consider models with linear structures and Gaussian noise. However, such assumptions are often restrictive in practice, especially for high-dimensional multivariate data.

Ann. Stat., 7:697–717

Friedrich, F., Kempe, A., Liebscher, V., and Winkler, G. (2008). Complexity penalized m-estimation: fast computation. p. 3

Where the paper says it

dure, where central challenge is often balancing computational efficiency against detection accuracy. Binary segmentation (Vostrikova, 1981) is fast and flexible while dynamic programming (Friedrich et al.

J. Comput. Graph Stat. p. 0
Where the paper says it

1 arXiv:2609. 31116v1 [stat.

, 17:201–224

Fryzlewicz, P. (2014). Wild binary segmentation for multiple change-point detection. p. 3

Where the paper says it

, 2012) achieves linear computational complexity, its performance depends on the choice of penalty. Alternatively, interval-generation methods such as Wild Binary Segmentation (WBS) (Fryzlewicz, 2014), Narrowest-Over-Threshold (NOT) (Baranowski et al.

Ann. Stat., 42:2243–2281

Fryzlewicz, P. (2018). Tail-greedy bottom-up data decompositions and fast multiple changepoint detection. p. 4

Where the paper says it

This limitation has motivated alternative segmentation strategies that are designed to better handle closely spaced change-points. For piecewise-constant signals, the Tail-Greedy Unbalanced Haar (TGUH) transform of Fryzlewicz (2018) adopts a bottom-up perspective by iteratively merging neighboring regions from the finest scale.

Ann. Stat., 46:3390–3421

Harchaoui, Z., Moulines, E., and Bach, F. (2008). Kernel change-point analysis. p. 0

Where the paper says it

We illustrate the proposed method through an analysis of a S&P 500 dataset. Keywords: Frequent change-points, Nonparametrics, Graph-based methods, Hierarchical merging, High-dimensional data ∗Corresponding authors.

Adv. Neural Inf Process Syst., 21

Hazrati-Marangaloo, H. and Noorossana, R. p. 1

Where the paper says it

, 2015), finance (Kim et al. , 2022), and social networks (Hazrati-Marangaloo and Noorossana, 2021).

(2021). A nonparametric change detection approach in social networks. p. 1
Where the paper says it

, 2022), and social networks (Hazrati-Marangaloo and Noorossana, 2021). We consider the offline multiple change-point detection problem, where the entire sequence is observed, and multiple structural changes partition the data into several distinct segments.

Qual Reliab Eng Int., 37:2916–2935

James, N. A. and Matteson, D. S. (2015). ecp: An r package for nonparametric multiple change point analysis of multivariate data. p. 4

Where the paper says it

These alternatives to top-down search are effective, but existing approaches rely on parametric assumptions in both univariate and high-dimensional settings. We propose gBottomup, a graph-based bottom-up framework for multiple change-point detection in high-dimensional multivariate data.

J. Stat Softw. p. 0
Where the paper says it

1 arXiv:2609. 31116v1 [stat.

, 62:1–25

Jiang, Y., Oldridge, D. A., Diskin, S. J., and Zhang, N. p. 1

Where the paper says it

, 2005; Malladi et al. , 2013), genomics (Zhang et al.

R. (2015). Codex: a normalization and copy number variation detection method for whole exome sequencing. p. 0
Where the paper says it

To address this challenge, we propose gBottomup, a graph-based bottom-up framework for multiple change-point detection in high-dimensional settings. gBottomup constructs a hierarchical segmentation by proposing merges of adjacent segments and verifying them through an unmerge rule that combines absolute significance with relative local heterogeneity, thereby adaptively refining partitions and estimating the number of change-points.

Nucleic Acids Res., 43:e39

Killick, R., Fearnhead, P., and Eckley, I. A. (2012). Optimal detection of changepoints with a linear computational cost. p. 3

Where the paper says it

, 2014) offers global optimality at a higher computational cost. Although the Pruned Exact Linear Time (PELT) method (Killick et al.

J. Am Stat Assoc. p. 0
Where the paper says it

1 arXiv:2609. 31116v1 [stat.

p. 0
Where the paper says it

1 arXiv:2609. 31116v1 [stat.

, 107:1590–1598

Kim, K., Park, J. H., Lee, M., and Song, J. p. 0

Where the paper says it

Hyeyoung Maeng∗ Department of Statistics, Ewha Womans University, Department of Mathematical Sciences, Durham University. and Hoseung Song∗ † Department of Industrial and Systems Engineering, KAIST.

W. (2022). Unsupervised change point detection and trend prediction for financial time-series using a new cusum-based approach. p. 4
Where the paper says it

We propose gBottomup, a graph-based bottom-up framework for multiple change-point detection in high-dimensional multivariate data. To the best of our knowledge, this is the first approach of this kind.

IEEE Access, 10:34690–34705

Kovács, S., Bühlmann, P., Li, H., and Munk, A. (2023). Seeded binary segmentation: a general methodology for fast and optimal changepoint detection. p. 3

Where the paper says it

dure, where central challenge is often balancing computational efficiency against detection accuracy. Binary segmentation (Vostrikova, 1981) is fast and flexible while dynamic programming (Friedrich et al.

Biometrika, 110:249–256

Maeng, H. and Fryzlewicz, P. (2024). Detecting linear trend changes in data sequences. p. 2

Where the paper says it

1 Graph-based top-down approaches Among nonparametric approaches, graph-based methods have emerged as effective tools for detecting distributional changes in multivariate and high-dimensional data (Song and Chen, 2022; Chen and Chu, 2023). Their main idea is to represent similarity relationships among observations through a graph and then to assess whether the graph structure changes across a candidate split point.

Stat Pap., 65:1645–1675

Maeng, H., Wang, T., and Fryzlewicz, P. (2026). High-dimensional sparsity-adaptive multiple change-point detection. p. 0

Where the paper says it

and Hoseung Song∗ † Department of Industrial and Systems Engineering, KAIST. September 28, 2026 Abstract We study nonparametric multiple change-point detection for high-dimensional sequences, aiming to identify time points at which the underlying distribution changes.

arXiv preprint arXiv:2607. p. 0
Where the paper says it

†This work was supported, in part, by the National Research Foundation of Korea(NRF) grant (RS2026-25471551,RS-2026-25517529) and the National IT Industry Promotion Agency(NIPA) grant (RS-2026- 25621650), both funded by the Korea government(MSIT). 1 arXiv:2609.

20928

Malladi, R., Kalamangalam, G. P., and Aazhang, B. (2013). Online bayesian change point detection algorithms for segmentation of epileptic activity. p. 0

Where the paper says it

To address this challenge, we propose gBottomup, a graph-based bottom-up framework for multiple change-point detection in high-dimensional settings. gBottomup constructs a hierarchical segmentation by proposing merges of adjacent segments and verifying them through an unmerge rule that combines absolute significance with relative local heterogeneity, thereby adaptively refining partitions and estimating the number of change-points.

In 2013 Asilomar conference on signals, systems and computers, pages 1833–1837 IEEE

Matteson, D. S. and James, N. p. 1

Where the paper says it

, 2008; Arlot et al. , 2019; Song and Chen, 2024) detect changes by mapping the data into a high-dimensional feature space andMatteson and James (2014) proposed the E-Divisive method based on empirical divergence measures.

A. (2014). A nonparametric approach for multiple change point analysis of multivariate data. p. 4
Where the paper says it

We propose gBottomup, a graph-based bottom-up framework for multiple change-point detection in high-dimensional multivariate data. To the best of our knowledge, this is the first approach of this kind.

J. Am Stat Assoc., 109:334–345

Song, H. and Chen, H. (2022). Asymptotic distribution-free changepoint detection for data with repeated observations. p. 7

Where the paper says it

We write S(W) as the generalized edge-count statistic evaluated on the window W at point ν. By Theorem 1 of Zhu and Chen (2024), under the null hypothesis of no change within the window, S(ν) has an asymptotic χ 2 2 distribution, which enables significance assessment.

Biometrika, 109:783–798

Song, H. and Chen, H. (2024). Practical and powerful kernel-based change-point detection. p. 0

Where the paper says it

While many existing methods perform well when change-points are well-separated, their performance can deteriorate when structural breaks are densely clustered. To address this challenge, we propose gBottomup, a graph-based bottom-up framework for multiple change-point detection in high-dimensional settings.

IEEE Trans Signal Process., 72:5174–5186

Staudacher, M., Telser, S., Amann, A., Hinterhuber, H., and Ritsch-Marte, M. (2005). A new method for change-point detection developed for on-line analysis of the heart beat variability during sleep. p. 0

Where the paper says it

We illustrate the proposed method through an analysis of a S&P 500 dataset. Keywords: Frequent change-points, Nonparametrics, Graph-based methods, Hierarchical merging, High-dimensional data ∗Corresponding authors.

Phys. A: Stat Mech Appl. p. 0
Where the paper says it

1 arXiv:2609. 31116v1 [stat.

, 349:582–596

Vostrikova, L. Y. (1981). Detecting “disorder” in multidimensional random processes. p. 2

Where the paper says it

1 Graph-based top-down approaches Among nonparametric approaches, graph-based methods have emerged as effective tools for detecting distributional changes in multivariate and high-dimensional data (Song and Chen, 2022; Chen and Chu, 2023). Their main idea is to represent similarity relationships among observations through a graph and then to assess whether the graph structure changes across a candidate split point.

In Doklady akademii nauk, volume 259, pages 270–274 Russian Academy of Sciences

Yang, P., Dumont, G., and Ansermino, J. M. (2006). Adaptive change detection in heart rate trend monitoring in anesthetized children. p. 1

Where the paper says it

1 Introduction Change-point detection aims to identify distributional changes in data and estimate their locations. Such problems arise in a wide range of application domains, including medical condition monitoring (Bosc et al.

IEEE Trans Biomed Eng., 53:2211–2219

Zhang, N. R. and Siegmund, D. O. (2007). A modified bayes information criterion with applications to the analysis of comparative genomic hybridization data. p. 0

Where the paper says it

We illustrate the proposed method through an analysis of a S&P 500 dataset. Keywords: Frequent change-points, Nonparametrics, Graph-based methods, Hierarchical merging, High-dimensional data ∗Corresponding authors.

Biometrics, 63:22–32

Zhang, N. R., Siegmund, D. O., Ji, H., and Li, J. Z. (2010). Detecting simultaneous changepoints in multiple sequences. p. 0

Where the paper says it

and Hoseung Song∗ † Department of Industrial and Systems Engineering, KAIST. September 28, 2026 Abstract We study nonparametric multiple change-point detection for high-dimensional sequences, aiming to identify time points at which the underlying distribution changes.

Biometrika, 97:631–645

Zhang, Y. and Chen, H. (2021). Graph-based multiple change-point detection. p. 0

Where the paper says it

While many existing methods perform well when change-points are well-separated, their performance can deteriorate when structural breaks are densely clustered. To address this challenge, we propose gBottomup, a graph-based bottom-up framework for multiple change-point detection in high-dimensional settings.

arXiv preprint arXiv:2110. p. 0
Where the paper says it

†This work was supported, in part, by the National Research Foundation of Korea(NRF) grant (RS2026-25471551,RS-2026-25517529) and the National IT Industry Promotion Agency(NIPA) grant (RS-2026- 25621650), both funded by the Korea government(MSIT). 1 arXiv:2609.

01170

Zhu, Y. and Chen, H. (2024). Limiting distributions of graph-based test statistics on sparse and dense graphs. p. 9

Where the paper says it

Following Zhang and Chen (2021), k is set proportional to the number of observations within the test window. Since these windows are of potentially different sizes, using window-specific values of k would result in graphs of different densities, rendering the cross-window comparison invalid.

Bernoulli, 30:770–796

--- Page 1 ---

Multiple change-point detection via bottom-up scanning

Abstract

We study nonparametric multiple change-point detection for high-dimensional sequences, aiming to identify time points at which the underlying distribution changes. While many existing methods perform well when change-points are well-separated, their performance can deteriorate when structural breaks are densely clustered. p. 0

Where the paper says it

September 28, 2026 Abstract We study nonparametric multiple change-point detection for high-dimensional sequences, aiming to identify time points at which the underlying distribution changes. While many existing methods perform well when change-points are well-separated, their performance can deteriorate when structural breaks are densely clustered.

To address this challenge, we propose gBottomup, a graph-based bottom-up framework for multiple change-point detection in high-dimensional settings gBottomup constructs a hierarchical segmentation by proposing merges of adjacent segments and verifying them through an unmerge rule that combines absolute significance with relative local heterogeneity Simulation results demonstrate that gBottomup performs reliably across a range of structural configurations and is particularly effective in frequent change-point settings, where existing top-down procedures may lose sensitivity

Pruning redundant reasoning tokens

The abstract states that the paper studies nonparametric multiple change-point detection for high-dimensional sequences aiming to identify time points at which the underlying distribution changes While many existing methods perform well when change-points are well-separated, their performance can deteriorate when structural breaks are densely clustered. The proposed gBottomup constructs a hierarchical segmentation by proposing merges of adjacent segments and verifying them through an unmerge rule that combines absolute significance with relative local heterogeneity Simulation results demonstrate that gBottomup performs reliably across a range of structural configurations and is particularly effective in frequent change-point settings, where existing top-down procedures may lose sensitivity. p. 0

Where the paper says it

gBottomup constructs a hierarchical segmentation by proposing merges of adjacent segments and verifying them through an unmerge rule that combines absolute significance with relative local heterogeneity, thereby adaptively refining partitions and estimating the number of change-points. Simulation results demonstrate that gBottomup performs reliably across a range of structural configurations and is particularly effective in frequent change-point settings, where existing top-down procedures may lose sensitivity.

How the training signal is built

The proposed method begins with a fine initial partition and proceeds through two phases: Local Merging and Hierarchical Merging to construct a robust set of candidate change-points which are then pruned using a BIC-type model-selection criterion Phase 1 involves partitioning the sequence into segments of fixed length L and screening adjacent pairs through provisional merge followed by a test using local graph-based statistic. Phase 2 involves iteratively merging remaining segments in a bottom-up manner to construct a nested candidate hierarchy

Where the gains come from

The primary advantage of gBottomup is that by operating from fine-scale segments upward, it is specifically designed to preserve sensitivity in frequent change-point settings where existing top-down graph-based procedures may lose detection power. Second, the framework is fully nonparametric and not tied to a specific test statistic Third, the proposed bottom-up construction is computationally practical with favorable scaling relative to graph-based top-down procedures. p. 5

Where the paper says it

Third, the proposed bottom-up construction is computationally practical. Empirical runtime comparisons show favorable scaling relative to graph-based top-down procedures, with the advantage becoming more pronounced in the larger configurations.

The local protection property of the unmerge rule ensures that a true boundary, present at the finest scale, could be erroneously merged away as the algorithm progresses. p. 7
Where the paper says it

Directly constructing a full hierarchy from these finest-scale segments can be computationally expensive and overly sensitive to local fluctuations. We therefore begin with a Local Merging step before the hierarchy is built, in which adjacent segments are provisionally merged and 1 ⌊x⌋ denotes the largest integer that is no larger than x.

In conclusion, gBottomup is the first approach of this kind for nonparametric multiple change-point detection in high-dimensional multivariate data. The simulation results show that the proposed method delivers reliable performance across a range of structural configurations, with particular advantages in frequent change-point settings where existing top-down procedures may lose sensitivity. By starting from a fine initial partition and progressively merging adjacent segments, the method preserves local boundary information that would otherwise be obscured by early large-scale splits. The framework is fully nonparametric and not tied to a specific test statistic The proposed method remains stable when both the mean and covariance structure change simultaneously. p. 5

Where the paper says it

In contrast to the top-down procedures, which lose sensitivity inside the dense cluster, the proposed method shows high detection frequencies at all five closely spaced change-points. Second, the framework is fully nonparametric and not tied to a specific test statistic.

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Bottom-up framework for multiple change-point detection in high-dimensional multivariate data allows AI systems to identify time points of distribution change by constructing a hierarchical segmentation through Local Merging and Hierarchical Merging phases. This preserves local boundary information that would otherwise be obscured by early large-scale splits, which is especially pronounced when change points are closely spaced.

  2. The method can detect frequent change-point settings more reliably than top-down procedures because it is specifically designed to preserve sensitivity in frequent change-point settings, where existing top-down graph-based procedures may lose detection power. This enables the AI system to maintain high detection frequencies even when structural changes are densely clustered.

  3. The framework is fully nonparametric and adaptable because the same bottom-up algorithm can accommodate other boundary scores, provided that they yield comparable values across windows and admit suitable filtering and model-selection criteria. This allows for extensions to other graph-based or nonparametric statistics beyond the generalized edge-count statistic.

  4. The system can estimate the number of change points using an ep-mBIC criterion combined with an Early-Stopped Backward Elimination (ES-BE) algorithm, which stops as soon as the best available deletion no longer increases ep-mBIC. This provides a conservative approach to minimize the risk of irreversibly discarding genuine change points.

  5. The system can select appropriate graph parameters based on window size using the rule in equation 12, which sets k based on whether it is for Phase 1 and 2 or Phase 3 evaluation. This adaptation ensures that the ep-mBIC remains comparable across candidate sets during final model selection.

Abstract

We study nonparametric multiple change-point detection for high-dimensional sequences, aiming to identify time points at which the underlying distribution changes. While many existing methods perform well when change-points are well-separated, their performance can deteriorate when structural breaks are densely clustered. To address this challenge, we propose gBottomup, a graph-based bottom-up framework for multiple change-point detection in high-dimensional settings. gBottomup constructs a hierarchical segmentation by proposing merges of adjacent segments and verifying them through an unmerge rule that combines absolute significance with relative local heterogeneity, thereby adaptively refining partitions and estimating the number of change-points. Simulation results demonstrate that gBottomup performs reliably across a range of structural configurations and is particularly effective in frequent change-point settings, where existing top-down procedures may lose sensitivity. We illustrate the proposed method through an analysis of high-dimensional sensor data from an experimental hydraulic system.

Sources

Related papers