그래프 컨볼루션 어텐션: 그래프 노이즈 제거 및 확산에 대한 스펙트럼 관점

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

그래프 노이즈 제거는 그래프 학습의 기본적인 문제이며, 그래프 확산 모델의 핵심 연산입니다. 최근에는 그래프 트랜스포머와 같은 어텐션 기반 아키텍처가 그래프 노이즈 제거에서 유망한 성능을 보여주고 있습니다. 그러나 어텐션 기반 그래프 노이즈 제거에 대한 우리의 체계적인 이해는 여전히 제한적이며, 표준 어텐션이 이 작업에 적합한 메커니즘인지 불분명합니다. 본 연구에서는 노이즈 제거 목표 하에서 선형 어텐션이 최적이 아니며, 훈련 데이터 분포 전반에 걸쳐 평균 스펙트럼 노이즈 제거 필터만을 학습할 수 있음을 보여줍니다. 이는 그래프가 종종 데이터 분포 내에서 스펙트럼적으로 다양하기 때문에 근본적인 제약으로 작용합니다. 이러한 제한을 극복하기 위해 입력 그래프의 스펙트럼을 직접 활용하고, 데이터 분포의 스펙트럼 다양성에 의해 결정되는 성능 향상을 보장하는 스펙트럼 어텐션을 소개합니다. 다음으로, 그래프 필터링된 쿼리와 키를 통해 스펙트럼 노이즈 제거를 구현하는 실용적이고 순열 동등성을 갖는 형태인 그래프 컨볼루션 어텐션(GCA)을 도출합니다. 확률 블록 모델의 경우, GCA는 이상적인 스펙트럼 어텐션 메커니즘과 동일한 성능을 보장합니다. 또한, 어텐션을 따르는 소프트맥스 연산이 노이즈가 있는 고유 벡터를 깨끗한 고유 공간으로 근사적으로 투영하여 추가적인 노이즈 제거 효과를 제공한다는 것을 보여줍니다. 실험 결과, GCA는 합성 및 실제 데이터셋에서 그래프 노이즈 제거 및 확산을 개선하며, 성능 향상은 스펙트럼 다양성과 밀접하게 관련되어 있습니다. DiGress 모델에서는 GCA가 비싼 구조적 특징을 계산하지 않고도 표준 그래프 트랜스포머와 동등한 성능을 제공하며, 최근에 제안된 PEARL 위치 인코딩과 결합하여 명시적인 고유값 분해 계산을 피함으로써 품질 저하 없이 더 빠른 추론을 가능하게 합니다. 관련 코드는 다음 주소에서 확인할 수 있습니다: github.com/shervinkhalafi/graph_conv_att

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