PaperlayerView exact revision on arXiv

Source-linked AI summary

Graph-Based Change-Point Detection

Hao Chen, Nancy Zhang

arXiv:1209.1625v3stat.ME

TL;DR

The paper addresses change-point testing for increasingly high-dimensional, complex, and non-Euclidean data, where existing methods can be restrictive. It develops graph-based scan statistics with analytic significance approximations for single changes and changed intervals, and reports increasing power advantages in moderate and high dimensions. The approach is illustrated in authorship and evolving-network applications, with inference supported by graph-based confidence regions.

  • Problem

    High-dimensional and non-Euclidean sequences require homogeneity tests beyond context-specific parametric and kernel-based approaches.

  • Method

    The paper constructs similarity graphs and uses graph-based scan statistics with analytic type I error control for single change-points and changed intervals.

  • Results

    As dimension increases, the nonparametric graph-based method gains power over applicable parametric methods, with accurate p-value approximations reported in simulations.

  • Takeaways & Limitations

    The method provides a general, off-the-shelf framework for homogeneity testing when observations are multivariate, complex, or non-Euclidean.

  • Takeaways & Limitations

    The theoretical analysis assumes independent observations, although modifications are discussed for local dependence.

Abstract

from arXiv · show

We consider the testing and estimation of change-points -- locations where the distribution abruptly changes -- in a data sequence. A new approach, based on scan statistics utilizing graphs representing the similarity between observations, is proposed. The graph-based approach is non-parametric, and can be applied to any data set as long as an informative similarity measure on the sample space can be defined. Accurate analytic approximations to the significance of graph-based scan statistics for both the single change-point and the changed interval alternatives are provided. Simulations reveal that the new approach has better power than existing approaches when the dimension of the data is moderate to high. The new approach is illustrated on two applications: The determination of authorship of a classic novel, and the detection of change in a network over time.

1. Introduction.

High-dimensional and non-Euclidean sequences make homogeneity testing difficult, while existing multivariate methods often rely on restrictive models or kernel choices. The paper proposes a general graph-based nonparametric framework for detecting single change-points and changed intervals under an independence assumption.

  • Motivation: High-dimensional and non-Euclidean observations arise in network, image, text, and genomic sequence applications.Examples include evolving interaction networks, abrupt image events, authorship changes, and DNA-word composition changes.
  • Problem formulation: The framework addresses testing under single change-point and changed interval alternatives, where observations are partitioned into groups with distributions that differ.Multiple change-points can be decomposed into these two simple alternative types.
  • Assumptions: The theoretical analysis assumes independent observations, although the paper discusses modifications for settings with local dependence.The independence assumption enables theoretical analysis and may still provide useful results when only slightly violated.
  • Existing limitations: Existing multivariate approaches are often parametric and context specific, while kernel methods depend heavily on kernel choices and lack fast analytic false-positive control.These limitations become more consequential in moderate to high dimensions and for large data sets.
  • Contribution: The paper introduces a nonparametric approach applicable in arbitrary dimensions and to non-Euclidean data, with analytic type I error formulas.The method is illustrated on authorship and temporal network-homogeneity problems.
  • Contribution: The method gains power over applicable parametric methods as dimension increases and is implemented in the R package gSeg.The authors describe it as an off-the-shelf tool for multivariate homogeneity testing.

2. A Graph-Based Framework for Change-Point Detection.

The framework builds a similarity graph once and scans its cross-group edges across possible change locations or intervals. Standardized graph-based statistics receive analytic permutation-null calibration and family-wise error control.

  • Graph construction: The method requires only a graph representing similarity between observations, without restrictions on the sample space or their distributions.Good power requires observations from the same distribution to be globally closer than observations from the other distribution.
  • Graph-based two-sample tests: Graph-based tests treat observations as graph nodes, with edges connecting close observations; the MST statistic counts edges joining different groups.Under differing distributions, within-group edges are expected to be more common, making a low cross-group count evidence against the null.
  • Graph construction: The framework accommodates MST, minimum distance pairing, nearest-neighbor graphs, and graphs supplied independently of an underlying distance measure.Once constructed, the test statistic and permutation-null properties depend on the graph rather than the original data or distance measure.
  • Single change-point statistic: For each candidate t, R_G(t) counts graph edges connecting observations at or before t with observations after t; smaller values oppose homogeneity.The graph stays fixed while group identities change as t changes.
  • Null calibration: The null distribution is defined by permuting observation order while keeping the similarity graph fixed, and R_G(t) is standardized so values are comparable across t.The sign is inverted so large Z_G(t) values provide evidence against the null.
  • Null calibration: Analytic expectation and variance formulas under the permutation null depend on t, n, graph edge count, and node-degree information.Analogous formulas are derived for changed intervals, with combinatorial details given for the single-change statistic.
  • Illustration: In the illustrative sequence, Z_G(t) peaks at the true change-point t = 20, whereas a homogeneous sequence produces only random fluctuations and a much smaller maximum.The example uses an MST on Euclidean distance for 40 observations whose distributions change after the first 20 points.
  • Scan statistics: The scan maximizes the standardized statistic over admissible change locations or interval endpoints subject to minimum group-size constraints.The threshold is selected to control family-wise error, and domain knowledge can further restrict candidate locations.

3. Analytic Approximations to Significance Levels.

The paper derives analytic approximations for graph-based scan-statistic tail probabilities by establishing Gaussian-process and Gaussian-random-field limits, then improves them with graph- and location-dependent skewness corrections.

  • Analytic tail-probability approximations: The permutation null distributions of the single change-point and changed-interval scan statistics are approximated analytically because exact finite-sample expressions are unavailable and permutation scans can be computationally prohibitive.The changed-interval scan can require O(n^2) computation when the interval-length range is O(n).
  • Analytic tail-probability approximations: Under asymptotic graph conditions, the single change-point process converges to a Gaussian process and the changed-interval process converges to a two-dimensional Gaussian random field.These limits provide the basis for approximating the corresponding family-wise error probabilities.
  • Analytic tail-probability approximations: The approximations use graph-dependent quantities, including node-degree summaries and covariance structures, to characterize the limiting processes and their tail behavior.The paper derives covariance expressions through combinatorial analysis and uses an overshoot-related function in the asymptotic formulas.
  • Skewness correction: Skewness correction adapts to the skewness of the scan statistic at each candidate location because skewness varies with t and is stronger near the sequence ends.Universal third-moment corrections are described as too crude for this setting.
  • Simulation evidence: MDP-based scan critical values depend only on n and search-window constraints, not on data dimension or the underlying distribution.This distribution-free property follows from the fixed structure of the MDP graph.
  • Simulation evidence: The skew-corrected approximations are substantially more accurate than Gaussian approximations as dimension increases and remain accurate for small minimum window sizes.For MST and NNG, accuracy remains strong at window size 25; for MDP, it works at 25 for 0.05 significance and 50 for 0.01 significance.

4. Power Comparisons.

The simulations compare graph-based scan statistics with Hotelling’s T2 and GLR across dimensions, variance settings, graph constructions, and change sizes. Graph-based methods become especially competitive or superior as dimension increases, while retaining change-point accuracy.

  • When variance is unchanged, Hotelling’s T2 outperforms other methods for d < 150, but graph-based methods surpass it for d ≥150 and remain applicable at higher dimensions.Hotelling’s T2 is designed for multivariate normal mean shifts and becomes unavailable when dimensionality exceeds the relevant sample-size constraints.
  • When both mean and variance change, graph-based scans exceed GLR in power by d = 20 after GLR dominates at d = 1, 5, 10.The lower GLR power at moderate dimension is attributed to estimating covariance matrices separately for both segments.
  • Under log-normal data, graph-based methods outperform T2 by d = 10 and GLR even when d = 1.This scenario violates the normality assumption used by the parametric competitors.
  • MST and NNG have comparable power and dominate MDP, while denser graph variants generally improve power and graph-construction sensitivity is limited when separation is effective.MDP retains half as many edges as MST and NNG, providing one explanation for its weaker performance.
  • Graph-based power mainly depends on change size and decreases little as dimension increases, including under the high-dimensional hubbing phenomenon.Increasing the change from 1.2 at d = 100 to 2 at d = 175 increased power, while a further increase to d = 500 with change 2.5 preserved similar power.
  • Graph-based methods achieve change-point-location accuracy comparable to or better than normal-theory methods among rejected simulations.Accuracy is assessed by whether the estimated change-point falls within [80, 120].

5. Real Data Examples.

The paper applies graph-based scans to authorship evidence in Tirant lo Blanc and to daily phone-call networks. The analyses identify strong authorship-change and network-change signals, while also showing that results depend on the data representation and graph construction.

  • 5.1. Authorship Debate.: The Tirant lo Blanc analysis uses 425 chapters with more than 200 words, normalized proportions of dimensions 10 and 25, and scans three graph constructions.The two representations are word-length frequencies and context-free frequencies of the 25 most frequent words.
  • 5.1. Authorship Debate.: For the first 350 chapters, word-length data does not reject homogeneity at 0.05, whereas context-free word frequency supports a change-point with graph-dependent locations.The authors suggest context-free frequencies may be more affected by context or by evolution in the first author’s style.
  • 5.1. Authorship Debate.: The full-book authorship scans produce p-values of 0.0000 for MST and NNG on both data sets, while MDP gives 0.0042 for word length and 0.0000 for context-free frequency.The corresponding skew-corrected approximations are reported in parentheses in Figure 9’s table.
  • 5.2. Network Data.: The phone-call application bins calls by day and constructs networks on 90 subjects using edge-difference dissimilarities, with raw and normalized variants across MST, MDP, and NNG.The study covers call logs collected from July 2004 to June 2005.
  • 5.2. Network Data.: MST and NNG scans identify network change around December 19, 2004 or January 9/10, 2005, with all corresponding p-values below 0.0001.These dates are near the two ends of the winter break and suggest a shift from fall-quarter to spring-quarter calling patterns.
  • 5.2. Network Data.: MDP is nearly horizontal over a long interval because gradual network change causes it to connect neighboring observations, weakening localization of a large abrupt change.This illustrates that graph informativeness depends on the data’s change structure and the graph construction.

6. Extensions.

The paper extends graph-based scan inference to locally dependent sequences through block permutation and modifies confidence regions to better reflect single-change-point uncertainty.

  • Local dependence: Block permutation divides the sequence into blocks, permutes those blocks, and uses the resulting null distribution for locally dependent data.The standardized count and p-value are recalculated under block permutation; brute-force computation can obtain null moments for medium to small data sets.
  • Local dependence: Block permutation reached the same conclusions as ordinary permutation in all cases, although larger blocks tended to increase p-values slightly.The reduced significance reflects less homogeneous mixing from larger blocks, while p-values remained in the same regime.
  • Confidence regions: The modified confidence region tests only the subsequence opposite the estimated change-point for each candidate location.For k before the estimate, it tests the right subsequence; for k after the estimate, it tests the left subsequence.
  • Confidence regions: Cα contains the original Cox-Spjøtvoll region and is conservative, more likely to form an interval, and more reflective of precision under a single-change premise.For the word-length data, the modified 0.01 region was [281, 355], whereas the original region was {296} ∪ [298, 355].
  • Scope: The approach requires an informative dissimilarity measure, whose design should use domain knowledge to detect the signal of interest.The graph-based test separates the choice of dissimilarity from formal change-point testing, but graph quality remains critical.

7. Conclusions and Discussion.

The conclusions emphasize that graph-based scans trade some low-dimensional power for robustness and broad applicability, while their accuracy and usefulness depend on graph structure and dependence handling.

  • Conclusions: Graph-based scans decouple dissimilarity modeling from change-point testing and provide general analytic formulas for family-wise error control.Once the graph is constructed, the scan statistics depend on the graph rather than the underlying data model.
  • Conclusions: P-value approximations were quite accurate, with accuracy depending mainly on minimum group size and graph structure rather than sequence length.Hub-dominated graphs require skewness correction, while extremely star-shaped graphs may require higher-order moment adjustments.
  • Conclusions: Hub-dominated graphs can lose high-order structural information, making the graph unhelpful for distinguishing F1 from F0 and motivating alternative dissimilarities or graph constructions.This limitation arises because perturbing a hub can drastically change topology while RG(t) ignores edge interactions.
  • Conclusions: Graph-based methods use fewer assumptions than parametric approaches, sacrificing some low-dimensional power for robustness and wider applicability.In high dimensions, they gain increasing advantage over Hotelling’s T 2 as covariance estimation becomes problematic.
  • Conclusions: MST and NNG scans performed similarly, while MDP had lower power; denser graph variants increased power, although the optimal graph remains unresolved.The paper attributes MDP’s lower power to its lower density and smaller use of information from the original data.
  • Conclusions: Block permutation can improve p-values under local dependence but is computationally intensive and requires choosing a block size.When local dependence is weak, block-permutation thresholds were close to analytic thresholds based on independence.

A.2. Proof of Theorem 3.1.

The appendix proves Gaussian-process convergence for graph-based scan statistics by establishing finite-dimensional normality under permutation and bootstrap distributions.

  • Gaussian-process convergence: Finite-dimensional convergence is reduced to showing that ZG([nu1]), ..., ZG([nuK]) becomes multivariate Gaussian for fixed ordered u-values.The proof sets tk = [nuk] and studies the joint distribution as n approaches infinity.
  • Gaussian-process convergence: The permutation distribution is represented by randomly assigning observation times and retaining assignments that form a permutation.This connects permutation sampling to a two-step bootstrap construction used in the proof.
  • Gaussian-process convergence: Under the bootstrap distribution, the relevant finite-dimensional vector is multivariate normal and its covariance matrix is characterized.Lemma A.1 states this result for ordered u-values under the stated conditions.
  • Gaussian-process convergence: Conditioning on bootstrap counts establishes equivalence with the permutation distribution, yielding multivariate Gaussianity for the graph scan process.The argument uses the conditional normality of bootstrap variables and identifies the resulting distribution with the permutation distribution.
  • Normal approximation: Stein’s method controls the normal approximation through local dependence neighborhoods determined by graph edges.The proof verifies the required dependence assumption for the sets Se and Te and bounds the approximation error δ.
  • Normal approximation: The approximation error vanishes under graph-size and neighborhood-growth conditions, including |G| = o(n^2) in the stated lemma.The proof bounds neighborhood sizes and derives conditions under which δ tends to zero.

A.3. Proof of Lemma 3.3.

The lemma’s proof derives the covariance structure of graph-based scan statistics by enumerating how graph edges overlap across two scan locations.

  • Covariance calculation: Joint edge-count terms are classified by whether two edges share endpoints or have four distinct endpoints.The resulting probabilities are represented by q1(s,t), q2(s,t), and q3(s,t).
  • Covariance calculation: Combining the overlap probabilities with graph size yields the covariance expression for the scan statistics.The proof then obtains the corresponding variance expression for RG(t) by an analogous calculation.
  • Proof strategy: The single-change-point case is handled using Woodroofe’s method by conditioning on the first cross-over.This supplies the starting point for the scan-statistic argument.

A.4. Proof of Proposition 3.4.

The proof derives the changed-interval result by relating endpoint perturbations to one-change-point processes, then passing a discrete summation to an integral. It also uses asymptotic order arguments and differentiability conditions.

  • As b →∞, terms are classified by their asymptotic orders so negligible contributions can be discarded in the approximation.The proof distinguishes quantities that are o(b^2) from those of order O(b).
  • The derivation handles the changed-interval case using the methods of Siegmund, while omitting most technical details.The proof notes that the required function is differentiable with a continuous derivative except at δ1 = 0 and δ2 = 0.
  • Endpoint perturbation processes are shown to be identical in distribution to a corresponding one-change-point process under the permutation null.This symmetry lets the changed-interval calculation reuse the one-change-point derivative structure.
  • The partial derivatives in the changed-interval expression are matched to the one-change-point derivative, yielding the stated limiting formula.The double summation is converted to an integral as n →∞.

B.1. Derivation of (3.13) and (3.15).

The derivation improves tail-probability approximations by exponential tilting and skewness correction. It approximates the tilted distribution locally by a normal density and expands the cumulant function to obtain formulas for θb and the p-value correction.

  • The tilted probability near b + dx/b is approximated using a normal density, with accuracy established for x/b →0.The local approximation is the basis for the subsequent tail calculation.
  • Taylor expansions of ψ around zero are combined to derive the skewness-adjusted approximation formulas.The derivation uses ψ(0) = ψ̇(0) = 0 and ψ̈(0) = 1 before combining the component approximations.
  • An approximation to θb is obtained by solving ψ̇(θb) after truncating ψ at third order.When γ = 0, the approximation reduces to θb = b.
  • The changed-interval formula is derived similarly, incorporating skewness to improve the approximation of P(ZG(t1,t2) ∈ b + dx/b).

B.2. Effect of Skewness and Extrapolation at Boundaries.

The section examines how graph structure affects skewness corrections and explains boundary extrapolation when the correction quantities are undefined. High-dimensional MST and NNG graphs can become hub-dominated and left-skewed.

  • For an MDP graph with n = 1000 and b = 3, γ is positive throughout, indicating right skewness and implying θb < b.Under right skewness, the Gaussian p-value approximation is smaller than the actual p-value, motivating skewness correction.
  • As dimension increases, Euclidean MST and NNG graphs become hub-dominated and ZG(t) becomes left-skewed.In this regime, γ ≤0, θb ≥b, and S ≤1.
  • When γ is smaller than −1/(2b), the current approximation may not yield a real-valued θb, so the paper uses a heuristic extrapolation procedure.This is a limitation of the skewness approximation in sufficiently left-skewed settings.
  • For a 100-dimensional Euclidean MST, θb,G(t) and SG(t) are undefined outside the middle region, so the integrand is extended to the edges using boundary tangents.Negative extrapolated values are set to zero; Figure 16 displays the integrand before and after extrapolation.

C.1. Critical Value.

The critical-value experiments compare Gaussian and skewness-corrected analytic p-value approximations for single change-point and changed-interval scans. Skewness correction is generally more accurate, especially as dimension increases, while remaining effective for small windows.

  • Single Change-Point Alternative (NNG): NNG-based single change-point p-value approximations produce results quite similar to those based on MST.
  • Changed-Interval Alternative: The skewness-corrected approximation performs much better than the Gaussian approximation, especially when data dimension increases.This conclusion holds for the changed-interval experiments and is consistent with the single change-point results.
  • Changed-Interval Alternative: The accuracy of the skewness-corrected approximation does not degrade significantly with dimension.
  • Changed-Interval Alternative: The skewness-corrected approximation performs well for MST- and NNG-based tests when the smallest window size is 25 at significance levels 0.05 and 0.01.The reported critical-value settings include both single change-point and changed-interval scans.

D.1. Authorship Data.

This section presents block-permutation results for the authorship data across scans of the entire book and its first 350 chapters, alongside results for phone-call network data.

  • Scan over the Entire Book: Block-permutation plots for the authorship data scan the entire book with block sizes 2 and 10.
  • Scan over the First 350 Chapters: The authorship analysis is also repeated using only the first 350 chapters under block sizes 2, 5, and 10.
  • Scan over the First 350 Chapters: A table reports p-values from 10,000 block permutations for the authorship data restricted to the first 350 chapters.
  • Phone Call Network Data: The phone-call network analysis reports block-permutation results using block sizes 2, 5, and 10, with corresponding p-values tabulated.
Loading 1209.1625v3…