Band-Masked Spectral Autoencoding for Self-Supervised Graph Representation Learning

Self-supervised graph representation learning is currently dominated by contrastive methods relying on engineered augmentations and masked autoencoders that reconstruct spatially masked features or edges. We introduce Band-Masked Spectral Autoencoding (BMSAE), a self-supervised framework that instead masks and reconstructs structured components of graph signals in the spectral domain. BMSAE decomposes node features into spectral bands using a fixed Meyer-wavelet Parseval frame, masks a subset of these bands, and predicts them from the remaining ones. Crucially, Parseval tightness yields an exact synthesis relation. This allows masked-band prediction error to bound reconstruction error in the original feature space, thereby controlling the risk of Lipschitz predictors evaluated on the reconstruction. Because the spectral transform is graph-local, applying the node-level objective to a disjoint union is equivalent to applying it independently to each graph, while segment pooling yields graph-level representations. Experiments show that BMSAE is competitive with or improves on strong contrastive and masked-autoencoder baselines on graph-level benchmarks. For node classification, its strongest results occur on heterophilic graphs, where BMSAE outperforms competing methods on most of the evaluated benchmarks.