GCN, GraphSAGE, GAT 는 graph data에 적용가능한 Neural Networks 중 원조격(대표적)인 프레임워크이다.
여기서 Graph data에 적용가능한 NN의 의미는 input graph가 NN을 통과하였을때 Permutaion equivariant, Permutation invariant 해야한다.[cs224w 6강]
•
permutation equivariant : node의 order가 달라져도 동일한 node라면 NN을 통과하였을때 동일한 representation을 보여야한다.
•
permutation invariant : node의 order가 달라져도 같은 그래프라면 동일한 graph representation을 보여야한다.
기존의 Neural Network는 위 성질을 가지지 못한다. 그래서 이를 해결하기 위해 이웃 노드들로 부터 정보를 message passing과 aggregating 하는 기법이 사용된다.
GCN, GraphSAGE 그리고 GAT는 이웃을 어떻게 정의하고 message를 어떻게 종합할지에 따라 구분될 수 있을 것이다.
GCN
•
Convolution 연산을 그래프 구조에 적용한 방법이다.
graph laplacian의 eigendecomposition을 구하고 Fourier domain에서 convolution을 정의.
•
GCN을 제안한 논문에서는 graph convolution의 복잡한 계산과정을 매우 간소화 하여
1-hop 이웃 정보를 normalize하여 message를 전달하는 방법을 제안한다.
•
self-loop가 추가된 Adjaceny matrix와 Degree matrix로 message passing을 구할 수 있고
K 번 반복하여 K-hop 떨어진 노드 정보까지 반영할 수 있다.
GraphSAGE
•
GCN은 transductive하기 때문에 새로운 node가 추가되거나, unseen graph에 적용할 수 없고 재학습을 해야한다는 단점이 있다. 또한 target node와 연결된 모든 이웃의 정보를 다 종합하게 되는데 large graph에서나 hop이 큰 경우에 학습에 어려움이 있다.
•
이를 보완하기 위한 방법으로 inductive setting에서 사용가능한 모델이 GraphSAGE이다. 먼저 이웃을 hop 별로 전체 이웃의 message를 다 반영하는 것이 아니라 고정된 개수의 이웃정보만 반영한다.
•
그리고 message를 통합하는 연산에서 다양한 연산을 적용할 수 있는데, 저자는 Mean, LSTM, (max)Pool 그리고 GCN을 적용하여 실험을 진행하였다.
GAT
•
GCN은 target node의 feature를 update하기 위해 target node의 degree와 message를 전달할 이웃 노드의 degree를 이용하여 가중합을 하게된다. 그리고 GraphSAGE에서는 이웃노드들의 message를 평균내어 target node의 feature를 update한다.
•
GAT는 이웃노드의 message를 aggregate할때 attention 계수를 계산하여 이웃 노드들의 feature를 가중합할때 사용하게 된다.
•
본 논문에서는 GAT를 transductive와 inductive setting 두 가지에서 실험 및 다른 모델들과 비교를 하였는다.