Graph Transformer Networks (2019, NIPS)

Introduction

• GNN은 homogeneous하고 fixed graph만 다룬다. 그래서 noise가 심하여 missing / spurious connection이 있는 graph에서는 좋은 성능을 안 보인다. 또한 heterogeneous graph에서는 작동을 할 수 없어서 단순하게 node / edge type들을 무시하여 homogeneous graph로 취급하는 경우도 있는데 이러면 suboptimal 한 결과만 낳는다.
• 이러한 문제를 해결하고자 주어진 heterogeneous graph에서 각각 task에 알맞는 meta-path graph들을 찾고 이에 graph convolution을 실행하여 node-representation들도 같이 학습할 수 있는 GTN을 소개하고자 한다.
• GTN은 STN(Spatial Transformer Network)의 graph version이라고 볼 수 있다고 한다.
• 그래서 meta-path를 손수 정하여 homogeneous graph로 변환 후 예측하는 게 최근 trend인데 이러면 전문가가 개입을 해야하며 meta-path를 고르는게 성능에 아주 큰 영향을 미치게 된다.

Preliminaries 

Notation들만 정리, LaTex 문법으로 최대한 나타내봄

• T^v , T^e : set of node / edge types
• V , E : set of nodes / set of observed edges
• f_v, f_e : mapping function between V → T^v, E → T^e respectively, each node and edge has only one type
• N : # of nodes (= |V|)
• K : # of edge types (= |T^e|)
• A (N x N x K) : set of adjacency matrices
• A_k (N x N): adjacency graph of k-th edge type, where A_k[i,j] is non-zero when there is a k-th type edge from j to i
• X (N x D) : D-dimensional input feature for each node.
• p: meta-path notation, v_1 -t_1→ v_2 -t_2→ … -t_l→ v_(l+1) where t_l means l-th edge type of meta-path, defines composite relation between node v_1 and v_(l+1)
• R : composite relation between nodes, e.g. R = t_1 o t_2 o … o t_l means composite relation between v_1 and v_(l+1)
• A_P : adjacency matrix of meta-path P, e.g. R = (t_1, … ,t_l) → A_P = A_(t_l)…A_(t_2)A_(t_1)

Method

• GTN은 결론적으로 새로운 graph structure를 생성하고 이에 대하여 node represenation을 동시에 학습하는 모델이다. 새로운 graph structure은 여러 후보 adjacency matrix를 활용하여 찾아 graph convolution을 더욱 효율적으로 하며 node represenation을 잘 학습할 수 있도록 한다고 한다.
• 처음으로는 1d convolution + softmax를 통하여 각 후보 adjacency matrix에 대한 convex combintion(Q)을 구한다. (일종의 후보 adjacency matrix들에 attention을 건 결과를 구한다고 생각하면 편하다.)
  • Q = sum of alpha_tl^(l) * A_tl for each tl in T^e
    • alpha_tl^(l) = weight for edge type tl at the lth GT layer
  • softmax 결과를 one-hot vector로 구성하면 그냥 candidate adjacency matrix들 중에 하나를 고르는 것과 마찬가지임.
    • 역으로 one-hot vector로 구성하지 않으면 모든 path들의 weighted sum을 구하는 것이므로 이를 통하여 임의의 l 길이의 meta-path 그래프 구조를 학습할 수 있다고 한다.
• 이후에 각 Q들을 곱하여 meta-path의 adjacency matrix를 계산한다.
  • meta-path를 계산 할 때, numerical stability를 고려해서 A^(l) = D^(-1)A^(l-1)Q(l) 이렇게 계산한다. D는 degree matrix이다.
  • 또한, l 길이의 이하의 meta-path도 동시에 고려할 수 있도록 candidate adjacency matrix들 중 I (identity matrix)도 넣는다.
• 한 번에 여러 meta-path 타입들을 고려할 수 있도록, 실제로는 1d convolution kernel의 채널 수를 C로 설정해 둔다고 한다. 이를 통해서 한 layer에서 여러 meta-path들의 집합을 고려할 수 있도록 했다.
• 이후에 맨 마지막에 나온 meta-path adjacency matrix에 GCN을 각 채널 별로 돌린 후에 여기서 나온 여러 node representation들을 concatenate하여 결과를 낸다.
  • 이러한 구조는 GT layer에서 학습된 여러 meta-path 그래프들에다가 GCN의 앙상블을 돌린 것으로 볼 수 있다고 한다.

Experiment

• 다음과 같은 세 개의 질문을 던지고 이를 실험 및 식을 통하여 증명하는 방식으로 이루어져있었음.
  
  1. GTN으로 생성된 graph 구조가 node representation을 학습하는데 효율적인가
  2. 데이터셋에 따라서 GTN이 가변적인 길이의 meta-path를 생성해낼 수 있는가?
  3. GTN이 생성한 adjacency matrix에서 각 meta-path들의 중요성을 어떻게 해석할 수 있는가?
• 이에 대한 답변들은 아래와 같다.
  1. DBLP, ACM, IMDB 데이터셋에서 GTN이 제일 좋은 성능을 보임을 통해서 알 수 있다고 함. 특히나 pre-defined meta-path를 활용하는 HAN 모델이 GAT보다도 성능에서 밀리는 것을 보아 meta-path를 미리 정의하는 게 오히려 성능에서 역효과가 날 수 있다고 함. 그에 반해서 GTN은 성능이 타 모델들 보다 GCN layer가 더 적어도 좋은 성능을 보였다고 함.
  2. 위에 method에서 언급한 것 처럼 GTN에서는 Identity matrix를 candidate adjacency matrix들 중에 넣어서 가변적인 길이의 meta-path도 생성할 수 있도록 하는데, 이를 검증하기 위해서 identity matrix를 candidate에서 제거한 GTN 모델을 ablation study로써 한 번 돌려보았다고 함. 해당 모델은 기존 GTN보다 꾸준하게 성능이 나빴는데 이러한 이유는 Identity matrix를 제거함으로써 meta-path의 길이가 고정되었기 때문이라고 함.
  3. (가정이 붙긴 했지만) 수식을 통해서 이를 해석함. 그래서 l-th layer에서 계산되는 adjacency matrix가 길이가 1부터 l 까지의 모든 meta-path들의 weighted sum으로 해석되는데 여기서 weight를 attention score로 해석되므로 task에서 각 meta-path 별로의 중요성을 알 수 있다고 한다.
• 이 외에도 각 데이터셋마다 잘 알려진 meta-path들이 있는데, 이를 GTN도 담아낼 수 있었다고 함. 거기에 추가적으로 더 많은 유용한 meta-path들도 찾았다고 함.

예전에 Transformer 논문을 읽고 재밌어서 좀 찾아보다가 읽게된 논문입니다. 리뷰를 대충 보시면 알겠지만 우리가 흔히 알던 Transformer 모델과는 상관이 없습니다. (Transform이 Heterogeneous graph를 Meta-path Graph로 변환해준다는 의미로 쓰였습니다.) 그래서 좀 당황스럽긴 했는데 내용이 꽤 흥미로워서 끝까지 읽어보았습니다. 그러면서 제가 학부연구생때 살짝 파보았던 MLC(Multi-Label Classificaiton)등에도 적용해볼 수 있을거라는 생각이 들었습니다. Graph 관련 AI를 한다면 한 번 읽어보면 좋은 논문이라 생각합니다.