[Study]Chapter 7. Graph Neural Networks 2: Design Space

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

I. A Single Layer of a GNN

\[\text{GNN layer = Message + Aggregation}\]

GNN layer는 벡터들의 집합을 하나의 벡터로 압축하는 것으로 아래와 같이 두 가지 절차로 이루어져있다.

• 1. message

  \[m_u^{(l)}= MSG^{(l)}(h_u^{(l-1)})\]

  각 노드는 message를 생성하고 다른 노드들에게 나중에 보낸다.
  ex. linear layer \(m_u^{(l)}= W^{(l)}(h_u^{(l-1)})\)

• 2. Aggregation

  \[h_u^{(l)}= SUM(m^{(l)}_u, u \in N(v))\]

  각 노드는 v의 이웃들로 부터 각 메시지를 종합한다.

\(h_v^{(l)}\)은 \(h_v^{(l-1)}\)에 직접적인 연산이 없어 자신의 정보를 잃어버리게 된다. 따라서 아래와 같이 \(h_v^{(l-1)}\)을 \(h_v^{(l)}\)계산에 포함시킨다.

Figure 1 : Classical GNN Layers, GCN

\[\begin{array}{ll} m_u^{(l)}= W^{(l)}(h_u^{(l-1)}), m_v^{(l)}= B^{(l)}(h_v^{(l-1)}) \\ h_v^{(l)}= CONCAT(AGG(m^{(l)}_u, u \in N(v)), m_v^{(l)})\\ \end{array}\]

위 처럼 이웃들의 정보를 먼저 종합하고 자기 자신의 정보를 다시 넣는 방식이다.

3. GraphSAGE

현재 노드와 이웃 노드를 분리.

Figure 2 : 두 단계로 구성되어 있으며 첫번째는 \(A_{N(v)}^{(l)} \leftarrow AGG(\{h_u^{(l-1)}, \forall u \in N(v)\})\) 노드 이웃들을 종합하고 두번째로 자신의 정보를 스스로 추가함.

II. GAT : Graph Attention Networks

Attention(\(a_{vu}\))는 Cognitive attention에서 영감을 받았아 입력 데이터의 중요한 부분만 집중하고 나머지는 흐려지게 만든다. 즉, 모든 노드의 이웃이 동일하게 중요하지는 않다.

1. Attention Score

Figure 3 : \(a_{vu}= \frac{1}{|N(v)|}\)로 u에서 v로 보내는 메시지의 가중치 factor

1. 어텐션 Score(\(e_{vu}\))는 학습 가능한 가중치 \(a\)를 가지고 계산.

   즉, 두 노드 사이의 상관관계를 scoring한다.

   Figure 4 : 어텐션 score는 u에서 노드 v로 가는 메시지의 중요도 지표이다.

2. \(e_{vu}\)를 정규화하여 어텐션 가중치를 계산.

   Figure 5 : softmax 함수를 사용

3. Figure3에 명시된 것처럼 가중 합을 진행

이처럼 이웃 요소들을 고려하는 방법은 NLP에서도 비슷한 방법¹이 있음.

그래프에서는 이웃 노드를 고려하는 부분과 해당 Task에서 주변에 존재하는 token을 고려하여 인코딩하는 부분이 유사한 매커니즘입니다.

Figure 9 : span(연속된 token)에 대한 임베딩을 만드는 것이 목표로 전체 문장에서 각 token을 양방향 LSTM을 사용하여 1차원 vector로 표현하고 해당 vector는 문장에서 각 token의 중요도(span을 얼마나 잘 나타내는가)를 구하게 됩니다. 이후 목표 token의 이웃한 token들의 vector들을 softmax로 계산함.

해당 방법은 상호참조해결 Task로 span이 명사류인지 아닌지도 중요하게 되어 span의 첫번째, 마지막 token을 참조하여 구분하게 됩니다. 따라서 최종 임베딩에는 [Span head(attention emb), Span의 첫 token, Span의 마지막 token]이 들어가게 됩니다.

상호참조해결

“나는 로봇이고, 자연인 너를 만나러 간다” 에서 ‘나’와 ‘로봇’이 같고, ‘자연’과 ‘너’는 똑같은 개체를 나타내므로 서로 참조하는 관계여서 이러한 관계속에서 어떤 token끼리 같은지 비교하려고 모든 span에 대한 임베딩을 만들어서 비교하는 Task이다.

2. 멀티 헤드 어텐션

다중 어텐션 점수를 만들어 나온 결과들을 결합하여 어텐션 매커니즘의 학습 절차를 안정시킨다.

Figure 7 : Multi attention score on Graph

아래와 같이 Transformer의 멀티헤드 어텐션과 유사한 형태이다.

Figure 16 : Transformer multi-head Attention

이러한 어텐션 매커니즘으로 다른 이웃들의 중요도 값(\(a_{vu}\))을 암묵적인 명시가 가능하다.

• 계산적 효율성 : 그래프의 모든 edge들에 대해 병렬적으로 어텐셔널 coefficient를 계산할 수 있다.
• 저장 효율성 : 희소 행렬은 \(O(V+E)\)보다 크게 요구되지않는다. 그래프 크기에 구애받지않고 파라미터의 수가 고정된다.
• Localized : local 네트워크 이웃들만 주의를 기울인다
• 귀납 능력 : edge-wise 매커니즘으로 공유된다. 글로벌 그래프 구조에 더이상 의존하지않는다.

3. Cora Citation Net

Figure 8 : Cora 데이터셋에 기반한 학술 논문 인용 네트워크에서의 다른 방법들보다 Attention을 활용한 GAT가 좋은 성능을 이끌어 낸 것을 확인할 수 있음.

실제로 이러한 classic GNN layer는 훌륭한 시작지점이 될 수 있어 일반적인 GNN layer 디자인으로 고려하여 더 좋은 성능을 낼 수 있다. 아래와 같이 현대의 심층신경망 모듈을 포함시켜 많은 도메인에 활용할 수 있다.

Figure 10 : GNN Layer in Practice

• 배치 정규화 : 신경망 학습을 안정화하는 방법으로 입력값에 배치 단위로 정규화를 진행하여 노드 임베딩의 평균과 분산을 재조정.
• 드랍 아웃 : 과적합 방지로 학습 도중 뉴런을 무작위로 비활성화하고 테스트에는 전체를 사용함.(MSG 함수의 선형층에서 활용가능)
• 어텐션, 게이팅 : 중요 메시지를 조절하는 역할
• 활성화 함수 : sigmoid, ReLU, Parametric ReLU(ReLU보다 실증적으로 성능이 좋다.)
• 다른 유용한 심층신경망 모듈들

이러한 GNN의 다양한 다자인은 GraphGym을 통해 탐구해볼 수 있다.

III. Stacking Layers

GNN을 만드는 기본적인 방법은 층을 연속적으로 쌓는 방법입니다. 입력으로 초기의 raw 노드 특징 \(x_v\)를 넣고, L개의 GNN Layer를 거친 \(h_v^{(L)}\) 노드 임베딩을 얻게 됩니다.

Figure 11 : Stacking Layers

1. over-smoothing problem

이렇게 많은 층을 쌓는 것은 over-smoothing인 모든 노드 임베딩이 같은 값으로 임베딩 되는 문제가 발생하는데, 이는 임베딩으로 노드들을 구분\(_{differentiate}\)하려는 특성 떄문에 문제가 됩니다.

Figure 12 : K 층을 가진 GNN에서 각 노드들은 K-hop 떨어진 이웃들은 수용 영역을 가지고 있고, 그림 처럼 hop의 수를 늘리면(GNN 층을 늘리면) 공유되는 이웃들이 빠르게 증가하는 현상이 보여진다.

노드들의 집합은 수용적인 영역에서 관심있는 노드의 임베딩을 결정하게 됩니다. 이는 layer를 깊게 쌓을수록 서로 다른 노드에서 참고하는 노드가 겹치게 되어 임베딩 영역 내에 비슷한 공간으로 맵핑하게 됩니다. 만약 두 노드가 심하게 수용영역이 겹치면 두 노드의 임베딩은 매우 유사(구분되지 못할정도로)할 것입니다. 즉, layer를 쌓을수록 점점 더 많은 주변 node의 features를 반영하게 된다.

Q) dropout으로 해결할 수 있는가?

• dropout은 NN 내의 cell의 의존성을 줄여 과적합을 방지하는 방법으로 해결이 되지 않습니다.
• 이러한 문제를 막기위해서는 겹치는 node를 막거나(Do not stack), 어떻게든 잘 피해서 표상(Skip Connection)해야 합니다.

따라서, 수용영역을 정의하는 것을 통해 오버 스무딩을 설명할 수 있어 노드의 임베딩은 수용영역에 의해 결정된다는 것을 알게 되었습니다.

위의 오버 스무딩 문제를 통해 다른 도메인에서의 신경망과는 다르게 층을 늘리는 형태는 항상 도움이 되지는 않아 조심해야하는 것을 알게되었습니다. 이를 통해 필수 수용역역을 분석하여 수용영역을 조금 작게 GNN 층을 설정하여 층의 개수 L을 필요 이상으로 크게 하지 말아야 합니다.

2. Shallow GNN의 표현력

층의 개수 L이 너무 작은\(_{Shallow}\) GNN의 표현력을 강화시키는 방법은 없을까?

Figure 13 : Add other Layers, GNN층 이외의 Pre-process, Post-process MLP Layer와 Skip-connection 등의 추가적인 Layer를 추가하는 방법

1. 각 층의 표현력을 더 늘리는 방법.

   • 집계나 변환 함수를 심층 신경망으로 만들 수 있다.

2. 메시지를 넘기지않는 층을 늘리는 방법.

   • GNN 층을 포함한 GNN만 있을 필요는 없다. Figure13처럼 GNN layer 앞뒤로 노드 특징을 인코딩하고, 노드 임베딩을 reasoning, transformation할때 중요한 pre-process, post-process layer를 만들 수 있다.
   • 위의 추가적인 layer로 부족하면, shortcut인 skip connection²을 추가하여 초기 층에서의 영향력을 마지막 노드 임베딩에 늘리면 된다.

Figure 14 : Skip connection

왜 skip connection이 먹히나?

Residual connetion과 유사한 개념으로 N개의 스킵 커넥션은 \(2^N\)의 가능한 통로를 자동적으로 얕은 GNN과 깊은 GNN등 신경망 모듈들의 혼합물들로 만들어 내 더 깊은 표현력을 얻게 된다.

IV. Graph Manipulation in GNNs

일반적인 GNN Framework에서는 Raw 입력 그래프와 계산가능한 그래프는 같지 않다. 따라서, 그래프의 feature 확대\(_{augmentation}\)와 그래프 구조를 조작\(_{Manipulation}\)해야한다.

Figure 15 : Graph Manipulation

우리는 지금까지 입력 그래프가 계산 그래프라고 가정해왔다. 이러한 가정을 하는 이유는 Feature-level에서 입력 그래프의 특징이 부족하면 특징을 늘려야\(_{augmentation}\)하고, Structure-level에서 그래프가 희소하면 메시지 패싱이 제대로 되지 않으며 이와 반대로 밀도가 높으면 많은 비용이 들고, 그래프가 너무 크면 GPU에 적용하지 못하기 때문이었다.

따라서, 단순한 입력 그래프는 임베딩을 위한 최적의 계산 그래프가 될 수 없다.

1. feature-augmentation

해당 방법은 GNN으로 학습하기 어려운 구조일때 필요합니다. 예를들어 노드가 l 길이의 cycle에 있는지 학습이 가능할까요? 계산 그래프에서 모든 노드는 2의 degree를 가지기 떄문에 항상 같은 이진트리가 되어 학습이 불가능합니다. 따라서, 아래와 같이 노드 feature로 cycle 길이의 차원으로 길이의 개수를 세는 방법이 존재합니다. 다른 특징을 증가하는 방법으로 군집 계수, PageRank, 중심성 등의 특징들을 사용할 수 있습니다.

1. Constant node feature;

   정수 값을 배정하는 방법으로 계산 비용이 1차원이므로 매우 낮고, 모든 노드는 구별가능하며 그래프의 구조에서 학습하므로 표현력은 중간정도이다. 또한, 새로운 노드에 대해 귀납적인 학습\(_{inductive-settings}\)이 가능해 일반화가 높습니다.

2. One-hot node feautre;

   노드의 unique ID를 배정하는 방법으로 차원이 높아져 계산 비요이 높고, 특정 노드의 정보가 저장되어 표현력이 높음, 새로운 노드를 일반화하지 못해 귀납 능력이 낮다. 따라서, 작은 그래프나 추론적인 학습\(_{Transductive-setting}\)에 사용이 가능합니다.

2. virtual nodes/ edges

1. 일반적인 접근법으로 2-hop 이웃들을 가상의 edge로 연결하는 방법으로 인접행렬을 A가 아닌 \(A+A^2\)으로 사용합니다. 이는 Bipartite graph, 양자 그래프 등에서 사용합니다.

2. 가상의 노드를 그래프의 모든 노드와 연결하는 방법으로 노드를 추가하면 모든 노드들의 거리는 2가 되어 희소 그래프에서 메시지 전달이 매우 향상됩니다.

3. Neighborhood sampling

임베딩 계산을 할때마다 메시지 전달에 노드들을 (무작위하게)표집 합니다. 이는 모든 노드를 사용한 임베딩과 유사하게 될것이고 계산 비용을 매우 낮추게 됩니다. 부분 그래프의 sample을 임베딩 계산하는데 사용 하는 방법들로 해결이 가능(Scaling up GNN에서 배울 내용.)하다.

1. Lee, K., He, L., Lewis, M., & Zettlemoyer, L. (2017). End-to-end Neural Coreference Resolution. ArXiv, abs/1707.07045. ↩

2. Veit et al. Residual Networks Behave Like Ensembles of Relatively Shallow Networks, ArXiv 2016 ↩