Title
Graph-Based Change-Point Detection
Speaker
Hao Chen, Stanford University
Abstract
After observing snapshots of a network, can we tell if there has been a change in dynamics? After reading chapters of a historical text, can we tell if there has been a change in authorship? Given a sequence of independent observa- tions, we are concerned with testing the null hypothesis of homogeneity versus change-point alternatives, where a segment of the sequence differs in distribu- tion from the rest. This problem has been well studied for observations in low dimension. Currently, many problems can be formulated in the change-point framework but with observations that are high-dimensional or non-Euclidean, where existing methods are limited. We develop a general nonparametric frame- work for change-point detection that relies on a distance metric on the sample space of observations. This new approach, which relies on graph-based tests, can be applied to high dimensional data, as well as data from non-Euclidean sample spaces. An analytic approximation for the false positive error probabil- ity is derived and shown to be reasonably accurate by simulation. We illustrate the method through the analysis of a phone-call network from the MIT Reality Mining project and of the authorship debate of a classic western novel.
