Paper Overview
Research area: Machine Learning Authors: Shervin Khalafi, Igor Krawczuk, Sergio Rozada Published: 2025-07-09 arXiv: 2507.06823
Summary
Graph denoising is a fundamental problem in graph learning and the core operation of graph diffusion models. Attention-based architectures such as graph transformers have recently shown promise for denoising graphs. However, principled understanding of attention-based graph denoising remains limited, making it unclear whether standard attention is the right mechanism for this task.
This 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 a distribution.
To overcome this, the authors introduce Spectral Attention, which directly utilizes the input graph spectrum and provably outperforms linear attention by a margin determined by the spectral diversity of the distribution. They then derive Graph Convolutional Attention (GCA), a practical, permutation-equivariant implementation of this idea that performs spectral denoising via graph-filtered queries and keys.
Key theoretical results
- Linear attention under a denoising objective can only learn an average spectral denoising filter over the training distribution.
- Spectral Attention provably outperforms linear attention in proportion to spectral diversity.
- For the stochastic block model, 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-world datasets, with gains strongly correlated with spectral diversity.
- In DiGress, GCA matches the performance of standard graph transformers without computing expensive structural features.
- Combined with the recently proposed PEARL positional encoding, GCA avoids explicit eigendecomposition, achieving faster inference without quality degradation.
Empirical findings
Original Abstract (excerpt)
> 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. Here we show that, under a denoising objective, linear attention is suboptimal and can only learn an average spectral denoising filter over the training distribution. This creates a fundamental limitation as graphs often vary spectrally across the distribution. To overcome this limitation, we introduce Spectral Attention, which directly utilizes the input graph spectrum and provably outperforms linear attention...
Paper link: https://arxiv.org/abs/2507.06823