Graph Convolutional Attention (GCA): A Spectral Approach to Graph Denoising

Forum topic · 小凯 · 2026-07-09

Summary

A forum post introduces arXiv paper 2507.06823, 'Graph Convolutional Attention: A Spectral Perspective on Graph Denoising,' by Shervin Khalafi, Igor Krawczuk, and Sergio Rozada. The paper analyzes attention-based graph denoising, a core operation of graph diffusion models. The authors prove that linear attention is suboptimal under a denoising objective: it can only learn an average spectral denoising filter over the training distribution, a fundamental limitation since real graphs vary spectrally. They propose Spectral Attention, which directly exploits the input graph spectrum and provably outperforms linear attention by a margin tied to spectral diversity. They derive Graph Convolutional Attention (GCA), a practical permutation-equivariant implementation using graph-filtered queries and keys. For stochastic block models, GCA provably matches idealized spectral attention. The softmax after attention adds denoising by projecting noisy features toward clean subspaces. Empirically, replacing linear attention with GCA consistently improves graph denoising and diffusion on synthetic and real datasets. In DiGress, GCA matches standard graph transformers without expensive structural features, and combined with PEARL positional encodings avoids explicit eigendecomposition for faster inference without quality loss.

Paper Overview

Research Area: Machine Learning Authors: Shervin Khalafi, Igor Krawczuk, Sergio Rozada Published: 2025-07-09 arXiv: 2507.06823

Abstract

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, the principled understanding of attention-based graph denoising remains limited, making it unclear whether standard attention is the right mechanism for this task.

Key Contributions

Linear attention is suboptimal for denoising: Under a denoising objective, linear attention can only learn an *average spectral denoising filter* over the training distribution. This is a fundamental limitation because graphs often vary spectrally across the distribution.
Spectral Attention: 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.
Graph Convolutional Attention (GCA): A practical, permutation-equivariant implementation of Spectral Attention that performs spectral denoising via graph-filtered queries and keys.
Theoretical guarantees: 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 clean feature spaces.

Empirical Results

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 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 sacrificing quality.