Unfolded Laplacian Spectral Embedding: A Theoretically Grounded Approach to Dynamic Network Representation

Dynamic relational data arise in many machine learning applications, yet their evolving structure poses challenges for learning representations that remain consistent and interpretable over time. A common approach is to learn time varying node embeddings, whose usefulness depends on well defined stability properties across nodes and across time. We introduce Unfolded Laplacian Spectral Embedding (ULSE), a principled extension of unfolded adjacency spectral embedding to normalized Laplacian operators, a setting where stability guarantees have remained out of reach. We prove that ULSE satisfies both cross-sectional and longitudinal stability under a dynamic stochastic block model. Moreover, the Laplacian formulation yields a dynamic Cheeger-type inequality linking the spectrum of the unfolded normalized Laplacian to worst case conductance over time, providing structural insight into the embeddings. Empirical results on synthetic and real-world dynamic networks validate the theory.

Networks are a natural way to describe relationships, such as interactions between people, connections in the brain, financial dependencies, or links in knowledge graphs. These networks often change over time, so researchers need methods that can track how each node’s role evolves. A key difficulty is that the resulting representations must be comparable across time: if a node’s behavior has not changed, its representation should also remain stable. We propose Unfolded Laplacian Spectral Embedding, or ULSE, a method for representing changing networks in a way that preserves this kind of temporal consistency. The method builds one combined matrix from all time steps and uses a degree-normalized graph representation, which helps when some nodes have many more connections than others. We prove mathematically that ULSE gives stable representations under a standard model for dynamic networks, and we also connect the method to classical ideas about graph clustering quality. Our experiments show that ULSE performs well on synthetic and real-world dynamic networks, especially when the network has uneven degrees. This makes ULSE useful for analyzing evolving network structure in a stable and interpretable way.