해당 포스팅은 네이버 부스트캠프 AI Tech 학습 정리 자료임을 알려드립니다.
1. 강의 정리
신기정 교수님 - 그래프 신경망이란 무엇일까? (기본)
1) 귀납식 정점 표현
출력으로 임베딩 자체를 얻는 변환식 임베딩 방법에 대해서 이미 배웠습니다. 하지만, 이 방법은 학습이 진행된 이후에 추가된 정점에 대해서는 임베딩을 얻을 수 없고, 모든 정점에 대해서 임베딩을 미리 계산해서 저장해놔야 합니다. 또 정점이 부가 정보를 가진 경우에 이를 활용하기 어렵다는 한계가 있습니다. 그래서 이번에는 출력으로 인코더를 얻는 귀납식 임베딩 방법에 대해서 알아보고자 합니다.
귀납식 임베딩 방법은 앞에서 언급했던 변환식 임베딩 방법의 한계를 모두 해결합니다. 그래프 신경망(Graph Neural Network)은 대표적인 귀납식 임베딩 방법입니다.
2) 그래프 신경망 기본
그래프 신경망은 그래프와 정점의 속성 정보를 입력으로 받습니다. 그래프의 인접행렬을 $A$라고 합시다. 여기서의 인접 행렬 $A$는 $|V| \times |V|$의 이진 행렬입니다. 또한 각 정점 $u$의 속성 벡터를 $X_{u}$, 이 속성 벡터는 $m$차원 벡터이고, $m$은 속성의 수를 의미합니다. 예를 들어, 정점의 속성은 SNS에서 사용자의 지역, 성별, 연령 등이 해당될 수 있고, 논문 인용 그래프에서는 논문에 사용된 키워드에 대한 원-핫 벡터가 해당될 수 있습니다. PageRank 등의 정점 중심성, 군집계수 등도 정점의 속성이 될 수 있습니다.
그래프 신경망은 이웃 정점들의 정보를 집계하는 과정을 반복하여 임베딩을 얻습니다. 위의 그림에서는 대상 정점의 임베딩을 얻기 위해 이웃들 그리고 이웃의 이웃들의 정보를 집계합니다. $A$라는 대상 정점을 얻기 위해 1번 층에는 대상 정점과 인접한 $B$,$C$,$D$ 정점에 대한 정보가 필요하고, 또 이 정점들과 인접한 이웃들의 정보를 한번 더 구하는 과정이 포함되어 있습니다. 우측에 있는 구조를 계산 그래프라고 합니다. 이때, 모든 층 별 집계함수는 대상 정점에 관계없이 동일한 것을 공유합니다. 다만, 1층 집계 함수와 0층 집계 함수는 다릅니다. 0번층에 있는 $X_{A}$는 앞에서 언급했던 것처럼 해당 정점에서의 속성 정보입니다. 하지만, 여기에서 보면 input으로 들어가는 것의 개수가 다른 것을 확인하실 수 있습니다. 이렇게 상이한 구조의 계산 그래프를 처리하기 위해서는 어떤 형태의 집계 함수가 필요할까요?
이웃들의 정보의 평균을 계산해서 신경망에 적용하는 방법을 사용합니다. 이 과정을 표현해보면 아래와 같은 수식을 얻을 수 있습니다.
$$ h_{v}^{0} = x_{v}, h_{v}^{k} = \sigma(W_{k}\sum_{u \in N(v)} \frac{h_{u}^{k-1}}{|N(v)|} + B_{k}h_{v}^{k-1}), \forall k > 0 $$
$h_{v}^{0}$ 는 0번 층에서 정점 $v$의 임베딩으로 정점 $v$의 속성 벡터로 초기화 합니다. $h_{v}^{k}$는 k번째 층에서 정점 $v$의 임베딩을 의미합니다. $\sigma$는 비선형 함수로 Relu, tanh 등을 의미합니다. $W_{k}$와 $B_{k}$는 신경망으로 학습하는 함수이며, $|N(v)|$는 정점 $v$의 이웃들의 개수를 의미하고, 합계 항은 이전 층에서 이웃들의 임베딩에 대한 평균을 계산한 항이 됩니다. 이런 방식으로 학습을 한 뒤에 마지막 $K$ 층에서의 출력 임베딩은 $h_{v}^{K}$가 됩니다.
그래프 신경망에서 인접성을 기반으로 유사도를 정의한다면 손실함수는 다음과 같습니다.
$$ \mathcal{L} = \sum_{(u,v) \in V \times V} ||z_{u}^{T}z_{v} - A_{u,v}||^2$$
각 임베딩 공간에서의 유사도와 그래프에서의 유사도를 비교해서 모든 정점 쌍에 대해 합산한 값으로 손실함수를 정의합니다.
그래프 신경망은 후속 과제(Downstream Task)의 손실함수를 이용한 종단종(End-to-End) 학습도 가능합니다. 예를 들어, 정점 분류가 최종 후속 과제라고 한다면, 그래프 신경망을 이용해서 정점의 임베딩을 얻고, 이를 분류기의 입력으로 사용하여 각 정점의 유형을 분류하는 방식으로 진행할 수 있습니다. 이러한 경우에는 분류기의 손실함수를 전체 프로세스의 손실함수로 사용해서 종단종(End-to-End) 학습을 할 수 있습니다.
$$ \mathcal{L} = \sum_{v \in V} y_{v} log( \sigma (z_{v}^{T} \theta )) + (1- y_{v}) log(1- \sigma ( z_{v}^{T} \theta )) $$
여기서 $y_v$는 정점의 실제 유형으로 0 or 1 값을 가지고, $z_u$는 정점의 임베딩을 뜻합니다. $\theta$는 분류기의 학습 변수입니다. 그래프 신경망의 종단종 학습을 통한 분류는 변환적 정점 임베딩 이후에 별도의 분류기를 학습하는 것보다 정확도가 대체로 높은 결과를 얻을 수 있습니다.
그래프 신경망으로 학습할 때에는 학습에 사용할 대상 정점을 결정하여 학습 데이터를 구성합니다. 이때, 모든 정점을 학습에 사용하지 않아도 됩니다. 이 방법에서도 기본 신경망들과 동일하게 오차역전파(Backpropagation)을 통해 손실함수를 최소화합니다. 이렇게 학습된 신경망은 학습에 사용되지 않은 정점의 임베딩을 구할 수 있으며, 추가되는 정점에 대해서도 임베딩을 구할 수 있습니다.
3) 그래프 신경망 변형
그래프 신경망에서는 앞에서 소개한 집계 함수말고도 다양한 형태의 집계 함수를 사용할 수 있습니다. 그 중 하나는 그래프 합성곱 신경망(Graph Convolutional Network, GCN)입니다. 아래는 GCN의 집계함수 형태입니다.
GraphSAGE의 집계함수는 이웃들의 임베딩을 AGG 함수를 이용해서 합친 후, 자신의 임베딩과 연결(Concatenation)하는 점이 독특합니다. 아래는 GraphSAGE에서의 집계 함수입니다. AGG 함수에는 Mean, Pool, LSTM 등 다양한 것들을 사용할 수 있습니다.
4) 합성곱 신경망과의 비교
합성공 신경망과 그래프 신경망은 모두 이웃의 정보를 집계하는 과정을 반복합니다. 구체적으로, 합성곱 신경망은 이웃 픽셀의 정보를 집계하는 과정을 반복합니다. 합성곱 신경망은 이웃의 수가 균일하지만, 그래프 신경망에서는 정점 별로 집계하는 이웃의 수가 다릅니다. 그래프 인접 행렬에 대해 합성곱 신경망을 적용하면 효과적일 수 있을까요? 효과적이지 않습니다. 왜냐하면, 보통 이미지의 픽셀 정보는 인접 픽셀이 유용한 정보를 담고 있을 가능성이 높습니다. 하지만, 인접 행렬에서 행과 열의 순서는 임의로 결정되는 경우가 많기 때문에 그래프의 인접 행렬에서의 인접 원소는 제한된 정보를 가집니다.
신기정 교수님 - 그래프 신경망이란 무엇일까? (심화)
1) 그래프 신경망에서의 어텐션
그래프 어텐션 신경망(Graph Attention Network, GAT)에서는 가중치 자체도 학습합니다. 실제 그래프에서는 이웃 별로 미치는 영향이 다를 수 있기 때문입니다. 가중치를 학습하기 위해서 셀프-어텐션(Self-Attention)이 사용됩니다. 각 층에서 정점 $i$로부터 이웃 $j$로의 가중치 $\alpha_{ij}$는 세 단계를 통해 계산합니다.
$$ 1. \tilde{h_{i}} = h_{i} W, \tilde{h_{j}} = h_{j}W, \, 2. e_{ij} = a^{T}[concat(\tilde{h_{i}}, \tilde{h_{j}})], \, 3. \alpha_{ij} = softmax_{j}(e_{ij}) = \frac{exp(e_{ij})}{\sum_{k \in \mathbb{N_i}}exp(e_{ik})}$$
-
해당 층의 정점 $i$의 임베딩 $h_i$에 신경망 $W$를 곱해 새로운 임베딩을 얻습니다.
-
정점 $i$와 정점 $j$의 새로운 임베딩을 연결한 후, 어텐션 계수 $a$를 내적합니다. 어텐션 계수 $a$는 모든 정점이 공유하는 학습 변수입니다.
-
2의 결과에 softmax를 적용합니다.
또한 여러 개의 어텐션을 동시에 학습한 뒤, 결과를 연결하는 멀티헤드 어텐션도 적용 가능합니다. 이렇게 어텐션을 적용한 신경망은 적용하지 않은 것보다 정점 분류의 정확도에서 좋은 결과를 나타내는 것을 확인할 수 있습니다.
2) 그래프 표현 학습과 그래프 풀링
지금까지는 정점 표현 학습에 대해 알아봤다면, 이번에 알아볼 그래프 표현 학습은 그래프 전체를 벡터의 형태로 표현하는 것입니다. 그래프 임베딩은 벡터의 형태로 표현된 그래프 자체를 의미하며 그래프 분류 등에 활용됩니다. 예를 들어, 그래프 형태로 표현된 화합물의 분자 구조로부터 특성을 예측하는 것이 포함됩니다.
그래프 풀링(Graph Pooling)은 정점 임베딩들로부터 그래프 임베딩을 얻는 과정입니다. 평균 등 단순한 방법보다 그래프의 구조를 고려한 방법을 사용할 경우 그래프 분류 등의 후속 과제에서 더 높은 성능을 얻을 수 있습니다.
위의 그림은 미분가능한 풀링으로 군집 구조를 활용해서 임베딩을 계층적으로 집계합니다.(강의 한번만 다시 듣기)
3) 지나친 획일화 문제
지나친 획일화(Over-smoothing) 문제는 그래프 신경망의 층의 수가 증가하면서 정점의 임베딩이 서로 유사해지는 현상을 의미합니다. 지나친 획일화 문제는 작은 세상 효과와 관련이 있습니다. 적은 수의 층으로도 다수의 정점에 의해 영향을 받게 됩니다.
위의 그림에서도 볼 수 있듯이 layer가 깊어질수록 정점의 임베딩이 서로 유사해지는 것을 확인할 수 있습니다. 이러한 현상으로 인해 그래프 신경망의 층의 수를 늘렸을 때, 후속 과제에서의 정확도가 감소하는 현상이 발견되었습니다. 아래 그래프에서도 볼 수 있듯이 층의 수가 2~3정도일 때의 정확도가 가장 높습니다.
이를 보완하기 위해서 잔차항(Residual)을 넣어서 이전 층의 임베딩을 한 번 더 더해주는 방법을 썼으나, 효과는 미미했습니다. 그래서 문제를 해결하기 위해 JK 네트워크(Jumping Knowledge Network)와 APPNP방법이 사용되었습니다. JK 네트워크는 마지막 층의 임베딩 뿐 아니라, 모든 층의 임베딩을 함께 사용합니다.
위의 그림처럼 각 층에서 만들어진 임베딩을 맨 마지막에 다 활용하는 방법입니다. APPNP는 0번째 층을 제외하고는 신경망 없이 집계 함수를 단순화했습니다. (추가 공부가 필요)
APPNP의 경우, 층의 수 증가에 따른 정확도 감소 효과가 없는 것을 확인할 수 있었습니다.
4) 그래프 데이터의 증강
데이터 증강(Data Augmentation)은 다양한 기계학습 문제에서 효과적입니다. 그래프에도 누락되거나 부정확한 간선이 있을 수 있고, 데이터 증강을 통해 보완할 수 있습니다. 임의 보행을 통해 정점간 유사도를 계산하고, 유사도가 높은 정점 간의 간선을 추가하는 방법이 제안되었습니다. 아래 그림은 데이터 증강하는 과정을 표현한 그림입니다.(좀 더 공부가 필요!)
그래프 데이터 증강의 결과로 정점 분류의 정확도가 개선되는 것을 확인할 수 있었습니다.
