[Study]Chapyer 6. Graph Neural Networks 1: GNN Model

해당 내용은 개인적으로 정리한 내용임으로 틀린 부분이 있을 수 있습니다.

이제부터 본격적으로 Graph Neural Network에 대한 내용을 다룬다.

I. Graph Neural Networks

Figure 1 : 노드를 d 차원의 임베딩 공간으로 그래프에서의 유사도를 지닌 채로 매핑.

\[ENC(v) = \begin{array}{ll} \text{그래프 구조에 기반한 } \\ \text{다층 비선형 변환} \end{array}\]

이러한 ENC들은 Lecture 3에서 배운 유사도 함수로 결합된다.

II. Bascics of deep learning

기계학습의 최적화로 지도 학습은 x가 주어졌을때 y를 학습하는 것을 목표로한다. 따라서, 최적화 문제로서 이러한 작업을 아래와 같이 형식화한다.

\[\min\limits_{\theta}\mathcal{L}(y,f(x))\]

• \(\theta\); 최적화해야하는 파라미터들의 집합.
• \(\mathcal{L}\); loss function¹
  • ex. L2 loss, \(\mathcal{L}(y,f(x))=\vert \vert y-f(x)\vert \vert _2\)

다층 퍼셉트론 MLP의 각 층은 아래와 같이 비선형과 선형 변환의 결합으로 이루어져 있었다.

\[x^{(l+1)}=\sigma(W_lx^{(l)}+b^l)\]

III. Deep learning for graphs

1. Local network neighborhoods

집계 전략으로 계산 그래프\(_{computational-graph}\)를 정의한다.

• Naive Approach

  인접행렬과 특징을 결합하여 신경망에 넣는 방식으로 \(O(\vert V\vert )\)의 파라미터를 가지고 있으며 다른 사이즈의 그래프는 적용이 안되고, 노드를 순서에 민감하다.

• Convolutional Networks

  이미지나 텍스트에서는 단순한 격자 이상의 Conv를 일반화하는 것이 목표로 노드의 특성이나 속성을 활용한다. 하지만 그래프는 지역성이나 sliding window와 같은 고정된 관념이 없어 순서를 무시\(_{permutation-invariant}\)합니다.

  순열 불변(permutation-invariant)

  그래프 \(G\)가 주어졌을때 fucntion \(f\)로 다른 order plan i,j를 가진 \(f(A_i, x_i)\)와 \(f(A_j, x_j)\)가 같으면 f를 “순열 불변”이라고 한다.

  Figure 3 : 동일한 인접 행렬 \(A\)와 노드 특징 행렬 \(X\)를 넣었을 때 동일한 그래프가 나오기에 순열-불변하고, 순서를 바꾼 두 그래프의 동일한 위치의 노드에서 같은 임베딩이 나오기에 순열-동질하다고 할 수 있다.

  f가 순열-불변하다는 것은 아래와 같다.

  \[f(A,X)=f(PAP^T,PX)\]

  그렇지 않다면(Permuation-equivariant) 아래와 같다.

  \[Pf(A,X)=f(PAP^T,PX)\]

  GNN을 CNN과 같은 유명한\(_{prominent}\) 어떻게 비교할 수 있을까?

  Figure 12 : 3x3 필터를 가진 CNN에서는 \(N(v)\)는 v의 8개의 이웃 픽셀을 표현

  이미지에서는 픽셀의 중심을 기준으로 상대적인 위치를 가진 9개의 이웃들의 순서를 부여할 수 있어서 특정 픽셀에서 서로 다른 이웃인 픽셀의 가중치 \(W_l^u\)를 학습할 수 있습니다.

  따라서, CNN은 순서화되고 고정된 이웃 크기를 가진 특별한 GNN으로 보여질 수 있습니다. 그러나 CNN은 permutation invariant/equivariant 하지 않기 때문에 픽셀의 순서를 바꾸게 되면 다른 결과로 이끌어 GNN과는 다른 결과를 불러오게 됩니다.

  Figure 4 : GNN은 여러개의 permutation equivariant와 invariant 함수로 구성되어있다.

  단순한 MLP 접근법이 그래프에서 실패하는 이유는 이와 같이 순열 불변/동질 하지 않기에 입력 순서를 바꾸면 결과값이 다르게 나오기 때문이다.

2. Graph Convolutional Networks

이제 이웃에서 정보를 전달하고 집계하는 방법으로 노드의 특징을 계산함으로써 그래프의 정보를 어떻게 전달하는지 학습해야합니다.

주된 핵심은 지역 네트워크 이웃들에 기반하여 노드 임베딩을 신경망을 통해 생성하는 것입니다.

Figure 5 : Aggregate Neighbors, (좌)노드의 계산 그래프 결정 (우) 정보의 변형 및 전달.

평균을 사용하면 GNN이 Figure 8에서 보이듯이 이웃들인 {B,C,D} 이전층 임베딩을 사용하는 A의 임베딩은 순열 불변성을 보여줍니다.

Figrue 8 : GCN에서 이웃들의 이전층 임베딩의 평균은 순열 불변이다.

Figure 6에서의 임의적인 깊이를 가지는 신경망 모델의 노드는 각 층에서 임베딩을 가지며 각 모델의 주된 차이는 각 층을 넘어서 정보를 종합하는 접근법(기본적으로 평균)을 다르게 하는가입니다.

Figure 6 : 노드는 이웃들을 계산 그래프\(_{computation-graph}\)로 정의하고, 신경망을 이용해 정보를 종합한다.

Figrue 7 : Figure 6 신경망의 hidden state 공식으로 노드 특징을 초기값으로 설정하여 이전 층의 해당 임베딩과 평균 임베딩의 선형결합 후 비선형 함수를 사용하여 계산한다.

많은 (희소) 행렬 작업으로 많은 aggregation이 효과적으로 수행 됩니다.

\[\begin{array}{ll} \text{Let. }H^{(k)}=[h_1^{k}, ..., h_{\vert V\vert }^{k}]^T, D_{v,v}=Deg(v)=\vert N(v)\vert \\ \text{Then, }\sum_{u \in N_v}h_u^{(k)}=A_{v,:}H^{(k)} \\ \text{Therefore, }\sum_{u \in N(v)}\frac{h_u^{(k-1)}}{\vert N(v)\vert } \rightarrow H^{(K+1)=D^{-1}AH^{(k)}} \end{array}\]

Figure 10 : 실제로 희소 행렬(\(\tilde{A}\)) 곱셈을 사용할 수 있다는 것을 의미합니다.

3. How to Train GCN

Figure 7에서 임베딩을 아무 loss 함수에 넣어 SGD를 통해 아래와 같은 가중치들을 학습시킨다.

• \(h_v^t\) : k 층의 v 노드의 은닉 표현
• \(W_k\) : 이웃들의 종합 가중치 행렬

• \(B_k\) : 자신의 은닉 벡터를 변환하는 가중치 행렬

• Unsuperviesd

  이제 임베딩을 생성하는 모델은 어떻게 학습해야하는지 아래와 같이 임베딩의 loss 함수를 정의할 필요가 있다.

  \[\mathcal{L} = \sum_{z_u, z_v}CE(y_{u,v}, DEC(z_u,z_v))\]

  위에서 \(y_{u,v}=1\)이면 노드 u와 v가 유사하다는 것을 의미하고 CE는 cross entropy, DEC는 내적 곱과 같은 decoder이다. 노드 유사도는 3장에서 설명한것과 같이 무작위 보행, 행렬 분해, 그래프의 node proximity 등으로 될 수 있따.

• Superviesd

  이후 지도 학습 작업(ex. 노드 분류)을 위해 직접 모델을 아래와 같이 학습 시킵니다.

  \[\mathcal{L}=-\sum_{v\in V}y_vlog(\sigma(z_v^T\theta))+(1-y_v)log(1-\sigma(z_v^T\theta))\]

  \(y_v\)는 노드 class label이고 \(z_v^T\)는 노드 임베딩으로 \(ENC(\cdot)\) 출력이고 \(\theta\)는 분류 가중치이다.

4. Overview

• (1) 이웃 집계 함수를 정의.
• (2) 임베딩의 loss 함수 정의.
• (3) 노드들의 집합 학습.
• (4) 필요한 노드들의 임베딩을 생성.

귀납 능력(inductive capability)

같은 집계 파라미터(\(W_l, B_l\))는 모든 노드에서 공유된다. 따라서 노드 임베딩의 귀납은 보지 못한 그래프 전체를 일반화할 수 있다. 실제로 끊임없이 새로운 노드들을 마주치게 된는데, 새로운 임베딩을 “매번”\(_{on-the-fly}\) 생성할 필요가 있다.

IV. GraphSAGE

GCN에서 이웃 메시지의 가중 평균을 통해 종합했는데 이보다 더 좋은 방법은 없을까?

Figure 11 : GraphSAGE, generalized neighborhood aggregation

\(l_2\) Normalization으로 아래와 같이 벡터들의 scale을 정규화한다.

\[h_v^t \leftarrow \frac{h_v^t}{\vert \vert h_v^t\vert \vert _2} \forall v \in V \text{, where } \vert \vert u\vert \vert _2 = \sqrt{\sum_iu_i^2} (\text{L2-norm})\]

이렇게 L2 정규화를 진행하면 모든 벡터들은 같은 L2-norm을 가져 성능의 향상되기도 한다.

Variants

• Mean
  • 이웃의 가중합으로 계산한다.
  \[AGG = \sum_{u \in N(v)}\frac{h_u^{(l)}}{\vert N(v)\vert }\]
• Pool
  • 대칭적인\(_{symmetric}\) 벡터함수를 적용해 집약시킨다.
  \[\begin{array}{ll} AGG = \gamma(\{MLP(h_u^{(l)}), \forall u \in N(v)\}) \\ \gamma : \text{Element-wise \space mean/max} \end{array}\]
• LSTM
  • LSTM을 적용하여 순서대로 이웃들을 계산하는 방식으로 순서가 없는 그래프에서 reshuffle등의 추가적인 순서 전략이 필요함.
  \[AGG = LSTM({h_u^{(l)}, \forall u \in N(v)\})\]

1. https://pytorch.org/docs/stable/nn.html#loss-functions ↩