VecFormer: 그래프 토큰 어텐션을 활용한 효율적이고 일반화 가능한 그래프 트랜스포머를 향하여

VecFormer: Towards Efficient and Generalizable Graph Transformer with Graph Token Attention

그래프 트랜스포머(Graph Transformer)는 그래프 표현 학습 분야에서 뛰어난 능력을 입증해 왔다. 그러나 기존 접근 방식은 두 가지 주요한 한계에 직면해 있다: (1) 대부분의 모델이 기하급수적으로 증가하는 연산 복잡도 문제를 겪어 대규모 그래프로 확장하기 어렵다; (2) 노드 수준의 연산에 기반한 어텐션 메커니즘은 모델의 유연성을 제한하고 분포 외(out-of-distribution, OOD) 시나리오에서 저조한 일반화 성능을 초래한다. 이러한 문제를 해결하기 위해, 우리는 특히 OOD 환경에서의 노드 분류를 위한 효율적이고 일반화 성능이 뛰어난 모델인 \textbf{VecFormer}(\textbf{Vec}tor Quantized Graph Trans\textbf{former})를 제안한다. VecFormer는 2단계 학습 패러다임을 채택한다. 첫 번째 단계에서는 두 개의 코드북을 사용하여 노드 특징과 그래프 구조를 재구성하며, 풍부한 의미를 지닌 \texttt{Graph Codes}를 학습하는 것을 목표로 한다. 두 번째 단계에서는 변환된 교차 코드북을 기반으로 \texttt{Graph Token} 수준에서 어텐션 메커니즘을 수행하여, 연산 복잡도를 줄이는 동시에 모델의 일반화 능력을 향상시킨다. 다양한 크기의 데이터셋에 대한 광범위한 실험을 통해 VecFormer가 성능과 속도 양면에서 기존 그래프 트랜스포머보다 우수함을 입증한다.

Graph Transformer has demonstrated impressive capabilities in the field of graph representation learning. However, existing approaches face two critical challenges: (1) most models suffer from exponentially increasing computational complexity, making it difficult to scale to large graphs; (2) attention mechanisms based on node-level operations limit the flexibility of the model and result in poor generalization performance in out-of-distribution (OOD) scenarios. To address these issues, we propose \textbf{VecFormer} (the \textbf{Vec}tor Quantized Graph Trans\textbf{former}), an efficient and highly generalizable model for node classification, particularly under OOD settings. VecFormer adopts a two-stage training paradigm. In the first stage, two codebooks are used to reconstruct the node features and the graph structure, aiming to learn the rich semantic \texttt{Graph Codes}. In the second stage, attention mechanisms are performed at the \texttt{Graph Token} level based on the transformed cross codebook, reducing computational complexity while enhancing the model's generalization capability. Extensive experiments on datasets of various sizes demonstrate that VecFormer outperforms the existing Graph Transformer in both performance and speed.