Date Approved
6-23-2025
Embargo Period
6-23-2026
Document Type
Thesis
Degree Name
M.S. Data Science
Department
Computer Science
College
College of Science & Mathematics
Advisor
Shen-Shyang Ho
Committee Member 1
Hieu Nguyen, Ph.D.
Committee Member 2
Vasil Hnatyshin, Ph.D.
Committee Member 3
Patrick McKee
Keywords
Change Detection;Conformal Prediction;Feature Attribution;Martingale;Shapley
Disciplines
Computer Sciences | Physical Sciences and Mathematics
Abstract
Dynamic networks undergo structural changes when their generative process shifts at a change-point. We need to detect this change-point with minimal delay while identifying its underlying causes. This is an optimization problem of minimizing the expected detection delay while controlling the false alarm probability below a threshold---leading to three critical challenges: non-parametric detection without distributional assumptions, exact feature attribution, and early detection with rigorous false alarm control. We construct additive martingale statistics from multiple graph features using conformal prediction, providing false alarm guarantees via Ville's inequality. Our key theoretical contribution proves the Martingale-Shapley equivalence: each feature's martingale value equals its Shapley value, enabling exact feature attribution to detected changes as an integral component of detection rather than post-hoc analysis. Our forecast-enhanced horizon martingales accumulate evidence from predicted network states, achieving earlier detection with statistical false-alarm guarantees. Empirical evaluation on synthetic networks (SBM, BA, ER, NWS) shows that single-feature approaches fail across diverse scenarios, while our multi-feature framework achieves robust detection with true positive rate (TPR) $>$88\% and 13--25\% delay reduction. Testing our approach on the MIT Reality dataset validates real-world effectiveness with 96.0\% TPR for academic event detection and 21.9\% delay reduction, while providing precise attribution of the network features driving these changes.
Recommended Citation
Ali, Izhar, "Martingale Methods for Structural Change Detection and Feature Attribution in Dynamic Networks" (2025). Theses and Dissertations. 3405.
https://rdw.rowan.edu/etd/3405