Segmenting Sequences of Node-Labeled Graphs

Sorour E. Amiri, Liangzhe Chen

Abstract

Detection of the changes in pattern of disease spread over a population network, Meme-tracking and opinion spread on the Twitter network and product-rating-cascade over a social network are a few among the many embodiments of graph sequence segmentation problem with labeled nodes. Most of the previous approaches to network sequence segmentation are on plain graphs without considerations for the dynamics of propagation process. These approaches either fix observation scales or extract a long list of expensive features. In this paper, we propose SNAPNETS a parameter free, and comprehensive algorithm, to find segmentation of networks sequences with node labels such that adjacent segments are different in characteristics of nodes of each label. Our method leverages a principled, multi-level, flexible framework which maps the original problem to a path optimization problem over a weighted DAG. Extensive experiments on several diverse real datasets show that our method finds cut points matching ground-truth or meaningful external signals outperforming non-trivial baselines.