Abstract

최근 많은 인공지능 분야에서 큰 성공을 거둔 트랜스포머 모델은 그래프 구조 데이터를 모델링하는 데 큰 잠재력을 발휘하고 있다. 지금까지 그래프 구조 데이터에 적응하기 위해 다양한 트랜스포머가 제안되었다. 그러나 그래프에 대한 이러한 트랜스포머 변형에 대한 포괄적인 문헌 검토와 체계적인 평가는 여전히 이용할 수 없다. 그래프에 대한 기존 트랜스포머 모델을 분류하고 다양한 그래프 작업에 대한 효과를 체계적으로 조사하는 것이 필수적이다. 본 설문조사에서, 우리는 아키텍쳐 설계 관점에서 다양한 그래프 트랜스포머 모델에 대한 포괄적인 검토를 제공한다.우리는 먼저 기존 모델을 분해하고 그래프 정보를 바닐라 트랜스포머에 통합하는 세 가지 일반적인 방법을 결론짓는다. 1) 보조 모듈로써의 GNN, 2) 향상된 위치 임베딩 적용, 3) 그래프의 개선된 어텐션 매트릭스. 또한 대표적인 구성 요소를 세 그룹으로 구현하고 다양한 종류의 유명한 그래프 데이터 벤치마크에 대한 종합적인 비교를 수행하여 각 구성 요소의 실제 성능 이득을 조사한다. 우리의 실험은 트랜스포머에서 현재 그래프 특정 모듈의 이점을 확인하고 다양한 종류의 그래프 작업에서 장점을 드러낸다.

1 Introduction

      그래프는 객체 집합(노드)과 그 관계(에지)를 구조적으로 묘사하는 데이터 구조의 일종이다. 고유 비유클리드 데이터 구조로서 그래프 분석은 노드 분류, 링크 예측, 클러스터링과 같은 작업에 중점을 둔다. 딥 러닝을 이용한 그래프 분석에 대한 최근 연구는 딥 러닝 모델의 풍부한 표현력으로 인해 점점 더 많은 관심을 끌고 있다. GNN(Graph Neural Networks,2016)은 딥 러닝 기반 방법의 일종으로 최근 설득력 있는 성능으로 인해 널리 사용되는 그래프 분석 도구가 되고 있다. 현재 GNN의 대부분은 메시지 전달 패러다임을 기반으로 하며, 표현력은 Weisfeiler-Leham 동형 계층 구조로 제한된다(WL 알고리즘을 활용한 그래프 분류).더 나쁜 것은 [Kreuzer et al., 2021]이 지적한 바와 같이, GNN은 반복적인 로컬 집계로 인한 과잉 평활(over-smoothing) 문제와 모델 깊이의 증가에 따른 지수 계산 비용으로 인한 과잉 스쿼싱 문제로 어려움을 겪고 있다.여러 연구는 이러한 문제를 해결하려고 한다. 그럼에도 불구하고, 그들 중 어느 누구도 메시지 전달 패러다임에서 이러한 문제들을 제거할 수 없는 것 같다.
     한편, 트랜스포머와 그 변형은 강력한 종류의 모델로서 자연어 처리(NLP), 컴퓨터 비전(CV) , 시계열 분석, 오디오 처리 등 다양한 분야에서 중요한 역할을 하고 있다. 더욱이, 최근 몇 년 동안 모델링 그래프에서 많은 성공적인 트랜스포머 변형을 목격했다. 이러한 모델은 양자 특성 예측, Catalyst Discovery 및 추천 시스템과 같은 많은 애플리케이션에서 GNN에 비해 경쟁적이거나 심지어 우수한 성능을 달성했다. 그러나 이러한 트랜스포머 변형에 대한 문헌 검토와 체계적인 평가는 부족하다.
     이 조사는 그래프 구조 데이터에 트랜스포머를 통합하는 것에 대한 현재 연구 진행 상황에 대한 개요를 제공한다. 구체적으로, 우리는 건축 설계 관점에서 20개 이상의 그래프 트랜스포머 모델에 대한 포괄적인 검토를 제공한다. 우리는 먼저 기존 모델을 해체하고 그래프 정보를 바닐라 트랜스포머에 통합하는 세 가지 일반적인 방법을 결론짓는다.
     1) GNN을 보조 모듈로, 즉 GNN을 트랜스포머 아키텍처에 직접 주입한다. 구체적으로, GNN 레이어와 트랜스포머 레이어 사이의 상대적 위치에 따라 세가지 종류로 구분할 수 있는데, 기존의 GNN 트랜스포머 아키텍처는 (a) 트랜스포머 블록 후에 GNN이 위치하는 경우 , (b) GNN과 트랜스포머를 각각 레이어마다 쌓는 경우, (c) GNN 블록 및 트랜스포머 블록을 각 레이어의 병렬시키는 경우가 있다 .

      2) 그래프의 향상된 위치 임베딩, 즉 그래프 구조를 위치 임베딩 벡터로 압축하여 바닐라 트랜스포머 모델에 공급하기 전에 입력에 추가한다. 이 그래프 위치 임베딩은 정도(degree) 및 중심성(centrality)과 같은 그래프의 구조 정보에서 파생될 수 있다.

      3) Improved Attention Matrices from Graphs, 즉 그래프 바이어스 term을 통해 그래프를 먼저 어텐션 계산에 주입하거나 그래프의 로컬 인접 노드에만 주의를 기울이는 노드를 제한하여 어텐션 마스킹 메커니즘으로 계산 가능하다.

      또한 다양한 종류의 그래프 작업에서 기존 모델의 효과를 조사하기 위해 3개 그룹으로 대표 구성 요소를 구현하고 각 구성 요소의 실제 성능 이득을 균일하게 테스트하기 위해 6개의 인기 있는 그래프 기반 벤치마크에 대한 포괄적인 절제 연구를 수행한다. 우리의 실험은 다음을 나타낸다:
1) 그래프 정보를 통합한 현재 모델은 그래프 수준 및 노드 수준 작업 모두에서 Transformer의 성능을 향상시킬 수 있다.
2) GNN을 보조 모듈로 활용하고 그래프에서 주의 매트릭스를 개선하는 것은 일반적으로 그래프를 위치 임베딩으로 인코딩하는 것보다 더 많은 성능 향상에 기여한다.
3) 그래프 수준 작업에서의 성능 향상은 노드 수준 작업에서의 성능 향상보다 더 중요하다.
4) 다른 종류의 그래프 작업은 다른 모델 그룹과 즐긴다(enjoy).본 설문조사의 나머지 내용은 다음과 같이 구성되어 있습니다.
먼저 섹션 2에서 일반적인 바닐라 트랜스포머 아키텍처를 검토합니다. 3절에서는 트랜스포머 변종에 대한 기존 작업을 그래프에서 요약하고 이러한 방법을 세 그룹으로 체계적으로 분류합니다. 섹션 4에서는 이러한 제안된 모델의 효과와 호환성을 검증하기 위해 포괄적인 절제 연구가 수행된다. 섹션 5에서는 이 설문조사를 마무리하고 향후 몇 가지 연구 방향에 대해 논의한다.

2 Transformer Architecture

multi-head

3 Transformer Architecture for Graphs

표준 트랜스포머의 셀프 어텐션 메커니즘은 실제로 입력 토큰을 완전히 연결된 그래프로 간주하며, 이는 데이터 중 본질적인 그래프 구조에 구애받지 않는다. Transformer가 위상 구조를 인식할 수 있도록 하는 기존 방법은 일반적으로 1) Transformer(GA)의 보조 모듈로서의 GNN, 2) 그래프의 위치 임베딩 개선, 3) 그래프(AT)의 주의 행렬 개선의 세 그룹으로 분류된다. 표 1에 이러한 3차원의 관점에서 관련 문헌을 요약한다.

3.1 GNNs as Auxiliary Modules in Transformer

셀프 어텐션의 전역 관계 모델링으로부터 이익을 얻기 위해 구조적 지식을 포함하는 가장 직접적인 해결책은 그래프 신경망을 트랜스포머 아키텍처와 결합하는 것이다. 일반적으로, GNN 레이어와 트랜스포머 레이어 사이의 상대적인 위치에 따라, GNN을 갖는 기존 트랜스포머 아키텍처는 그림 1과 같이 세 가지 유형으로 분류된다: (1) GNN 블록 위에 트랜스포머 블록을 구축, (2) GNN 블록과 트랜스포머 블록을 교대로 적층, (3) GNN 블록과 트랜스포머를 병렬화.

첫 번째 아키텍처는 세 가지 옵션 중에서 가장 자주 채택된다. 예를 들어, GraphTrans [Jain et al., 2021]는 표준 GNN 계층 위에 Transformer 하위 네트워크를 추가합니다. GNN 계층은 노드의 바로 이웃 구조의 로컬 표현을 학습하기 위해 특수 아키텍처로 수행하는 반면, Transformer 하위 네트워크는 위치에 구애받지 않는 방식으로 모든 쌍별 노드 상호 작용을 계산하여 모델 전역 추론 기능에 힘을 실어준다.GraphTrans는 생물학, 컴퓨터 프로그래밍 및 화학의 그래프 분류 작업에 대해 평가되며 벤치마크보다 일관된 개선을 달성한다.
Grover [Long et al., 2020]는 노드 수준 특징과 에지 수준 특징을 각각 나타내는 두 개의 GT 변환기 모듈로 구성된다. 각 G트랜스포머에서 입력은 먼저 dyMPN이라는 이름의 맞춤형 GNN에 공급되어 벡터를 그래프의 노드에서 쿼리, 키 및 값으로 추출한 다음 표준 다중 헤드 주의 블록을 따른다. 이 바이 레벨 정보 추출 프레임워크를 통해 모델은 분자 데이터에서 구조 정보를 포착하고 노드 간의 전역 관계를 추출할 수 있어 그로버의 대표력을 향상시킬 수 있다.
GraphiT [Mialon et al., 2021]는 또한 하나의 Graph Convolutional Kernel Network (GCKN) [Chen et al., 2020] 레이어를 채택하여 원래 기능에서 구조 인식 표현을 생성하고 트랜스포머 아키텍처의 입력으로 연결하는 첫 번째 아키텍처에 속한다. 여기서 GCKN은 GNN과 유사한 일련의 그래프 피쳐 맵을 생성하는 다중 레이어 모델이다. GNN과 달리 GCKN의 각 레이어는 각 노드의 로컬 하위 구조를 열거하고 커널 임베딩을 사용하여 인코딩하고 하위 구조 표현을 출력으로 집계한다. 기능 맵의 이러한 표현은 이웃 집계를 기반으로 하는 기존 GNN보다 더 많은 구조적 정보를 전달한다.
Mesh Graphormer [Lin et al., 2021]는 3D 메쉬 정점과 바디 조인트 사이의 로컬 및 글로벌 상호 작용을 모델링하기 위해 다중 헤드 자기 주의 레이어에 GRB(Graph Resident Block)를 적층함으로써 두 번째 아키텍처를 따른다. 구체적으로, 방정식 3의 다중 헤드 자기 주의(MHSA)에 의해 생성된 문맥화된 특징 M을 고려할 때, 메시 그래포머는 다음과 같이 각 트랜스포머 블록의 그래프 컨볼루션(graph convolution)을 사용하여 로컬 상호 작용을 개선한다.

3.2 Improved Positional Embeddings from Graphs

그래프 신경망과 트랜스포머를 결합하면 그래프 구조 데이터를 모델링하는 데 효과를 보였지만, 이를 통합하는 최상의 아키텍처는 여전히 문제로 남아 있으며 많은 하이퍼 매개 변수 검색이 필요하다. 따라서 Transformer 아키텍처를 조정하지 않고 그래프 인코딩 전략을 탐색하는 것은 의미가 있다. 문장과 같은 순차적 데이터에 대한 트랜스포머의 위치 인코딩과 유사하게 그래프 구조를 위치 임베딩(PE) 벡터로 압축하여 실제 트랜스포머 모델에 공급하기 전에 입력에 추가하는 것도 가능하다.

2020에 제안된 Laplacian eigenvectors를 이용한 방법

2021에 제안된 SVD를 이용한 방법

인접 행렬을 조밀한 위치 임베딩으로 압축하려는 고유 PE 및 SVD PE와는 달리, 인접 행렬의 추출에서 특정 구조 정보를 인코딩하는 몇 가지 휴리스틱 방법이 존재한다. 예를 들어, Graphormer [Ying et al., 2021]는 각도 중심성을 신경망에 대한 추가 신호로 사용한다. 구체적으로, Graphformer는 각 노드에 그 정도와 정도에 따라 두 개의 실제 값 임베딩 벡터를 할당한다. i번째 노드의 경우, degree에 대한 인식 표현은 다음과 같이 표시된다.

중심성(centrality)를 포착하는데 사용하는 방법(해당 노드에서 얼마만큼 input으로 오는지 output으로 오는지를 나타낸다)

Graph-BERT [Zhang et al., 2020]는 노드 위치 정보를 내장하기 위해 세 가지 유형의 PE를 소개한다. 즉, Weisfeiler-Lehman 알고리듬으로 레이블이 지정된 서로 다른 코드를 나타내는 절대 WL-PE, 친밀도 기반 PE 및 홉 기반 PE 모두 샘플링된 하위 그래프에 변형된 것이다. [Cai and Lam, 2020]은 트리 구조의 추상적 의미 표현(AMR) 그래프에 그래프 변환을 적용한다. 전체 문장 의미론에서 해당 개념의 중요성에 대한 플래그로 루트 노드로부터의 최소 거리를 인코딩하여 각 노드에 대한 거리 임베딩을 채택한다. [Kreuzer et al., 2021]은 주어진 그래프에서 각 노드의 위치를 학습하기 위해 전체 라플라시안 스펙트럼을 활용할 수 있는 학습된 위치 인코딩을 제안한다.

3.3 Improved Attention Matrices from Graphs

노드 위치 임베딩은 Transformer 아키텍처에 그래프를 먼저 주입하는 편리한 방법이지만, 그래프 구조를 고정 크기 벡터로 압축하는 과정은 정보 손실로 인해 효과를 제한할 수 있다. 이를 위해, 다른 작업 그룹은 그래프 정보를 기반으로 주의 행렬 계산을 개선하려고 시도한다.


기존 방식의 계산으로는 주변 정보들만을 반영하여 계산할 수밖에 없었으나,

이렇게 만들면 엣지에 대한정보(E')역시 반영하여 계산이 가능해진다.

이 관행의 가능한 확장 중 하나는 서로 다른 그래프 사전으로 서로 다른 헤드의 주의 행렬을 마스킹하는 것이다. 원래의 다중 헤드 자체 주의 블록에서, 서로 다른 주의 헤드는 서로 다른 노드의 서로 다른 표현 하위 공간의 정보에 암묵적으로 주의를 기울인다. 한편, 이 경우 그래프 마스킹 메커니즘을 사용하여 그래프 사전이 있는 다른 하위 공간에 헤드를 명시적으로 적용하면 그래프 데이터에 대한 모델 대표 기능이 더욱 향상된다. 예를 들어 [Yao et al., 2020]은 확장된 Levi 그래프를 기반으로 주의를 계산합니다. 레비 그래프는 서로 다른 유형의 에지를 포함하는 이기종 그래프이기 때문이다.이들은 먼저 모든 에지 유형을 단일 유형으로 그룹화하여 연결된 하위 그래프라고 하는 균일한 하위 그래프를 얻습니다.연결된 하위 그래프는 실제로 원본 그래프에 연결된 전체 정보를 포함하는 무방향 그래프입니다. 그런 다음 입력 그래프를 에지 유형에 따라 여러 하위 그래프로 분할합니다. 직접 연결된 관계를 학습하는 것 외에도, 그들은 간접적으로 연결된 노드 간의 암묵적 관계를 학습하기 위해 완전히 연결된 하위 그래프를 도입한다. AMR 작업에 대한 더 나은 표현을 배우기 위해 여러 인접 행렬이 서로 다른 주의 헤드에 할당된다. [Min et al., 2022]은 유사한 관행을 채택하고 있으며, CTR 예측 작업에서 이웃 관계를 모델링하기 위해 유도 하위 그래프, 유사성 그래프, 교차 이웃 그래프 및 완전 그래프의 네 가지 유형을 신중하게 설계한다. 그리고 그들은 이웃 표현을 향상시키기 위해 마스킹 메커니즘을 사용하여 이러한 그래프를 인코딩한다.

GraphiT [Mialon et al., 2021]은 인접한 행렬을 커널 행렬로 확장하여 다양한 그래프 커널을 인코딩하는 데 더 유연하다. 또한 [Tsai et al., 2019]의 권고에 따라 키와 쿼리에 동일한 매트릭스를 사용하여 실제 성능을 해치지 않고 매개 변수를 줄이고, 고도로 연결된 그래프 구성 요소의 압도적인 영향을 줄이기 위해 degree 매트릭스를 채택한다. 업데이트 방정식은 다음과 같이 공식화될 수 있다.

4 Experimental Evaluations

우리는 다양한 방법의 효과를 연구하기 위해 광범위한 평가를 수행한다. 표준 트랜스포머를 기반으로 보조 GNN 모듈(GA), 위치 임베딩(PE), 주의력 향상(AT) 세 그룹의 방법을 비교한다. 대부분의 방법은 두 개 이상의 그래프 특정 모듈로 구성되고 다양한 트릭으로 훈련되기 때문에 각 모듈의 효과를 공정하고 독립적으로 평가하기는 어렵다. 우리의 실험에서, 우리는 기존 모델의 대표 모듈을 추출하고 개별적으로 성능을 평가한다. GA 방법의 경우 섹션 3.1에 설명된 세 가지 아키텍처를 비교합니다. 교대 및 병렬 설정 모두에서 GNN 및 Transformer 레이어는 FFN 레이어보다 먼저 결합됩니다. PE 방법에는 차수 임베딩 [Ying et al., 2021], Laplacian Igenvectors [Dwivedi and Bresson, 2020] 및 SVD 벡터 [Hussain et al., 2021]가 포함된다. AT 방법에는 공간 편향(SPB) [Ying et al., 2021], 근접 강화 다중 헤드 주의(PMA) [Zhao et al., 2021], 1홉 인접 매트릭스(Mask-1)로 마스킹된 주의[Dwivedi and Bresson, 2020]가 포함된다. 우리는 또한 (Mask-n)로 표시된 인접 행렬의 다른 홉으로 주의를 마스킹한다 [Yao et al., 2020; Min et al., 2022]의 다중 헤드 마스킹 메커니즘에서 영감을 받았다. 작은 그래프에 대한 그래프 수준 작업과 단일 큰 그래프에 대한 노드 수준 작업 모두에 대한 방법을 평가한다. 작업 및 데이터 세트에 대한 자세한 내용은 표 2에 나와 있습니다.

result

GA 및 AT 방법은 PE 방법보다 더 많은 이점을 가져옵니다.결론적으로, 체육의 약점은 두 가지입니다. 첫째, 3.2절에서 소개한 바와 같이 PE에는 온전한 그래프 정보가 포함되어 있지 않다. 둘째, PE는 네트워크의 입력 계층에만 공급되기 때문에 그래프 구조 정보는 모델 전체에서 계층별로 붕괴되어 성능이 저하될 수 있다.

다양한 종류의 그래프 작업이 다른 모델 그룹을 즐기는 것처럼 보인다. GA 방법은 노드 수준 작업의 절반 이상(9건 중 5건)에서 최고의 성능을 달성한다. 더 중요한 것은 AT 방법이 그래프 수준 작업의 거의 모든 경우(9건 중 8건)에서 최고의 성능을 달성한다는 것이다. 우리는 GA 방법이 노드 수준 작업에서 샘플링된 유도 하위 그래프의 로컬 정보를 더 잘 인코딩할 수 있는 반면 AT 방법은 그래프 수준 작업에서 단일 그래프의 전역 정보를 모델링하는 데 적합하다고 추측한다.

5 Conclusion and Future Directions

이 설문 조사에서는 그래프에 트랜스포머 모델을 적용하는 현재 진행 상황에 대한 포괄적인 검토를 제시한다.Transformer에서 그래프 데이터와 그래프 모델의 주입 부분을 기반으로 기존 그래프별 모듈을 보조 모듈로 GNN, 그래프의 개선된 위치 임베딩, 그래프의 개선된 주의 행렬의 세 가지 일반적인 그룹으로 분류한다. 공정한 설정 하에서 실제 성능 향상을 조사하기 위해, 우리는 세 그룹의 대표 모듈을 구현하고 서로 다른 작업을 가진 6개의 벤치마크에서 비교한다. 우리의 체계적인 검토와 비교가 이 분야에 대한 이해를 높이고 새로운 아이디어를 자극할 수 있기를 바랍니다.현재의 성공에도 불구하고, 우리는 그래프와 트랜스포머를 통합하는 새로운 패러다임을 포함하여 몇 가지 방향이 더 조사하고 미래에 시작할 것이라고 믿는다. 대부분의 연구에서는 Transformer 모델을 수정하기 전에 그래프를 강한 것으로 취급합니다. 그래프를 선험적으로만 받아들이는 것이 아니라 그래프의 속성을 더 잘 반영하는 새로운 패러다임을 개발하는 데 큰 관심이 있다.

• 다른 종류의 그래프로 확장한다. 기존 GraphTransformer 모델은 대부분 노드 유형과 에지 유형을 동일하게 간주하는 동종 그래프에 중점을 둔다. 이기종 그래프와 하이퍼 그래프와 같은 다른 형태의 그래프에서 잠재력을 탐구하는 것도 중요하다.
• 대규모 그래프로 확장한다. 대부분의 기존 방법은 작은 그래프에 대해 설계되었으며, 큰 그래프에서는 계산적으로 불가능할 수 있다. 실험에서 알 수 있듯이, 샘플링된 하위 그래프에 직접 적용하면 성능이 저하될 수 있다. 따라서 판매 가능한 Graph-Transformer 아키텍처를 설계하는 것은 필수적이다.