You Only Spectralize Once: Taking a Spectral Detour to Accelerate Graph Neural Network

Training Graph Neural Networks (GNNs) often relies on repeated, irregular, and expensive message-passing operations over all nodes (e.g., N ), leading to high computational overhead. To alleviate this inefficiency, we revisit the GNNs training from the spectral perspective. Node features and embeddings in many real-world graph exhibit sparse representation in Graph Fourier domain. This inherent sparsity aligns well with the Compressed Sensing principles, which posits that sparse signals can be accurately reconstructed from significantly fewer measurements (e.g., M and M ≪ N ). This observation motivates designing efficient GNNs that operates predominantly in a compressed spectral subspace. In this paper, we propose You Only Spectralize Once (YOSO), a GNN training scheme that first performing a single projection of features onto a learnable orthonormal Graph Fourier basis U ℓ , and after compressed sensing is used, retaining only M spectral coefficients where M ≪ N . The entire GNN computation then performs in this reduced/compressed spectral domain. Finally, the full graph embeddings are recovered back to original domain at output layer by solving a compressed sensing bounded ℓ 2 , 1 -regularized optimization problem. Theoretically, drawing upon the compressed sensing theory, we prove that stable recovery by showing that this whole process can satisfy the Restricted Isometry Property when M = O ( k (log N/k )) . Empirically, YOSO achieves an average 74% training time reduction across five benchmark datasets compared to state-of-the-art baseline schemes, while maintaining the competitive model accuracy.