Online Change Point Detection for Weighted and Directed Random Dot Product Graphs
Given a sequence of random (directed and weighted) graphs, we address the problem of online monitoring and detection of changes in the underlying data distribution. Our idea is to endow sequential change-point detection (CPD) techniques with a graph representation learning substrate based on the versatile Random Dot Product Graph (RDPG) model. We consider efficient, online updates of a judicious monitoring function, which quantifies the discrepancy between the streaming graph observations and the nominal RDPG. This reference distribution is inferred via spectral embeddings of the first few graphs in the sequence. We characterize the distribution of this running statistic to select thresholds that guarantee error-rate control, and under simplifying approximations we offer insights on the algorithm's detection resolution and delay. The end result is a lightweight online CPD algorithm, that is also explainable by virtue of the well-appreciated interpretability of RDPG embeddings. This is in stark contrast with most existing graph CPD approaches, which either rely on extensive computation, or they store and process the entire observed time series. An apparent limitation of the RDPG model is its suitability for undirected and unweighted graphs only, a gap we aim to close here to broaden the scope of the CPD framework. Unlike previous proposals, our non-parametric RDPG model for weighted graphs does not require a priori specification of the weights' distribution to perform inference and estimation. This network modeling contribution is of independent interest beyond CPD. We offer an open-source implementation of the novel online CPD algorithm for weighted and direct graphs, whose effectiveness and efficiency are demonstrated via (reproducible) synthetic and real network data experiments.
Code (1)
Tasks
Change Point DetectionGraph Representation LearningRepresentation LearningTime Series AnalysisSimilar Papers 제목 키워드 기반
Fast Online Changepoint Detection
We study online changepoint detection in the context of a linear regression model. We propose a class of heavily weighted statistics based on the CUSUM process of the regression residuals, which are specifically designed…
regressionTime SeriesSequential online prediction in the presence of outliers and change points: an instant temporal structure learning approach
In this paper, we consider sequential online prediction (SOP) for streaming data in the presence of outliers and change points. We propose an INstant TEmporal structure Learning (INTEL) algorithm to address this problem.…
Anomaly DetectionNEWMA: a new method for scalable model-free online change-point detection
We consider the problem of detecting abrupt changes in the distribution of a multi-dimensional time series, with limited computing power and memory. In this paper, we propose a new, simple method for model-free online ch…
Change Point DetectionTime SeriesTime Series AnalysisOnline Identification of Time-Varying Systems Using Excitation Sets and Change Point Detection
In this work, we first show that the problem of parameter identification is often ill-conditioned and lacks the persistence of excitation required for the convergence of online learning schemes. To tackle these challenge…
Change Point DetectionGaussian Derivative Change-point Detection for Early Warnings of Industrial System Failures
An early warning of future system failure is essential for conducting predictive maintenance and enhancing system availability. This paper introduces a three-step framework for assessing system health to predict imminent…
Change Point Detection