Multiple change-point detection via bottom-up scanning
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 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.Where the paper says it
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 Classical change-point detection methods often rely on specified model structures and
distributional assumptions. Parametric methods, as surveyed by Chen et al.Where the paper says it
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 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. 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. As described in
Section 2. 1, this provisional merge-and-verify procedure is repeated for hlocal levels, where
hlocal is defined in Eq.Where the paper says it
Where the paper says it
Where the paper says it
** Phase 2 (Hierarchical Merging) iteratively merges the remaining segments in a bottom-up manner to construct a nested candidate hierarchy. p. 6 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. 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 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.Where the paper says it
Where the paper says it
Where the paper says it
** Phase 3 (Model Selection) prunes the candidate change-point set using an extended pseudo-modified Bayesian information criterion, ep-mBIC. p. 5 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. 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. 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. 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.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
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 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−α
.Where the paper says it
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 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. 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. (2006) and Malladi
et al. (2013) consider models with linear structures and Gaussian noise. , 2008; Frick et al. , 2014) offers global optimality at a higher
computational cost.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
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 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. , 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. 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. 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.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
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 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. 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. 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. 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. 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.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
References
Arlot, S., Celisse, A., and Harchaoui, Z. p. 1 In response, various nonparametric methods have been proposed. For instance,
kernel-based approaches (Harchaoui et al. 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.Where the paper says it
Where the paper says it
Baranowski, R., Chen, Y., and Fryzlewicz, P. p. 3 ,
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. ,
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. ,
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. 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. 1
arXiv:2609. 31116v1 [stat. 1
arXiv:2609. 31116v1 [stat.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
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 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.Where the paper says it
Chen, H. and Chu, L. p. 2 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. 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.Where the paper says it
Where the paper says it
Chen, H. and Zhang, N. p. 1 , 2005; Malladi et al. , 2013),
genomics (Zhang et al. 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.Where the paper says it
Where the paper says it
Chu, L. and Chen, H. p. 1 Classical change-point detection methods often rely on specified model structures and
distributional assumptions. Parametric methods, as surveyed by Chen et al. Classical change-point detection methods often rely on specified model structures and
distributional assumptions. Parametric methods, as surveyed by Chen et al. Classical change-point detection methods often rely on specified model structures and
distributional assumptions. Parametric methods, as surveyed by Chen et al. Classical change-point detection methods often rely on specified model structures and
distributional assumptions. Parametric methods, as surveyed by Chen et al. Classical change-point detection methods often rely on specified model structures and
distributional assumptions. Parametric methods, as surveyed by Chen et al. 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.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Frick, K., Munk, A., and Sieling, H. (2014). Multiscale change point inference. p. 0 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.Where the paper says it
Friedman, J. H. and Rafsky, L. C. (1979). Multivariate generalizations of the wald-wolfowitz and smirnov two-sample tests. p. 1 (2013) consider models with linear structures and Gaussian noise. However, such
assumptions are often restrictive in practice, especially for high-dimensional multivariate
data.Where the paper says it
Friedrich, F., Kempe, A., Liebscher, V., and Winkler, G. (2008). Complexity penalized m-estimation: fast computation. p. 3 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. 1
arXiv:2609. 31116v1 [stat.Where the paper says it
Where the paper says it
Fryzlewicz, P. (2014). Wild binary segmentation for multiple change-point detection. p. 3 ,
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.Where the paper says it
Fryzlewicz, P. (2018). Tail-greedy bottom-up data decompositions and fast multiple changepoint detection. p. 4 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.Where the paper says it
Harchaoui, Z., Moulines, E., and Bach, F. (2008). Kernel change-point analysis. p. 0 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.Where the paper says it
Hazrati-Marangaloo, H. and Noorossana, R. p. 1 , 2015), finance (Kim et al. , 2022), and social
networks (Hazrati-Marangaloo and Noorossana, 2021). , 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.Where the paper says it
Where the paper says it
James, N. A. and Matteson, D. S. (2015). ecp: An r package for nonparametric multiple change point analysis of multivariate data. p. 4 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. 1
arXiv:2609. 31116v1 [stat.Where the paper says it
Where the paper says it
Jiang, Y., Oldridge, D. A., Diskin, S. J., and Zhang, N. p. 1 , 2005; Malladi et al. , 2013),
genomics (Zhang et al. 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.Where the paper says it
Where the paper says it
Killick, R., Fearnhead, P., and Eckley, I. A. (2012). Optimal detection of changepoints with a linear computational cost. p. 3 , 2014) offers global optimality at a higher
computational cost. Although the Pruned Exact Linear Time (PELT) method (Killick et al. 1
arXiv:2609. 31116v1 [stat. 1
arXiv:2609. 31116v1 [stat.Where the paper says it
Where the paper says it
Where the paper says it
Kim, K., Park, J. H., Lee, M., and Song, J. p. 0 Hyeyoung Maeng∗
Department of Statistics, Ewha Womans University,
Department of Mathematical Sciences, Durham University. and
Hoseung Song∗ †
Department of Industrial and Systems Engineering, KAIST. 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.Where the paper says it
Where the paper says it
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 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.Where the paper says it
Maeng, H. and Fryzlewicz, P. (2024). Detecting linear trend changes in data sequences. p. 2 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.Where the paper says it
Maeng, H., Wang, T., and Fryzlewicz, P. (2026). High-dimensional sparsity-adaptive multiple change-point detection. p. 0 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. †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.Where the paper says it
Where the paper says it
Malladi, R., Kalamangalam, G. P., and Aazhang, B. (2013). Online bayesian change point detection algorithms for segmentation of epileptic activity. p. 0 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.Where the paper says it
Matteson, D. S. and James, N. p. 1 , 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. 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.Where the paper says it
Where the paper says it
Song, H. and Chen, H. (2022). Asymptotic distribution-free changepoint detection for data with repeated observations. p. 7 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.Where the paper says it
Song, H. and Chen, H. (2024). Practical and powerful kernel-based change-point detection. p. 0 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.Where the paper says it
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 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. 1
arXiv:2609. 31116v1 [stat.Where the paper says it
Where the paper says it
Vostrikova, L. Y. (1981). Detecting “disorder” in multidimensional random processes. p. 2 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.Where the paper says it
Yang, P., Dumont, G., and Ansermino, J. M. (2006). Adaptive change detection in heart rate trend monitoring in anesthetized children. p. 1 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.Where the paper says it
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 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.Where the paper says it
Zhang, N. R., Siegmund, D. O., Ji, H., and Li, J. Z. (2010). Detecting simultaneous changepoints in multiple sequences. p. 0 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.Where the paper says it
Zhang, Y. and Chen, H. (2021). Graph-based multiple change-point detection. p. 0 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. †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.Where the paper says it
Where the paper says it
Zhu, Y. and Chen, H. (2024). Limiting distributions of graph-based test statistics on sparse and dense graphs. p. 9 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.Where the paper says it
--- 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 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.Where the paper says it
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 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.Where the paper says it
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 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. 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.Where the paper says it
Where the paper says it
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 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.Where the paper says it
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
-
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.
-
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. -
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. -
The system can estimate the number of change points using an
ep-mBIC
criterion combined with anEarly-Stopped Backward Elimination (ES-BE) algorithm,
which stops as soon asthe best available deletion no longer increases ep-mBIC.
This provides a conservative approach to minimize the risk of irreversibly discarding genuine change points. -
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
- High-dimensional sparsity-adaptive multiple change-point detection
- Graph-based multiple change-point detection
Related papers
- Learning Robust Treatment Rules for Censored Data
- Neural Estimation of Summary Statistics for Simulation-Based Inference with Non-Asymptotic Guarantees
- Spectral divide-and-conquer MCMC for long stationary time series
- Improving the Efficiency of Subgroup Analysis in Randomized Controlled Trials with TMLE
- Personalized Federated Vector Autoregression with Personalization Diversity
- Doubly Robust and Efficient Calibration of Prediction Sets for Right-Censored Time-to-Event Outcomes