[Study]Chapter 19. GNNs for Science

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

I. GNN pre-training

GNN은 아래의 반복적으로 이웃의 정보를 종합하여 노드 임베딩을 얻고, 노드 임베딩을 풀링하여 글래프 임베딩을 얻는 두 단계를 통해 전체 그래프에 대한 임베딩을 얻는다.

Figure 1 : 분자 그래프에서 그래프 임베딩을 얻기 위한 과정

ML을 위와 같이 과학 분야에 적용하는 데의 기본적인 두 가지 문제가 존재합니다.

1. scarcity of labeled data
2. out-of-distribution prediction

(1)은 라벨이 있는 data를 얻는 것은 많은 비용이 들어서 작은 학습 데이터로 과적합시키는 경우로 딥러닝 모델이 학습용으로 라벨링된 데이터 개수보다 많은 파라미터를 가지게 되어 작은 라벨 데이터에 과적화되는 경향이고, (2)는 테스트 예제가 학습 데이터와 매우 다른 경우 추론이 빈약해지는 문제를 뜻합니다.이러한 딥러닝 모델은 데이터셋과 밀접하게 관련되어 예측을 하여 엉성한 추론을 하게 됩니다. 한 예로 북극곰과 갈색곰의 이미지를 분류하는 문제에서 대부분의 북극곰의 배경은 눈이 배경이 되어 모델이 동물 자체보다 배경에 대한 학습을 하여 예측을 하는 경우 초원에 있는 북극곰은 분류하지 못하는 문제가 발생합니다,

1. injecting domain knowledge

위의(2)번 문제의 예측 성능이 제한된 데이터에서도 향상시키는 것을 목표로 주된 아이디어는 도메인 지식을 모델이 (1)번 문제를 가지는 작업의 학습 전에 주입하는 것입니다. 모델이 데이터에 대한 도메인 지식을 학습 전에 알고 있다면 모델은 특정 작업에 라벨된 데이터 없이 일반화가 잘 될 것이고, 더 좋은 추정을 하는데 필수적인 패턴을 추출할 것입니다.

효과적인 방법으로 pre-training이 존재합니다.

모델을 관련된 작업에 데이터가 풍부한 사전 학습을 시키면 모델의 파라미터는 도메인 지식을 포함하고 있어 downstream-task에서 사전학습된 파라미터에서 시작하여 파인튜닝하게 됩니다.

Figure 2 : 사전학습은 NLP나 CV분야에서 이러한 사전학습은 위의 (1), (2) 문제에서 매우 성공적인 솔루션이 됩니다.

이제 GNN에 사전학습을 고려하여 GNN 사전학습 전략과 시스템적인 투자를 만들어 봅시다.

1. GNN에서 사전학습이 얼마나 효과적인가?
2. 효과적인 사전학습 전략은 무엇인가?

Figure 1 처럼 분자 특성 예측에서 간단한 전략으로 다양한 label에 대한 사전학습을 하고, 적은 label을 가지는 downstream-task에 적용하는 방법이 있습니다.

Figure 3 : GNN에 사전학습을 적용시키는 단순한 방법으로 관련된 label을 멀티 태스크에 사전학습을 진행시키는 것.

이러한 방법은 Figure 4 처럼 다운 스트림 작업에서 negative transfer처럼 제한적인 성능 향상이 일어난다.

Figure 4 : (좌)노드와 그래프 임베딩을 사전학습 시킨 경우 (우)노드와 그래프 임베딩을 각각 사전학습 시킨 경우

노드와 그래프 임베딩을 사전학습 시키면 GNN은 지역과 글로벌 구조의 도메인-특정 지식을 Figure 1에서 가운데에서 지역 이웃 구조를 오른쪽에서는 글로벌 구조를 수집할 수 있습니다.

Figure 5 : 사전학습 방법의 목적들.

• Attribute masking

  노드 속성을 mask하는 방법으로 GNN을 통해 노드 임베딩을 생성하는데 사용됩니다. 이러한 임베딩으로 가려진 속성을 예측하는데 사용하려면 GNN은 도메인 지식의 학습이 강제됩니다.

• Context prediction

  각 그래프에서 한개의 중심 노드를 뽑고 이웃과 context 그래프를 추출합니다. GNN을 사용하여 이웃과 context 그래프를 벡터로 인코딩하여 true/false(이웃, context) 쌍에대한 내적곱을 최대화/최소화 합니다.

  유사한 context로 둘러싸여진 부분그래프는 의미론적으로 유사하게 된다는 뜻으로 NLP에서는 word2vec에 사용되는 분포 가설이라고 합니다.

• Supervised Attribute prediction

  많은 연관된 라벨에서 멀티태스크로 지도 학습시킨다.

Figure 6 : 사전학습 전략

이러한 전략의 결과로 negative transfer를 피할 수 있고, 상당한 성능 향상을 보입니다. 따라서, 사전학습한 다른 GNN 모델들의 비교를 했을때 GIN이 사전학습에서 가장 많은 이득을 보았고 도메인지식을 더 잘 학습했습니다.

II. Hyperbolic Graph Embeddings

이전 까지는 유클리디안 임베딩 차원에서 그래프 표현 학습에 집중을 했습니다. 그러나 이러한 차원에서는 트리 구조나 트리 같은 그래프(작은 서클을 포함하는)에서의 깊이는 노드의 수에 지수적으로 증가해 복잡한 그래프 구조를 파악하지는 못합니다.

grid 형태의 그래프에서는 유클리디안 공간 임베딩이 최적이고, 많은 서클을 가지고 있는 그래프에서 구 모양의 공간 임베딩이 최적입니다.

Figure 7 : 구 모양의 공간 임베딩과 grid형태의 임베딩 공간의 예시

이처럼 계층적이거나 트리 같은 복잡한 그래프들은 하이퍼볼릭 공간으로 임베딩을 해야합니다.

계층적이거나 트리 같은 그래프에서의 쌍곡선 지형은 유클리디안 지형과 평행성 공준\(_{parallel-postulate}\)이라는(5th axiom) 가설로 서로 다릅니다. 즉, 유클리디안 면 지형에서 선과 선에 있지 않은 점이 주어졌을때 점을 통과하는 선과 평행한 선을 그릴 수 있지만 쌍곡선 지형에서는 무한한 개수의 평행하는 라인을 그릴 수 있습니다.

위처럼 쌍곡선 영역의 특별한 속성 때문에 자연적으로 유클리디안 공간에 표현할 수 없습니다. 따라서, 우리는 2가지의 같은 지형 모델을 사용합니다.

Figure 8 : 복잡한 그래프 모델들을 하이퍼볼릭 공간으로 임베딩하는 두가지 지형 모델

• Poincaré Model

  Radius proportional to $\sqrt{K}$, open ball(바운더리를 초과), 각 삼각형은 같은 공간이다.

• Hyperboloid Model(Loprentz Model)

  위의 모델과 비교하여 지수적으로 많은 임베딩 점을 poincare ball 영역에 가깝게 표현할 필요가 있다.

Figure 9 : 계층적인 그래프에서 Poincare embedding의 시각화로 링크 예측과 노드 분류 등의 작업이 존재함.

• Riemannian Manifold

  내적곱(metric space), tangent space(\(\mathbb{R}^n\) manifold의 어느 한 점 x로 근사하는) 두가지를 가지고 있고, 두 함수는 다양한 manifold에서 부드럽게 변합니다.

Geodesic

manifold에서 가장 짧은 통로를 뜻합니다.

Figure 10 : 하이퍼볼릭 포인트 두 점의 거리는 위와 같다.

Hyperbolic space는 Riemannian 매니폴드로 음의 곡률(\(-\frac{1}{K}\))을 가집니다. 이는 K가 무한대로 갈 수록 더 많은 곡률이 생겨 공간이 더 꺾임을 나타냅니다.

이러한 곡률의 영향은 임베딩 영역에 어떠한 영향을 미치는가?

Figure 11 : tangent space는 하이퍼볼로이드 모델 아래에서 표현된다.

하이퍼볼로이드 공간에서의 Geodesic 거리는 유클리디안 공간에서 가장 짧은 통로의 거리와 유사합니다. 따라서, 해당 공간에서의 직선의 곡률이 음수가 될 수록 Geodesic는 안쪽으로 굽고, x와 y의 거리 또한 증가합니다.

Figure 12 : 두 하이퍼볼릭 점 사이의 Geodesic는 안쪽으로 더 굽을 수록 곡률이 음수가 되고, Poincare ball의 반지름이 작아질수록 더 큰 곡률의 결과가 됩니다. 즉, 같은 좌표 사이의 거리는 반지름이 작아질 수록 증가합니다.

탄젠트 영역과 하이퍼볼로이드 모델 사이의 연산자를 아래와 같이 표현합니다.

• Exponential map : 탄젠트 공간(유클리디안)에서 매니폴드로.
• Logarithmic map : Exponential map의 역연산자

Figure 13 : Exp(\(\cdot\))은 탄젠트 공간에서 하이퍼볼릭 영역으로 Log(\(\cdot\))은 그 반대의 경우로 맵핑하는 함수입니다.(\(Norm ||v||_\mathcal{L} = <v,v>_{\mathcal{L}}\))

1. Hyperbolic GNN¹

노드 특성을 유클리디안 공간으로 넣는 것으로 메시지 패싱을 위해 하이퍼볼릭 집계를 수행합니다. GNN의 각 층에서는 그래프의 특성에 맞는 적절한 하이퍼볼릭 공간의 곡률을 선택해야합니다.

Figure 14 : Hyperbolic GNN Overview

하이퍼볼릭 지형을 계층적이고 트리 같은 그래프의 임베딩 공간으로 설명했습니다. 이러한 하이퍼 볼릭 공간은 두 가지 모델로 표현(Poincare, Hyperbolic)됩니다. 이러한 공간에서의 포인트들을 탄젠트 영역으로 매핑하기 위해서 신경망을 통해 진행합니다. 이러한 곡률은 모델이 성능과 안정성 사이에서의 트레이드 오프를 학습하도록 해야합니다.

Figure 15 : 복잡한 구조를 가진 그래프의 Hyperbolic GNN

III. Designing Space of GNNs²

특정 GNN task에 적합한 GNN의 디자인을 최적화하는 방법은 어떻게 될까요? 이러한 내용은 중요하지만 여전히 어려운 문제입니다. GNN은 다양한 분야에서 성공적으로 사용되고 있으며 도메인 전문가들은 SOTA GNN을 사용하고 싶어합니다. 그러나 수많은 GNN 모델과 다양한 도메인이 존재해 한가지 작업에서 좋은 디자인은 다른 작업에서의 성능이 안좋을 수 있습니다. 따라서, grid-search를 각 작업에 하는것은 불가능한 일이됩니다.

\[GNN layer = Transformation + Aggregation\]

위를 intra-layer design이라 부르고 GNN 층의 디자인 차원은 layer connectivity, pre-process layer, massage passing layer, post or pre learning configuration, batch-size, learning-rate, optimizers, epochs, 등 315K의 수많은 디자인이 존재합니다.

Figure 16 : GNN의 가능한 디자인 영역

이러한 모든 가능한 디자인을 커버하고 싶지는 않고, 개별적인 GNN 디자인보다 더 효과적인 디자인 영역을 설명하고자 합니다.

일반적인 GNN task 영역으로 GNN task를 카테고라이즈하면 보통 node/edge/graph level task가 있고, 이러한 분류는 정밀하지 않습니다.예를 들어 노드 예측에서 군집 계수 예측과 노드의 subject area 예측은 완전히 다른 task입니다.

하지만 이렇게 정밀한 GNN task의 분류는 매우 어려워 새로운 GNN 어플리케이션이 발생할 수 있습니다. 따라서, 정략적인 task의 유사도 측정을 진행해 GNN task를 이해하고 여러 task에 걸쳐 최적의 GNN 모델로 전달합니다.

정량적인 task의 유사도 측정은 아래와 같이 이루어집니다.

1. anchor 모델을 선택
   1. 작은 데이터셋을 선택
   2. 무작위로 디자인 공간에서 N개의 모델을 샘플링
   3. 성능을 가지고 해당 모델을 정렬하면(M개의 모델을 앵커모델로 선택) 최저와 최고의 성능 범위를 가지게 됩니다.
2. task를 특징화하여 anchor 모델의 성능에 순위를 매긴다.
3. 유사한 랭킹을 가지는 task는 유사하다고 고려한다.

여기서 알아야하는 것은 한 작업의 나쁜 모델은 다른 작업에서는 최적일 수 있다는 것입니다.

1. Evaluation of GNN Design

일반적으로 한개의 모델을 고르고 두개의 모델을 비교하지만 가능한 315K의 모델을 10M 모델 작업의 조합으로 근사하여 10M의 가능한 모델-작업 조합에서의 표본을 뽑아 모델의 순위를 매기는 방법을 사용합니다.

1. 모델-작업 배열의 무작위 샘플을 뽑음.
2. 해당 성능에 순위를 매김.
3. 평균과 순위의 분포를 그림.

Figure 17 : 디자인 차원에서 무작위 샘플들의 분포

2. GNN task의 이해.

최적의 GNN 디자인은 작업에 따라 상당히 다르기 때문에 task space의 연구가 중요하며 유익합니다.

Figure 18 : GNN 작업에 따른 유사도로 특징 정보와 구조 정보에 따라 두가지 그룹으로 나뉘어짐

Figure 18 처럼 task 간의 유사도를 계산하는 것은 간단하고, 유사한 task들은 비슷한 최적의 아키텍처를 가지게 됩니다.

Figure 19 : PCA 방법을 통해 유사한 작업에서 비슷한 최적 아키텍처를 가진다는 것을 확인할 수 있다.

3. 새로운 작업으로의 이전

위의 방법을 통해 최적의 모델을 찾지 못한 task로 일반화가 가능합니다.

새로운 작업(OGB)에 디자인을 적용시키기 위해 유사한 task를 찾는 절차를 아래와 같이 실행합니다.

1. 12개의 앵커 노드를 새로운 작업에 실행한다.
2. 새로운 작업과 존재하는 작업간의 유사도를 계산한다.
3. 높은 유사도를 가진 존재하는 작업에서 최적의 디자인을 추천한다.

Figure 20 : ogbg-molhiv task와 유사한 task를 찾는 pearson-correlation 유사도

위처럼 task space는 최적의 모델을 새로운 작업으로 안내합니다.

Figure 21 : 체계적인 GNN 디자인의 일반적인 가이드라인 설계로 GNN task에 대한 이해와 task간 최적의 GNN 디자인 전달 등이 있습니다.

그래프 알고리즘과 자료구조에 관해서 https://www.geeksforgeeks.org/graph-data-structure-and-algorithms/

1. Hyperbolic Graph Convolutional Neural Networks, NeurIPS 2019 ↩

2. J. You, R. Ying, J. Leskovec. Design Space of Graph Neural Networks, NeurIPS 2020 ↩