Graph Transformer Networks

NeurlPS2019

---

Graph Transformer Networks

---

Seongjun Yun, Minbyul Jeong, Raehyun Kim, Jaewoo Kang, Hyunwoo J. Kim

Koera University

---

본 논문은 GNN(Graph Neural Netowrk)에 관한 기술로 기존의 homogeneous graph를 처리하는 것에 초점이 맞추어져 있던 GNN을 heterogeneous graph에서 적절하게 사용하기 위한 방법을 제시한 논문이다.

Transformer에서 사용되던 self-attention과 비슷한 구조를 사용하여 문제를 해결하기 위한 방법을 제시하였다.

다양한 분야에서 graph structure를 접목해서 사용하기에 좋은 방법이라 생각한다.

DoI : https://doi.org/10.48550/arXiv.1911.06455

Graph Transformer Networks

---

1. Introduction

최근 Graph Neural Networks (GNNs)는 넓은 분야에서 다양한 task에 맞춰 사용되고 있다.

대표적인 GNN task로는 graph classification, link prediction, node classification 등이 있다.

GNN은 social networks, citation networks, functional structure of brains, recommender systems 등 graph data를 활용하여는 분야에서 최적의 성능을 얻음을 확인할 수 있다.

 

기본 graph 구조는 node feature를 이웃에 전달하여 그래프에서 직접 convolution 연산을 수행하거나 주어진 graph의 Fourier 기반 즉, Laplacian 연산자의 고유함수를 이용하여 spectral domain에서 convolution을 수행하기 위해 GNN을 사용한다.

 

그러나 대부분의 GNNs는 graph의 구조가 fixed되고 homogeneous하다고 가정을 하고 작동 된다는 한계를 가지고 있다. graph convolution은 fixed graph 구조에 의해 결정되므로 missin/spurious connection이 있는 noisly graph는 잘못된 이웃과 비효율적인 convolution을 초래할 수도 있다. 또한 몇몇 heterogeneous graph는 GNN을 수행하기 위한 graph를 구성하는 것이 매우 어려워 기존의 GNN은 그다지 효욜적이다고 볼 수 없다.

 

Heterogeneous graph (이기종 그래프)?

Heterogeneous graph를 알아보기전 homogeneous graph에 대해서 알아야할 필요가 있다.

우선 homogenous graph은 graph의 모든 node가 같은 성질을 가지고 있는 graph이다.

예를 들어 가계도를 생각해보자. 가계도의 노드는 전부 사람을 의미하므로 homogeneous graph라고 할 수 있다.

 

Heterogeneous graph란 homogenous graph와 반대로 node가 여러 종류의 성질을 가지고 있는 그래프를 뜻한다.

예를 들어, citation graph에서 여러 종류의 nodes(author, papers, conferences)와 이들의 관계에 의해 정의된 edge(author -paper, paper-conference)가 있으면 이를 Heterogeneous graph(이기종 그래프) 라고 부른다.

 

Heterogeneous graph 처리 방법

Heterogeneous graph를 처리하는 방법으로는 크게 두 가지가 있다고 한다.

1. node/edge type을 무시하고 homogeneous graph를 처리하는 방식을 사용하는 것
2. 최근 heterogeneous edges와 연결 경로인 meta-path를 수동으로 설계하고 변경하는 방식을 사용

이때 두 번째 방식에서 meta-path를 사용하는 이유는 heterogeneous graph는 meta-path를 통해 homogeneous graph로 transform되기 때문이다. 이렇게 변경을 하고 나면 GNN 연산을 수행할 수 있는 형태가 되게 된다.

이러한 tow-stage 접근 방식은 각 문제에 대한 hand-crafted meta-path를 필요로 한다. 또한 downstream의 성능은 선택된 meta-path의 영향을 받는다. 즉, 좋은 성능을 내기 위해서는 적절한 meta-path의 선정을 필요로하며 각 문제마다 새로운 meta-path를 필요로 한다는 것이다.

 

Contributions

위와 같은 문제를 개선하고 최적의 meta-path를 제안하기 위해 이들은 Graph Transformer Network (GTN)을 제안한다.

GTN은 heterogeneous input graph를 각 task에 유용한 meta-path로 transform하는 방법을 학습하며 end-to-end 방식으로 graph의 node represenation을 학습할 수 있다고 한다.

이는 Input image or features의 spatial transformations를 명시적으로 학습하는 spatial transformer network의 graph analogue 표현으로 볼 수 있다.

 

Heterogeneous graph를 meta-path에 의해 새로운 graph 구조로 변환하는데 있어서 주요 과제는 meta-path 가 임의의 길이와 edge type을 가질 수 있다는 문제이다.

예를 들어 author classification in citation networks는 Author-Paper-Author (APA) 또는 Author-Paper-Conference-Paper-Author (APCPA)인 meta-path의 이점을 누릴 수 있다. 또한 citation networks는 비교적 적인 graph neural network가 작동할 수 있는 방향성 graph이다.

 

이러한 문제를 해결하기 위해서 heterogeneous graph에서 soft chosen edge와 연결된 복합 관계를 기반으로 새로운 graph structure를 생성하고 주어진 문제에 대해 학습된 graph structure에서 convolution을 통해 node feature 학습하는 모델을 필요로 한다고 설명하고 있다.

 

이를 정리해보자면 이들의 contributions는 아래와 같다.

1. Graph에서 효과적인 node representation을 학습하기 위해 유용한 meta-path와 multi-hop connections를 식별하는 것과 관련된 새로운 graph 구조를 학습하기 위해 새로운 Framework인 Graph Transformer Networks를 제안
2. Graph generting은 해석가능하며 model은 예측을 위한 효과적인 meta-path에 대해 insight를 제공할 수 있다.
3. Heterogeneous graph의 세 가지 benchmark에서 domainknowledge를 추가로 사용하는 sate-of-the-art method에 대한 최고 성능을 제공한다.

 

---

2. Method

Graph Transformer Networks는 새로운 graph structures를 생성하고 동시에 학습된 graph에서 node representation을 학습한다.

기존의 graph가 주어진다고 가정하는 기존의 CNN과 달리 효과적인 graph convolution 수행과 강력한 node representation까지 학습을 하기 위해 여러 후보 인접 행렬을 사용한다.

 

새로운 graph structures를 학습하기 위해서는 heterogeneous edges와 multi-hop connection으로 연결된 meta-path를 식별해야한다고 한다.

 

우선 meta-path와 GCN의 기본개념을 확인해 보자.

 

2.1 Preliminaries

우선 이들이 제안하는 framework의 input은 하나의 서로다른 node와 deges 유형을 가지는 multiple graph structures이다.

 

< Meta-Path >

meta-path는 mutli-hop관계를 새로운 path로 보고 새로운 network를 구성할 수 있게 해준다.

https://younghk.github.io/machine-learning/2019-12-14---graph-neural-networks-2/

multi-hop connections를 가정하고 Framework의 새로운  graph structures는 인접행렬로 표현된다.

복합관계 R 또는 edge 유형의 sequence가 주어졌을때 meta-path p의 인접행렬 A_p는 같은 인접행렬의 곱에 의해 구해진다.

예를 들어 Author - Paper - Conference (APC)의 meta-path가 있다고 가정하자.

이때 A -> P -> C로 표현이 가능하고 이를 통해 인접행렬 A_APC가 생성가능하다.

인접 행렬 A_APC는 A_AP와 A_PC를 행렬곱하여 구할 수 있다.

 

< Graph Convolutional network (GCN) >

본 논문에서, graph convolutional network(GCN)를 사용하여 end-to-end 방식으로 유용한 node classification의 representation을 학습한다.

H^(l)이 l-th layer의 feature representation이라고 하면 아래와 같이 forward propagation이 진행된다.

graph 전체에 convolution 연산은 주어진 graph 구조에 의해 결정되면 node-wise linear transform말고는 학습할 수가 없다고 한다.

GTN은 graph의 구조를 학습하는데 이는 다른 기존과 convolution을 사용하여 얻은 이점이라고 한다.

 

2.2 Meta-Path Generation

이전에 연구에서는 수동으로 정의된 meta-path를 필요로하며 meta-path graphs에서 GNN을 수행하였다.

그러나 이들이 제안하는 GTNs는 주어진 data를 통해 meta-path를 학습하고 학습된 meta-path에서 graph convolution을 수행하는 방식을 사용하였다.

이러한 방식은 더 유용한 meta-path를 찾을 수 있는 기회를 제공하고 여러 meta-path를 사용하여 다양한 graph convolution으로 이어지게 된다는 이점을 가진다.

Graph Transformer(GT) Layer를 사용한 새로운 meta-path generation은 위 Fig1과 같이 진행된다.

1. GT Layer는 후보 인접 행렬 A에서 2개의 graph structures Q1과 Q2를 sofly select 한다.
2. 두 관계의 구성으로 새로운 graph structures를 학습한다. (두 인접행렬의 행렬곱 Q1, Q2)

Softmax function의 weights를 Fig.1과 같이 식(4)에서의

로 1x1 convolution의 인접 행렬의 convex combination을 계산한다. 이를 식으로 표현하면 아래와 같다.

이는 channel attention pooling과 유사한 구조라고 본 저자들은 설명하고 있다.

이때 numerical stability를 위해 matrix는 degree matrix에 의해 normalized 된다.

 

이제, 이들은 GTN이 임의의 meta-path를 edge types와 path length에 관련하여 학습할 수 있는지 확인해야 한다.

임의의 length l meta-path의 인접행렬은 아래와 같이 계산될 수 있다.

l 개의 GT layers stack은 임의의 길이 l개의 meta-path graphs 구조를 학습할 수 있다.

 

이렇게 학습을 진행하게 되면 GT layer를 추가할때 항상 meta-path의 length가 증가하게 되며 원래 edge를 허용하지 않는다는 문제가 발생하게 된다.

이들은 이러한 문제점을 개선하여 원래 edge를 포함하고 짧고 긴 meta-path를 학습하기 위해서 인접행렬 A에 identity matrix I를 포함하게 된다. (A0 = I)

이 trick을 통해서 GTNs는 I GT Layers가 쌓였을 때 I+1까지의 meta-path를 학습할 수 있게 된다.

 

3.3 Graph Transformer Networks

위 Fig.2 는 Graph TransformerNetworks이다.

우선 여러 유형의 meta-path를 고려하기 위해 1x1 convolution의 output channel을 C로 설정해준다.

GT layer는 meta-path의 set을 산출하고 intermediate 인접행렬 Q1과 Q2는 인접 tensors Q1 and Q2 ∈ R^(N×N×C) 가 된다. 이는 여러 개의 서로 다른 graph structures를 통해 서로 다른 node의 표현을 학습하는데 유용하다.

그 후, l GT layers는 각 channel의 meta-path tensor A(l) ∈ R^(N×N×C)은 GCN에 적용된다. 그리고 multiple node representation은 concatenated 된다.

이를 식으로 표현하면 아래와 같이 표현할 수 있다.

---

3. Experiments

위 tabel은 DBLP, ACM and IMDB 데이터를 기존의 sota model들과 비교 실험한 결과이다.

이를 통해 이들이 제안하는 방법의 성능이 더 높음을 확인할 수 있다.

Identity matrix를 제외하였을때는 성능이 저조한 경우도 있지만 identity matrix를 추가하였을 때 눈에 띄게 성능이 오름을 확인할 수 있다.

---

본 논문은 최종적으로 self-attention과 비슷한 구조를 가지게 된다. 이를 통해 meta-path를 찾음으로써 관계의 중요도를 확인할 수 있음이라 생각된다. 이는 수동적으로 meta-path를 찾는 것이 아닌 data의 node간의 관계를 통해 meta-path를 찾으므로 더 의미있는 학습이 가능해질 수 있는 계기가 되었다고 생각한다.

이러한 구조는 다양한 graph convoltuional network에 응용이 가능하여 중요한 부분이라 생각하며 중요한 논문이라고 생각한다.

---

Reference

https://velog.io/@thecho7/Graph-Neural-Network-3

Graph Neural Network - (3)

https://younghk.github.io/machine-learning/2019-12-14---graph-neural-networks-2/

Graph Neural Networks 2

https://greeksharifa.github.io/machine_learning/2021/09/08/GTN/

Python, Machine & Deep Learning