Paper Overview
Field: Machine Learning Authors: Shervin Khalafi, Igor Krawczuk, Sergio Rozada Published: 2025-07-09 arXiv: 2507.06823
Summary
Denoising graphs is a fundamental problem in graph learning and the core operation of graph diffusion models. Attention-based architectures like graph transformers have recently shown promise in denoising graphs. However, our principled understanding of attention-based graph denoising remains limited, making it unclear whether standard attention is the right mechanism for this task.
The paper shows that, under a denoising objective, linear attention is suboptimal: it can only learn an average spectral denoising filter over the training distribution. This is a fundamental limitation, since graphs often vary spectrally across the distribution.
Key Contributions
- Spectral Attention: directly utilizes the input graph spectrum and provably outperforms linear attention by a margin determined by the spectral diversity of the distribution.
- Graph Convolutional Attention (GCA): a practical, permutation-equivariant implementation of this idea that performs spectral denoising via queries and keys built from graph filtering.
- For stochastic block models, GCA provably matches the idealized Spectral Attention mechanism.
- The softmax operation after attention provides additional denoising by approximately projecting noisy feature vectors onto the clean feature space.
- Replacing linear attention with GCA consistently improves graph denoising and diffusion on both synthetic and real datasets, with gains strongly correlated with spectral diversity.
- In DiGress, GCA matches standard graph transformer performance without computing expensive structural features.
- Combined with the recently proposed PEARL positional encoding, GCA avoids explicit eigendecomposition, enabling faster inference without degradation in quality.
Empirical Results
*Auto-collected on 2026-07-09*