Recap

• 노드 임베딩이란 그래프 상에서 유사한 노드들이 함수 $f$를 거쳐 $d$차원으로 임베딩 되었을 때에 가까이 위치하도록 만드는 것이다.
• 이 과정에서의 핵심은 low-dimension으로 맵핑을 해주는 인코더와 original network에서의 유사도와 embedding space에서의 내적이 유사하도록 만드는 similarity function이다.
  
• 가장 간단한 인코딩 방법은 노드의 임베딩 벡터를 각 column에 담는 lookup 방식이다.
• 하지만 다음과 같은 limitations가 있다.

  1. 노드 간의 파라미터 공유가 없기 때문에 $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:$ 노드 집합
$A:$ 인접 행렬(binary로 가정)
$X \in \mathbb{R}^{m \times |V|}:$ 노드 feature의 행렬
$N(v):$ 노드 $v$의 이웃 노드 집합

Convolutional Networks

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

Graph Convolutional Networks

• CNN은 고정된 구조에서 여러 데이터(이미지)를 받아 순전파, 손실함수 계산, 역전파 과정을 거치게 된다.
• GCN은 고정된 구조가 아니기 때문에 다음과 같은 과정을 거친다.

  1. 각 노드별 계산 그래프 생성
  2. 각 노드 별 계산 그래프에 따라 순전파
  3. 손실함수 계산 및 역전파

Aggregate Neighbors

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

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

Matrix Formulation

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

Training

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

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

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

3. GraphSAGE

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

References

• Lecture 6.1: https://www.youtube.com/watch?v=F3PgltDzllc&list=PLoROMvodv4rPLKxIpqhjhPgdQy7imNkDn&index=17&t=2s
• Lecture 6.2: https://www.youtube.com/watch?v=tutlI9YzJ2g&list=PLoROMvodv4rPLKxIpqhjhPgdQy7imNkDn&index=18
• Lecture 6.3: https://www.youtube.com/watch?v=MH4yvtgAR-4&list=PLoROMvodv4rPLKxIpqhjhPgdQy7imNkDn&index=19