Abstract

우리는 다양한 벤치마크 세트에서 선형 복잡성과 최첨단 결과를 가진 일반 강력하고 확장 가능한(GPS) 그래프 트랜스포머를 구축하는 방법에 대한 레시피를 제안한다. 그래프 트랜스포머(GT)는 최근 다양한 출판물로 그래프 표현 학습 분야에서 인기를 얻었지만 무엇이 좋은 위치 또는 구조적 인코딩을 구성하고 무엇이 이들을 차별화하는지에 대한 공통된 기반이 부족하다. 본 논문에서, 우리는 더 명확한 정의로 다양한 유형의 인코딩을 요약하고 로컬, 글로벌 또는 상대적인 인코딩으로 분류한다. 또한, GT는 수백 개의 노드가 있는 작은 그래프로 제한되며, 우리는 완전히 연결된 트랜스포머에서 로컬 실제 에지 집계를 분리하여 노드 수와 에지 O(N + E)에 선형인 복잡성을 가진 첫 번째 아키텍처를 제안한다. 우리는 우리의 아키텍처가 그래프의 보편적인 함수 근사치이기 때문에 이 디커플링이 표현성에 부정적인 영향을 미치지 않는다고 주장한다. 우리의 GPS 레시피는 (i) 위치/구조 인코딩, (ii) 로컬 메시지 전달 메커니즘 및 (iii) 글로벌 주의 메커니즘의 세 가지 주요 성분을 선택하는 것으로 구성된다. 우리는 여러 유형의 인코딩을 지원하고 작은 그래프와 큰 그래프 모두에서 효율성과 확장성을 제공하는 모듈식 프레임워크1을 구축하고 오픈 소스화한다. 우리는 11개의 벤치마크에서 아키텍처를 테스트하고 모든 벤치마크에서 매우 경쟁력 있는 결과를 보여줌으로써 모듈화와 다양한 전략의 조합으로 얻은 경험적 이점을 보여준다.

1 Introduction

그래프 변환기(GT)는 노드가 그래프의 다른 모든 노드에 주의를 기울일 수 있도록 허용함으로써 희소 메시지 전달 메커니즘(예: 과평활화 [46], 과평활화 [1] 및 표현성 한계 [60, 44]와 관련된 근본적인 제한을 완화한다. 이는 공유 결합[62]을 넘어 화학적 상호 작용을 모델링하거나 그래프 기반 로봇 제어[36]와 같은 여러 실제 애플리케이션에 도움이 된다. 그러나 전 세계적인 관심으로 인해 노드는 그래프와 그 하위 구조 내에서 더 잘 식별할 수 있어야 한다[14]. 이로 인해 최근 제안된 완전히 연결된 그래프 변압기 모델 [14, 35, 62, 43, 30]뿐만 아니라 스펙트럼 특징 [14, 35, 38]과 그래프 특징 [16, 9]을 활용하는 다양한 위치 인코딩 체계로 이어졌다. 또한 표준 전역 주의는 N개의 노드와 E개의 에지가 있는 그래프에 대해 2차 계산 비용 O(N2)를 발생시키며, 이는 GT를 최대 수백 개의 노드가 있는 작은 그래프로 제한한다.다양한 GT 모델이 특정 노드 식별 가능성 측면에 초점을 맞추고 있지만, GT 설계를 위한 원칙적인 프레임워크는 여전히 누락되어 있다. 본 연구에서는 이러한 격차를 해결하고 일반적이고 강력하며 확장 가능한(GPS) 그래프 트랜스포머를 구축하는 방법을 제안한다. 이 방법은 (i) 위치 인코딩(PE) 및 구조 인코딩(SE)을 노드, 에지 및 그래프 수준 입력 기능과 통합하는 것을 담당하는 임베디드 모듈, (ii) 로컬 메시지 전달 및 글로벌 주의 레이어의 조합을 사용하는 처리 모듈(그림 1 참조)을 정의합니다.임베딩 모듈은 제안된 여러 PE 및 SE 체계를 추가 노드 기능으로 제공하는 로컬 및 글로벌 수준으로 구성하는 반면, 위치 및 구조적 상대적 기능은 에지 기능에 기여한다. 처리 모듈은 노드 수 O(N)에서 선형으로 나타나는 주의 메커니즘을 포함하여 메시지 전달 그래프 신경망(MPNN)과 트랜스포머와 같은 글로벌 주의 사이에서 균형을 맞출 수 있는 계산 그래프를 정의한다.우리가 아는 한, 효율적인 주의 모델의 적용은 그래프 영역에서 아직 철저히 연구되지 않았다. 예를 들어, 한 연구[11]만이 작은 그래프에서 수행자 스타일 주의 근사치의 적응을 탐구한다. 완전히 연결된 그래프 변압기에 주의 편향으로 통합된 명시적 에지 특징에서 특정 문제가 발생한다 [35, 62]. 선형 변압기는 주의 매트릭스를 직접 구현하지 않으므로 에지 기능을 통합하는 것은 사소한 작업이 된다. 본 연구에서, 우리는 명시적인 에지 기능이 전역 그래프 주의를 위해 필요하지 않다고 가정하고 Performer [12]와 BigBird [65]를 예시적인 선형 주의 메커니즘으로 채택한다.우리의 기여는 다음과 같다. (i) 그림 1에서 시각화된 위치 및 구조적 인코딩과 로컬 메시지 전달 및 글로벌 주의를 통합하는 일반 강력하고 확장 가능한(GPS) GT Blueprint를 제공합니다. (ii) PE 및 SE에 대한 더 나은 정의를 제공하고 로컬, 글로벌 및 상대 범주로 구성합니다. (iii) 예를 들어 Performer [12] 또는 BigBird [65]에서 제공하는 선형 전역 주의를 가진 GPS가 수천 개의 노드를 가진 그래프로 확장되고 주의 모듈 내에 명시적인 에지 기능이 없어도 경쟁력 있는 결과를 보여주는 반면, 기존 완전 연결된 GT [35, 62]는 최대 수백 개의 노드의 그래프로 제한된다는 것을 보여준다(iv) Cond.여러 벤치마킹 데이터 세트의 관점에서 PE, 로컬 MPNN 및 글로벌 주의 구성 요소의 기여를 평가하는 광범위한 절제 연구. (v) 마지막으로, GraphGym [64]의 성공에 따라 모듈형 고성능 GraphGPS 패키지 내에서 청사진을 구현한다.