(9) GCN - Architecture of GCN

 

 

 

 

Features of Convolution¶

구체적인 구조를 설명하기 전에 먼저 Convolution의 특징을 다시 한번 되새겨 생각해보고 넘어가겠습니다.
기존에 사용하던 MLP는 모든 노드들을 펼쳐서 연결하였으므로 파라미터의 수가 너무 많아지는 문제가 있었습니다.
또한 이미지가 1픽셀만 움직이더라도 한 줄로 펼쳐짐으로 인해 정확한 feature의 추출이 어려워지는 문제점이 있었습니다.

Convolution을 사용한 레이어는 아래의 세 가지의 특징으로 이를 개선했었죠.

1. Weight sharing
   하나의 필터가 이미지 전체를 슬라이드함으로써 Weight를 공유하고 파라미터의 수를 줄임
   (less overfitting, low computational cost)

2. Learn local feature
   하나의 노드가 담는 정보가 Receptive field라는 인접한 노드들의 지역적인 정보를 함축

3. Translation invariance
   모든 노드를 펼쳐서 연결하지 않고 필터 슬라이딩 방식으로 Feature를 추출하므로 translation에 대한 편차가 적어짐

 

What Should We Update When Training GCN?¶

우선 Convolution 개념을 응용해서 Graph를 다루는 네트워크를 구성하기 위해서 아래의 두 가지 질문에 대해 생각해봅시다.

(1)
CNN에서 이미지의 상태를 나타내는 값은 어떤 것이었죠?
CNN에서는 바로 매 레이어의 출력 결과인 Activation map이 이미지의 상태를 나타냈습니다.
그리고 레이어를 통과할 때마다 이 Activation map을 업데이트해서 유용한 Feature를 추출했습니다.

(2)
그러면 이번에는 그래프의 상태를 나타내는 값은 무엇일까요?
각 노드가 갖는 Feature입니다.

그러면 GCN에서는 레이어를 통과할 때마다 Node Feature의 값을 업데이트하도록 만들어서 Feature를 추출하면 되겠네요.

 

How to Update Hidden State in GCN¶

(1)
1번 노드가 2, 3, 4번 노드와 연결되어 있는 경우 1번 노드를 n번째 레이어에서 업데이트하기 위해 아래와 같은 수식이 성립합니다.
(자기 자신의 Hidden state와 연결된 노드들의 Hidden state를 레이어의 Weight와 각각 점곱하고 더하는 수식입니다.)

$H_1^{(n+1)} = \sigma~\left( H_1^{(n)} W^{(n)} + H_2^{(n)} W^{(n)} + H_3^{(n)} W^{(n)} + H_4^{(n)} W^{(n)} + b^{(n)} \right)$

(2)
즉, i번 노드와 연결되어 있는 j번 노드들을 W와 점곱한 값의 합으로써 아래와 같이 일반화하여 표현할 수 있습니다.

$H_i^{(n+1)} = \sigma~\left( \displaystyle \sum_{j \in N(i)} H_j^{(n)} W^{(n)} + b^{(n)}\right)$

(3)
그런데 우리는 연결되어 있는 j번 노드에 대한 정보를 이미 갖고 있습니다.
바로 Adjacency Matrix($A$)가 그 역할을 했었죠.
따라서, 이러한 Connectivity를 고려한 전체 연산은 Linear algebric한 관점에서 아래와 같이 표현할 수 있습니다.

$H^{(n+1)} = \sigma~ \left( A (H^{(n)} W^{(n)}) + b^{(n)} \right)$

($\sigma$는 여기에서 Sigmoid가 아닌 Activation을 의미합니다.)

 

Actual Calculation for GCN¶

이해를 돕기 위해서 최종적으로 우리가 도출했던 아래의 식을 통해 실제로 GCN의 계산과정을 따라가 보겠습니다.

$H^{(n+1)} = \sigma~ \left( A (H^{(n)} W^{(n)}) + b^{(n)} \right)$

 

(1)

예시로 사용할 Graph는 아래와 같습니다.

Node Feature Matrix(= H)는 아래와 같습니다.

레이어의 out_features가 64일때 해당 층의 Weight행렬(= W)은 아래와 같습니다.

그러면 Node Feature Matrix와 Weight를 통해 $(H^{(n)} W^{(n)})$를 계산해보겠습니다.
H는 5x10의 행렬이고 W는 10x64의 행렬이므로, dot product를 하면 5x64 행렬이 되겠네요.
그리고 H의 각 노드가 Weight의 각 필터들에 의해 선형변환하는 것을 확인할 수 있습니다.
(선형대수 관점에서 행렬곱을 이해하는 것이 중요합니다.)

이는 CNN에서 이미지가 각 filter들과 연산하는 것과 같습니다.

 

(2)

이제는 $A(H^{(n)} W^{(n)})$을 계산해보겠습니다.

이 그래프의 Adjacency matrix는 아래와 같습니다.

아래는 조금 전에 계산했던 $(H^{(n)} W^{(n)})$의 결과 행렬의 모습입니다.

두 행렬을 행렬곱하면 5x64의 행렬이 됩니다.
또한 마찬가지로 Adjacency Matrix의 Connectivity 정보가 각 필터와 연산하는 것을 확인할 수 있습니다.

이렇게 Adjacency Matrix를 행렬곱하는 것만으로도 각 노드의 Connectivity가 반영되게 됩니다.

 

(여기서 자기 자신 노드의 연결을 1로 하는 이유는 다음 층으로 값을 넘길 때에 자기 자신의 hidden state 역시 반영되어야 하기 때문입니다.
원직적으로 CS적인 의미에서의 그래프라면 자기 자신으로 가는 연결이 없기때문에 0이어야 합니다.)

 

Readout layer : Permutation invariance¶

위에 예시로 사용한 그래프에서 만약 0번 노드를 4번 노드라고 이름을 바꾸고 4번 노드를 0번 노드로 이름을 바꾼다면 이 그래프는 원본 그래프와 다른 그래프일까요?

노드의 순서가 바뀌었을 뿐 우리가 인식하는 그래프의 성질이나 상태는 동일한 그래프입니다.
단, Node Feature Matrix는 변할 수 있습니다.
이렇게 달라진 Feature Matrix를 컴퓨터의 입장에서는 동일한 것으로 인식하지 못합니다.

Readout layer는 그러한 Permutation들이 인풋으로 들어와도 같은 결과를 낼 수 있게 해주는 레이어입니다.

메인 아이디어는 모든 Node의 Hidden state에 MLP를 씌운 후 더하는 것입니다.
Hidden state에 MLP를 씌우면 MLP의 Weight가 Hidden state의 모든 노드와 연결되면서 하나의 벡터로 만들 수 있습니다.
이제 이 벡터들을 모두 더하면, 아무리 순서가 바뀌어도 동일한 값이 되겠네요.

Node wise summation
$z_G = \tau \left( \displaystyle \sum_{i \in G} MLP \left( H_i^{(L)} \right)\right)$

(MLP를 통과하므로 $H_i^{(L)}$이 Flatten 하게 됩니다.)

 

Overall Structure of GCN¶

GCN의 전체 구조를 보면 아래와 같습니다.

1. Graph Input: G(X, A)
2. Stack of Graph Convs
3. Readout Layer
4. Predictor
5. Output: Labels (= Properties)

(1) 그래프 인풋이 입력되면 (2) Graph Conv 레이어들을 통과하고 (3) 마지막 Graph Conv 레이어 이후에 Readout 레이어를 통과하여 Permutation invariance를 확보합니다.
이 후에 (4) Predictor를 통과시켜 (5) 최종적으로 우리가 얻고자 하는 y값에 도달하게 됩니다.

 

Features of Convolution in GCN¶

마지막으로 GCN 구조가 처음에 확인했던 Convolution의 특성을 어떻게 반영하는지를 알아보겠습니다.

1. Weight sharing $\Rightarrow$ 동일한 W를 행렬곱함으로써 sharing
2. Learn local feature $\Rightarrow$ 인접한 노드를 반영함으로써 local feature를 학습
3. Translation invariance $\Rightarrow$ Readout 레이어를 사용함으로써 invariance 확보