"Martingale Methods for Structural Change Detection and Feature Attribu" by Izhar Ali

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.

Available for download on Tuesday, June 23, 2026

Share

COinS