//////
Search
Duplicate

변호윤

과제여부
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 두 가지에서 실험 및 다른 모델들과 비교를 하였는다.