Exphormer: 그래프를 위한 스파스 트랜스포머

그래프 트랜스포머는 다양한 그래프 학습 및 표현 작업에 대해 유망한 아키텍처로 부상하고 있다. 그러나 이러한 성공에도 불구하고, 메시지 전달 네트워크와 경쟁 가능한 정확도를 유지하면서도 대규모 그래프에 그래프 트랜스포머를 확장하는 것은 여전히 도전적인 과제이다. 본 논문에서는 강력하고 확장 가능한 그래프 트랜스포머를 구축하기 위한 Exphormer 프레임워크를 제안한다. Exphormer는 가상의 글로벌 노드와 확장 그래프(expander graphs)를 기반으로 하는 희소 주의(mechanism)를 포함하며, 스펙트럼 확장성(spectral expansion), 의사난수성(pseudorandomness), 희소성(sparsity)과 같은 수학적 특성 덕분에 그래프 크기에 비례하는 선형 복잡도를 가지면서도, 도출된 트랜스포머 모델의 바람직한 이론적 성질을 증명할 수 있다. 우리는 최근 제안된 GraphGPS 프레임워크에 Exphormer를 통합함으로써, 다양한 그래프 데이터셋에서 경쟁력 있는 실험적 성과를 달성함을 보이며, 세 가지 데이터셋에서는 최신 기준(SOTA) 성과를 기록하였다. 또한 Exphormer가 이전 그래프 트랜스포머 아키텍처보다 더 큰 그래프 데이터셋에 확장 가능함을 입증하였다. 코드는 \url{https://github.com/hamed1375/Exphormer}에서 확인할 수 있다.