[Stanford/CS224W] 6. GNN(3) : Deep Learning for Graphs

스탠포드 강의를 듣고 정리한 내용입니다.

 

지난 포스팅에서는 그래프 신경망에 본격적으로 들어가기 전 딥러닝 개념에 대해서 빠르게 훑어보았습니다. 

이번 포스팅에서는 신경망을 일반화하여 그래프에 적용해보겠습니다. 

 

Deep Learning for Graphs

이제 그래프와 딥러닝에 대해서 한번씩 배웠으니 두 개를 묶어서 보겠습니다. 

이를 그래프 신경망, Graph Neural Network(GNN)이라고 부릅니다. 

 

첫 번째로는 "Local Network Neighborhoods"에 대해 알아볼텐데요. 앞의 포스팅에서처럼 현재 노드는 이웃 노드들의 정보를 얻고, 그 정보를 합산해서 사용했습니다. 여기서도 똑같이 적용할 것입니다. 

 

두 번째로는 이제 신경망을 이용하게 될텐데요. 이 신경망을 어떻게 정의하고, 학습시키는지 알아보겠습니다.

 

본격적인 설명에 들어가기 앞서, 몇몇의 개념을 정의하고 가겠습니다. 

• G : 그래프입니다.
• V : 그래프 내의 노드셋(vertex set)입니다.
• A : 노드간의 관계 matrix(Adjaceny matrix), 여기서는 이진값으로 생각하고, 무방향으로 간주합니다. 
• X : 노드 피쳐의 매트릭스입니다. 여기서 (mx|V|)차원을 가진다고 정의합니다. 
• v : 노드 집합 V에 속하는 한 개의 노드 입니다. 
• N(v) : 노드 v의 이웃 노드들을 뜻합니다. 

여기서 노드 피쳐란 소셜 네트워크에서는 유저 프로필이나 이미지가 될 수 있고, 바이오 네트워크에서는 유전의 표현 등이 될 수 있습니다. 만약에 노드 피쳐가 없을 경우에는 단순히 one-hot으로 나타내거나 노드의 degree를 사용할 수도 있다고 하네요!

 

나이브한 접근방법

노드와 관계 matrix에 대해서는 위에서 다 정의가 되었습니다. 그렇다면 이 정보를 어떻게 신경망을 통과시켜야할까요?

 

일반적으로 우리가 생각할 수 있는 방법은 아래와 같습니다. 

단순히 노드 피쳐와 관계 피쳐를 하나의 피쳐로 concat한 뒤에 신경망의 입력으로 넣는 것입니다. 

 

정말 간단한 개념이지만, 이 방법에는 몇 가지 문제점이 존재합니다. 

 

첫 번째는 파라미터 문제인데요. 위의 입력을 받아들이려면, 적어도 노드 수 이상의 파라미터가(노드 수 + 노드의 피쳐 차원 수) 필요합니다. 파라미터가 너무 많아지면 계산량이 클 뿐만 아니라 과적합될 확률도 매우 커집니다. 

 

두 번째는 다른 사이즈를 가지는 그래프에는 적용할 수 없다는 점입니다. 위의 예시를 보면 신경망에 총 5개의 노드를 가지는 입력을 넣어줍니다. 만약 총 10개의 노드를 가지는 입력을 넣어주려고하면 신경망의 파라미터 수가 맞지 않게되죠. 따라서 아예 적용할 수가 없습니다. 

 

세 번째는 노드 순서에 매우 민감하다는 점입니다. 위에서 보시는것처럼 입력 피쳐는 노드가 순서대로 붙어있습니다. 만약 A와 E노드의 순서를 바꾼다면 피쳐가 굉장히 많이 달라지겠죠. 

 

그래서 생각한 것이 바로 Convolutional Networks!

 

Convolutional Networks

일반적으로 Convolutional Network는 이미지에서 주로 사용하죠. 

Convolutional layer의 작동 과정은 위와 같습니다. window가 이미지의 grid를 옮겨다니면서 그 정보들을 하나로 압축해주죠!

따라서 이미지의 정보가 압축된 새로운 matrix가 만들어집니다. 

 

하지만 그래프에 적용하기는 쉽지 않은데요. 

이미지는 grid형태의 데이터이기 때문에 window에 동일하게 각 데이터들이 들어오고, 압축할 수가 있었습니다. 하지만 그래프는 정해진 데이터 형식이 없죠. 따라서 위의 그림처럼 하나의 widnow에 노드 3개가 들어올 때도 있고, 7개의 노드가 들어올 때도 있습니다. 

 

그럼 어떻게 그래프 데이터에 이 개념을 적용해야할까요?

 

GNN은 Convolutional layer의 "압축"에 중점을 두었습니다. 

공통점이 보이시나요? 이미지에서는 window에 들어오는 모든 정보들을 하나로 압축했고, 압축된 데이터로 새로운 matrix를 얻었죠. 

그래프도 이와 비슷하게 주변에 있는 노드들의 정보를 압축해서 새로운 정보를 얻겠다! 라는겁니다. 

 

그래서 탄생한 것이 바로 Graph Convolutional Network입니다.

 

Graph Convolutional Network(GNN)

일반적으로 이미지에서 딥러닝 모델은 Convolutional layer, Pooling layer를 거치고, 텍스트는 LSTM등의 모델을 거칩니다. 그래프에서도그래프에 '특화된' 두 가지 과정을 거치는데요. 바로 노드별 계산 그래프 생성, 노드별  계산 그래프 전파입니다.

 

노드별 계산 그래프 생성

챕터 5에서 message passing에 대해서 배웠었죠. 나랑 직접 연결되어있는 노드가 아니더라도, 건너 건너서 메세지를 받을 수 있다는 것인데요. GNN에서도 그 개념을 사용합니다.

다음과 같이 입력 그래프가 있을때, A 노드에 대한 피쳐를 알고싶다고 가정합시다. 이 경우 A와 연결되어있는 B, C, D에 대한 정보를 받을 수 있고, 각각 B, C, D는 그 노드에 연결되어있는 (A,C), (A,E,F), (A)에 대한 정보를 받을 수 있습니다. 이렇게 타고타고 정보를 받게 되는데, 이것을 계산 그래프라고합니다. 

 

즉, 어떤 노드가 기준이냐에 따라서 정보를 받아야하는 노드가 다 달라지는 것이죠.

각 노드에 대해서 계산 그래프를 생각해보면 위와 같이 그려질 수 있겠네요! 위의 계산 그래프를 보면 노드별 그래프가 모두 다릅니다. 

 

노드별  계산 그래프 전파

말 그대로 위에서 그려진 계산 그래프내에서 노드 정보를 보내주고, 취합하여 노드를 업데이트하는 과정입니다. 

여기서 layer-0은 초기 노드의 임베딩 벡터를 뜻하고, layer-k는 K hop 떨어진 곳에서 받은 정보를 뜻합니다. 예를 들어 layer-2는 '현재 기준 노드에서 2hop 떨어진 노드로부터 정보를 받아온다'라고할 수 있습니다.

 

그렇다면 노드 정보를 어떻게 취합해야할까요?

아까도 말했듯이 그래프 데이터는 순서가 없는 데이터입니다. 따라서 노드 순서가 어떻게 들어오든 상관 없는 방법이여야합니다. 

 

여기서 가장 간단한 방법은 들어오는 노드 값의 평균을 구해주고, 신경망을 거치는 것입니다.

이를 수식으로 표현하면 아래와 같습니다. 

해석을 하자면 노드 v의 l+1번째 임베딩 값(h_v^(l+1))은 현재 노드에 학습 파라미터 B를 곱한 값과 주변 노드의 평균에 학습 파라미터 W를 곱한 값을 활성화 함수를 통과시켜줍니다. 

 

학습에 사용되는 파라미터는 B_l, W_l입니다. 또한 loss값을 구하고 SGD를 실행하는 등 모든 과정은 기존 딥러닝과 같습니다. 

 

이제 위의 수식을 실제로 적용하기 위해 matrix로 바꿔보겠습니다. 

l번째 레이어에서 모든 노드를 하나의 matrix로 나타낸 행렬은 H^l입니다. 위의 우측 그림에서 보시는 것 처럼 하나의 노드 벡터는 행렬의 한 행입니다. 

 

이후 adjacency matrix인 A와 곱해주면 기준이 되는 노드와 연결된 모든 노드의 합을 구할 수 있습니다. 연결성이 있는 노드간의 관계는 1이고, 없으면 0이되기 때문에, 연결성 없는 값은 0과 곱해져 버려지고, 있는 값은 1과 곱해져 살아남기 때문에, 연결성 있는 노드들을 합한거라고 할 수 있습니다. 

 

자 이제 남은 과정은 평균을 구할 수 있게 노드 수로 나눠주는 것인데요. 이부분은 D라는 matrix를 정의해주시면 됩니다. D는 대각성분이 v 노드의 degree로 설정해주시면 되고, 이 matrix의 역행렬을 구하면 각 degree의 역수가 취해지기 때문에, 이 행렬을 곱해준다면 우리가 원하는 받은 노드 값들의 평균을 구할 수 있습니다. 

따라서 다음과 같이 수식을 행렬식으로 바꿔줄 수 있겠네요. 

 

학습

이제 수식을 모두 정의했으니 학습을 해볼까요?

학습은 지도학습과 비지도학습으로 나뉩니다. 

 

여기서 z_v는 최종적으로 나온 H라고 생각하시면 됩니다.

 

1. 지도학습

z_v를 최종 예측 함수 f에 넣고 라벨을 얻습니다.

여기서 라벨은 y이고, L은 loss함수입니다. loss함수를 최소화하는거는 다른 모델들과 같습니다. 

loss를 좀더 풀어쓰면 다음과 같이 얻을 수 있습니다.

 

2. 비지도 학습

비지도학습은 말 그대로 라벨이 없는 경우 사용하는데요. 노드의 라벨 대신에 그래프 구조를 학습합니다. 

 

이 말이 무슨 말이냐!!

 

초기 포스팅에서 그래프 임베딩의 목적을 기억하시나요? 

'실제 그래프에서 유사한 노드는 임베딩 공간에서도 유사도가 높다'라는 것을 목적으로 했었죠. 여기서는 이 목적과 동일하게 학습합니다. 

DEC는 decoder로 기존과 동일한 역할을 합니다. y_u,v는 노드 u와 v가 유사도가 높으면 1입니다. CE는 cross-entropy입니다. 

 

GNN의 전체적인 디자인

마지막으로 전체적으로 어떻게 디자인되는지 한번 정리하고 마무리하겠습니다. 

 

노드 정보를 취합하기 위한 aggregation function을 먼저 정의해주셔야하고, 이 예측값이 맞는지 계산해줄 loss function을 정의해주셔야합니다. 

이후 노드 집합을 배치로 학습합니다. 

마지막으로 필요한 노드에 대해 임베딩을 생성하면 됩니다. 

 

정리하자면, 

1. aggregation function 정의

2. loss function 정의

3. 노드의 집합을 배치를 통해 학습

4. 필요한 노드 임베딩 생성

이 과정을 거쳐가며 사용됩니다.

이 때, 학습 파라미터인 W, B는 공유가됩니다. 이 덕분에 학습에 사용되지 않았던 노드들도 임베딩시켜줄 수 있습니다.(Inductive Capability)