DIstributed Change Point Detection in Streaming Manifold-Valued Signals Over Graphs

Xiuheng Wang, Ricardo Augusto Borsoi, Cédric Richard, André FerrariACSSC 2023 · DOI

Introduction

Detecting abrupt changes in data streams is a fundamental challenge in signal processing. While traditional change point detection (CPD) algorithms typically operate in Euclidean space, many modern applications—such as brain connectivity analysis or video descriptor processing—involve data that resides on non-Euclidean, curved Riemannian manifolds. Furthermore, when these signals are observed across a network, changes often manifest within specific communities or clusters of nodes.

This paper addresses the need for a CPD framework that is simultaneously manifold-aware, graph-aware, and fully distributed. The proposed method enables decentralized networks to detect localized shifts in data distributions without the need for a central processing unit.

Proposed Framework

The authors introduce Algorithm 2, a three-stage distributed framework designed for manifold-valued signals on graphs:

  1. Local Manifold Statistics: Each node maintains two recursive estimates of the Karcher mean (the Riemannian average) of its incoming data stream. One estimate uses a small step size for long-term stability, while the other uses a larger step size for rapid adaptation. The Riemannian distance between these two "two-speed" estimators serves as a local anomaly score.
  2. Graph Filtering (GFSS): To leverage the network structure, a Graph Fourier Scan Statistic (GFSS) is applied. This process smooths local anomaly scores across the graph, amplifying signals from coordinated changes within communities while suppressing isolated stochastic noise.
  3. Distributed Implementation: To ensure scalability, the global graph filter is implemented via a parallel ARMA (AutoRegressive Moving Average) filter. This allows nodes to update their detection status using only local communication with immediate neighbors, avoiding costly global eigen-decompositions.

Experimental Evaluation

The framework was validated using a synthetic dataset designed to mimic complex network interactions. The testbed consisted of a graph with 250 nodes and 2,508 edges, structured into eight distinct communities.

The experimental graph topology featuring 250 nodes organized into 8 distinct communities.

The signals consisted of streaming $6 \times 6$ Symmetric Positive Definite (SPD) matrices, which are commonly used to represent covariance in signal processing. An abrupt change was simulated by shifting the distribution of matrices within a single community at a specific time step.

Results and Discussion

The proposed method (Algorithm 2) was compared against two baselines: a Euclidean-based graph detector (daGFSS) and a node-by-node manifold detector that ignores graph topology (Algorithm 1).

Comparison of mean detection delay versus false alarm rate for the proposed Algorithm 2 and baselines.

As shown in the performance analysis, Algorithm 2 significantly outperforms the baselines, achieving a lower mean detection delay for any given false alarm rate. The results highlight two key insights:

  • Geometric Accuracy: Accounting for the Riemannian geometry of SPD matrices is crucial; treating them as Euclidean vectors leads to significant performance degradation.
  • Community Awareness: By aggregating information through graph filters, the algorithm successfully identifies subtle changes that are statistically invisible to individual nodes acting in isolation.

Conclusion

This work demonstrates that combining Riemannian statistics with distributed graph filtering provides a robust and scalable solution for CPD in networked systems. Future research will focus on extending this framework to dynamic graphs where node connectivity evolves over time and automating the tuning of filter parameters for diverse manifold types.

Summary updated

BibTeX
@inproceedings{wang2023distributed,
  author = {Xiuheng Wang and Ricardo Augusto Borsoi and Cédric Richard and André Ferrari},
  title = {{DIstributed Change Point Detection in Streaming Manifold-Valued Signals Over Graphs}},
  booktitle = {ACSSC},
  year = {2023},
  doi = {10.1109/ieeeconf59524.2023.10477092},
}
Figure