About GNN
이 글은 huggingface 의 포스팅을 번역, 요약한 글입니다. 모든 컨텐츠에 대한 저작권은 huggingface 에 있습니다.
그래프란 무엇인가?
이 글에서는 그래프라는 자료구조로부터 얻을 수 있는 것을 이야기하고 있습니다.
그래프의 노드와 에지에 타입을 넣게되면 이형(heterogeneous) 그래프라고 부를 수 있는데, 이렇게 되면 그래프가 다양한 의미를 가지게 됩니다.
그래프는 어디에 쓰는가?
그래프로 접근을 하게되면, 다음과 같은 작업을 할 수 있습니다.
- 그래프 생성
- 예) 새로운 분자를 발견하기 위해 약학에 사용
- 그래프 진화
- 예) 주어진 그래프가 시간에 따라 어떻게 발전하는지를 통해 물리학 등에서 주어진 시스템의 예측하는데 사용
- 그래프 예측
- 예) 그래프 분류나 회귀를 통해 분자의 독성을 예측
노드 레벨
노드 레벨에서는, 각 노드의 특성을 예측하여 그래프에 속하는 임의의 노드가 3차원 상에서 어떻게 접히는지 등을 예측합니다.
에지 레벨
에지 레벨에서는 각 에지의 특성을 예측하여, 정보가 없는 에지를 예측합니다. 이를 통해 화학이나 추천시스템에서 주어진 노드간의 관계를 유추합니다.
하위 그래프 레벨
하위 그래프 레벨에서는, 사회 관계망에서 커뮤니티를 탐지하거나, 어떻게 사람들이 연결되는지를 유추하는데 사용될 수 있습니다. 또는 여행시스템같은곳(구글 맵스)에서 도착 시간을 예측하는데도 사용될 수 있습니다.
그래프의 진화는 transductive(변환) 과정을 통해 추측할 수 있습니다.
그래프는 모든 간선들의 집합, 혹은 인접 행렬, 인접 리스트로 표현가능합니다.
이런 그래프들은 ML에서 다루기 좀 더 까다롭습니다.
왜냐하면, 단순한 시퀀스 데이터(텍스트나 오디오), 혹은 정렬된 격자(이미지, 비디오 등)보다 위상 관계가 복잡하기 때문입니다.
이 것은, 비슷하게 행렬로 표현된 데이터라고 하더라도, 이것을 그래프로 접근했을 때, 정렬된 객체(시퀀스, 격자)로 이해하면 안된다는 것입니다.
이를 요약하면, 그래프 구조와 시퀀스 구조는 순열 불변성(Permutation Invariance)에서 차이가 있습니다. 그래프 구조는 서로 다르 순열에 대해 변하지 않는 특성이 있습니다.
그래프를 ML에 적용했을 때는 결국 얼마나 그래프를 통해 내가 관심있는 정보를 표현(나타낼) 수 있는가 가 중요합니다. 예를 들면 그래프로 표현했을 때 서로 다른 두 노드가 얼마나 가까운가 등을 어떻게 측정하는가? 그리고 무엇을 의미하는가? 등이 있을 수 있겠습니다.
Pre-Neural Approaches
이전에는 그래프와 그래프에 속하는 것들을 특징들의 조합으로 표현하였습니다.
예를 들어 노드 레벨에서는 한 노드가 얼마나 해당 그래프에서 중요한 노드인가? 등을 그래프의 구조 등을 통해 알아냈습니다. 이것의 한 예시는 노드의 “중심도(centrality)”가 있습니다.
노드의 차수, 군집 계수(Clustering Coefficient), 그래플릿 차수 벡터(Graphlet degree vector) 등을 통해 측정할 수 있습니다.
에지 레벨에서는 가까운 이웃들이나, 최단 거리, 카츠 인덱스(Katz Index)를 통하여 측정할 수 있습니다.
그래프 단위에서는, 그래플릿 개수, 커널 메소드 등을 통해 이러한 특성을 알아낼 수 있습니다.
Walk-based approaches
이 방법은, 유사도를 측정하기 위해 한 노드에서 다른 노드로 임의의 걸음을 통해 갈 수 있는 확률을 사용합니다.
예를 들어, Node2Vec는 노드간의 랜덤한 걸음을 시뮬레이팅합니다. 이 것을 skip-gram으로 처리합니다. 이 방법은 페이지 랭크 메소드의 계산을 가속하기 위해서도 사용합니다.
하지만 이런 기존의 방법들은 새로운 노드에 대한 임베딩을 얻기 어렵습니다. 노드 간의 구조적 유사성을 정밀하게 얻기 어렵기 때문입니다.
GNN
Graph Neural Network는 처음보는 데이터에 관해서도 확장가능합니다.
GNN을 적용하기 위한 신경망은 순열 불변성과 순열 등가성을 가져야합니다.
g: graph 이고, p가 permutation function 일 때,
- 순열 불변성(Permutation Invariant
- f(p(g)) = f(g)를 만족합니다.
- 순열 동일성(Permutation Equivariant)
- p(f(g)) = f(p(g))를 만족합니다.
보통의 신경망(RNN, CNN)은 이 것을 만족하지 못합니다.
그래서 GNN이 도입 되었습니다.
GNN은 연속적인 계층으로 구성되는데, 각 계층은 각 노드를 인접한 표현들의 조합(집계) 와 이전 계층(메시지 전달)로 표현합니다.
CNN은 인접 노드의 수와 순서가고정된 GNN으로 볼 수 있고, 위치 임베딩이 없는 트랜스포머 모델은 fully-connected 그래프에 대한 GNN으로 볼 수 있습니다.
집계와 메시지 전달
인접한 노드들로 부터 메시지를 집계하는 것은 여러가지 방법이 있습니다.
- Graph Convolutional Network
- 정규화된 주변 노드들의 표현을 평균합니다.
- Graph Attention Network
- 중요도에 따라 서로 다른 주변 노드들에 가중치를 부여합니다.
- GraphSAGE
- 주변 노드들을 서로 다른 거리에서 모으고, max pooling을 이용하여 집계합니다.
- Graph Isomorphism Networks
- 주변 노드 표현들의 합에 MLP를 적용하여 집계합니다.
은 각각 다른 방법을 사용하여 집계합니다.
GNN 모양과 over-smoothing 문제
노드들에 대해 많은 계층에서 집계를 계속하게 되면, 노드들의 집계가 그래프에 속하는 모든 노드를 포함하게 되어 각 노드의 특징을 반영하게 되지 못하는 문제가 발생합니다. 이 것을 oversmoothing problem이라 합니다.
- GNN을 충분히 작은 계층만을 사용하거나,
- 각 계층의 복잡도를 증가시키거나,
- 메시지 전달을 하지 않는 계층을 추가하거나,
- skip-connection을 추가하는
방법으로 해결할 수 있습니다.
이 oversmoothing 문제는 그래프 ML 분야에서 중요한 문제입니다.
Graph Transformers
위에서 다뤘듯이, 트랜스포머 모델을 그래프에 적응시키는 것이 연구되고 있습니다.
대부분의 방법들은, 새로운 데이터에 대해 그래프의 특징과 위치 정보를 가장 잘 표현하는 방법을 찾고 있습니다.
현재까지 가장 좋은 성능을 보이는 연구는 다음과 같습니다.
- Graph Transformer for Graph-to-Sequence Learning (Cai and Lam, 2020)
- Rethinking Graph Transformers with Spectral Attention (Kreuzer et al, 2021)
- GRPE: Relative Positional Encoding for Graph Transformer (Park et al, 2021)
- Global Self-Attention as a Replacement for Graph Convolution (Hussain et al, 2021)
- Do Transformers Really Perform Badly for Graph Representation (Ying et al, 2021)
가장 최신의 연구는 TokenGT를 소개하는 Pure Transformers are Powerful Graph Learners (Kim et al, 2022)입니다. 이 방법은 입력 그래프를 노드의 시퀀스로 표현하며, 간선 임베딩을 사용합니다.
Recipe for a General, Powerful, Scalable Graph Transformer (Rampášek et al, 2022)는 모델은 아니지만 프레임워크인 GraphGPS를 소개합니다.
트랜스포머를 그래프에 사용하는 것은 굉장히 초기 단계이지만, 꽤 가능성이 있어보입니다.
