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

• URL: http://arxiv.org/abs/2607.06546v1
• Date: Tue, 07 Jul 2026 17:52:17 GMT
• Title: Graph Convolutional Attention: A Spectral Perspective on Graph Denoising and Diffusion
• Abstract summary: We show that under a denoising objective, linear attention is suboptimal and can only learn an average spectral denoising filter over the training distribution.<n>We introduce Spectral Attention, which directly utilizes the input graph spectrum and provably outperforms linear attention by a margin governed by the spectral diversity of the distribution.<n>For block models, GCA provably matches the idealized Spectral Attention mechanism.
• Score: 82.7007012514703
• License: http://creativecommons.org/licenses/by/4.0/
• 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, 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 by a margin governed by the spectral diversity of the distribution. We then derive Graph Convolutional Attention (GCA), a practical and permutation-equivariant realization of this idea that implements spectral denoising through graph-filtered queries and keys. For stochastic block models, GCA provably matches the idealized Spectral Attention mechanism. We further show that the softmax operation, that follows the attention, provides additional denoising by approximately projecting noisy eigenvectors onto the clean eigenspace. Empirically, replacing linear attention with GCA consistently improves graph denoising and diffusion on synthetic and real datasets, with gains strongly correlated with spectral diversity. In DiGress, GCA matches standard graph-transformer performance without computing expensive structural features, and when combined with the recently proposed PEARL positional encodings, avoids explicit eigendecomposition computations resulting in faster inference without degrading quality. The code can be found here: github.com/shervinkhalafi/graph_conv_att

Related papers

• Improved large-scale graph learning through ridge spectral sparsification [65.84577791298442]
  We consider the problem of learning over the Laplacian L in a distributed streaming setting.<n>In this setting, it is hard to learn quickly or approximately while keeping a distributed representation of L.<n>We present a novel algorithm, GSQUEAK, which efficiently sparsifies the Laplacian by maintaining a small subset of effective resistances.
  arXiv  Detail & Related papers  (2026-04-22T00:49:31Z)
• Advection-Diffusion on Graphs: A Bakry-Emery Laplacian for Spectral Graph Neural Networks [2.6124895681424323]
  Graph Neural Networks (GNNs) often struggle to propagate information across long distances due to oversmoothing and oversquashing.<n>We introduce a Bakry-Emery graph Laplacian that integrates diffusion and advection through a learnable node-wise potential.<n>We develop mu-ChebNet, a spectral architecture that jointly learns the potential and Chebyshev filters.
  arXiv  Detail & Related papers  (2026-02-20T11:01:12Z)
• A Spectral Interpretation of Redundancy in a Graph Reservoir [51.40366905583043]
  This work revisits the definition of the reservoir in the Multiresolution Reservoir Graph Neural Network (MRGNN)<n>It proposes a variant based on a Fairing algorithm originally introduced in the field of surface design in computer graphics.<n>The core contribution of the paper lies in the theoretical analysis of the algorithm from a random walks perspective.
  arXiv  Detail & Related papers  (2025-07-17T10:02:57Z)
• Mitigating Over-Squashing in Graph Neural Networks by Spectrum-Preserving Sparsification [81.06278257153835]
  We propose a graph rewiring method that balances structural bottleneck reduction and graph property preservation.<n>Our method generates graphs with enhanced connectivity while maintaining sparsity and largely preserving the original graph spectrum.
  arXiv  Detail & Related papers  (2025-06-19T08:01:00Z)
• RobGC: Towards Robust Graph Condensation [61.259453496191696]
  Graph neural networks (GNNs) have attracted widespread attention for their impressive capability of graph representation learning.<n>However, the increasing prevalence of large-scale graphs presents a significant challenge for GNN training due to their computational demands.<n>We propose graph condensation (GC) to generate an informative compact graph that enables efficient training of GNNs while retaining performance.
  arXiv  Detail & Related papers  (2024-06-19T04:14:57Z)
• How Powerful is Graph Filtering for Recommendation [7.523823738965443]
  We show two limitations suppressing the power of graph filtering. Due to varied noise distribution, graph filters fail to denoise sparse data where noise is scattered across all frequencies. supervised training results in worse performance on dense data where noise is concentrated in middle frequencies that can be removed by graph filters without training.
  arXiv  Detail & Related papers  (2024-06-13T05:37:54Z)
• Handling Missing Data via Max-Entropy Regularized Graph Autoencoder [37.8103274049137]
  MEGAE is a regularized graph autoencoder for graph attribute imputation. It aims at mitigating spectral concentration problem by maximizing the graph spectral entropy. It outperforms all the other state-of-the-art imputation methods on a variety of benchmark datasets.
  arXiv  Detail & Related papers  (2022-11-30T06:22:40Z)
• Quasi-Framelets: Robust Graph Neural Networks via Adaptive Framelet Convolution [28.474359021962346]
  We propose a multiscale framelet convolution for spectral graph neural networks (GNNs) The proposed design excels in filtering out unwanted spectral information and significantly reduces the adverse effects of noisy graph signals. It exhibits remarkable resilience to noisy data and adversarial attacks, highlighting its potential as a robust solution for real-world graph applications.
  arXiv  Detail & Related papers  (2022-01-11T00:10:28Z)
• Pointspectrum: Equivariance Meets Laplacian Filtering for Graph Representation Learning [3.7875603451557063]
  Graph Representation Learning (GRL) has become essential for modern graph data mining and learning tasks. While Graph Neural Networks (GNNs) have been used in state-of-the-art GRL architectures, they have been shown to suffer from over smoothing. We propose PointSpectrum, a spectral method that incorporates a set equivariant network to account for a graph's structure.
  arXiv  Detail & Related papers  (2021-09-06T10:59:11Z)
• Unrolling of Deep Graph Total Variation for Image Denoising [106.93258903150702]
  In this paper, we combine classical graph signal filtering with deep feature learning into a competitive hybrid design. We employ interpretable analytical low-pass graph filters and employ 80% fewer network parameters than state-of-the-art DL denoising scheme DnCNN.
  arXiv  Detail & Related papers  (2020-10-21T20:04:22Z)
• Bridging the Gap Between Spectral and Spatial Domains in Graph Neural Networks [8.563354084119062]
  We show some equivalence of the graph convolution process regardless it is designed in the spatial or the spectral domain. The proposed framework is used to design new convolutions in spectral domain with a custom frequency profile while applying them in the spatial domain.
  arXiv  Detail & Related papers  (2020-03-26T01:49:24Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.