<CS224W> Lecture 6. Graph Neural Networks 1: GNN Model

kimkj38·2022년 4월 1일
0

CS224W

목록 보기
6/17

Recap

  • 노드 임베딩이란 그래프 상에서 유사한 노드들이 함수 ff를 거쳐 dd차원으로 임베딩 되었을 때에 가까이 위치하도록 만드는 것이다.
  • 이 과정에서의 핵심은 low-dimension으로 맵핑을 해주는 인코더와 original network에서의 유사도와 embedding space에서의 내적이 유사하도록 만드는 similarity function이다.
  • 가장 간단한 인코딩 방법은 노드의 임베딩 벡터를 각 column에 담는 lookup 방식이다.
  • 하지만 다음과 같은 limitations가 있다.
    1. 노드 간의 파라미터 공유가 없기 때문에 O(V)O(|V|)의 파라미터가 필요하다.
    2. Training 과정에서 보지 못한 노드는 임베딩을 생성할 수 없다.
    3. 노드의 feature를 포함하지 않는다.

1. Graph Neural Networks

  • GNN에서는 Multiple layer로 구성된 인코더를 활용한다.
  • 이러한 구조를 통해 node classification, link prediction, community detection, network similarity 등의 task를 수행할 수 있다.
  • 그래프는 이미지나 텍스트와 달리 사이즈나 구조에 있어 유연하고 복잡하기 때문에 어려움이 있다.(Arbitrary size and complex topological structure)

2. Deep Learning for Graphs

V:V: 노드 집합
A:A: 인접 행렬(binary로 가정)
XRm×V:X \in \mathbb{R}^{m \times |V|}: 노드 feature의 행렬
N(v):N(v): 노드 vv의 이웃 노드 집합

Convolutional Networks

  • 그래프에 convolution을 적용하는데는 locality나 sliding window에 고정된 개념이 없다는 어려움이 있다.
  • 즉, 하나의 필터에 들어오는 노드의 수가 슬라이딩을 하면서 바뀐다.
  • CNN의 필터는 중심 픽셀을 기준으로 이웃 픽셀들과의 관계를 통해 값을 내주는 역할을 하므로 그래프에서도 이웃노드들의 메세지를 통해 결과를 내는 개념으로 적용할 수 있다.

Graph Convolutional Networks

  • CNN은 고정된 구조에서 여러 데이터(이미지)를 받아 순전파, 손실함수 계산, 역전파 과정을 거치게 된다.
  • GCN은 고정된 구조가 아니기 때문에 다음과 같은 과정을 거친다.
    1. 각 노드별 계산 그래프 생성
    2. 각 노드 별 계산 그래프에 따라 순전파
    3. 손실함수 계산 및 역전파

Aggregate Neighbors

  • Local network neighborhoods를 통해 노드 임베딩을 만들 수 있다.
  • 2개의 레이어를 거치도록 구성하면 target node AA는 이웃 노드인 B,C,DB,C,D로부터 정보를 받고 이 이웃노드들은 또 다른 각자의 이웃 노드들로부터 정보를 받는다.
  • Layer-1에 있는 BBA,CA,C로부터 받은 정보와 자기 자신의 정보가 합쳐져 있으므로 Layer-0에 있는 BB와는 다른 벡터로 구성되어 있다.

  • 모든 노드들에 대해 다음과 같이 local한 계산그래프를 정의할 수 있다.
  • 각각의 계산그래프는 서로 다른 구조를 가지게 된다.
  • Layer의 수는 임의로 정할 수 있으나 노드의 개수만큼 계산그래프가 생기므로 너무 깊게 쌓는데는 한계가 있다.
  • 이웃노드 정보의 전달은 input의 위치와 관계가 없는 평균값을 활용하며 이후 neural network를 거친다.
  • 첫번째 layer에서는 input으로 노드의 feature가 그대로 들어간다.
  • 두번째 layer부터는 이웃노드들의 이전 레이어에서의 임베딩의 평균값과 각 이웃노드들의 임베딩이 input으로 들어가며 활성화함수를 거쳐 hvl+1h_v^{l+1}을 얻는다.
  • WlW_lBlB_l은 학습되는 파라미터이다.

Matrix Formulation

  • H(l)=[h1(l),...,hV(l)]:H^{(l)}=[h_1^{(l)}, ... ,h^{(l)}_{|V|} ]: ll번째 레이어의 모든 노드에 대한 vector를 concat한 행렬
  • AA는 인접행렬이므로 AH(l)AH^{(l)}을 통해 vv노드의 모든 이웃 노드의 벡터의 합을 구할 수 있다.
  • DDvv노드의 이웃노드의 수가 담긴 대각행렬이다. D1=1N(v)D^{-1}=\frac{1}{|N(v)|}vv노드의 이웃노드의 수의 역수가 된다.
  • 따라서, H(l+1)=D1AH(l)H^{(l+1)}=D^{-1}AH^{(l)}과 같이 maxtirx 연산이 가능하다.
  • 빨간색은 이웃 노드의 정보를 모으는 부분, 파란색은 본인 노드의 정보를 변형하는 부분이다.
  • A~\tilde{A}는 sparse한 행렬이기 때문에 sparse matrix multiplication을 도입해 효과적인 연산이 가능함을 의미한다.

Training

  • Unsupervised의 경우 그래프의 구조를 supervision으로 사용하여 유사한 노드가 embedding space에서도 유사해지도록 학습한다.

    yu,v:u,vy_{u,v}:u,v노드가 유사할 때 1
    CECE: cross entropy
    DEC:DEC: Decoder(ex. 내적)

  • Supervised는 노드 예측 시 에러가 최소가 되도록 학습.
  • 여러개의 계산그래프를 배치 단위로 학습 시키며 모델의 파라미터들은 공유되어 보지 않은 노드 혹은 그래프에 대해서도 일반화 능력을 가질 수 있다.

3. GraphSAGE

  • Aggregation을 (가중)평균을 이용하는 대신 미분 가능한 함수를 사용할 수도 있다.

References

0개의 댓글