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

2025/08/18 by Haruka Ezoe, Ezoe, Haruka, Hiroki Matsumoto +3
Computer Science · Physics and Astronomy · #Advanced Graph Neural Networks #Complex Network Analysis Techniques #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Opinion Dynamics and Social Influence #Social and Information Networks (cs.SI)

paper · pdf · doi:10.48550/arxiv.2508.12674

openalex publication_date 2025/08/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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.

Citations

• A Comprehensive Review of Recommender Systems: Transitioning from Theory to Practice
• TGB 2.0: A Benchmark for Learning on Temporal Knowledge Graphs and Heterogeneous Graphs
• Learning Persistent Community Structures in Dynamic Networks via Topological Data Analysis
• A Simple and Powerful Framework for Stable Dynamic Network Embedding
• Towards Foundation Models for Knowledge Graph Reasoning
• Deep Temporal Graph Clustering
• Towards Better Dynamic Graph Learning: New Architecture and Unified Library
• Spectral embedding for dynamic networks with stability guarantees
• The multilayer random dot product graph
• Temporal Graph Networks for Deep Learning on Dynamic Graphs
• Strong Consistency, Graph Laplacians, and the Stochastic Block Model
• Inductive Representation Learning on Temporal Graphs
• Understanding Regularized Spectral Clustering via Graph Conductance
• A Generative Model for Dynamic Networks with Applications
• Spectral Algorithms for Temporal Graph Cuts
• node2vec: Scalable Feature Learning for Networks
• A cospectral family of graphs for the normalized Laplacian found by toggling
• A useful variant of the Davis--Kahan theorem for statisticians
• The Nonparanormal: Semiparametric Estimation of High Dimensional Undirected Graphs
• Stochastic blockmodels: First steps
• Multi-set spectral clustering of time-evolving networks using the supra-Laplacian

Related

• Spectral embedding for dynamic networks with stability guarantees
• Unsupervised Attributed Dynamic Network Embedding with Stability Guarantees
• A Simple and Powerful Framework for Stable Dynamic Network Embedding
• Doubly unfolded adjacency spectral embedding of dynamic multiplex graphs
• Beyond the Laplacian: Interpolated Spectral Augmentation for Graph Neural Networks