Recipe for a General, Powerful, Scalable Graph Transformer
범용적이고 강력하며 확장 가능한 그래프 트랜스포머의 레시피
Ladislav Rampášek, Mikhail Galkin, Vijay Prakash Dwivedi, et al. (2022)
위치/구조 인코딩(PE/SE), 로컬 MPNN 어텐션, 글로벌 Transformer 어텐션을 하나의 프레임워크로 결합하는 GraphGPS를 제안하여, 그래프 Transformer의 설계 공간을 체계적으로 정리하고 다양한 벤치마크에서 최고 수준의 성능을 달성했다.
배경
Transformer가 NLP와 비전에서 큰 성공을 거둔 후, 그래프 데이터에 Transformer를 적용하려는 시도가 활발해졌다. 그러나 그래프 Transformer에는 고유한 도전이 있었다: (1) 그래프에는 자연스러운 위치 개념이 없어 위치 인코딩 설계가 어렵고, (2) 모든 노드 쌍에 대한 전역 어텐션은 O(N^2) 비용이 들어 대규모 그래프에 비효율적이며, (3) 로컬 이웃 정보를 명시적으로 활용하는 MPNN의 귀납적 편향(inductive bias)을 어떻게 통합할지 불명확했다. SAN, Graphormer 등 초기 그래프 Transformer가 제안되었지만, 통일된 설계 원칙이 부재했다.
핵심 아이디어
GraphGPS(General, Powerful, Scalable Graph Transformer)는 그래프 Transformer를 세 가지 모듈의 조합으로 구조화하는 레시피를 제안한다. (1) 위치/구조 인코딩(PE/SE): 랜덤 워크 기반(RWSE), 라플라시안 고유벡터(LapPE), 또는 학습 가능한 구조 인코딩을 노드/엣지 특징에 추가하여 위치 정보를 제공한다. (2) 로컬 메시지 전달: GCN, GIN, GINE 등 기존 MPNN으로 로컬 이웃 정보를 처리한다. (3) 글로벌 어텐션: Transformer 셀프 어텐션으로 장거리 의존성을 포착한다. 각 레이어에서 로컬 MPNN과 글로벌 Transformer의 출력을 결합하여, 두 접근의 장점을 동시에 취한다.
방법론
각 GPS 레이어는 다음과 같이 구성된다: (1) 노드 특징에 PE/SE를 추가, (2) MPNN 서브레이어(GCN, GIN, GINE, PNA 등 선택 가능)로 로컬 이웃 정보 처리, (3) 전역 Transformer 셀프 어텐션(또는 효율적 변형인 Performer, BigBird 등), (4) 두 출력의 합산 또는 연결, (5) FFN + 잔차 연결 + 정규화. 대규모 그래프에서는 전역 어텐션을 선형 복잡도 변형으로 대체할 수 있다. 위치 인코딩으로는 SignNet을 사용한 고유벡터 기반 LapPE와 RWSE를 권장한다. 하이퍼파라미터 탐색으로 각 데이터셋에 최적의 조합을 찾는다.
주요 결과
GraphGPS는 ZINC(분자 성질 예측), PATTERN/CLUSTER(패턴 인식), MolPCBA/MolHIV(분자 활성), PCQM4Mv2(양자 화학) 등 11개 벤치마크에서 평가되었다. ZINC에서 MAE 0.070을 달성하여 기존 GNN 및 그래프 Transformer를 크게 능가했다. PCQM4Mv2에서도 GCN+Transformer 조합이 단독 MPNN이나 단독 Transformer보다 우수한 성능을 보였다. 특히 로컬 MPNN과 글로벌 어텐션의 결합이 단독 사용보다 일관되게 좋은 결과를 보여, 두 접근의 상호 보완성을 입증했다.
임팩트
GraphGPS는 그래프 Transformer 설계의 체계적 가이드라인을 제공하여, 이후 연구들이 비교하고 발전시킬 수 있는 통일된 프레임워크를 확립했다. 로컬+글로벌 어텐션의 결합, PE/SE의 중요성 등의 발견은 이후 Exphormer, GRIT, TokenGT 등 후속 그래프 Transformer 설계에 직접 반영되었다. GraphGPS 프레임워크의 오픈소스 구현은 그래프 Transformer 연구의 재현성과 접근성을 크게 높였으며, GNN과 Transformer의 융합이라는 연구 방향의 표준 참조점이 되었다.