Untitled

[머신 러닝/딥 러닝] 그래프 어텐션 네트워크 (Graph Attention Network) 구조 및 설명 본문

지능형시스템/머신 러닝

[머신 러닝/딥 러닝] 그래프 어텐션 네트워크 (Graph Attention Network) 구조 및 설명

CHML 2021. 8. 1. 15:02
1. Self-Attention Mechanism

Graph attention network (GAT) [1]를 이해하기 위해서는 먼저 self-attention mechanism에 대한 이해가 필요하다. 아래의 그림 1은 구글 AI 블로그의 예제를 이용하여 자연어 처리에서 self-attention이 어떻게 정의되고 이용되는지를 보여준다.

 

그림 1. 자연어 처리에서 self-attention의 정의와 동작.

 

자연어 처리에서는 'it', 'them', '그것'과 같이 문맥을 고려해야 단어가 무엇을 의미하는지 알 수 있는 경우가 많다. 그림 1의 예제에서도 'it'이라는 단어가 'animal'을 의미하는지 'street'을 의미하는지 알기 위해서는 같이 입력된 문장 전체를 고려해야 한다. Self-attention은 어떠한 입력을 이해하기 위해 같이 입력된 요소들 중에서 무엇을 중요하게 고려해야 하는지를 수치적으로 나타내는 기법이다. GAT은 이러한 self-attention mechanism을 노드 embedding 과정에 적용한 인공신경망이다.

 

2. GAT의 구조와 Graph Self-Attention의 개념

GAT은 기존의 graph neural network (GNN)과 유사하게 그림 2처럼 노드 embedding layer와 dense layer로 구성된다. 입력 그래프에 대해 노드 embedding layer에서는 각 노드에 대한 embedding을 생성한다. Readout은 그래프 단위의 출력을 만드는 경우에만 존재하는 계층으로써 전체 노드에 대한 노드 embedding을 모두 더하거나 평균을 내는 방식으로 그래프 전체의 embedding을 생성한다. 마지막으로, dense layer에서는 주어진 노드 또는 그래프 embedding에 대해 출력이 계산된다. Dense layer의 출력으로는 노드 또는 그래프의 embedding뿐만 아니라, 노드 또는 그래프에 대한 class label 및 target property 등이 될 수도 있다.

 

그림 2. 일반적인 GNN의 구조.

 

가장 대표적인 GNN인 graph convolutional network (GCN)에서는 노드 embedding layer가 graph convolution이라는 연산으로 정의되었지만, GAT에서는 self-attention으로 노드 embedding layer가 정의된다. 즉 GAT은 어떠한 노드의 embedding을 생성할 때 인접한 노드들에 대한 중요도를 계산하여 이를 기반으로 새로운 embedding 만든다. 이는 그림 1에서 'it'이라는 단어의 의미를 파악할 때 같이 입력된 단어들의 중요도를 보는 것과 비슷한 개념이다.

 

그림 3. Self-attention 기반의 노드 embedding 과정.

 

그림 3은 self-attention 기반의 노드 embedding $\textbf{s}_i$를 생성하기 위한 과정을 보여준다. 그림에서 $W$는 학습 가능한 가중치 행렬, $\textbf{x}_i$는 $i$번 노드의 feature, $\alpha_{i,j}$는 $i$번 노드에서 $j$번째 노드로의 attention 값을 의미한다. 마지막으로, $\mathcal{N}_i$는 $i$번 노드와 edge로 연결된 인접 노드들의 index set이다. 그림 3의 예시에서는 2번 노드에 대해 attention 기반의 node embedding $\textbf{s}_2$를 생성한다. 이 과정에서 인접한 1, 3, 5번 노드에 대해 attention score를 계산하여 이를 기반으로 $\textbf{s}_2$를 생성하기 위한 weighted sum을 수행한다. 생성된 node embedding $\textbf{s}_2$에 대해 활성 함수 $f$를 적용함으로써 최종 node embedding인 $\textbf{h}_2 = f(\textbf{s}_2)$를 계산한다. 이러한 self-attention 기반의 노드 embedding을 수행하는 계층을 GAT에서는 graph attention layer라고 하며, 다음 항목에서는 GAT의 각 계층을 수식적으로 서술한다.

 

2.1. Graph Attention Layer

Graph attention layer는 그림 3과 같이 self-attention을 기반으로 노드 embedding을 생성하는 계층이다. GAT에서 $k$번째 graph attention layer의 출력 $\textbf{h}_i^{(k)}$은 다음과 같이 정의된다.

$$\textbf{s}_i^{(k)} = \alpha_{i,i}^{(k)}\textbf{W}^{(k)}\textbf{h}_i^{(k-1)} + \sum_{j\in\mathcal{N}_i} \alpha_{i,j}^{(k)}\textbf{W}^{(k)}\textbf{h}_j^{(k-1)}, \tag{1}$$

$$\textbf{h}_i^{(k)} = f_k(\textbf{s}_i^{(k)}). \tag{2}$$

위의 식에서 $\mathcal{N}_i$는 $i$번째 노드에 대한 인접 노드들의 index이며, $\textbf{W}^{(k)}$와 $f_k$는 각각 $k$번째 graph attention layer의 가중치 행렬과 활성 함수이다. $\textbf{h}_i^{(k-1)}$은 이전 graph attention layer의 출력으로써 $\textbf{h}_i^{(0)}$은 $\textbf{x}_i$로 표현되는 입력 node-feature이다. 마지막으로, 식 (1)의 attention score $\alpha_{i,j}^{(k)}$는 다음의 식 (3)과 같이 정의된다.

$$\alpha_{i,j}^{(k)} = \frac{\exp\left(\phi^{(k)}(\textbf{W}^{(k)}\textbf{h}_i^{(k)},\textbf{W}^{(k)}\textbf{h}_j^{(k)}) \right)}{\sum_{r\in\mathcal{N}_i} \exp\left(\phi^{(k)}(\textbf{W}^{(k)}\textbf{h}_i^{(k)},\textbf{W}^{(k)}\textbf{h}_r^{(k)}) \right)}. \tag{3}$$

식 (3)에서 $\phi^{(k)}: \mathcal{Z}\times\mathcal{Z} \rightarrow \mathbb{R}$는 $k$번째 graph attention layer의 attention 함수로써, 논문에서는 Leaky ReLU를 기반으로 식 (4)와 같이 정의되었다.

$$\phi^{(k)}(\textbf{W}^{(k)}\textbf{h}_i^{(k)},\textbf{W}^{(k)}\textbf{h}_j^{(k)}) = \text{LeakyReLU}\left(\textbf{a}_k^T [\textbf{W}^{(k)}\textbf{h}_i^{(k)}\oplus\textbf{W}^{(k)}\textbf{h}_j^{(k)}]\right). \tag{4}$$

위의 식에서 $\textbf{a}_k$는 학습 가능한 가중치 벡터이고, $\oplus$는 벡터 접합 (vector concatenation) 연산을 의미한다. 요약하자면, graph attention layer는 학습 가능한 가중치 행렬 $\textbf{W}^{(k)}$와 attention 함수의 가중치 벡터 $\textbf{a}_k$를 기반으로 식 (1)-(4)의 과정을 통해 새로운 노드 embedding $\textbf{h}_i^{(k)}$를 생성한다.

 

2.2. Readout (Optional)

GNN에서 readout은 생성된 노드 embedding을 하나의 벡터로 변환하여 그래프 전체의 embedding을 생성하는 기능을 수행한다. 따라서, GAT을 비롯한 GNN을 이용하여 노드에 대한 embedding, classification, regression을 수행하고자 하는 경우에는 GNN 구조에 readout이 포함되지 않는다. 그러나 그래프 embedding이나 분자 속성 예측과 같이 그래프 단위의 작업을 수행할 때는 readout이 GNN 구조에 포함되어야 한다.

일반적으로 readout은 모든 노드들의 embedding을 평균내거나 더함으로써 그래프 embedding을 생성한다. 예를 들어, 가장 많이 이용되고 있는 평균값 기반의 readout 함수 $\phi:\mathbb{R}^{N\times m} \rightarrow \mathbb{R}^m$은 다음의 식 (5)와 같이 정의된다.

$$\phi(\textbf{H}^{(K)}) = \left[\frac{1}{N}\sum_{i=1}^{N}\textbf{h}_{i,1}^{(K)}, \frac{1}{N}\sum_{i=1}^{N}\textbf{h}_{i,2}^{(K)} ..., \frac{1}{N}\sum_{i=1}^{N}\textbf{h}_{i,m}^{(K)}\right]. \tag{5}$$

식 (5)에서 $N$은 그래프에 포함된 노드의 수, $m$은 마지막 $K$번째 node embedding layer의 출력 차원이다. 기존 GNN과 GAT의 차이점은 node embedding layer에 있기 때문에 GAT의 readout은 기존의 GNN과 동일한 함수들을 이용한다.

 

2.3. Dense Layer

기존 GNN과 동일하게 GAT에서도 그림 2와 같이 node embedding 다음에 dense layer가 순차적으로 구현된다. Dense layer는 fully-connected layer로 구현되며, 입력된 노드 embedding 행렬 또는 그래프 embedding 벡터에 대한 출력을 계산한다. 따라서, 첫 번째 dense layer의 입력 차원은 마지막 node embedding layer의 출력 차원과 같은 $m$이어야 한다.

 

 

참고 문헌

[1] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. (2018). Graph Attention Networks. International Conference on Learning Representation.

10 Comments
  • 프로필사진 777천재777 2022.02.17 05:17 신고 그림 3. Self-attention 기반의 노드 embedding 과정 -> 의 수식을 자세하게 이해 하고 싶은데 설명 좀 해주실 수 있을 까요?

    시그마는 합계이고
    a 는 인접행렬인것 같고
    Wx2 의 W는 가중치 인것 같고

    이해안가는 부분 (상수, 변수, 계수)?
    S2
    Wx2
    ∑j∈N2
    α2,i Wxj

    아래의 2는 지수인것 같은데 맞나요?
    Wx2
    N2

    전체적으로 합계를 왜 하는지도 모르겠고
    수식을 이해 할 수 있게 알려주세요
    감사합니다.
  • 프로필사진 CHML 2022.02.18 20:50 신고 그림 3에서 s2와 x2는 각각 그래프에서 2번째 노드에 대한 embedding과 입력 feature를 의미합니다.

    수식을 전체적으로 합하는 이유는 attention 기반의 weighted sum을 통해 새로운 node embedding을 생성하기 위해서입니다. 이 과정에서 attention의 값은 weighted sum에서 weight, 즉 중요도와 같은 역할을 수행합니다.

    설명을 더욱 명확히 하기 위해 그림 3에 대한 내용을 수정했습니다. 수식에 대한 이해를 위해 한 번 다시 읽어보시는 것도 좋을듯합니다.
  • 프로필사진 777천재777 2022.02.19 11:45 신고 답변주셔서 감사드립니다.

    그림3 에서

    1. 왼쪽 노드 그림의 α2,i는 인접행렬 오른쪽 수식의 α2,i는 어텐션 값이 맞나요?

    2. Ni는 수식에는 N2라고 되어있는데 결국에는 N2인거죠? 여기서는 노드2에서는
    Ni = N2(2번 노드의 index set(1,3,5))

    3. 어텐션s 값하고 features값하고 다른거죠? 어텐션은 뭔가 추가적인 가중치 인것 같고요

    4. 어텐션기반의 합계를 구하는 이유는 결국에는 높은 가중치의 노드로 분류하기 위한 것 인가요? node embedding을 생성해서 그 이후에 어떻게 사용하는지 궁금합니다.

    감사합니다.
  • 프로필사진 777천재777 2022.02.19 11:52 신고 4. 은 전체적인 gat 의 활용 과정을 한번 해봐야 어텐션기반의 합계를 구하는 이유를 알 수 있을것 같은데요
  • 프로필사진 CHML 2022.02.19 12:00 신고 1. alpha는 왼쪽과 오른쪽에서 모두 어텐션 값을 의미합니다.

    2. 네, 맞습니다. 노드2에서는 Ni = N2 = {1, 3, 5}입니다.

    3. 네, s와 features는 서로 다른 것을 의미하며, 어텐션은 추가적인 가중치와 같은 역할을 하는 것이 맞습니다. s는 노드 feature와 어텐션을 기반으로 생성된 노드의 latent feature입니다.

    4. Node embedding을 사용하는 방법은 응용에 따라 매우 다양합니다. Node embedding으로부터 node의 class label을 예측하는 문제도 있고, node embedding을 종합해서 전체 그래프의 target value를 예측하는 문제도 있습니다.
  • 프로필사진 777천재777 2022.02.19 12:23 신고 그림3 의 왼쪽 α2,j 의 α 는 adjacency matrix 의 adjacency이고(그냥 인접행렬을 나타냄) 오른쪽 수식의 α2,j는 해당 adjacency node 의 어텐션값인 건가요? 그러니까 둘다 α = adjacency의 약자 인건가요 아니면 알파인가요
  • 프로필사진 CHML 2022.02.20 09:30 신고 α2,j는 왼쪽과 오른쪽에서 모두 어텐션을 의미합니다. α는 adjacency의 약자가 아닙니다.
  • 프로필사진 777천재777 2022.02.25 09:22 신고 답변 감사드립니다 이런 인공지능 수학수식들을 이해할수 있는데 기초적인 수학부터 중고급까지 어떤것들을 공부하면 될까요?
  • 프로필사진 CHML 2022.02.25 22:21 신고 기본적으로 선형대수와 확률이론 정도만 아셔도 많이 사용되는 인공지능 알고리즘을 이해하시는 것에는 문제가 없습니다.
    추가적으로 인공지능 이론이나 고급 알고리즘을 온전히 이해하고 싶으시면 convex optimization, nonlinear optimization, graph theory를 공부하시는 것이 필요할듯합니다.
  • 프로필사진 천재 2022.04.04 19:11 3. 네, s와 features는 서로 다른 것을 의미하며, 어텐션은 추가적인 가중치와 같은 역할을 하는 것이 맞습니다. s는 노드 feature와 어텐션을 기반으로 생성된 노드의 latent feature입니다.

    위의 s는 mbedding si 를 말하는 건가요?
댓글쓰기 폼