Graph attention network (GATs)

우리가 머신러닝 분야에서 주로 사용하는 Convolutional Neural Network (CNNs)는 data representation이 그리드 형 구조를 지닌다는 전제를 갖고 있다. 이러한 네트워크는 모든 input position 별로 같은 로컬 필터를 재사용하여 학습을 시켜준다. (Convolution이 각 stage 별로 input feature들에 대해 어떻게 일어나는지를 상상하면 된다.)

하지만 모든 데이터들이 이러한 grid-like structure을 가지는 것은 아니다. 상당수의 데이터는 불규칙적인 domain에 존재하며 3D meshes, social networks, brain connectomes 등이 바로 그러하다. 이러한 데이터는 주로 graph의 형태로 표현가능하다.

 

여기서, Graph란 무엇을 의미하는 것일까? 물론 node와 edge로 이루어진 것이 graph라는 사실은 거의 대다수가 알 것이다. 그렇다면 인공지능 측면에서, graph data는 무엇일까?

 

다음은 Graph Convolutional Networks(GCN)에서의 Input graph에 대한 그림이다. 그림과 같이 A,B,C,D와 같은 Node를 지닌 undirected graph가 있다고 하자. GCN에서의 Input은 크게 feature matrix와 adjacency matrix로 구분할 수 있는데, 우선 전자는 각 노드별로의 feature 정보를 담고 있다. 그림에서와 같이 각 노드는 1x3 사이즈의 피쳐 값을 갖고 있으므로 feature matrix의 크기는 4x3이 될 것이다. 이처럼 Feature Matrix가 노드 고유 정보를 갖고 있는 반면, Adjacency Matrix는 엣지 정보를 담고 있다. Adjacency matrix는 항상 node 수가 n개일 때 nxn 크기를 지니고 있는데, 따라서 위 예시의 경우 4x4 matrix가 된다. Matrix 내 요소들은 각각의 노드들이 서로 연결되어있으면 1, 연결되어있지 않으면 0을 지니며, 자기 자신의 정보 또한 참고하자라는 GCN의 특징 때문에 대각행렬 값 역시 1이다.

 

irregular domain에서의 데이터를 겨냥한 머신러닝 모델들에 대한 연구가 꾸준히 진행되었으며 2017에는 다방면에서 적용되고 있는 Attention 개념을 Graph에도 적용하는 논문이 나오게 되었다.

 

따라서 오늘은 간략하게 Graph attention이 어떻게 작용하는지에 관해 짧게 다루도록 하겠다.

 

Graph attention의 핵심적인 개념은 다음 그림과 같다. 특정 노드 h1은 주위 다른 노드들과 자신에게 영향을 받아 h'으로 업데이트된다. 그림에서는 Multi-head attention을 사용했기 때문에 (heads=3) 보라,파랑,초록으로 표현된 선들이 세개씩 존재하는 것을 볼 수 있다.

 

결국 GAT의 구현은 다음 두 식으로 표현 가능하다. single graph attentional layer의 input은 node feature들의 집합인 h로 표현하였으며 이 h는 n(#of nodes)개의 feature vector들로 이루어져 있다. 마찬가지로 output h'역시 n개의 updated된 feature vector들로 구성되어 있다.

 

먼저 수식1부터 살펴보면, input feature들을 고차원으로 표현하기 위해 learnable parameter인 W( W ∈ R^(F ′ ×F))를 곱해주게 된다. 이후 F'길이를 갖는 두 임베딩 벡터 Wh를 Concat해주어 single-layer feedforward NN에 집어넣어준다. 이때 다시 한번 learnable parameter인 weight vector  ⃗a ∈ R^(2F ′)가 등장하며, 논문에서 쓰이는 LeakyReLU는 negative input slope α = 0.2을 사용하였다.

 

수식1로부터 αij (attention coefficient)를 얻게 되면 수식 2에서는 이 αij를 가지고 Feature들에 대한 linear combination을 계산해줌으로써 각 노드마다의 final output feature를 뱉어내준다. 이때 nonlinear activation function이 사용된다.

 

Multihead attention의 경우, 다음과 같은 작업을 head의 개수만큼 반복하면 된다.

 

 

Results

다음은 GAT의 성능을 실험한 결과이다. 그림을 보면 Transductive, Inductive의 경우 모두 GAT가 더 우수한 정확도를 지니는 것을 볼 수 있다.