Spectral embedding for dynamic networks with stability guarantees
This work addresses the need for stable embeddings in dynamic network analysis, which is incremental as it builds on existing spectral embedding methods with formal stability guarantees.
The paper tackled the problem of embedding dynamic networks to obtain time-evolving node representations, and demonstrated that unfolded adjacency spectral embedding satisfies both cross-sectional and longitudinal stability conditions, unlike alternative methods.
We consider the problem of embedding a dynamic network, to obtain time-evolving vector representations of each node, which can then be used to describe changes in behaviour of individual nodes, communities, or the entire graph. Given this open-ended remit, we argue that two types of stability in the spatio-temporal positioning of nodes are desirable: to assign the same position, up to noise, to nodes behaving similarly at a given time (cross-sectional stability) and a constant position, up to noise, to a single node behaving similarly across different times (longitudinal stability). Similarity in behaviour is defined formally using notions of exchangeability under a dynamic latent position network model. By showing how this model can be recast as a multilayer random dot product graph, we demonstrate that unfolded adjacency spectral embedding satisfies both stability conditions. We also show how two alternative methods, omnibus and independent spectral embedding, alternately lack one or the other form of stability.