Researchers introduce Graph Convolutional Attention (GCA), a mechanism that addresses the limitations of linear attention in graph denoising by utilizing the input graph spectrum. The study demonstrates that standard linear attention is suboptimal because it can only learn an average spectral denoising filter, which fails when graphs vary spectrally across a distribution.
- GCA implements spectral denoising through graph-filtered queries and keys, provably outperforming linear attention by a margin governed by spectral diversity.
- For stochastic block models, GCA provably matches the idealized Spectral Attention mechanism.
- The softmax operation in GCA provides additional denoising by approximately projecting noisy eigenvectors onto the clean eigenspace.
- Replacing linear attention with GCA consistently improves graph denoising and diffusion on synthetic and real datasets.
- In DiGress, GCA matches standard graph-transformer performance without computing expensive structural features.
- Combined with PEARL positional encodings, GCA avoids explicit eigendecomposition computations, resulting in faster inference without degrading quality.
The authors consider this important because it provides a principled understanding of attention-based graph denoising and offers a practical realization that improves performance while reducing computational costs.