Asymptotic distribution-free change-point detection for data with repeated observations

Change-point analysis plays a significant role in various fields when a sequence of observations is collected. In general, the problem concerns testing whether or not a change has occurred, or several changes might have occurred, and identifying the locations of any such changes. In this paper, we consider the offline change-point detection problem where a sequence of independent observations $\{y_{i}\}_{i=1,\ldotp\ldotp\ldotp,n}$ is completely observed at the time when data analysis is conducted. Here, $n$ is the length of the sequence, and $i$ is the time index or other meaningful index depending on the specific application. We consider testing the null hypothesis

against the single change-point alternative

or the changed-interval alternative

where $F_{0}$ and $F_{1}$ are two different distributions.

This problem has been extensively studied for univariate data; see Chen & Gupta (2011) for a survey. However, in many modern applications, $y_{i}$ is high-dimensional or even non-Euclidean. For high-dimensional data, most methods are based on parametric models; see for example Zhang et al. (2010); Wang et al. (2017); Wang & Samworth (2018). To apply these methods, the data sequence needs to follow specific parametric models. In the nonparametric domain, Harchaoui et al. (2009) made use of kernel methods, Lung-Yut-Fong et al. (2011) utilized marginal rankings, and Matteson & James (2014) made use of distances among observations. These methods can be applied to a wider range of problems than parametric methods. However, it is in general difficult to conduct theoretical analysis on nonparametric methods and none of these nonparametric methods provides analytic formulas for false discovery control, making them difficult to be applied to large datasets.

Recently, Chen & Zhang (2015) and Chu & Chen (2019) developed a graph-based framework to detect the change-point for high-dimensional and non-Euclidean data sequences. This framework is based on a similarity graph $G$, such as a minimum spanning tree (MST), which is a spanning tree that connects all observations with the sum of distances of the edges in the tree minimized, constructed on the sample space. Based on $G$ over $t$, test statistics rely on three basic quantities, $R_{0,G}(t)$, $R_{1,G}(t)$, and $R_{2,G}(t)$, where for each $t$ $R_{0,G}(t)$ is the number of edges connecting observations before and after $t$, $R_{1,G}(t)$ is the number of edges connecting observations prior to $t$, and $R_{2,G}(t)$ is the number of edges connecting observations after $t$. Then, four scan statistics were studied: the original edge-count scan statistic $Z(t)$, the weighted edge-count scan statistic $Z_{w}(t)$, the generalized edge-count scan statistic $S(t)$, and the max-type edge-count scan statistic $M(t)$ that can be applied to various alternatives. For detailed comparisons, see Chu & Chen (2019).

While the methods proposed by Chen & Zhang (2015) and Chu & Chen (2019) work well for continuous data, they are problematic for data with repeated observations, which is common for discrete data, such as network data. The reason is that these methods depend on the similarity graph constructed on observations. When there are repeated observations, the similarity graph is in general not uniquely defined and these methods are troublesome. For example, Chen & Zhang (2015) analyzed a phone-call network dataset and the task was to test whether there is any change in the dynamics of the networks over time. In this dataset, a few networks in the sequence are exactly the same. Chen & Zhang (2015) used the MST as the similarity graph. More specifically, in the phone-call network dataset, there are in total 330 networks $\{y_{1},\ldots,y_{330}\}$ in the sequence and among them are 290 distinct networks. For example, $y_{1}$, $y_{6}$, $y_{16}$ are exactly the same. All repeated observations are listed in Supplement A. Due to this, there are numerous ways in assigning edges in the MST with repeated observations. Hence, the MST is not uniquely defined and existing graph-based methods are not reliable since they are formulated by the unique similarity graph on pooled observations.

Table 1 lists test statistics and their corresponding $p$-values of four testing procedures proposed in Chen & Zhang (2015) and Chu & Chen (2019) on three randomly chosen MSTs. We see that the $p$-value depends heavily on the choice of the MST: It could be very small under one MST, but very large on another MST, leading to completely different conclusions on whether the sequence is homogeneous or not. Moreover, since the number of possible MSTs is huge, it is impractical to compute the test statistics on all possible MSTs directly to get a summary.

We extend the methods in Chen & Zhang (2013) and Zhang & Chen (2017) to the change-point settings and propose new graph-based testing procedures that can deal with repeated observations properly. This work fills the gap for the graph-based framework in dealing with discrete data. We show that the new tests are asymptotically distribution-free under the null hypothesis of no change and reveal that the limiting distributions for two approaches in Chen & Zhang (2013) are the same, even for continuous data. We also derive analytic formulas to approximate permutation $p$-values for those modified test statistics, making them fast applicable to real datasets. To improve the analytical $p$-value approximations for finite sample sizes, skewness correction is also performed. We show that the proposed tests work well to detect the change when the data has repeated observations. We illustrate the new testing procedures through an analysis on phone-call network dataset. The new methods are implemented in an R package gSeg available on CRAN.

Here, we focus on extending the weighted, generalized, and max-type test statistics for repeated observations, which will turn out to be the asymptotic distribution-free tests. Details for extending the original edge-count test is in Supplement E. Based on the two-sample test statistics in Chen & Zhang (2013) and Zhang & Chen (2017), we could define the extended basic quantities at time $t$ under the averaging approach as follows:

and under the union approach as follows:

These are discrete data version of $R_{1,G}(t)$ and $R_{2,G}(t)$ to address infeasibility of computing test statistics in data with repeated observations. Hence, relatively large value of the sum of $R_{1,(a)}(t)$ and $R_{2,(a)}(t)$ or $R_{1,(u)}(t)$ and $R_{2,(u)}(t)$ could be the evidence against the null hypothesis.

Under the null hypothesis $H_{0}$ (1), the null distribution is defined to be the permutation distribution, which places $1/n!$ probabilities on each of the $n!$ permutations of $\{y_{i}\}_{i=1,\ldotp\ldotp\ldotp,n}$. With no further specification, pr, $E$, var, and cov denote the probability, the expectation, the variance, and the covaraince, respectively, under the permutation null distribution. Then, analytic formulas for the expectation and the variance of extended basic quantities can be calculated through combinatorial analysis and detailed expressions and proof can be found in Supplement C.

For any candidate value $t$ of $\tau$, the extended test statistics can be defined as

where

with $w(t)=(t-1)/(n-2)$. Relatively large values of test statistics are the evidence against the null.

Based on the extended statistics, we could define the scan statistics for the single change-point alternative to handle data with repeated observations as follows:

1. 1.

   Extended weighted edge-count scan statistic: $\max_{n_{0}\leq t\leq n_{1}}Z_{w,(a)}(t)$  &  $\max_{n_{0}\leq t\leq n_{1}}Z_{w,(u)}(t)$,

2. 2.

   Extended generalized edge-count scan statistic: $\max_{n_{0}\leq t\leq n_{1}}S_{(a)}(t)$  &  $\max_{n_{0}\leq t\leq n_{1}}S_{(u)}(t)$,

3. 3.

   Extended max-type edge-count scan statistic: $\max_{n_{0}\leq t\leq n_{1}}M_{(a)}(t)$  &  $\max_{n_{0}\leq t\leq n_{1}}M_{(u)}(t)$,

where $n_{0}$ and $n_{1}$ are set to be pre-specified values. For example, we can set $n_{0}=\lceil 0.05n\rceil$ and $n_{1}=n-n_{0}$ in order to contain enough observations to represent the distribution.

Each scan statistic has its own characteristics aimed for different situations (see Section 5 for a comparison of them). For example, the extended weighted edge-count test is useful when a change-point occurs away from the middle of the sequence. The extended generalized edge-count test is effective under both location and scale alternatives. The extended max-type edge-count test is similar but gives more accurate $p$-value approximation. The null hypothesis is rejected if the maxima is greater than a certain threshold. How to choose the threshold to control the type I error rate is described in Section 4.

For illustration, Figure 1 plots the processes of $S_{(a)}(t)$ and $S_{(u)}(t)$ for the first 50 observation generated from Multinomial$\left(10,(0.2,0.3,0.3,0.2)^{T}\right)$ and the second 50 observations generated from Multinomial$\left(10,(0.4,0.3,0.2,0.1)^{T}\right)$ with $C_{0}$ the nearest neighbor link constructed on the Euclidean distance. We see that both $S_{(a)}(t)$ and $S_{(u)}(t)$ peak at the true change-point $\tau=50$ (left panel). On the other hand, when there is no change-point, $S_{(a)}(t)$ and $S_{(u)}(t)$ have random fluctuations with smaller maximum values (right panel). Illustrations of other test statistics are provided in Supplement D.

For testing the null $H_{0}$ (1) against the changed-interval alternative $H_{2}$ (3), test statistics can be derived in a similar way to the single change-point case. For example, the extended generalized edge-count scan statistics are

for the averaging and union approaches, respectively, where $S_{(a)}(t_{1},t_{2})$ and $S_{(u)}(t_{1},t_{2})$ are the extended generalized edge-count statistics on the two samples: observations within $[t_{1},t_{2})$ and observations outside $[t_{1},t_{2})$. The details of all statistics for the changed-interval alternative are in Supplement F.

We first consider the averaging approach. We are concerned with the tail distribution of the scan statistics under $H_{0}$. Take the extended generalized edge-count scan statistic as an example, we want to compute

for the single change-point alternative, and

for the changed-interval alternative.

Under the null hypothesis, the scan statistics are defined as the permutation distribution. For small sample size $n$, we can directly sample from the permutation distribution to compute the permutation $p$-value. However, when $n$ is large, one needs to draw a large number of random permutations to get a good estimate of the $p$-value, which is very time consuming. Hence, we seek to derive analytic approximations to these tail probabilities.

By the definition of $Z_{w,(a)}(t)$, $S_{(a)}(t)$, and $M_{(a)}(t)$, stochastic processes $\{Z_{w,(a)}(t)\}$, $\{S_{(a)}(t)\}$, and $\{M_{(a)}(t)\}$ boil down to two pairs of basic processes: $\{Z_{w,(a)}(t)\}$ and $\{Z_{d,(a)}(t)\}$ for the single change-point case and $\{Z_{w,(a)}(t_{1},t_{2})\}$ and $\{Z_{d,(a)}(t_{1},t_{2})\}$ for the changed-interval case in the similar way. Therefore, we first study the properties of these basic stochastic processes. Let $\mathcal{E}_{u}^{C_{0}}$ be the subgraph of $C_{0}$ containing all edges that connect to node $u$, $\mathcal{E}_{u,2}$ be the set of edges in $C_{0}$ that contains at least one node in $\mathcal{E}_{u}^{C_{0}}$, and $|\mathcal{E}_{u}^{C_{0}}|$ and $|\mathcal{E}_{u,2}^{C_{0}}|$ be the number of edges in the sets. To derive the asymptotic behavior of the stochastic processes in averaging approach, we work under the following conditions:

Let $[x]$ denotes the largest integer that is no larger than $x$.

The proof for this theorem uses the technique developed in Chen & Zhang (2015) that utilizes the Stein’s method (Chen & Shao, 2005). The details of the proof are in Supplement G.

Let $\rho_{w,(a)}^{*}(u,v)=\text{cov}(Z_{w,(a)}^{*}(u),Z_{w,(a)}^{*}(v))$ and $\rho_{d,(a)}^{*}(u,v)=\text{cov}(Z_{d,(a)}^{*}(u),Z_{d,(a)}^{*}(v))$. The next theorem states explicit expressions for the covariance functions of the limiting Gaussian process, $\{Z_{w,(a)}^{*}(w),\ 0<w<1\}$ and $\{Z_{d,(a)}^{*}(w),\ 0<w<1\}$. It is proved through combinatorial analysis and details are given in Supplement H.

For the union approach, let $\bar{G}$ be the set of graphs that the union of all possible optimal graphs between observations $\{y_{i}\}$, $\mathcal{E}_{i}^{\bar{G}}$ be the subgraph of $\bar{G}$ containing all edges that connect to node $y_{i}$, and $|\mathcal{E}_{i}^{\bar{G}}|$ be the number of edges in the set. We work under

The details of the proof are in Supplement I.

Let $\rho_{w,(u)}^{*}(u,v)=\text{cov}(Z_{w,(u)}^{*}(u),Z_{w,(u)}^{*}(v))$ and $\rho_{d,(u)}^{*}(u,v)=\text{cov}(Z_{d,(u)}^{*}(u),Z_{d,(u)}^{*}(v))$. The next theorem states explicit expressions for the covariance functions of the limiting Gaussian processes, $\{Z_{w,(u)}^{*}(w),\ 0<w<1\}$, and $\{Z_{d,(u)}^{*}(w),\ 0<w<1\}$. Its proof is in Supplement J.

We now examine the asymptotic behavior of tail probabilities. Following similar arguments in the proof for Proposition 3.4 in Chen & Zhang (2015), we can obtain the foundation for analytical approximations to the probabilities. Assume that $n_{0},n_{1},n,b\rightarrow\infty$ in a way such that for some $0<x_{0}<x_{1}<1$ and $b_{1}>0$, $n_{0}/n\rightarrow x_{0},\ n_{1}/n\rightarrow x_{1},\ b/\surd{n}\rightarrow b_{1}$.

Based on Theorem 4.5 and 4.11, as $n\rightarrow\infty$, for both averaging and union approaches, we have

where $\nu(s)\approx(2/s)\left\{\Phi(s/2)-0.5\right\}/\left\{(s/2)\Phi(s/2)+\phi(s/2)\right\}$ (Siegmund & Yakir, 2007) with $\Phi(\cdot)$ and $\phi(\cdot)$ being the standard normal cumulative density function and probability density function, respectively, and

It can be shown that $h_{w}^{*}(x)=\left\{x(1-x)\right\}^{-1}$ and $h_{d}^{*}(x)=\left\{2x(1-x)\right\}^{-1}$.

Since $Z_{w,(a)}^{*}(t)$ and $Z_{d,(a)}^{*}(t)$ are independent and $Z_{w,(u)}^{*}(t)$ and $Z_{d,(u)}^{*}(t)$ are independent, for both averaging and union approaches, we have

In addition, following similar arguments in the proof for Proposition 4.4 in Chu & Chen (2019), we obtain the analytical $p$-value approximations for the extended generalized edge-count test. Assume that $n_{0},n_{1},n,b_{S}\rightarrow\infty$ in a way such that for some $0<x_{0}<x_{1}<1$ and $b_{2}>0$, $n_{0}/n\rightarrow x_{0},\ n_{1}/n\rightarrow x_{1},\ b_{S}/n\rightarrow b_{2}$. Then, as $n\rightarrow\infty$, for both averaging and union approaches, we have

where $h_{s}^{*}(x,w)=h_{d}^{*}(x)\cos^{2}(w)+h_{w}^{*}(x)\sin^{2}(w)$. The analytical $p$-value approximations for the changed-interval are in Supplement M.