Fast Temporal Path Localization on Graphs via Multiscale Viterbi Decoding

We consider a problem of localizing a temporal path signal that evolves over time on a graph. A path signal represents the trajectory of a moving agent on a graph in a series of consecutive time stamps. Through combining dynamic programing and graph partitioning, we propose a path-localization algorithm with significantly reduced computational complexity. To analyze the localization performance, we use two evaluation metrics to quantify the...