Abstract

우리는 그래프 특정 수정 없이 표준 트랜스포머가 이론과 실제 모두에서 그래프 학습에서 유망한 결과를 가져올 수 있음을 보여준다. 그래프를 지정하면 모든 노드와 에지를 독립적인 토큰으로 처리하고 토큰 임베딩으로 보강한 후 트랜스포머에 공급한다. 적절한 토큰 임베딩 선택을 통해, 우리는 이 접근 방식이 적어도 이론적으로 등변 선형 레이어로 구성된 불변 그래프 네트워크(2-IGN)만큼 표현력이 있으며, 이는 이미 모든 메시지 전달 그래프 신경망(GNN)보다 표현력이 뛰어나다는 것을 증명한다.대규모 그래프 데이터 세트(PCQM4Mv2)에 대해 교육할 때, 우리의 방법은 만들어졌다.토큰화된 그래프 변환기(TokenGT)는 정교한 그래프 특정 유도 편향을 가진 변환기 변형에 비해 GNN 기준선과 경쟁 결과에 비해 훨씬 더 나은 결과를 달성한다.

1 Introduction

최근 몇 년 동안 Transformer [57]는 자연어 처리 [17, 7], 컴퓨터 비전 [18] 및 강화 학습 [9]과 같은 광범위한 종류의 기계 학습 문제에서 다용도 아키텍처로 역할을 해왔다. 트랜스포머의 완전 주의 구조는 임의의 구조의 입력과 출력을 취, 처리 및 관련시킬 수 있을 만큼 일반적이고 강력하기 때문에 데이터 및 작업별 유도 편향이 네트워크 아키텍처에 적용될 필요가 없기 때문이다. 대규모 교육과 결합하여 다양한 데이터 양식과 심지어 양식 혼합을 포함하는 광범위한 문제를 해결할 수 있는 다용도 모델을 구축하기 위한 새로운 장을 엽니다 [30, 29, 49].획기적인 발전에 영감을 받은 그래프 학습 영역에서, 여러 연구는 메시지 전달이 이전에 지배적이었던 그래프 신경망(GNN) 아키텍처에 자기 주의를 결합하려고 시도했다[43]. 그러나 노드 전반에 걸친 글로벌 자기 주의는 그래프 구조를 반영할 수 없기 때문에 이러한 방법은 그래프별 아키텍처 수정을 도입한다. 여기에는 메시지 전달과 함께 글로벌 자기 주의를 사용하여 지역 이웃에 대한 자기 주의 제한[58, 44, 19]이 포함된다.GNN [50, 37, 31] 및 주의 편향[60, 65, 28, 47]을 통해 글로벌 자기 주의에 에지 정보를 주입한다. 적절한 성능에도 불구하고, 그러한 수정은 특히 다중 작업 및 다중 모달 범용 아키텍처로의 미래 통합을 고려할 때, 다용성 측면에서 제한적인 제약이 될 수 있다[30]. 또한 이러한 방법은 순수한 자기 주의에서 벗어나 과잉 평활[34, 8, 45]과 같은 메시지 전달 문제를 상속할 수 있으며, 예를 들어 표준 자기 주의를 위해 개발된 선형 주의[54]와 같은 유용한 엔지니어링 기법과 호환되지 않을 수 있다.대신 그래프에 표준 트랜스포머를 직접 적용하는 반대 방향을 탐구한다. 이를 위해 모든 노드와 에지를 독립적인 토큰으로 처리하고 적절한 토큰별 임베딩으로 보강한 후 토큰을 표준 트랜스포머에 입력으로 공급한다. 이 모델은 언어와 시각에 사용되는 트랜스포머와 동일하게 작동한다. 각 노드 또는 에지는 문장 또는 이미지의 패치에 있는 단어와 동일한 토큰으로 처리된다[57, 18]. 아마도 놀랍게도, 우리는 이 간단한 접근 방식이 이론과 실제 모두에서 강력한 그래프 학습자를 산출한다는 것을 보여준다.
핵심 이론적 결과로, 우리는 적절한 토큰별 임베딩을 통해 노드 및 에지 토큰이 그래프의 모든 순열 등가 선형 연산자를 근사할 수 있음을 증명한다[40].놀랍게도, 우리는 노드 식별자와 유형 식별자로 구성된 임베딩의 매우 간단한 선택만으로도 정확한 근사에 충분하다는 것을 보여준다. 이는 임베딩과 충분한 주의 헤드로 트랜스포머가 적어도 2차 불변 그래프 네트워크(2-IGN)[40, 31]만큼 표현력이 뛰어나다는 탄탄한 이론적 보장을 제공하며, 이는 이미 모든 메시지 전달 GNN[21]보다 표현력이 뛰어나다. 이는 또한 실제 그래프 데이터[70]에 종종 충분한 2차원 Weisfeiler-Lehman(WL) 그래프 동형 테스트[39]만큼 우수한 표현력을 즉시 모델에 부여한다. 우리는 또한 이론적 결과를 순서 k 하이퍼 에지가 있는 하이퍼그래프로 확장하여 순서 k 일반화 토큰 임베딩을 가진 트랜스포머가 적어도 k-IGN만큼 표현력이 뛰어나고 결과적으로 k-WL 테스트라는 것을 보여준다.우리는 주로 3M 분자 그래프를 포함하는 PCQM4Mv2 대규모 양자 화학적 특성 예측 데이터 세트에서 토큰화 그래프 변환기(TokenGT)라는 우리의 모델을 테스트한다[26]. TokenGT는 최소한의 그래프별 아키텍처 수정을 수반하지만 모든 GNN 기준선보다 훨씬 우수한 성능을 발휘하여 대규모 훈련과 결합된 Transformer 아키텍처의 장점이 GNN의 하드 유도 편향의 이점을 능가한다는 것을 보여준다. 게다가, 토큰GT는 강력한 그래프별 수정을 통해 Transformer 변종과 비교하여 경쟁력 있는 성능을 달성합니다 [65, 28, 47]. 마지막으로, 성능을 크게 저하시키지 않고 선형 계산 비용을 가능하게 하는 커널 어텐션[11]을 사용하여 TokenGT가 이러한 변형과 대조적으로 Transformer에서 효율적인 근사치를 자연스럽게 활용할 수 있음을 보여준다.