[그래프 AI]Graph Attention Network(GAT)

Graph Attention Network(GAT)

1. GAT의 배경

Graph Attention Network(GAT)는 Spatial한 방법론을 채택하여 인접 행렬를 이용하지 않는다. GAT의 핵심 아이디어는 노드들이 이웃 노드들의 중요도를 학습하여 각 이웃 노드로부터의 메시지(특징)를 다른 가중치로 받아들일 수 있게 하는 것이다. 이를 통해 각 노드에는 가중치(Weight)가 부여되며, 이 가중치들이 적용된 가중합(Weighted Sum) 연산을 수행한다. 즉, GAT는 단순히 이웃 노드들의 특징을 합치는 것이 아니라, ‘나’한테 영향을 주는 ‘정도’까지 학습하여 각 이웃 노드로부터의 영향을 동적으로 반영하는 것이다.

GCN의 경우 이웃 정보를 집계(aggregation)시 메세지를 모두 더해주는 Sum을 함수로 사용한다. Sum 방식의 기저에는 타겟 노드에 기여하는 이웃들의 영향력이 동일하다는 가정이 있다. GAT는 “GCN에 타겟 노드와 이웃 노드의 중요도를 차수(degree)만 고려했는데, 과연 이것을 충분할까?”라는 질문에서 시작한다.

위의 그림에서 메세지를 취합하는 부분(Aggregate)를 보면, 이웃에서 타겟 노드로 전달되는 정보의 방향성을 화살표로 나타내고 있다. GCN의 경우 화살표의 굵기가 동일하다. 왜냐하면 타겟 노드 \(u\)를 기준으로 이웃 노드 \(v\)의 차수를 반영하여 정규화를 \(\frac{1}{\vert N(v) \vert}\)로 하였을 때, 타겟 노드의 이웃들은 모두 차수가 동일하기 때문에 그 영향력 또한 동일하다는 것이다. 하지만, GAT의 경우 각 이웃들과 타겟과의 연결 유무가 아닌 연결 강도가 다르다고 가정하는 것이다. 따라서 그림에서와 같이 화살표의 굵기에 따라 각 이웃들이 주는 메세지의 영향력도 다르다.

2. “Attention” 이란?

어텐션(Attention)은 2017년 구글에서 발표한 트랜스포머(Transformer) 이후로 여러 AI 분야에서 보편적으로 사용되고 있는 테크닉이다. 어텐션은 입력으로 들어온 여러 데이터들에 대해 서로 간의 “중요도”를 계산하는 것이다. 이는 정보의 과잉 상태에서 무엇에 ‘집중’할 지 결정하기 위한 작업이다. GAT는 이 어텐션의 아이디어를 차용해 이웃들의 메세지에 ‘중요도’를 계산해서 전달받는 것이 핵심이다.

3. GAT에서의 Attention

3-1. Hidden Representation

위의 그림을 통해 GAT의 메커니즘을 잘 설명할 수 있다. GCN과 GAT의 가장 큰 차이점은 이웃으로부터 타겟에 메세지 전달(Message Passing)을 수행할 때 각 메세지별 가중치의 유무이다. 위의 그림에서 타겟 노드를 \(A\)라고 가정할 때 GCN은 \(l\)번째 layer의 히든 임베딩(hidden representation)은 다음과 같이 정의된다.

$$h_A^{(l)} = \sigma \left( W^{(l)}h_B^{(l-1)} + W^{(l)}h_C^{(l-1)} + W^{(l)}h_D^{(l-1)} \right)$$

하지만, GAT에서는 각 노드(=이웃)이 타겟에 주는 영향력이 다르다. 각 노드 사이의 연결에는 가중치가 부여되어 있기 때문에 위의 식은 가중합(Weighted Sum)으로 바뀌게 된다.

$$h_A^{(l)} = \sigma \left( \textcolor{red}{\alpha_{AB}}W^{(l)}h_B^{(l-1)} + \textcolor{red}{\alpha_{AC}}W^{(l)}h_C^{(l-1)} + \textcolor{red}{\alpha_{AD}}W^{(l)}h_D^{(l-1)} \right)$$

즉 GAT의 layer는 타겟 노드 \(v\)에 대해 \(h_v^{(l)} =\sigma \left(\textcolor{red}{\alpha_{vu}}W^{(l)h_u^{(l-1)}} \right)\)와 같은 방식으로 작동한다. GAT는 어텐션 가중치(Attention Weight)를 학습해야 하기 때문에 학습해야 할 파라미터 수가 늘어난다. 노드마다 \(\alpha\)와 \(W\)가 모두 다르기 때문이다.

3-2. Attention Coefficient

학습을 위해서는 타겟 노드 \(v\)와 이웃 노드 \(u\) 사이의 가중치 \(\alpha_{vu}\)를 정의해야한다. GAT에서 Attention Coefficient를 구하는 과정은 다음과 같다.

1) 특징 변환
각 노드 \(i\)와 이웃 노드 \(j\)의 은닉 표현(hidden representation)은 각각 \(h_i\)와 \(h_j\)이다. 이 두 벡터를 가중치 행렬 \(W\)를 통해 각각 \(Wh_i\)와 \(Wh_j\)로 변환한다.

2) 어텐션 스코어 계산
변환된 특징 벡터 \(\mathbf{Wh}_i\)와 \(\mathbf{Wh}_j\)를 이용하여 두 노드 간의 유사성을 계산한다. 이는 주로 내적이나 결합(Concatenation) 후 소프트맥스 함수를 통해 이루어진다. 이 과정에서 비정규화된 어텐션 스코어는 다음과 같이 만들어진다. \(a\)는 어텐션 메커니즘을 의미한다.

$$e_{ij} = a(\mathbf{Wh}_i, \mathbf{Wh}_j)$$

일반적으로 어텐션 메커니즘은 두 벡터를 결합한 후, 신경망(Neural Network)을 통과시켜 나온 결과값을 사용한다. 논문에서는 구체적으로 LeakyReLU 함수를 활성 함수(Activation function)로 사용하는 신경망을 사용하였다. \(\mathbf{a}\)는 학습 가능한 벡터이며 \(\vert \vert\)는 결합(Concatenation)을 의미한다.

$$e_{ij} = \text{LeakyReLU}(\mathbf{a}^T [Wh_i \mid \mid Wh_j])$$

3) 어텐션 가중치 정규
계산된 어텐션 스코어 \(e_{ij}\)를 정규화하면 최종적으로 어텐션 가중치(Attention Weight) \(\alpha_{ij}\)가 된다. 논문에서는 소프트맥스 함수를 사용하여 정규화한다.

$$\alpha_{ij} = \text{softmax}_j \frac{\text{exp}(e_{ij})}{\sum_{k \in \mathcal{N}(i)} \text{exp}(e_{ik})}$$

4) 특징 결합
각 노드는 이웃 노드들로부터 수신한 메시지(특징)를 어텐션 가중치를 사용하여 가중합을 구하고, 이를 통해 새로운 특징 벡터를 계산한다. GAT의 \(l\)-th 레이어에서의 타겟 노드 \(v\)의 최종 특징 벡터(hidden representation) \(\mathbf{h}_v^{(l)}\)는 다음과 같다. \(\sigma\)는 활성화 함수이다.

$$\mathbf{h}_v^{(l)} = \sigma \left( \displaystyle\sum_{u \in \mathcal{N}(v)} \alpha_{vu} Wh_u^{l-1} \right)$$

이 과정을 통해 각 노드는 이웃 노드로부터의 영향을 동적으로 학습하며, 어텐션 메커니즘을 통해 각 이웃 노드의 중요도를 반영한다.

4. GAT with Multi-head Attention

4-1. 예시로 보는 Multi-head Attention

학습 단계에서 안정성을 높이기 위해서 멀티 헤드 어텐션(Multi-head attention)을 사용하곤 한다. 멀티 헤드 어텐션은 서로 다른 파라미터를 가지는 헤드(head)를 여러 개 두고, 독립적으로 어텐션을 수행하는 방법이다. 일반적으로 싱글 헤드 어텐션보다 성능이 더 좋다는 연구 결과가 많다. 멀테 헤드 어텐션에서는 입출력 차원의 크기를 맞춰주는 것이 핵심이다.

싱글 헤드 어텐션일때와 임베딩의 전체 차원 수가 같아지려면, 각 헤드로 입력되는 임베딩을 전체에서 헤드 개수인 \(k\)로 나눠주면 된다. 즉, 원래 임베딩 차원이 \(100\)차원이고 헤드의 수가 \(5\)라면, 각 헤드의 입력 임베딩은 \(100/5 = 20\)차원이 된다.

$$\mathbf{h}_i = \vert \vert^{K}_{K=1} \sigma \left( \sum_{u_j \in N (u_j)} \textcolor{red}{\alpha_{ij}^k} W^k h_j \right)$$

멀티 헤드를 사용할 경우 어텐션의 결과는 위의 식과 같이 변한다. \(\alpha_{ij}^k\)는 각 헤드가 독립적으로 어텐션 연산을 수행할 때, \(k\)번째 헤드에 의해 계산된 어텐션 계수(attention coefficient)를 의미한다. 다시 말해, 멀티 헤드 어텐션은 여러 개의 어텐션 메커니즘(헤드, head)을 병렬로 사용하여 서로 다른 부분의 정보를 동시에 캡처할 수 있게 한다. 각 헤드는 독립적으로 어텐션 계산을 수행하며, 최종적으로 이들의 출력을 결합한다.

이 그림은 멀티 헤드 어텐션을 사용하는 GAT를 시각적으로 잘 표현해준다. 그림의 예시에서는 타겟 노드가 \(\mathbf{h_1}\)이다. 이 노드의 이웃으로는 \(\mathbf{h_2}, \mathbf{h_3}, \mathbf{h_4}, \mathbf{h_5}, \mathbf{h_6}\)이 있다. 각 헤드는 독립적으로 어텐션 가중치를 계산한다. 예를 들어, 그림에서 보라색, 녹색, 파란색 선은 각각 다른 헤드를 나타내며, 각 헤드는 다른 파라미터를 사용하여 어텐션 가중치를 계산한다. \(\alpha_{12}^k, \alpha_{13}^k, \alpha_{14}^k, \alpha_{15}^k, \alpha_{16}^k\)는 \(k\)번째 헤드가 계산한 노드 \(\mathbf{h_1}\)과 각 이웃 노드 사이의 어텐션 가중치(Attention Weight)이다. 이 가중치들은 해당 이웃 노드의 중요도를 나타낸다.

각 헤드는 이웃 노드들로부터 수신한 메시지(특징 벡터)를 어텐션 가중치를 사용하여 가중합을 구한다. 예를 들어, 보라색 헤드는 \(\mathbf{h_1}\)과 이웃 노드의 특징 벡터 \(\mathbf{h_2}, \mathbf{h_3}, \mathbf{h_4}, \mathbf{h_5}, \mathbf{h_6}\)를 보라색 어텐션 가중치 \(\alpha_{12}, \alpha_{13}, \alpha_{14}, \alpha_{15}, \alpha_{16}\)를 사용하여 가중합을 구한다.

각 헤드의 출력을 결합(concatenate)하거나 평균(average)하여 최종 출력 벡터 \(\mathbf{h_1}^{'}\) 을 만든다. 그림에서 “concat/avg“는 이 과정을 나타낸다. 최종적으로 \(\mathbf{h_1}^{'}\)가 \(v_1\)의 새로운 특징 벡터가 된다.

4-2. GAT with Multi-head Attention 수식 정리

최종적으로 이 과정을 일반화하면 다음과 같다.

[각 노드의 특징 벡터]

$$\text{Input features: } \mathbf{h} = \{\vec{h_1}, \vec{h_2}, \cdots, \vec{h_N} \}, \vec{h_i} \in \mathbb{R}^F $$

[두 노드 사이의 중요도]

$$\text{Importance of } v_j \text{ to } v_i: e_{ij} = a(W\vec{h_i}, W\vec{h_j})$$

[어텐션 계수(Attention Coefficient)]

$$\alpha_{ij} = \text{softmax}_j(e_{ij})$$

$$\alpha_{ij} = \frac{\exp \left( \text{LeakyReLU} \left( \vec{a}^T [\mathbf{W} \vec{h}_i \| \mathbf{W} \vec{h}_j] \right) \right)}{\sum_{k \in \mathcal{N}_i} \exp \left( \text{LeakyReLU} \left( \vec{a}^T [\mathbf{W} \vec{h}_i \| \mathbf{W} \vec{h}_k] \right) \right)} $$

[GAT 업데이트]

$$\text{GAT Update: } \mathbf{h}'_i = \bigg\Vert_{k=1}^{K} \sigma \left( \sum_{j \in \mathcal{N}_i} \alpha_{ij}^k \mathbf{W}^k \mathbf{h}_j \right) $$

[최종 출력 특징 벡터]

$$\text{Final Layer: } \mathbf{h}'_i = \sigma \left( \frac{1}{K} \sum_{k=1}^{K} \sum_{j \in \mathcal{N}_i} \alpha_{ij}^k \mathbf{W}^k \mathbf{h}_j \right) $$

Reference

논문: Graph Attention Network

Graph 카테고리 내 다른 글 보러가기