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

You are here

Top Reasons to Join SPS Today!

1. IEEE Signal Processing Magazine
2. Signal Processing Digital Library*
3. Inside Signal Processing Newsletter
4. SPS Resource Center
5. Career advancement & recognition
6. Discounts on conferences and publications
7. Professional networking
8. Communities for students, young professionals, and women
9. Volunteer opportunities
10. Coming soon! PDH/CEU credits
Click here to learn more.

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

Bernardo Marenco; Paola Bermolen; Marcelo Fiori; Federico Larroca; Gonzalo Mateos

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.

SPS on Twitter

  • Join Dr. Peilan Wang and Dr Jun Fang for "Channel State Information Acquisition for Intelligent Reflecting Surface-…
  • The SPS Webinar Series continues on Monday, 10 October when Dr. Luisa Verdoliva presents "Media Forensics and DeepF…
  • DEADLINE EXTENDED: The IEEE Transactions on Multimedia is accepting submissions for a Special Issue on Point Cloud…
  • Short courses return to ! Register for live and remote sessions, "A Hands-on Approach for Implementing Sto…
  • Join Dr. Sabyasachi Ghosh on Wednesday, 21 September for a new SPS Webinar, “Tapestry: A Compressed Sensing Approac…

SPS Videos

Signal Processing in Home Assistants


Multimedia Forensics

Careers in Signal Processing             


Under the Radar