Dynamic systems such as sensor networks, social networks, computer networks, and power grids can be modeled as evolving graphs, requiring effective methods to monitor structural changes in real-time. In this paper, we present a change detection framework for detecting global structural changes in evolving graphs. This framework combines multiple martingale-based change detectors using different graph features. We establish a mathematical relationship between an additive martingale (derived from the multiple graph features) and the Shapley Additive Explanations (SHAP) method, demonstrating that martingale values at detected change-points directly quantify each feature’s contribution to the detected change. Thus, graph features with significantly high martingale values provide meaningful explanations for detected structural changes. We demonstrate our approach using three synthetic graph types (random topology, scale-free, and small-world), showing how different graph features vary in detection performance across network types. This highlights the importance of using multiple graph features, as relying on any single feature might not detect certain changes. Additionally, we apply our approach to the MIT Reality dataset to identify changes in social interactions among dormitory students at some special time periods. Our results reveal which graph features best characterize the real-world network changes during these special time periods.

Dynamic networks evolve through structural changes that significantly impact their functionality. Early detection of these changes remains a fundamental challenge due to the inherent tradeoffs between detection delay and false alarm control. Current methods accumulate evidence of these changes only after they occur, creating unavoidable detection delays that limit practical utility in time-sensitive applications. We address this limitation through horizon martingales that leverage statistical forecasting to accumulate evidence from predicted future network states, enabling detection before changes fully manifest. We establish two fundamental results: (1) horizon martingales preserve the martingale property under proper forecasting calibration, and (2) they maintain rigorous false alarm control with probability bounds of$1/\lambda$for detection threshold$\lambda$. Comprehensive evaluation across diverse synthetic network types and real-world social interaction data demonstrates consistent improvements in detection speed with 13–25% reductions in detection delay while maintaining strict statistical guarantees.