High-Dimensional Change Point Detection via Graph Spanning Ratio

Statistical change point (CP) detection methods typically rely on likelihood-based inference and ignore contextual information about plausible CP locations beyond the observed sequence. Although informative priors provide a natural way to incorporate such information, general and computationally efficient methods for doing so are lacking, especially for multiple CP detection. To address this gap, we propose a prior-informed CP detection algorithm (Pi-Change) that incorporates prior information on CP locations through a time-varying penalty term. We prove that the proposed penalty can be embedded in the Pruned Exact Linear Time framework while preserving the dynamic programming recursion and pruning rule required for efficient multiple CP detection. Across simulation studies and three time-series applications, Pi-Change discourages spurious CPs unsupported by prior information, remains robust to prior misspecification, and improves detection accuracy. More broadly, Pi-Change extends multiple CP detection beyond purely data-driven fitting by incorporating partial prior knowledge in a computationally efficient and interpretable way. It is particularly useful when CPs arise from heterogeneous mechanisms or are associated with known external events, helping quantify the delay between an event and the resulting structural change.

Traditional change point detection in dynamic networks assumes abrupt transitions between stationary states, overlooking scenarios of continuous evolution which arise in most real-world applications, such as social networks or physical systems. We address this gap by formally defining regimes as periods of coherent dynamics in temporal graphs, which we characterize as trajectories along geodesics in a suitably defined graph space. This original perspective allows us to define regime changes as significant drifts in dynamics, either toward new trajectories or with pace changes. We leverage graph regression methods to measure the cumulative distance of sequences of observed graphs from the estimated geodesics between their endpoints, in the relevant graph space, which we can combine with change point detection algorithms. We present experiments on dynamic networks, with changing trajectories and varying speeds, in which we outperform state of the art change point detection models. Then, we analyse mobility data during the Covid-19 pandemic, and show that our assumptions on regular network evolution lead to change points that are more aligned to external events compared to the outcomes of baseline methods. Our work is the first to model and detect changes between evolving regimes in graph space, providing a realistic and powerful tool for analyzing complex temporal graph data.

Detecting a change in a multivariate series answers only the first of two questions; the operational question is which coordinates changed. Existing answers are incomplete. Block-level procedures certify predefined groups of coordinates under an additive union bound, high-dimensional variable-selection methods return interpretable rankings without error guarantees, and the post-detection inference literature controls error along the time axis rather than across coordinates. We propose ARM (Attribution by Rank Maxima), a wrapper that accepts a changepoint located by an arbitrary detector and returns the set of coordinates certified to have changed, each carrying a location or scale type label. ARM scores each coordinate by a max-over-splits rank statistic. Because this statistic dominates the corresponding statistic at the estimated split, the resulting certificate is invariant to the manner, and to the accuracy, of the changepoint estimate. Three finite-sample guarantees follow from within-coordinate ranks alone: per-coordinate validity under any detector; exact family-wise error control through a Westfall--Young joint permutation that preserves cross-coordinate dependence, with a fully distribution-free Holm fallback; and false discovery rate control under arbitrary coordinate dependence in high dimensions through Benjamini--Yekutieli and e-BH. In simulations, naive per-coordinate testing at the estimated changepoint inflates its family-wise error beyond $0.66$ as the dimension grows, whereas ARM maintains the nominal level while retaining validity under heavy tails, power in high dimensions, and accurate type labels. On five financial series surrounding the 2008 collapse, ARM attributes a scale change to every asset class and excludes injected control coordinates.