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:
- 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.
- 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.
- 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 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).
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