SPG Solves Graph AI's Hardest Problem by Merging Frequency and Structure
SPG introduces spectral signal decomposition and geometry-aware prototypes to finally crack cross-domain graph transfer learning
Takeaways
- SPG is a new graph foundation model that achieves cross-domain generalization by combining spectral signal decomposition with geometry-aware structural prototypes.
- Learnable Chebyshev filters decompose node features into multiple frequency bands, letting the model apply different propagation behaviors to high-frequency local patterns vs. low-frequency global patterns.
- A Gromov-Wasserstein prototype geometry builds a shared structural space from pairwise relational patterns across training graphs, bypassing the limitations of predefined substructures like trees and cycles.
- The learned prototype geometry is projected back as a propagation operator, making graph structure a direct driver of information flow rather than just an input feature.
- SPG shows consistent improvements in cross-domain node classification over prior GFMs on citation, web, and co-authorship graph benchmarks.
- Main limitations include high compute cost from Gromov-Wasserstein optimization and limited evaluation beyond node-level tasks; no public code repository confirmed yet.
Graph neural networks are powerful within a single domain, but getting them to generalize across radically different graphs -- say, from citation networks to protein interaction graphs -- has remained one of the field's stubborn open problems. A new paper introduces SPG (Spectral Parsing with Prototype-Guided propagation), a graph foundation model that attacks this problem from two angles simultaneously: by decomposing graph signals in the frequency domain and by learning a universal structural geometry that travels across graph types.
Why graphs are the hardest modality to generalize
Foundation models have become a cornerstone of general-purpose machine learning, enabling cross-task and cross-domain generalization -- with large language models for text and large vision models for images as the canonical examples. Graphs have lagged behind. Despite the success of foundation models in text and vision, their extension to graph-structured data remains nascent, primarily due to the high variability across graph datasets. Graphs from different domains often encode distinct phenomena -- social networks model human relationships, while molecular graphs represent chemical structures -- leading to both feature and structural heterogeneity.
Existing domain-agnostic graph foundation models (GFMs) are provably bounded by their fixed operator bases or fixed message-passing depth, and therefore may under-reach on tasks that exceed these bounds. This failure mode can be demonstrated empirically using simple synthetic node classification tasks, for which existing methods collapse even under generous operator expansions. The core issue is that there is no shared vocabulary or spatial grid for graphs the way pixels or tokens provide structure for images and text.
What prior work got wrong
The GFM field has tried two main approaches to bridge structural gaps between graphs. The first is unifying feature spaces -- projecting node features from different graphs into a common embedding. The second is building structural vocabularies. One prominent example, GFT (NeurIPS 2024), rethinks transferable patterns as computation trees derived from the message-passing process, treating those trees as tokens within a transferable vocabulary to improve model generalization and reduce the risk of negative transfer.