Graph Convolutional Attention: A Spectral Perspective on Graph Denoising and Diffusion
By Shervin Khalafi, Igor Krawczuk, Sergio Rozada, Charilaos Kanatsoulis, Antonio G Marques, Alejandro Ribeiro
"This paper identifies limitations of linear attention for graph denoising and proposes Graph Convolutional Attention (GCA), which uses graph-filtered queries and keys to implement spectral denoising, improving performance on synthetic and real datasets."
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
Technical Analysis & Implementation
Technical Breakdown§
Motivation and Core Problem§
Denoising graphs is crucial for graph learning and diffusion models. Standard attention mechanisms, especially linear attention, are commonly used but the paper shows they are suboptimal under a denoising objective. Linear attention can only learn an average spectral denoising filter over the training distribution, which fails when graphs vary spectrally (e.g., different community structures). The paper introduces Spectral Attention, a theoretically optimal mechanism, and then derives a practical permutation-equivariant implementation called Graph Convolutional Attention (GCA).
Spectral Attention Formulation§
Let the graph adjacency matrix be $A$ with eigendecomposition $A = U \Lambda U^\top$, where $U$ contains eigenvectors and $\Lambda$ eigenvalues. The graph signal $X$ (node features) can be transformed as $\tilde{X} = U^\top X$. Spectral Attention computes attention weights using a spectral filter $f(\lambda)$: $$ \text{Attention}(Q, K, V) = \text{softmax}\left(\frac{Q K^\top}{\sqrt{d_k}}\right) V, $$ where $Q = U f(\Lambda) U^\top X W_Q$, $K = U f(\Lambda) U^\top X W_K$, and $V = X W_V$. The filter $f$ is learned to denoise based on eigenvalues. The paper proves that this mechanism outperforms linear attention by a margin depending on spectral diversity.
Graph Convolutional Attention (GCA)§
To avoid explicit eigendecomposition, GCA approximates the spectral filter using graph convolution. Specifically, queries and keys are obtained by applying a polynomial filter (e.g., Chebyshev or simple $K$-hop convolution) to the node features: $$ Q = \sum_{k=0}^K \theta_k L^k X W_Q, \quad K = \sum_{k=0}^K \theta_k L^k X W_K, $$ where $L = I - D^{-1/2} A D^{-1/2}$ is the normalized Laplacian. The parameters $\theta_k$ are learned. This yields permutation-equivariant attention. Values are computed as $V = X W_V$ without filtering. The attention output is then $\text{softmax}(Q K^\top / \sqrt{d}) V$.
Theoretical Insights§
- Stochastic block models (SBM): GCA provably matches Spectral Attention, effectively separating intra- and inter-community edges.
- Softmax denoising: The softmax operation projects noisy eigenvectors onto the clean eigenspace, acting as an additional denoiser.
Implementation Example§
import torch
import torch.nn as nn
class GraphConvAttention(nn.Module):
def __init__(self, d_model, d_k, K):
super().__init__()
self.W_q = nn.Linear(d_model, d_k)
self.W_k = nn.Linear(d_model, d_k)
self.W_v = nn.Linear(d_model, d_model)
self.filters = nn.Parameter(torch.randn(K+1)) # theta_k
self.K = K
def forward(self, X, L):
# X: (N, d_model), L: (N, N) symmetric normalized Laplacian
# Compute filtered Q and K via K-hop convolution
def poly_filter(X, coeffs):
out = coeffs[0] * X
for k in range(1, len(coeffs)):
X = L @ X
out += coeffs[k] * X
return out
Q = poly_filter(self.W_q(X), self.filters)
K = poly_filter(self.W_k(X), self.filters)
V = self.W_v(X)
attn = torch.softmax(Q @ K.T / (Q.size(-1)**0.5), dim=-1)
return attn @ VEmpirical Results§
Replacing linear attention with GCA in graph diffusion models (e.g., DiGress) consistently improves denoising quality on synthetic SBM graphs and real datasets (e.g., ZINC, QM9). The improvement correlates with spectral diversity. GCA also avoids expensive eigen-decompositions when combined with PEARL positional encodings, leading to faster inference.