gfpop: an R Package for Univariate Graph-Constrained Change-Point Detection

Vincent Runge, Toby Dylan Hocking, Gaetano Romano, Fatemeh Afghah, Paul Fearnhead, Guillem Rigaill

Abstract

In a world with data that change rapidly and abruptly, it is important to detect those changes accurately. In this paper we describe an R package implementing a generalized version of an algorithm recently proposed by Hocking et al. [2020] for penalized maximum likelihood inference of constrained multiple change-point models. This algorithm can be used to pinpoint the precise locations of abrupt changes in large data sequences. There are many application domains for such models, such as medicine, neuroscience or genomics. Often, practitioners have prior knowledge about the changes they are looking for. For example in genomic data, biologists sometimes expect peaks: up changes followed by down changes. Taking advantage of such prior information can substantially improve the accuracy with which we can detect and estimate changes. Hocking et al. [2020] described a graph framework to encode many examples of such prior information and a generic algorithm to infer the optimal model parameters, but implemented the algorithm for just a single scenario. We present the gfpop package that implements the algorithm in a generic manner in R/C++. gfpop works for a user-defined graph that can encode prior assumptions about the types of change that are possible and implements several loss functions (Gauss, Poisson, binomial, biweight and Huber). We then illustrate the use of gfpop on isotonic simulations and several applications in biology. For a number of graphs the algorithm runs in a matter of seconds or minutes for 10^5 data points.

Introduction: The Challenge of Structured Change-Point Detection

In many fields, from genomics to finance, data arrives as a sequence where the underlying "truth" changes abruptly at specific points. Standard change-point detection algorithms often struggle because they treat every change as equally likely. However, practitioners often have prior knowledge about the structure of these changes. For example, a biologist looking for a "peak" in genomic data expects an upward change followed by a downward one.

Standard latent state model for change-point detection where $Z_i$ represents the hidden state and $Y_i$ the observed data.

Existing tools were often either too specialized (handling only one type of constraint) or computationally prohibitive for large datasets. The gfpop R package addresses this gap by providing a generalized, efficient framework for detecting abrupt changes in univariate data while enforcing user-defined constraints via a graph.

The gfpop Framework

The core of the package is the Generalized Functional Pruning Optimal Partitioning (gfpop) algorithm. The "aha" moment of the framework is that complex domain knowledge can be translated into a simple directed graph. This turns a difficult statistical problem into a path-finding problem on a graph.

Key Technical Highlights

  • Graph-Based Constraints: Users define a directed graph where nodes represent states and edges represent possible transitions. Each edge can carry a constraint (e.g., $\mu_t \le \mu_{t+1}$), a penalty for the change ($\beta$), and a specific loss function.
  • Functional Pruning: Unlike standard dynamic programming which can be slow ($O(n^2)$), gfpop uses functional pruning to reduce the search space. This allows the algorithm to run in near-linear time for many common scenarios.
  • Diverse Loss Functions: The package supports several analytical decompositions (L2, Lin-log, and Log-log), enabling the use of Gaussian, Poisson, Binomial, and robust losses like Huber and biweight. Robust losses are particularly critical for handling outliers in "dirty" real-world data.
A collapsed graph representing isotonic constraints ($\mu_t \le \mu_{t+1}$) and the resulting monotonically increasing step-function signal.

Applications and Results

The authors evaluate gfpop using both simulations and high-impact real-world applications, including DNA Copy Number data for cancer research, neuroscience calcium imaging for neuron spikes, and ECG data for heartbeat analysis.

  • Superior Accuracy in Genomics: On DNA copy number data, the constrained gfpop model achieved zero label errors, whereas unconstrained models consistently produced false positives or missed relevant changes.
  • Robustness to Outliers: In simulations with 30% outliers, gfpop using a biweight loss was the only method capable of accurately recovering the true underlying signal. Standard "least-squares" approaches failed catastrophically in these scenarios.
  • Computational Speed: For a dataset of $10^5$ points, gfpop can find optimal change-points in roughly 0.35 seconds, making it practical for modern high-throughput data.

Conclusion and Future Work

While gfpop is slightly slower than hyper-specialized tools, its generality makes it a powerful asset for researchers. Currently, the package supports "collapsed" graphs where state transition rules are time-independent. Future work may address time-dependent constraints, auto-correlated noise, and online detection for real-time applications.

Summary updated

Abstract

In a world with data that change rapidly and abruptly, it is important to detect those changes accurately. In this paper we describe an R package implementing a generalized version of an algorithm recently proposed by Hocking et al. [2020] for penalized maximum likelihood inference of constrained multiple change-point models. This algorithm can be used to pinpoint the precise locations of abrupt changes in large data sequences. There are many application domains for such models, such as medicine, neuroscience or genomics. Often, practitioners have prior knowledge about the changes they are looking for. For example in genomic data, biologists sometimes expect peaks: up changes followed by down changes. Taking advantage of such prior information can substantially improve the accuracy with which we can detect and estimate changes. Hocking et al. [2020] described a graph framework to encode many examples of such prior information and a generic algorithm to infer the optimal model parameters, but implemented the algorithm for just a single scenario. We present the gfpop package that implements the algorithm in a generic manner in R/C++. gfpop works for a user-defined graph that can encode prior assumptions about the types of change that are possible and implements several loss functions (Gauss, Poisson, binomial, biweight and Huber). We then illustrate the use of gfpop on isotonic simulations and several applications in biology. For a number of graphs the algorithm runs in a matter of seconds or minutes for 10^5 data points.
BibTeX
@article{runge2023gfpop,
  author = {Vincent Runge and Toby Dylan Hocking and Gaetano Romano and Fatemeh Afghah and Paul Fearnhead and Guillem Rigaill},
  title = {{gfpop: an R Package for Univariate Graph-Constrained Change-Point Detection}},
  journal = {J. Stat. Softw.},
  year = {2023},
  doi = {10.18637/jss.v106.i06},
}
Figure