BoostCamp AI Tech - Day25

1. 그래프 신경망(GNN,Graph Neural Network)

 

그래프에 있는 노드 사이의 관계를 모델링하고, 그에 대한 representation을 생성하는 것

 

1.1 그래프 신경망 구조

 

1) 그래프 신경망은 그래프와 정점의 속성 정보를 입력으로 받는다.

 

그래프의 인접 행렬을 A라고 하자. 이 때, 인접 행렬 A 은 |𝑉| × |𝑉|의 이진 행렬이 된다.

각 정점 𝑢의 속성(Attribute) 벡터를 𝑋𝑢라고 하면, 정점 속성 벡터 𝑋𝑢는 𝑚차원 벡터이고, 𝑚은 속성의 수를 의미한다.

 

정점의 속성의 예시는 다음과 같다.

- 온라인 소셜 네트워크에서 사용자의 지역, 성별, 연령, 프로필 사진 등

- 논문 인용 그래프에서 논문에 사용된 키워드에 대한 원-핫 벡터

- PageRank 등의 정점 중심성, 군집 계수(Clustering Coefficient) 등

 

2) 그래프 신경망은 이웃 정점들의 정보를 집계하는 과정을 반복하여 임베딩을 얻는다.

 

다음 그림과 같이 대상 정점의 임베딩을 얻기 위해 이웃들 그리고 이웃의 이웃들의 정보를 집계한다.

 

이 때, 각 집계 단계를 층(Layer)이라고 부르고, 각 층마다 임베딩을 얻는다. 

 

(출처 : Boost Camp AI Tech)

각 정점별로 계산 그래프로 나타낸 것

서로 다른 대상 정점 간에도 층 별 집계 함수는 공유한다.

 

그러나, 위의 정점 A,B 처럼 서로 다른 구조의 계산 그래프(입력의 개수가 다른 것 등)를 처리하기 위해서는 어떤 형태의 집계함수가 필요한 지 알아볼것이다.

 

집계 함수는 이웃 정보들의 평균을 계산하고 신경망에 적용하는 단계를 거친다. 

이웃 정보들의 평균을 계산한다는 것은 각 이웃들의 정보(입력)의 차원을 동일하게 적용한다는 뜻이다. 적용한 것으로 신경망에 적용한다.

 

회색 사각형(집계함수)의 자세한 식은 다음과 같다.

그 다음에 마지막 층에서의 정점(Node) 별 임베딩이 해당 정점의 출력 임베딩이다.

 

1.2 그래프 신경망의 학습

 

GNN의 학습변수(Trainable Parameter)는 층 별 신경망의 가중치이다.

 

먼저 손실함수를 결정한다. 정점간 거리를 “보존”하는 것을 목표로 할 수 있습니다. 변환식 정점 임베딩에서처럼 그래프에서의 정점간 거리를 “보존”하는 것을 목표로 할 수 있을 것이다. 만약, 인접성을 기반으로 유사도를 정의한다면, 손실 함수는 다음과 같다.

 

후속 과제(Downstream Task)의 손실함수를 이용한 종단종(End-to-End) 학습도 가능하다.

이 경우 분류기(Classfier)의 손실함수, 예를 들어, 교차 엔트로피(Cross Entropy)를, 전체 프로세스의 손실함수로 사용하여 종단종(End-to-End) 학습을 할 수 있다.

 

다음 그림은 그래프가 주어졌을 때, 이것을 정점 표현 학습을 하고 분류를 하는 것이다. 중요한 것은 정점 분류(후속 과제)에 손실함수를 써서 분류만 하는 것이 아니라, GNN에 역전파를 하는 것이다.

 

그래프 신경망의 종단종(End-to-End) 학습을 통한 분류는, 변환적 정점 임베딩 이후에 별도의 분류기를 학습하는 것보다 정확도가 대체로 높다. 아래 표는 다양한 데이터에서의 정점 분류의 정확도(Accuracy)이다.

그 다음, 학습에 사용할 대상 정점을 결정하여 학습 데이터를 구성한다. 선택한 대상 정점들에 대한 계산 그래프를 구성하면 된다.

마지막으로 오차역전파(Backpropagation)을 통해 손실함수를 최소화하고, 신경망의 학습 변수들을 학습한다.

 

1.3 그래프 신경망의 활용

 

학습된 신경망을 적용하여, 학습에 사용되지 않은 정점의 임베딩을 얻을 수 있다.

 

이와 마찬가지로, 학습 이후에 추가된 정점의 임베딩도 얻을 수 있다. 온라인 소셜네트워크 등 많은 실제 그래프들은 시간에 따라서 변화한다.

 

학습된 그래프 신경망을, 새로운 그래프에 적용할 수도 있다. 예를 들어, A종의 단백질 상호 작용 그래프에서 학습한 그래프 신경망을 B종의 단백질 상호작용 그래프에 적용할 수 있다.

 

2. 그래프 신경망의 변형

 

2.1 그래프 합성곱 신경망(GCN, Graph Convolutional Network)

 

위 그림(GNN)의 집계함수(회색 사각형) 부분을 다르게 사용할 수 있다. GCN의 집계함 수는 다음과 같다.

 

기존 집계 함수와 비교

2.2 GraphSAGE

 

GraphSAGE의 집계 함수는 이웃들으 임베딩을 AGG함수(즉, Aggregation)를 이용해 합친 후, 자신의 임베딩과 연결(Concatenation)하는 것이다.

 

이 때, AGG함수는 평균, 풀링, LSTM 등이 사용될 수 있다.

 

3. 합성곱 신경망(CNN)과 비교

 

3.1 합성곱 신경망과 그래프 신경망의 유사한 점

 

합성곱 신경망과 그래프 신경망은 모두 이웃의 정보를 집계하는 과정을 반복한다. 정확히는 이웃 픽셀의 정보를 집계하는 과정을 반복한다.

 

3.2 합성곱 신경망과 그래프 신경망의 차이점

 

합성곱 신경망에서는 이웃의 수가 균일하지만, 그래프 신경망에서는 그렇지 않다. 그래프 신경망에서는 정점 별로 집계하는 이웃의 수가 다르다.

 

또한, 그래프의 인접 행렬에 CNN을 적용하는 것이 바람직하지 않다. 그래프에는 GNN을 적용하여야한다. 합성곱 신경망이 주로 쓰이는 이미지에서는 인접 픽셀이 유용한 정보를 담고 있을 가능성이 높다. 하지만, 그래프의 인접 행렬에서의 인접 원소는 제한된 정보를 가집니다 특히나, 인접 행렬의 행과 열의 순서는 임의로 결정되는 경우가 많기 때문이다.

 

4. 그래프 신경망에서의 어텐션(Attention)

 

4.1 기본 그래프 신경망의 한계

 

기본 그래프 신경망에서는 이웃들의 정보를 동일한 가중치로 평균을 낸다. GNN 역시 단순히 연결성을 고려하여 가중치로 평균값을 낸다.

그러나, 그래프의 정점들은 서로 이웃하지만, 그것이 대등하게 연결되었다는 보장이 없을 것이다. 예를 들면, 본인에게는 아주 친한 친구가 있을 것이고 덜 친한 친구가 있을 것이다. 따라서, 이를 극복한 것이 그래프 어텐션 신경망(Graph Attention Network, ,GAT)이다. 이는 가중치 자체도 학습을 사용한다. 실제 그래프에서는 이웃 별로 미치는 영향이 다를 수 있기 때문이다. 아래 오른쪽 그림처러 서로 다른 가중치를 학습하기 위해서 셀프-어텐션(Self-Attention)이 사용된다.

 

각 층에서 정점 𝑖로부터 이웃 𝑗로의 가중치 $a_{ij}$는 세 단계를 통해 계산한다.

 

1) 해당 층의 정점 𝑖의 임베딩 𝐡𝑖에 신경망 𝑾를 곱해 새로운 임베딩을 얻는다.

2) 정점 𝑖와 정점 𝑗의 새로운 임베딩을 연결한 후, 어텐션 계수 𝒂를 내적합니다 어텐션 계수 𝒂는 모든 정점이 공유하는 학습 변수이다.

$ e_{ij} = a^T[CONCAT(\tilde{h_i},\tilde{h_j})] $

3) 2)의 결과에 소프트맥스(Softmax)를 적용한다

여러 개의 어텐션을 동시에 학습한 뒤, 결과를 연결하여 사용하는 데, 이를 멀티헤드 어텐션(Multi-head Attention)이라고 부른다.

어텐션의 결과 정점 분류의 정확도(Accuracy)가 향상되는 것을 확인할 수 있었다.

5. 그래프 표현 학습과 그래프 풀링

 

5.1 그래프 표현 학습

 

그래프 표현 학습, 혹은 그래프 임베딩이란 그래프 전체를 벡터의 형태로 표현하는 것이다. 개별 정점을 벡터의 형태로 표현하는 정점 표현 학습과 구분된다. 그래프 임베딩은 벡터의 형태로 표현된 그래프 자체를 의미하기도 한다. 그래프 임베딩은 그래프 분류 등에 활용된다. 예를 들면, 그래프 형태로 표현된 화합물의 분자 구조로부터 특성을 예측하는 것이 다.

 

5.2 그래프 풀링

 

평균 등 단순한 방법보다 그래프의 구조를 고려한 방법을 사용할 경우 그래프 분류 등의 후속 과제에서 더 높은 성능을 얻는 것으로 알려져 있다. 아래 그림의 미분가능한 풀링(Differentiable Pooling, DiffPool)은 군집 구조를 활용 임베딩을 계층적으로 집계한다. 처음에 GNN을 사용하여 임베딩을 얻고, 각 군집별로 임베딩을 합산한다. 합산된 것을 다시 군집화 시켜 합산하고 최종적으로 그래프를 위한 임베딩을 얻어 Classfier를 통과하여 분류한다.

 

6. 지나친 획일화 문제

 

6.1 지나친 획일화 문제

 

지나친 획일화(Over-smoothing) 문제란 그래프 신경망의 층의 수가 증가하면서 정점의 임베딩이 서로 유사해지는 현상을 의미한다. 지나친 획일화 문제는 작은 세상 효과와 관련이 있다. 적은 수의 층으로도 다수의 정점에 의해 영향을 받게 된다.

 

지나친 획일화의 결과로 그래프 신경망의 층의 수를 늘렸을 때, 후속 과제에서의 정확도가 감소하는 현상이 발견되었다. 아래 그림처럼 그래프 신경망의 층이 2개 혹은 3개 일 때 정확도가 가장 높다.

잔차항(Residual)을 넣는 것, 즉 이전 층의 임베딩을 한 번 더 더해주는 것 만으로는 효과가 제한적이다.

획일화 문제에 대한 대응으로 JK 네트워크(Jumping Knowledge Network)는 마지막 층의 임베딩 뿐 아니라, 모든 층의 임베딩을 함께 사용한다.

JK 네트워크

APPNP는 0번째 층을 제외하고는 신경망 없이 집계 함수를 단순화한다.

APPNP

APPNP의 경우, 층의 수 증가에 따른 정확도 감소 효과가 없는 것을 확인했다. 후속 과제로는 정점 분류가 사용되었다.

5. 그래프 데이터의 증강

 

데이터 증강(Data Augmentation)은 다양한 기계학습 문제에서 효과적이다 23 그래프에도 누락되거나 부정확한 간선이 있을 수 있고, 데이터 증강을 통해 보완할 수 있다 임의 보행을 통해 정점간 유사도를 계산하고, 유사도가 높은 정점 간의 간선을 추가하는 방법이 제안되었다.

(출처 : BoostCamp AI Tech)

그래프 데이터 증강의 결과 정점 분류의 정확도가 개선되는 것을 확인했다. 아래 그림의 HEAT과 PPR은 제안된 그래프 데이터 증강 기법을 의미한다.