[Study]Chpater 9. Theory of Graph Neural Networks
해당 내용은 개인적으로 정리한 내용임으로 틀린 부분이 있을 수 있습니다.
이번 강의에서는 GNN의 표현력에 대해서 이야기 합니다.
I. theory of GNNs
많은 GNN 모델(GCN, GAT, GraphSAGE, desing space 등)들이 제안되었는데, 각 모델들의 표현력(다른 그래프 구조를 구별하는 능력)은 어떻게 될까요? 또한, 이러한 GNN 모델을 극대화하는 표현을 어떻게 디자인 할까요?
1. Node colors
다른 그래프 구조에서 GNN을 잘 구별하기 위해 같은 feature의 노드 표현을 동일한 색상으로 사용합니다.
Local Neighborhood structures
그래프에서 각 노드를 둘러싼 지역 이웃 구조를 고려합니다.
Figure 1 : (좌)1,4는 같은 degree를 가지지만 이웃의 degree가 다르므로 다르다. (우)1,2 노드는 그래프에서 대칭적이기 떄문에 같은 이웃 구조를 가져 같다고 할 수 있따.
이러한 지역이웃구조를 GNN 노드 임베딩은 구별할 수 있을까요? 이에 앞서 GNN이 지역 이웃 구조를 어떻게 수집하는지 이해할 필요가 있습니다.
Computational graph
각 레이어에서 GNN은 이웃들로 정의된 계산 그래프를 통해 이웃 노드 엠비딩을 집계하여 노드 임베딩을 생성합니다.
Figure 2 : (좌)원 그래프 (우)노드 1과 2의 computational graph(2-layer GNN)
Figure2 에서 GNN은 오직 node feature(ID가 아닌)만 보고 임베딩을 생성합니다. 따라서 GNN은 노드 1과 2를 구별할수 없다. 일반적으로 다른 이웃들은 다른 계산 그래프로 정의되고, 각 노드를 둘러싼 동일한 rooted subtree structure(이하 RSS)를 가지게 됩니다.
rooted subtree structure- root 노드로부터 재귀적으로 펼쳐진 이웃한 노드들로 정의된다.
Figure 3 : 각 RSS에 따른 임베딩
따라서, Figure 3 처럼 GNN의 노드 임베딩은 RSS를 수집하게 되고 표현력이 높은 GNN은 서로 다른 루트를 가진 부분 트리들을 각각 다른 노드 임베딩으로 효과적으로 포함시킵니다.
\[\text{fuction }f:X \rightarrow Y\]2. injective function
위의 함수를 입력과 결과가 일대일 대응되는 ‘단사 함수’\(_{injective-function}\)이라고 합니다. 즉, \(f\)는 입력의 모든 정보를 얻게 됩니다.
이를 통해 표현력이 높은 GNN은 부분 트리를 노드 임베딩으로 전사적으로 포함시킵니다. 이러한 GNN은 동일한 깊이의 부분 트리가 잎 노드에서 뿌리 노드까지 재귀적으로 특성화될 수 있습니다. 즉, 이러한 부분 트리를 임베딩으로 만들어 계층적(재귀적)으로 만들 수 있다는 의미입니다.
Figure 4 : 초록색 박스에서 injective neighbor aggregation을 사용하여 다른 subtree를 구분한다.
만약 GNN의 종합하는 각 단계에서 이웃 정보를 모두 얻을 수 있다면 다른 루트를 가지는 부분 그래프를 구별할 수 있는 노드 임베딩이 생성되어진다. 다른말로, 표현력 있는 GNN은 전사적인 이웃 집계 함수를 각 단계에서 사용한다.
II. Designing the Most Powerful GNN
GNN의 표현력은 이웃 집계 함수에 의해 특징화됩니다. 전사적인 집계 함수는 표현력 있는 GNN으로 이끌어 이러한 집계 함수의 표현력을 이론적으로 분석합니다.
1. Neighbor aggregation.
우리는 GNN에서 message-passing이 최대화하도록 디자인하는것이 목표입니다.
Figure 8 : \(\phi(\cdot)\)은 비선형함수, \(f(\cdot)\)은 선형 함수, \(S\)는 여러개의 \(f(\cdot)\) 합으로 전사적인 다항집합 함수를 표현됩니다. \(f\)는 색상들의 원핫 인코딩을 수행하고, 원핫인코딩의 합으로 입력된 멀티셋의 모든 정보를 얻게 됩니다.
GCN
이러한 집계 함수는 노드 색상을 원-핫 인코딩으로 표현한다고 가정하면 같은 색상 비율을 가지는 다른 멀티셋을 구별하지 못한다.
Figure 6 : GCN; 이웃한 노드 특징 위에서 elemvet-wise mean pooling 를 사용
GraphSAGE
동일하게 뚜렷한 색상의 같은 집합을 가지는 다른 멀티셋을 구별하지 못한다.
Figure 7 : GraphSAGE; MLP를 적용한 후 GCN과 동일하게 elemnet-wise max pooling을 사용합니다.
III. GIN
Universal Approximation Theorem1에 의해서 아래와 같이 충분히 큰 은닉층 차원과 비선형 함수 $\sigma (\cdot)$를 사용하는 1개의 은닉층을 갖는 다층 퍼셉트론(MLP)이 임의의 연속 함수를 임의의\(_{arbitrary}\) 정확도로 근사할 수 있습니다. 즉, 적절한 크기와 구성의 신경망이 어떤 연속 함수든지 원하는 정확도로 근사할 수 있는 능력을 보장하는 결과입니다.
\[MLP_{\phi}(\sum_{x \in S}MLP_f(x))\]따라서, 이제는 신경망이 전사적인 다항함수로 모형화가 가능하다는 것을 알게 되었습니다.
Graph Isomorphism Network(GIN)의 이웃 집계 함수는 단사적인 것을 알게 되었습니다. 따라서, 이러한 경우가 실패하는 경우는 없고, GIN은 GNN의 message-passing class에서 가장 잘나타내는 GNN임을 나타냅니다.
여태까지 GIN의 이웃 종합 부분을 묘사했고, graph-level 특징을 얻는 전통적인 방법인 WL graph kernel과 연관하여 전체 모델을 이야기합니다.
1. WL graph kernel
그래프 G에서 V 노드들의 집합이 주어졌을때 각 노드의 컬러는 HASH 맵을 통해 아래와 같이 각 노드의 색상을 정의하게 됩니다. 이러한 재정의를 K 번 반복한 이후 K-hop 이웃들의 구조를 요악하게 됩니다.
Figure 11 : 노드 색상 재정의
GIN은 단사적인 HASH function을 신경망으로 사용한다. 아래 Figure 11 에서 HASH Table 안에 있는 좌측 변수는 Root node feature이고 우측에 있는 값은 Neighboring node colors이다.
Figure 10 : 두 그래프가 주어졌을때 color refinement example로 stable coloring으로 도달할때까지 반복하고, 두 그래프는 만약 같은 컬리 집합을 가지고 있다면 isomorphic로 고려된다.
이는 아래와 같이 모델링된다.
Figure 12 : GIN의 모델링 함수, \(\epsilon\)은 학습 가능한 scalar이다.
따라서, GIN의 노드 임베딩은 아래와 같이 업데이트 된다.
Figure 13 : GIN의 노드 임베딩
즉, GIN은 WL graph kernel의 신경망 버전으로 이해할 수 있습니다.
| Update tartget | Update function | |
| WL Graph Kernel | Node color (one-hot) | HASH |
| GIN | Node embeddings (low-dim vectors) | GINCOnv |
이러한 GIN의 노드 임베딩은 저차원으로 다른 노드들의 유사도가 더 잘보이게 \(_{fine-grained}\) 수집하고, downstream task를 통해 업데이트 함수의 파라미터를 학습 가능하다.
이와 같이 GIN과 WL graph kernel 사이의 관계 때문에 두 방법으로 얻은 그래프 표현은 완전히 같게 나타낼 수 있습니다. 즉, 두 그래프가 GIN으로 구별 가능하면, WL 커널을 사용해도 구별이 가능합니다.
완벽히 같게 표현된다. 만약 두 그래프가 GIN으로 구별가능하면 WL kernel로도 구별가능하다.
이러한 관계가 얼마나 이게 강력한것인가?
WL kernel은 이론상으로 그리고 관찰적으로 실세계 그래프를 가장 잘구별하는 것을 증명2했습니다. 따라서 GIN 또한 실세계 그래프에서 충분히 강력하게 적용될 수 있습니다.
2. Polling
Figure 14 : mean, max pooling의 실패 케이스와 판별력 비교 이미지
3. implement of GNN
이러한 GNN의 표현력을 추가적으로 향상시킬 수 있을까? 다른 cycle과 같이 GNN으로 구별할 수 없는 기본적인 그래프 구조 문제를 해결함으로써 GNN의 표현력을 향상3시킬 수 있다고 합니다.