Change Point Detection for Data with Network Structure

检测驱动数据生成机制中的中断和异常是一项关键任务，因为在包括健康、社会和工程科学在内的高影响力领域有许多应用。该项目旨在通过开发一个简单实现、功能强大、可扩展的算法框架，推动大数据和复杂数据的变化点分析技术的发展，从而提供新的工具来检查高维、长流的感兴趣的事件。该项目的潜在应用领域包括但不限于大脑连接数据集的癫痫发作，经济和金融数据中的协调市场和其他系统性故障，以及计算机网络流中精心策划的恶意活动的识别。开发的算法和方法将在开源软件中实现，而经过整理的数据集将向社区提供，用于变化点分析调查。该项目将为未来一代统计学家的跨学科研究培训和进一步加强数学科学的多样性提供多种独特的机会。为了实现既定目标，该项目(i)为网络和高维时间流的复杂统计模型中的变化点开发了统一的检测框架，（ii）以一致性、有限样本边界和变化点和其他模型参数的渐近分布的形式对其准确性进行了严格的理论分析。该框架利用一种简单、易于实现的两步策略，其中第一步选择适当长度的时间序列窗口，并使用标准穷举搜索策略在每个窗口中最多识别一个变化点。第二步，采用基于全局信息准则的二次搜索来消除虚假的变化点。该策略在时间上表现出线性复杂性（因此与文献中最快的策略相匹配），但易于实现和理论分析，特别是对于表现出网络和低秩结构的复杂统计模型。此外，严格解决了以下问题：(i)模型参数和变化点的可识别性条件；（ii）在高维、网络结构、时间依赖性以及数据流之间的依赖性存在的情况下，它们的概率保证和不确定性量化。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Detecting breaks and anomalies in a mechanism that drives the generation of data represents a critical task, due to numerous applications in high-impact areas including health, social, and engineering sciences. This project aims to advance the state of the art of change point analysis for big and complex data, by developing a simple to implement, yet powerful, scalable algorithmic framework, thus providing new tools to examine high-dimensional, long streams for events of interest. The potential application domains of this project include but not limited to occurrence of seizure in brain connectivity data sets, coordinated market and other systemic failures in economic and finance data, and identification of orchestrated malicious activities in computer network streams. The developed algorithms and methodology will be implemented in open-source software, while curated data sets will be made available to the community for use in change point analysis investigations. The project will offer multiple unique opportunities for interdisciplinary research training of the future generation of statisticians and for further enhancement of diversity in mathematical sciences.To achieve the stated goals, the project (i) develops a unified detection framework for change points in complex statistical models for network and high dimensional time streams and (ii) provides a rigorous theoretical analysis of their accuracy in the form of consistency, finite sample bounds, and asymptotic distributions for the change points and other model parameters. The framework leverages a simple, easy to implement two-step strategy, wherein the first step one selects windows of the time series of appropriate length and using a standard exhaustive search strategy identifies at most a single change point in each of them. In the second step, a second search based on a global information criterion is employed to eliminate spurious change points. The strategy exhibits linear complexity in time (and thus matches the fastest available in the literature), yet is simple to implement and theoretically analyze, in particular for complex statistical models that exhibit network and low rank structure. Further, the following issues are rigorously addressed: (i) conditions of identifiability of the model parameters and the change points and (ii) probabilistic guarantees and uncertainty quantification for them in the presence of high dimensionality, network structure, temporal dependence, as well as dependence across data streams.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.