[paper review] GRAPH ATTENTION NETWORKS

date

Oct 10, 2023

slug

GAT

author

status

Public

Introduction

CNN은 local filter를 사용하며 grid 기반의 데이터 구조(e.g. image)에 성공적으로 적용되어 왔습니다.

하지만, 실제 많은 Task(3d-mesh, social networks, telecommunication networks, ..)들은 이러한 grid-like 구조를 사용할 수 없습니다.

따라서 임의의 구조화 된 데이터(arbitrarily structured data)에 신경망을 적용하기 위한 노력들이 계속되고 있습니다.

GNN 또한 이러한 노력 중 하나 입니다.

GNN에는 크게 두가지 종류가 존재합니다.

첫 번째는, GCN과 같은 Spectral approach입니다.

Spectral approach는 Graph의 signal(graph laplacian)을 eigenvalue decomposition하여 푸리에 도메인에서 정의된 Convolution 연산을 통해 그래프(노드)를 표현합니다.

GCN은 특히 추천 시스템과 같이 빈 값이 많은 semi-supervised node classification에서 매우 뛰어난 성능을 보였지만, 느낌적으로도 알 수 있듯, eigenvector를 사용하기 때문에 그래프의 구조가 조금이라도 바뀐다면 학습한 내용을 다른 그래프에 적용(inductive case)할 수 없습니다.

두 번째는, graph-sage와 같은 non-spectral approach입니다.

non-spectral approach는 spectral analysis를 사용하지 않고, 단순히 이웃들의 정보를 aggregator를 통해 취합하는 방식으로 그래프를 학습합니다. 따라서 non-spectral approach의 관건은 불 특정한 다수의 이웃 정보를 어떠한 방식으로 aggregate할 것인지 입니다. 예시로, graph sage는 fixed size의 이웃을 sampling하는 방식의 aggregator를 사용합니다.

본 논문은 non-spectral의 관점에서 attention을 사용한 aggregator 모델인 GAT(graph attention networks)를 제안하고 있습니다.

본 논문의 contribution은 다음과 같습니다.

node pair로 병렬화 시킬 수 있는 매우 효율적인 aggregation 방법을 제안합니다.

동일한 degree를 갖지 않는 node에 대해서도 적용할 수 있습니다.

unseen graph(inductive learning problem)에도 적용할 수 있습니다.

Proposed Method

간단하게 하나의 GAT layer를 예시로 들어 제안하는 방법을 설명드리겠습니다.

GNN과 Attention mechanism을 아신다면 쉽게 이해하실 수 있습니다.

input

먼저, GAT layer의 input은 다음과 같습니다.

set of node features.

is # or nodes, is # of features

output

GAT layer는 output 역시 input과 동일한 구조를 갖습니다. 하지만 일반적인 신경망과 같이 feature space의 크기는 달라질 수 있습니다.

is # of nodes, is # of features

GAT layer computation

모든 인공신경망이 그렇듯 input feature를 high leavel output feature로 변환하기 위해서는 최소한 하나의 learnable linear transformation layer가 필요합니다. GAT역시 동일하며, weight matrix 는 각각에 노드에 적용되어 그 역할을 수행합니다.

따라서 이웃 노드 사이의 attention은 다음과 같이 계산됩니다.

attention 를 기반으로 한 node i,j 사이의 attention coefficients는 다음과 같습니다.

<그림 1> 왼쪽과 같이, 본 논문에서는 attention mechanism 를 구하기 위해 weight matrix 를 포함하는 single-layer feedforward network를 사용합니다. (bahdanau attention)

따라서 종합하면, 를 기반으로 한 attention coefficients 는 아래의 식과 같아집니다.

이웃 노드와의 attention coefficients를 반영한 GAT layer를 지난 node i의 feature는 다음과 같아집니다.

당연하게, k개의 multi-head attention을 concat하여 사용할 수도 있습니다.

final(prediction) layer에 한해서는 concat이 아닌 averaging을 사용합니다.

Experiments

실험은 transductive, inductive setting에서 각각 node classification 성능을 비교하였습니다.

실험에 사용한 dataset 입니다.

3개의 transductive problem과 1개의 inductive problem인 것을 확인할 수 있습니다.

transductive problem

mean classfication acc를 비교하였습니다.

GAT가 spectral model인 GCN보다 우수한 성능을 보였습니다.

inductive problem

micro-averaged F1 score를 비교하였습니다.

GraphSage보다 매우 우수한 성능을 보였습니다.