Abstract

그래프를 노드 기능 세트로 보고 구조 및 위치 정보를 트랜스포머 아키텍처에 통합하면 고전적인 그래프 신경망(GNN)으로 학습한 표현을 능가할 수 있음을 보여준다. 우리의 모델인 GraphiT는 (i) 그래프의 양의 확정 커널을 기반으로 한 자기 주의 점수의 상대적 위치 인코딩 전략을 활용하고, (ii) 길이가 짧은 경로와 같은 로컬 하위 구조를 열거하고 인코딩함으로써 이러한 정보를 인코딩한다. 우리는 많은 분류 및 회귀 작업에 대해 이 두 가지 아이디어를 철저히 평가하여 각각의 효과와 조합의 효과를 독립적으로 입증한다. 표준 벤치마크에서 우수한 성능을 발휘할 뿐만 아니라, 우리 모델은 예측을 설명하는 그래프 모티브를 해석하기 위한 자연 시각화 메커니즘을 인정하여 해석이 중요한 과학적 응용 프로그램의 잠재적인 강력한 후보가 된다.

1 Introduction

그래프 구조 데이터는 수많은 과학 응용 프로그램에 존재하며 점점 더 관심이 높아지고 있다. 이러한 데이터의 예는 아미노산의 서열로 볼 수 있는 계산 생물학 [29]의 단백질만큼 다양하며, 또한 아미노산의 3차 구조, 화학 정보학 [11]의 분자, 컴퓨터 비전 및 컴퓨터 그래픽의 형태 [38], 전자 건강 기록 또는 소셜 네트워크의 커뮤니티를 나타내는 그래프로도 볼 수 있다. 머신 러닝을 위한 그래프 표현을 설계하는 것은 새로운 것은 아니지만 특히 활발한 연구 분야이며 [4] 현재 그래프 신경망에 중점을 두고 있다[6, 7, 18, 28, 37, 40]. 주요 어려움은 계산적으로 다루기 쉽고, 주어진 작업에 적응할 수 있으며, 위상 구조와 국소 특성이 다른 그래프를 구별할 수 있는 그래프 표현을 찾는 것이다.

본 논문에서, 우리는 자연어 처리[36]의 표준 아키텍처가 되었고 컴퓨터 비전[9]과 계산 생물학[27]에서 입지를 굳히고 있는 변압기에 관심이 있다. 시퀀스 데이터를 위해 긴 컨텍스트에 걸쳐 정보를 집계하는 변압기의 기능은 다층 방식으로 이웃의 로컬 정보를 연속적으로 집계하는 GNN에 흥미로운 도전자가 된다.대조적으로, 변압기의 단일 자기 주의 계층은 잠재적으로 입력 그래프의 모든 노드가 통신할 수 있게 할 수 있다. 지불해야 할 대가는 이 핵심 구성 요소가 입력 노드의 순열에 불변하므로 그래프의 위상 구조를 고려하지 않고 중요한 정보를 손실한다는 것이다.

시퀀스 데이터의 경우, 이 문제는 각 토큰의 위치 정보를 인코딩하여 트랜스포머 아키텍처에 제공함으로써 해결된다. 그래프의 경우 노드 위치를 인코딩하는 단일 방법이 없기 때문에 문제가 더 어렵다. 이러한 이유로, 그래프 표현을 위해 바닐라 트랜스포머를 사용하려는 시도는 거의 없었다. 우리가 아는 한, 가장 가까운 작업은 Dwivedi와 Bresson [12]의 그래프 변압기 아키텍처로 보이며, 이들은 그래프 Laplacian [1]의 고유 벡터를 기반으로 우아한 위치 인코딩 전략을 제안한다. 그러나 그들은 GNN에서와 같이 인접 노드에만 주의를 적용하는 데 초점을 맞추고 있으며, 그들의 결과는 모든 노드가 통신하도록 하는 것이 경쟁력 있는 접근 방식이 아님을 시사한다.우리의 논문은 다른 관점을 제공하고 약간 다른 결론에 도달한다. 우리는 지역 통신이 실제로 종종 더 효과적이지만, 글로벌 통신을 갖춘 변압기도 좋은 결과를 얻을 수 있음을 보여준다. 이를 위해 모델인 GraphiT(변압기의 그래프 구조 인코딩) 내에서 로컬 그래프 구조를 인코딩하는 일련의 기술을 소개한다. 더 정확히 말하면, GraphiT는 독립적으로 결합되거나 사용될 수 있는 두 가지 성분에 의존한다. 첫째, [35]에서 시퀀스에 대해 도입된 관점인 양의 확정 커널을 사용하여 주의 점수를 가중하기 위한 상대적 위치 인코딩 전략을 제안한다. 이 개념은 노드 간의 유사성을 인코딩하는 강력한 도구인 그래프 [21, 33]의 커널에 대한 풍부한 문헌을 활용할 수 있기 때문에 그래프에 특히 매력적이다.두 번째 아이디어는 그래프의 로컬 구조를 인코딩하는 컴퓨팅 특징에 있다. 이를 위해, 우리는 [7]의 그래프 컨볼루션 커널 네트워크(GCKN)의 원리를 활용하는데, 이는 작은 하위 구조(예: 경로 또는 하위 트리 패턴)를 열거하고 인코딩하는 것으로 구성되며, 변환기 모델에 대한 입력으로 사용될 수 있다.우리는 몇 가지 분류 및 회귀 벤치마크에 대한 접근 방식의 효과를 보여줌으로써 글로벌 또는 로컬 주의 레이어를 가진 GraphiT가 다양한 작업에서 GNN을 능가할 수 있음을 보여주며, 또한 기본적인 시각화 메커니즘을 통해 차별적인 그래프 모티브를 자동으로 발견할 수 있으며, 이는 잠재적으로 과학화에 유용하다.c 해석이 중요한 응용 프로그램.

2 Related work

Graph kernels.

기계 학습 작업에 대한 그래프를 표현하는 고전적인 방법은 그래프에 대한 고차원 임베딩을 정의하는 것으로, 선형 모델(예: 지원 벡터 머신)으로 예측을 수행하는 데 사용될 수 있다. 그래프 커널은 일반적으로 그래프 내에 존재하는 로컬 하위 구조의 발생 횟수를 계산하여 이러한 임베딩을 제공한다[4]. 목표는 표현 표현으로 이어지는 하위 구조를 충분히 차별적으로 선택하는 동시에 빠른 알고리듬이 이러한 임베딩 사이의 내부 제품을 계산할 수 있도록 하는 것이다. 예를 들어, walk은 그러한 목적[14]뿐만 아니라 최단 경로 [5], 하위 트리 [15, 24, 31] 또는 그래플릿 [32]을 위해 사용되어 왔다. 우리의 작업은 짧은 경로를 사용하지만, 원칙적으로 다른 하부 구조가 사용될 수 있습니다. 그래프를 비교하는 맥락에서 사용되는 그래프 커널은 노드의 임베딩을 계산하기 위해 섹션 3에서 소개할 그래프의 커널과는 다른 작업 라인입니다.