Paper Overview
Field: 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, our principled understanding of attention-based graph denoising remains limited, and it is 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 creates a fundamental limitation, because graphs often vary spectrally across the 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 and permutation-equivariant implementation of this idea that achieves spectral denoising via queries and keys obtained through graph filtering.
Key theoretical results:
- For the stochastic block model, GCA provably matches the idealized spectral attention mechanism.
- The softmax operation applied after attention provides additional denoising by approximately projecting noisy feature vectors onto the clean feature subspace.
- 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 encodings, GCA avoids explicit eigendecomposition entirely, achieving faster inference without degraded quality.
Empirical results:
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