스탠포드 강의를 듣고 정리한 내용입니다.
지난 포스팅에서는 단일 레이어를 어떻게 쌓는지 한번 살펴보았습니다.
이번 포스팅에서는 graph augmentation에 대해서 알아보겠습니다.
Graph Augmentation
일반적인 그래프 프레임워크는 아래와 같이 구성되어 있다는 것을 배웠었죠.
정리하자면, 이웃 노드로부터 메세지를 받아 변환하고 기준 노드로 넘기는 Message과정, 기준 노드와 변환된 이웃 노드를 받아 하나로 합쳐주는 Aggregation과정, 이 계층을 이어주는 Layer connectivity, 그래프의 표현을 더 풍부하게 만들어주는 graph augmentation, 마지막으로 어떻게 학습할지에 대한 Learning Objective입니다.
이번 포스팅에서는 그래프의 표현을 더 풍부하게 만들기 위한 Graph augmentation에 대해 알아보겠습니다.
Graph augmentation이 필요한 이유
지금까지 배웠던 GNN은 입력으로 들어온 그래프와 계산 그래프가 일치했습니다.
즉, 왼쪽과 같이 그래프가 들어오면, 그 그래프에서 중심 노드를 기준으로 n개의 hop을 계산하여 오른쪽 그래프처럼 계산 그래프를 생성했습니다.
하지만 여기서는 그래프의 피쳐, 구조적인 면에서 graph augmentation을 쓰는것이 좋다고 이야기하고 있습니다.
먼저 피쳐의 측면에서 보겠습니다.
여기서는 그래프의 표현이 부족할 수 있기 때문이라고 말하고 있는데요.
뒤에서도 자세히 말하겠지만, 예를 들어 adj matrix만 입력으로 들어오는 경우를 뜻합니다.
→ feature augmentation 사용하면 해결할 수 있습니다.
이번에는 그래프 구조적인 측면에서 보겠습니다.
여기서는 크게 3가지를 이야기하고 있습니다.
첫 번째는 그래프가 너무 sparse할 수 있다는 것인데요.
adj matrix를 일반적으로 떠올렸을때, 0이 아주 많은 부분을 차지합니다. 이는 효율적이지 않다는 문제점이 있습니다.
→ virtual node/edge 추가하여 해결할 수 있습니다.
두 번째는 그래프가 너무 dense할 수 있다는 것인데요.
위와는 조금 상반되는 이야기지만, 이러한 경우는 계산량이 너무 많다는 문제점이 있습니다.
→ 메세지 패싱 과정에서 neighbor 샘플링하여 해결할 수 있습니다.
마지막으로 그래프가 너무 클 수 있다는 것인데요.
이럴 경우 계산 자체가 불가능할 수 있습니다.
→ subgraph 샘플링한 뒤 임베딩 수행하여 해결할 수 있습니다.
이제부터 하나씩 차근차근 알아봅시다.
Feature : 그래프의 표현이 부족할 수 있는 경우
앞에서 말했듯이 adj matrix만 입력받는 경우가 있기 때문에, 표현이 매우 부족한 경우가 있습니다.
여기서는 두 가지 방법으로 해결할 수 있다고 말하고 있는데요.
먼저 첫 번째 방법은 노드에 상수를 할당하는 방법입니다.
위와 같이 모든 노드를 1로 초기화 시켜주는 것입니다.
정말 단순한 방법입니다.
두 번째 방법은 각 노드에 유니크한 ID를 붙여주는 방법입니다.
표현은 다음과 같이 one-hot 인코딩으로 할 수 있습니다.
이 두가지 해결 방법을 한번 자세히 비교해봅시다!
| 상수로 초기화 시켜주는 방법 | one-hot인코딩으로 표현하는 방법 | |
| 그래프 |  |
 |
| 표현력 | 중간 - 각 노드 중심보다는 그래프 구조 자체를 학습하기 좋음 | 높음 - 각 노드에 유니크한 아이디가 있기 때문에, 노드 중심의 정보가 저장됨 |
| 새로운 그래프 활용도* | 모든 노드가 초기 1으로 세팅되기 때문에(혹은 같은 상수) 새로운 그래프를 입력받더라도 활용도가 높음 | 노드들은 유니크한 아이디를 가지기 때문에, 새로운 그래프에 활용하기에는 한계가 있음 |
| 계산 비용 | 노드의 차원이 1이기 때문에 비용이 매우 낮음 | 노드가 많을수록 노드 차원이 커짐. O(|V|)의 시간 복잡도를 가짐 |
| 사용 케이스 | 어떤 그래프든 가능(supervised learning) | 작은 그래프(unsupervised learning) |
여기서 끝이면 좋겠지만, feature augmentation이 필요한 경우가 하나 더 있다고 합니다!
바로 cycle graph인데요.
위의 왼쪽 그래프는 노드가 3개, 오른쪽 그래프는 노드가 4개입니다. 하지만 degree는 모두 2로 같습니다. 아쉽게도 GNN은 두 그래프를 구별하지 못한다고 합니다.
GNN을 생각해 보면 주변 노드로부터 feature를 받아 기준 노드를 update했었는데, 모든 노드는 degree가 2이기 때문에 계산 그래프를 그려보면 똑같습니다!
이를 해결하기 위한 방법은 cycle의 수치를 노드 feature로 사용하는 것입니다.
즉, 현재의 그래프가 노드 몇개로 이루어진 cycle인지 one-hot 벡터로 표현해 주는 것이죠. 위의 값을 입력받는다면 GNN은 힌트를 얻게 되어 이를 잘 처리할 수 있다고 합니다.
이외에도, node degree, clustering coefficient, pargerank, centrality 등등을 사용할 수 있다고 합니다.
Structure : 그래프가 너무 sparse할 경우
그래프가 너무 sparse할 경우의 단점은 굉장히 효율적이지 못하다는 것인데요.
여기서는 2가지 해결 방안을 설명하고 있습니다.
첫 번째 방법은 virtual edges를 추가하는 방법입니다.
이 방법으로 가장 흔히 쓰이는 방법은 2hop의 edge를 사용하는 방법인데요.
이게 무슨소리지? 싶으시겠지만 수식을 보면 바로 이해가실겁니다!
A가 기존의 adj matrix였다고하면, 2 hop은 A2이겠죠? 두 matrix를 더해주고 virtual edges matrix를 만들어 주는 것입니다.
그래서 이게 의미하는 바가 무엇이냐!
한가지 예를 통해서 확인해봅시다. 위와 같이 저자-논문으로 이어진 biparite graph가 있다고 하겠습니다.
보시다시피 이 그래프는 author-paper사이의 관계만 있습니다.
여기서 2hop을 이용한다면 어떻게 될까요?
바로 author-author사이의 연결성이 생기게 됩니다. 공동 저자가 묶이는 것이죠!
즉, 각 집단에 대한 연결성을 묶게 되는 것이죠!
반대로 paper에 대한 2hop은 한 저자가 쓴 다른 논문이 됩니다.
이 방법을 사용하게 된다면 연결성이 부족했던 sparse한 matrix에서 연결성이 풍부해지게 됩니다.
두 번째 방법은 가상의 노드를 추가하는 방법인데요.
이 방법은 기존에 노드 임베딩 방법에서 잠시 언급한 바 있습니다.
다음과 같이 가상의 노드를 하나 두고, 모든 노드와 다 연결을 시키는 방법입니다. 즉, 각 노드의 2hop은 모든 노드가 됩니다.
따라서 거리가 먼 노드끼리도 message passing을 할 수 있게 됩니다.
이 방법의 이점은 sparse한 그래프에서도 message passing을 증가시킬 수 있다는 것입니다.
Structure : 그래프가 너무 dense할 경우/그래프가 너무 클 경우
위와는 반대되는 상황인데요. 그래프가 너무 dense할 경우에는 계산량이 너무 커지죠.
따라서 계산량을 조금 줄여줄 필요가 있는데요. 여기서는 samplig을 이용하여 계산량을 줄인다고합니다.
기존에는 위와 같이 입력받았다면, 모든 이웃 노드들에서 message passing을 받아 사용했을텐데요.
샘플링 방법은 이웃노드들 중 샘플링을 이용하여 몇몇 노드들에게서면 message passing을 받습니다. 학습시 epoch, layer마다 샘플링을 다르게 한다면, 이웃 노드를 빠뜨리지 않고 골고루 학습할 수 있을 것입니다.
그럼에도 가장 중요한 노드가 학습 과정에서 제외당할 가능성이 있는데요. 이러한 방법에 대해서는 뒷부분에서 다룬다고 합니다.
이 방법의 장점은 계산량이 줄기 때문에 조금 더 큰 그래프에서 사용이 가능하다는 것입니다.
'인공지능공부 > 그래프' 카테고리의 다른 글
| [Stanford/CS224W] 7. GNN2(3) : Stacking Layers of a GNN (0) | 2023.03.29 |
|---|---|
| [Stanford/CS224W] 7. GNN2(2) : A Single Layer of a GNN (0) | 2023.03.28 |
| [Stanford/CS224W] 7. GNN2(1) : A General Perspective on Graph Neural Networks (0) | 2023.03.24 |
| [Stanford/CS224W] 6. GNN(3) : Deep Learning for Graphs (1) | 2023.03.23 |
| [Stanford/CS224W] 6. GNN(2) : Basic of Deep Learning (0) | 2023.03.22 |
