CS224W 7.3 Stacking Layers of a GNN

1. Introduce

이전까지 그래프신경망의 단일계층을 설계하고 정의하는 것에 대해 논의하였고, 레이어를 쌓는 것에 대해 다뤄보는 강의!

1.1. Stacking GNN Layers

• 문제정의
  • 지금까지 살펴본 Single layer들을 어떻게 쌓을 수 있을까?
  • 그래프 신경망에 연결을 추가하거나 건너뛸 수 있는 방법이 있을까?

1.2. How to construct a GNN?

• Standard way: 그냥 순차적으로 쌓아보자
  • Input: raw node feature $\mathbf{x}_v$
  • Output: $L$ Layer 이후의 노드임베딩 $\mathbf{h}_v^{(L)}$

2. Problems

• 그래프 신경망의 깊이: 정보 수집을 위해 얼마나 많은 홉을 이동해야하는가?를 의미
  그래프 신경망의 많은 레이어와, 레이어 내의 hop은 각각 다른 의미를 가짐
• 너무 많은 레이어를 쌓는것은 문제가 됨
  • Over-smoothing Problem: 모든 노드의 임베딩이 유사한 값으로 수렴하는 현상!
    • receptive field가 너무 크면, 모든 네트워크가 동일 정보를 수집하기 때문에 발생

2.1. Receptive Field of a GNN (수용필드)

• Receptive field : 관심있는 노드의 임베딩을 결정하는 "노드집합"

  • K 레이어의 GNN에서 각 노드는 해당 노드 주변의 k-hops이웃의 수용필드를 가짐
  • 6개 다리를 지나면 전세계가 연결된다..
    • 6-hop이면 어떤노드를 선택하든 전체 그래프가 수용필드로 선택될것!

• 두 노드 간의 Receptive filed의 오버랩영역!

  • hop이 증가할수록, 공유하는 이웃의 수가 매우 빠르게 증가함!
  • 즉, hop이 증가할수록 서로 다른 노드를 임베딩으로 구별하기가 어려워짐

2.2. Receptive Field와 Over-smoothing의 연결

• 노드의 임베딩은 receptive field(노드의 이웃집합)에 의해 결정됨
  • 만일 두 노드의 receptive fields가 매우 많이 겹치면, 임베딩도 매우 유사함
• GNN layer를 많이 쌓으면
  • 노드들은 같은 receptive fields를 중복되게 갖게 될 것이며
  • 노드임베딩들이 거의 다 유사해질 것이며
  • Over-smoothing 문제를 겪게 됨

3. Solutions

3.1. Over-Smoothing problem의 Solution

• GNN layer수를 추가하는 것을 주의하라
  • 이미지 분류를 위한 CNN과는 다르게, GNN은 레이어를 깊게 쌓는게 언제나 유익하지x
  • (1) 필요한 수용필드의 수를 분석
    • e.g. graph의 직경(diameter)을 계산해본다든지
  • (2) 레이어 수 $L$을 결정하되, GNN layer $L$을 불필요하게 크게 잡아선 안됨
• Layer 수를 적게 유지하면서 표현력을 향상시킬 수 있는 방법이 있을까?

3.2. Expressive power for shallow GNNs

• Shallow GNN을 표현력있게 만드는 방법?
  • Solution1 : 각 GNN 레이어 내에 표현을 위한 층을 추가하기
  • Solution2 : GNN 레이어 전후에 다층퍼셉트론 레이어를 추가하기
    • 사전/사후처리 레이어

3.3. Skip-connection

• 많은 GNN layers가 필요한 경우?

  • GNN에 Skip-connection을 추가하여 over-smoothing 방지

• Skip-connection:

  • GNN에 지름길을 추가하는 것
  • Skip connection을 활용하면, 혼합모델을 생성할 수 있음
  • $N$ Skip connection $\rightarrow$ $2^N$ 개만큼의 경로 생성

• 👇 GCN with Skip Connections

  

  • Skip connection이 적용되면
    • 이전 레이어의 임베딩 $\mathbf{h}_v^{(l-1)}$을 그대로 더해주는 수식이 추가됨

• 💡참고 : Skip connection의 다른 옵션

  • 최종 레이어까지 직접 스킵하는 방법!
  • 최종 레이어에서 직접적으로 이전레이어들의 모든 노드임베딩을 집계하는 방식, ICML 2018 논문 게재