Spectralization: Generalizing Spectral Invariants for Expressive Graph Learning

Spectral invariant graph neural networks (GNNs), which use spectral invariants to avoid eigenvector ambiguities, have demonstrated strong expressive power. Rooted graph invariants (RGIs), such as distance measures and substructure counts, are also commonly incorporated as structural encodings to improve the expressiveness of GNNs and graph Transformers. We connect these two threads by reformulating these spectral invariants in terms of spectral responses to the identity signal, which is itself an elementary RGI. The construction of these spectral invariants can thus be understood as spectrally enriching the identity signal by capturing its interactions with graph topology. We therefore propose Spectralization, a general framework that extends this construction from the identity signal to arbitrary RGIs, thereby substantially broadening the scope of spectral invariants. To demonstrate its benefits, we spectralize the atomic types underlying Weisfeiler-Leman (WL) refinement to obtain Spectralized $k$-FWL, which we prove to be strictly more expressive than $k$-FWL for every $k\ge 2$ and place within a hierarchy of classical and spectral WL variants. Beyond atomic types, we further show that spectralizing diverse RGIs can improve model expressiveness compared with using their raw forms directly. We then develop structural encoding schemes guided by Spectralization, with experiments corroborating these expressiveness gains on graph-isomorphism benchmarks and demonstrating improved predictive performance across multiple neural architectures and downstream tasks.