소개

Graph Attention Network (GAT)는 그래프 데이터에 masked self-attention의 이점을 적용하여 기존 graph convolution의 단점을 보완할 수 있는 모델이라고 소개하고 있다. 이 논문은 transformer의 self-attention 구조에서 영감을 얻어서 다음과 같이 node-classification에 적용시키고 있다. 각 노드에 대한 hidden representation을 계산할 때, 이웃을 방문하는 개념을 self-attention을 통해서 적용하는 것이다.

Attention 구조는 다음과 같은 특징들이 있다.

1. 노드-이웃 쌍을 평행하게 계산할 수 있기 때문에, 효율적이다.
2. 서로 다른 차원의 그래프 노드에도 이웃들에 임의의 weight를 정의하여 적용할 수 있다.
3. 모델을 미확인된 그래프에 일반화시키는 등의 inductive 문제에도 바로 적용이 가능하다.

이 논문에서는 Cora, Citeseer, Pubmed citation network, inductive protein-protein interaction 데이터셋의 총 4개의 벤치마크에 대해서 측정을 하고, SOTA급의 수준을 달성했다.

• 논문 : arXiv
• 구현 코드 (pytorch)

Graph Attentional Layer

GAT 모델의 기초가 되는 단일 graph attentional layer에 대한 설명이다. 이 논문에서 사용한 어텐션은 Bahdanau 어텐션과 흡사하게 구성되어 있다. 이는 transformer 모델에서는 scaled dot product 어텐션을 사용한 것과 대비된다.

먼저, 여기서 사용되는 기호에 대해 아래와 같이 정의한다.

• 레이어의 입력은 node feature의 집합이다. 이를 $h={\vec h_1,…,\vec h_N}, \vec h_i\in \mathbb R^F$로 표기한다. $N$은 노드의 개수를, $F$는 각 노드의 feature 개수를 나타낸다.
• 레이어의 출력은 입력과 다른 새로운 node feature의 집합이다. 이를 $h'={\vec h'_1,…,\vec h'_N},\vec h'_i\in\mathbb R^{F'}$로 표기한다. $F'$는 출력 노드의 node feature 개수이다.
• 입력 feature 들을 고수준의 feature 로 변환하기 위해서는 최소한 한개의 선형 변환이 있어야 한다. 이 선형변환의 weight를 $W\in\mathbb R^{F'\times F}$로 표기한다.
• 선형변환 후에 적용하는 self-attention 변환을 $a:\mathbb R^{F'}\times\mathbb R^{F'}\rarr\mathbb R$로 정의한다.

각 어텐션 값 구하기

먼저, 각 노드쌍의 어텐션 값을 구해야 한다. 이는 다음과 같은 방법으로 진행된다.

Attention Coefficients

먼저 각 노드쌍의 attention coefficients을 다음과 같은 식으로 정의한다.

\[e_{ij}=a(W\vec h_i,W\vec h_j)\]

이 식을 살펴보면, 먼저 $W$를 통해서 기존에 $F$개의 feature들을 가지고 있던 $\vec h_i,\vec h_j$벡터들이 $F'$개의 feature 를 가진 벡터들 $W\vec h_i,W\vec h_j$로 선형변환된다. 이렇게 얻어진 벡터들의 정보를 self-attention $a$를 통해 하나의 값으로 통합한 것이 바로 attention coefficient 가 되는 것이다.

여기서 이 attention coefficient $e_{ij}$의 의미는 결국 노드 $j$의 feature들($\vec h_j$)이 노드 $i$에 얼마나 중요한지에 대한 정도가 되는 것이다.

Masked Attention

Masked attention이란, $e_{ij}$를 계산할 때, $j$가 $i$의 이웃 노드일 경우($j\in \mathcal N_i$)에 대해서만 계산을 수행하는 작업을 말한다.

위 식은 그래프의 구조에 대한 정보가 없기 때문에 모든 노드사이의 값이 계산되어버리게 된다. 그래서 여기서 그래프의 구조 정보를 주입하기 위해 masked attention을 수행한다. 이 논문에서 $\mathcal N_i$는 정확히 $i$의 1차 이웃(자기자신 포함), 즉 $i$와 직접 연결된 모든 이웃을 의미한다.

Normalized Attention Coefficients

이제 서로다른 노드들의 attention coefficient 값들을 쉽게 비교하기 위해 다음과 같이 softmax를 통해서 normalize시키면 다음과 같은 식이 된다.

\[\alpha_{ij}=softmax_j(e_{ij})=exp(e_{ij})/\sum_{k\in\mathcal N_i}exp(e_{ik})\]

여기서 normalized attention coefficient $\alpha_{ij}$가 바로 최종적으로 $j$의 각 feature가 $i$에게 영향을 주는 정도를 나타내는 값이 되는 것이다.

마지막으로, 이 논문에서 사용한 self-attention 매커니즘 $a$는 가중치를 벡터 $\vec a\in \mathbb R^{2F'}$로 하고, activation function으로 $LeakyReLU$를 적용시킨 단일 feed-forward 뉴럴네트워크 레이어다. 위에서 언급했던 Bahdanau 어텐션과 흡사하게 concat을 사용해서 weight를 계산하였다.

이를 적용하면 최종적으로 다음 식이 된다.

\[\alpha_{ij}=\frac{LeakyReLU(\vec a^T[W\vec h_i\Vert W\vec h_j])}{\sum_{k\in\mathcal N_i}exp(LeakyReLU(\vec a^T[W\vec h_i\Vert W\vec h_k]))}\]

여기서 $\Vert$는 concat을 나타내는데, 즉 두 $W\vec h_i,W\vec h_j$벡터들을 $\vec a^T$로 한번에 선형변환시키고, $LeakyReLU$를 적용하여 $e_{ij}$로 만들었다는 뜻이 된다.

최종 레이어 출력

이렇게 계산된 각 노드들의 normalized attention coefficients 값을 이전레이어에서의 각 이웃들의 feature $\vec h_j$를 선형변환시킨 값에 적용하여 모든 노드들의 최종 출력 feature $\vec h'_i$를 구하게 된다. 노드 $i$에 대한 각 레이어 출력 식은 다음과 같다.

\[\vec h'_i=\sigma(\sum_{j\in\mathcal N_i}\alpha_{ij}W\vec h_j)\]

여기서 self-attention 과정의 안정성을 위해서 transformer논문에서와 마찬가지로 multi-head attention을 적용한다. 결국 $K$개의 각 헤드마다 위 식을 계산해서 따로 activation function을 적용시키고, 이를 모두 합치는 것이다. 이를 식으로 표현하면 다음과 같다.

\[\vec h'_i=\underset {k=1}{\overset K\Vert}\sigma(\sum_{j\in\mathcal N_i}\alpha_{ij}^kW^k\vec h_j)\]

마지막 multi-head attention 레이어는 concat이 필요없으므로, 다음과 같이 전체 head들의 attention에 대한 평균을 구하는 식으로 대체하고, 마무리 activation(classification의 경우에는 softmax 등)을 적용한다.

\[\vec h'_i=\sigma(\frac 1K\sum_{k=1}^K\sum_{j\in\mathcal N_i}\alpha_{ij}^kW^k\vec h_j)\]

이런식으로 각 노드에 대한 모든 attention 레이어를 구성하고, 최종 출력 레이어까지 구하면 모델이 전부 완성된다.

이 논문에서는 각 head의 activation function으로 $ELU$를 사용했다.

결론

논문에는 GAT 성능에 대한 다양한 비교와 실험 결과가 있는데, 이 부분은 생략하도록 한다.

GAT의 가장 큰 장점중 하나는 바로 전체 그래프구조가 필요하지 않다는 것이다. 기존의 GCN만 보더라도, 전체 그래프의 인접행렬 $A$를 통해서 normalized laplacian matrix를 구해야 했고, 계산비용뿐만 아니라 그래프의 변화에도 취약했다.

하지만 GAT는 해당 노드의 인접노드 정보만으로도 feature 를 구할 수 있으며, 그 성능이 좋기 때문에 transductive뿐만 아니라 inductive 문제(특히, 예를 들면 완전히 미확인된 그래프를 테스트셋으로 활용하는 등)까지 가능하게 되었다.