Graph Persistence goes Spectral

Including intricate topological information (e.g., cycles) provably enhances the expressivity of message-passing graph neural networks (GNNs) beyond the Weisfeiler-Leman (WL) hierarchy. Consequently, Persistent Homology (PH) methods are increasingly employed for graph representation learning. In this context, recent works have proposed decorating classical PH diagrams with vertex and edge features for improved expressivity. However, these methods still fail to capture basic graph structural information. In this paper, we propose SpectRe -a new topological descriptor for graphs that integrates spectral information into PH diagrams. Notably, SpectRe is strictly more expressive than PH and spectral information on graphs alone. We also introduce notions of global and local stability to analyze existing descriptors and establish that SpectRe is locally stable. Finally, experiments on synthetic and real-world datasets demonstrate the effectiveness of SpectRe and its potential to enhance the capabilities of graph models in relevant learning tasks. Code is available at https://github.com/Aalto-QuML/SpectRe/ . Understandably, there is a growing interest in designing more expressive PH descriptors for graphs [2] . Recently, Immonen et al. [33] analyzed the representational ability of color-based PH schemes, providing a complete characterization of the power of 0-dimensional PH methods that employ vertex-level or edge-level filtrations using graph-theoretic notions. They also introduced RePHINE as a strictly more powerful descriptor than these methods. However, it turns out that RePHINE is still unable to 39th Conference on Neural Information Processing Systems (NeurIPS 2025).