일반적이고 강력하며 확장 가능한 그래프 트랜스포머의 레시피

우리는 일반적, 강력하고 확장 가능한 (GPS) 그래프 트랜스포머를 구축하는 방법에 대한 레시피를 제안합니다. 이 그래프 트랜스포머는 선형 복잡도와 다양한 벤치마크에서 최신 연구 결과를 달성합니다. 최근 여러 논문을 통해 그래프 표현 학습 분야에서 그래프 트랜스포머 (GTs)의 인기가 증가했지만, 좋은 위치적 또는 구조적 인코딩이 무엇인지, 그리고 그것들이 어떻게 다른지에 대한 공통적인 기반이 부족합니다. 본 논문에서는 이러한 인코딩의 종류들을 더 명확한 정의로 요약하고, 그들을 $\textit{국소적}$, $\textit{전역적}$ 또는 $\textit{상대적}$으로 분류합니다.기존의 GTs는 몇백 개의 노드를 가진 작은 그래프에 제약을 받았습니다. 여기서 우리는 국소적인 실제 엣지 집합과 완전 연결된 트랜스포머를 분리하여 노드와 엣지 수에 선형적으로 복잡도가 증가하는 ($O(N+E)$) 첫 번째 아키텍처를 제안합니다. 우리는 이 분리가 표현력을 부정적으로 영향을 미치지 않는다고 주장하며, 우리의 아키텍처는 그래프 상에서 보편적인 함수 근사자임을 입증합니다. 우리의 GPS 레시피는 3개의 주요 성분을 선택하는 것으로 구성됩니다: (i) 위치적/구조적 인코딩, (ii) 국소 메시지 전달 메커니즘, (iii) 전역 주목 메커니즘.우리는 여러 유형의 인코딩을 지원하고, 작은 그래프와 큰 그래프 모두에서 효율성과 확장성을 제공하는 모듈화된 프레임워크인 $\textit{그래프GPS}$를 제공합니다. 우리는 16개의 벤치마크에서 아키텍처를 테스트하여 모든 벤치마크에서 매우 경쟁력 있는 결과를 보여주며, 모듈성과 다양한 전략의 조합으로 얻은 경험적인 이점을 입증합니다.