Graph Convolutional Attention: A Spectral Perspective on Graph Denoising and Diffusion

TL;DR

The paper identifies a fundamental limitation of linear attention in graph denoising: it learns a single average spectral filter, which is suboptimal when graphs exhibit diverse spectral properties. To address this, it introduces Spectral Attention, a mechanism that leverages the graph spectrum directly, and develops Graph Convolutional Attention (GCA) as a practical, permutation-equivariant implementation. GCA improves denoising performance, especially in high-spectral-diversity settings, and enhances diffusion models without requiring costly eigendecompositions.

Why It Matters

Graph denoising is critical for robust graph learning and diffusion models. This work provides a principled framework for designing attention mechanisms that adapt to spectral variations, leading to faster, more accurate models without relying on expensive structural features or eigendecompositions.

Key Findings

• Linear attention in graph denoising is limited to learning a single average spectral filter across the data distribution.
• Spectral Attention, which uses the input graph spectrum, provably outperforms linear attention by leveraging spectral diversity.
• Graph Convolutional Attention (GCA) realizes this idea efficiently, matching idealized performance on stochastic block models and improving diffusion models with faster inference.