High-Dimensional Change Point Detection using Graph Spanning Ratio

• URL: http://arxiv.org/abs/2512.07541v1
• Date: Mon, 08 Dec 2025 13:22:25 GMT
• Title: High-Dimensional Change Point Detection using Graph Spanning Ratio
• Authors: Youngwen Sun, Katerina Papagiannouli, Vladimir Spokoiny,
• Abstract summary: Inspired by graph-based methodologies, we introduce a novel graph-spanning algorithm designed to identify changes in both offline and online data.<n>We demonstrate that the algorithm achieves high detection power when the magnitude of the change surpasses the lower bound of the minimax separation rate.
• Score: 0.764671395172401
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Inspired by graph-based methodologies, we introduce a novel graph-spanning algorithm designed to identify changes in both offline and online data across low to high dimensions. This versatile approach is applicable to Euclidean and graph-structured data with unknown distributions, while maintaining control over error probabilities. Theoretically, we demonstrate that the algorithm achieves high detection power when the magnitude of the change surpasses the lower bound of the minimax separation rate, which scales on the order of $\sqrt{nd}$. Our method outperforms other techniques in terms of accuracy for both Gaussian and non-Gaussian data. Notably, it maintains strong detection power even with small observation windows, making it particularly effective for online environments where timely and precise change detection is critical.

Related papers

• Learning Time-Varying Graphs from Incomplete Graph Signals [1.7430416823420511]
  We develop an efficient Alternating Direction Multiplier algorithm for solving the problem of imputing missing data from a graph.<n>We prove that the proposed ADMM scheme converges to and we derive a stationary point.
  arXiv  Detail & Related papers  (2025-10-19T11:12:13Z)
• Mitigating Over-Squashing in Graph Neural Networks by Spectrum-Preserving Sparsification [81.06278257153835]
  We propose a graph rewiring method that balances structural bottleneck reduction and graph property preservation.<n>Our method generates graphs with enhanced connectivity while maintaining sparsity and largely preserving the original graph spectrum.
  arXiv  Detail & Related papers  (2025-06-19T08:01:00Z)
• Online Proximal ADMM for Graph Learning from Streaming Smooth Signals [9.34612743192798]
  We develop a novel algorithm for online graph learning using observation streams, assumed to be smooth on the latent graph. Our modus operandi is to process graph signals sequentially and thus keep memory and computational costs in check. The proposed approach also exhibits better tracking performance (in terms of suboptimality) when compared to state-of-the-art online graph learning baselines.
  arXiv  Detail & Related papers  (2024-09-19T17:12:03Z)
• Deep Manifold Graph Auto-Encoder for Attributed Graph Embedding [51.75091298017941]
  This paper proposes a novel Deep Manifold (Variational) Graph Auto-Encoder (DMVGAE/DMGAE) for attributed graph data. The proposed method surpasses state-of-the-art baseline algorithms by a significant margin on different downstream tasks across popular datasets.
  arXiv  Detail & Related papers  (2024-01-12T17:57:07Z)
• GRAM: An Interpretable Approach for Graph Anomaly Detection using Gradient Attention Maps [26.011499804523808]
  We propose a novel approach to graph anomaly detection that leverages the power of interpretability to enhance performance. Our method extracts an attention map derived from gradients of graph neural networks, which serves as a basis for scoring anomalies. We extensively evaluate our approach against state-of-the-art graph anomaly detection techniques on real-world graph classification and wireless network datasets.
  arXiv  Detail & Related papers  (2023-11-10T16:14:21Z)
• Low-rank extended Kalman filtering for online learning of neural networks from streaming data [71.97861600347959]
  We propose an efficient online approximate Bayesian inference algorithm for estimating the parameters of a nonlinear function from a potentially non-stationary data stream. The method is based on the extended Kalman filter (EKF), but uses a novel low-rank plus diagonal decomposition of the posterior matrix. In contrast to methods based on variational inference, our method is fully deterministic, and does not require step-size tuning.
  arXiv  Detail & Related papers  (2023-05-31T03:48:49Z)
• Optimal Propagation for Graph Neural Networks [51.08426265813481]
  We propose a bi-level optimization approach for learning the optimal graph structure. We also explore a low-rank approximation model for further reducing the time complexity.
  arXiv  Detail & Related papers  (2022-05-06T03:37:00Z)
• High dimensional change-point detection: a complete graph approach [0.0]
  We propose a complete graph-based, change-point detection algorithm to detect change of mean and variance from low to high-dimensional online data. Inspired by complete graph structure, we introduce graph-spanning ratios to map high-dimensional data into metrics. Our approach has high detection power with small and multiple scanning window, which allows timely detection of change-point in the online setting.
  arXiv  Detail & Related papers  (2022-03-16T15:59:20Z)
• Fast and Accurate Anomaly Detection in Dynamic Graphs with a Two-Pronged Approach [49.25767340466445]
  We propose AnomRank, an online algorithm for anomaly detection in dynamic graphs. AnomRank uses a two-pronged approach defining two novel metrics for anomalousness. We show theoretically and experimentally that the two-pronged approach successfully detects two common types of anomalies.
  arXiv  Detail & Related papers  (2020-11-26T01:38:27Z)
• Offline detection of change-points in the mean for stationary graph signals [55.98760097296213]
  We propose an offline method that relies on the concept of graph signal stationarity. Our detector comes with a proof of a non-asymptotic inequality oracle.
  arXiv  Detail & Related papers  (2020-06-18T15:51:38Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.