RING-CPD: Asymptotic Distribution-free Change-point Detection for Multivariate and Non-Euclidean Data

Change-point detection (CPD) concerns detecting distributional changes in a sequence of independent observations. Among nonparametric methods, rank-based methods are attractive due to their robustness and efficiency and have been extensively studied for univariate data. However, they are not well explored for high-dimensional or non-Euclidean data. In this paper, we propose a new method, Rank INduced by Graph Change-Point Detection (RING-CPD), based on graph-induced ranks to handle high-dimensional and non-Euclidean data. The new method is asymptotically distribution-free under the null hypothesis with an analytic p-value approximation derived for fast type-I error control. Extensive simulation studies show that the RING-CPD method works well for a wide range of alternatives and is robust to heavy-tailed distribution or outliers. The new method is illustrated by the detection of seizures in a functional connectivity network dataset and travel pattern changes in the New York City Taxi dataset.