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

arXiv:2607.06546v2 Announce Type: replace-cross Abstract: Denoising graphs is a fundamental problem in graph learning and the core operation of graph diffusion models. Attention-based architectures such as graph transformers have shown promise for this task, yet the mechanisms through which attention denoises graphs remain poorly understood. We show that, under a graph denoising objective, standard attention scores learn an average spectral denoising filter across the training distribution and are suboptimal when the graph spectra vary. To address this limitation, we introduce spectral attention scores, which are attention scores that depend on the input graph spectrum. We characterize the improvement over standard attention scores in terms of the spectral diversity of the graph distribution. We then propose graph convolutional attention (GCA), a practical realization of spectral attention that uses graph-filtered queries and keys. For asymptotically large stochastic block models, we show that GCA matches the optimal denoising loss of spectral attention under suitable conditions. We also show that softmax can further reduce denoising error by approximately projecting noisy eigenvectors onto the clean eigenspace. Across synthetic and real datasets, replacing standard query--key projections with GCA improves graph denoising and diffusion, with denoising gains correlated with spectral diversity. Furthermore, replacing the DiGress architecture with a GCA-based architecture within the DiGress generative framework yields comparable generation quality with significantly faster inference.

Abstract:Denoising graphs is a fundamental problem in graph learning and the core operation of graph diffusion models. Attention-based architectures such as graph transformers have shown promise for this task, yet the mechanisms through which attention denoises graphs remain poorly understood. We show that, under a graph denoising objective, standard attention scores learn an average spectral denoising filter across the training distribution and are suboptimal when the graph spectra vary. To address this limitation, we introduce spectral attention scores, which are attention scores that depend on the input graph spectrum. We characterize the improvement over standard attention scores in terms of the spectral diversity of the graph distribution. We then propose graph convolutional attention (GCA), a practical realization of spectral attention that uses graph-filtered queries and keys. For asymptotically large stochastic block models, we show that GCA matches the optimal denoising loss of spectral attention under suitable conditions. We also show that softmax can further reduce denoising error by approximately projecting noisy eigenvectors onto the clean eigenspace. Across synthetic and real datasets, replacing standard query--key projections with GCA improves graph denoising and diffusion, with denoising gains correlated with spectral diversity. Furthermore, replacing the DiGress architecture with a GCA-based architecture within the DiGress generative framework yields comparable generation quality with significantly faster inference.

Machine Learning (cs.LG); Artificial Intelligence (cs.AI)

arXiv:2607.06546 [cs.LG]

(or arXiv:2607.06546v2 [cs.LG] for this version)

https://doi.org/10.48550/arXiv.2607.06546 Focus to learn more arXiv-issued DOI via DataCite

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.

aiqbench analysis

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

Related coverage