# Online Change Point Detection for Weighted and Directed Random Dot Product Graphs

arXiv: https://arxiv.org/abs/2201.11222 · HTML: https://mlsanity.com/paper/2201.11222/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 43 references that are in the map.
- First posted on arXiv 26 Jan 2022.

## Builds on (most cited first, 14 of 14)

- [Statistical inference on random dot product graphs: a survey](https://mlsanity.com/paper/1709.05454/) (2017)
- [A statistical interpretation of spectral embedding: the generalised random dot product graph](https://mlsanity.com/paper/1709.05506/) (2017)
- [GraSPy: Graph Statistics in Python](https://mlsanity.com/paper/1904.05329/) (2019)
- [Detecting change points in the large-scale structure of evolving networks](https://mlsanity.com/paper/1403.0989/) (2014)
- [Sequential change-point detection based on nearest neighbors](https://mlsanity.com/paper/1604.03611/) (2016)
- [Semiparametric spectral modeling of the Drosophila connectome](https://mlsanity.com/paper/1705.03297/) (2017)
- [Robust Estimation from Multiple Graphs under Gross Error Contamination](https://mlsanity.com/paper/1707.03487/) (2017)
- [Change point localization in dependent dynamic nonparametric random dot product graphs](https://mlsanity.com/paper/1911.07494/) (2019)
- [Optimal network online change point localisation](https://mlsanity.com/paper/2101.05477/) (2021)
- [Connectome Smoothing via Low-rank Approximations](https://mlsanity.com/paper/1609.01672/) (2016)
- [Sequential change-point detection in high-dimensional Gaussian graphical models](https://mlsanity.com/paper/1806.07870/) (2018)
- [A Random Dot Product Model for Weighted Networks](https://mlsanity.com/paper/1611.02530/) (2016)
- [Network topology change-point detection from graph signals with prior spectral signatures](https://mlsanity.com/paper/2010.11345/) (2020)
- [Distributed Change Detection in Streaming Graph Signals](https://mlsanity.com/paper/1910.06561/) (2019)

## Built on by (most cited first, 6 of 6)

- [Graph Filters for Signal Processing and Machine Learning on Graphs](https://mlsanity.com/paper/2211.08854/) (2022)
- [Gradient-Based Spectral Embeddings of Random Dot Product Graphs](https://mlsanity.com/paper/2307.13818/) (2023)
- [Weighted Random Dot Product Graphs](https://mlsanity.com/paper/2505.03649/) (2025)
- [LASE: Learned Adjacency Spectral Embeddings](https://mlsanity.com/paper/2412.17734/) (2024)
- [Grassmanian Interpolation of Low-Pass Graph Filters: Theory and Applications](https://mlsanity.com/paper/2510.23235/) (2025)
- [Subspace Projection Methods for Fast Spectral Embeddings of Evolving Graphs](https://mlsanity.com/paper/2603.19439/) (2026)

## Abstract (arXiv)

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.