Vertex Alignment and Localizing First-order Changepoints in Time Series of Graphs

Music City Center 

We consider localization of changepoints in a time series of networks. Existing methodologies rely on correctly-specified vertex alignment between networks across time. We consider the impact of vertex misalignment on inference for dynamic networks, and describe two models for network evolution as illustrative cases: one in which vertex misalignment is comparatively inconsequential, and
another in which it renders localization effectively impossible. We characterize when changepoints in network evolutionary processes can be successfully localized without alignment and prove an identifiability theorem on when certain changepoints cannot be localized at all. We also describe how procedures such as graph matching and optimal transport can be used to mitigate error from misalignments in some cases and provide simulations and real data analysis demonstrating their efficacy.

Time series of networks

changepoint localization

Euclidean mirror 

IMS