CS224W - (5) A General Perspective on Graph Neural Networks

GNN의 싱글 레이어

GNN Layer

GNN 레이어는 다음의 두 과정을 통해 이웃 노드의 여러 벡터 집합을 단일 벡터로 압축합니다.

1. 각 노드의 벡터를 메시지로 변환
2. 변환된 메시지를 집계

메시지 계산(Message Computation)

메시지로 변환하는 함수는 다음과 같습니다.

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

각 노드는 메시지를 생성해서 이후 다른 노드로 전송하게 됩니다. 이전 레이어에서 온 정보인 $h_u^{(l-1)}$가 현재 레이어의 메시지 변환 함수 $\text{MSG}^{(l)}$를 통과하여 현재 레이어의 정보가 되는거죠. 예를 들어 선형 함수를 메시지 변환 함수로도 사용할 수 있습니다.

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

메시지 집계(Message Aggregation)

노드 $v$의 이웃으로부터 메시지를 집계하는 메시지 집계 함수를 수식으로 표현하면 다음과 같습니다.

\[h_v^{(l)} = \text{AGG}^{(l)} \left( \left\{ m_u^{(l)}, \; u \in N(v) \right\} \right)\]

메시지 집계 함수로는 합, 평균, 최댓값 등 다양한 함수를 사용할 수 있습니다.

\[h_v^{(l)} = \text{Sum} \left( \left\{ m_u^{(l)}, \; u \in N(v) \right\} \right)\]

하지만 이렇게 했을 때 노드 $v$로부터 전달되는 정보가 손실될 수 있습니다. $h_v^{(l)}$를 계산할 때 이전 레이어의 $h_v^{(l-1)}$에 직접 의존하지 않기 때문입니다. 따라서 $h_v^{(l-1)}$를 계산에 직접 포함하여 문제를 해결할 수 있습니다.

메시지를 계산할 때는 이웃 노드로부터 오는 정보는 똑같이 계산하지만 여기에 노드 $v$가 직접 메시지를 전달하는 계산을 추가합니다.

\[\begin{aligned} m_u^{(l)} &= W^{(l)} h_u^{(l-1)} \\ m_v^{(l)} &= B^{(l)} h_v^{(l-1)} \end{aligned}\]

메시지를 집계할 때는 $m_v^{(l)}$도 같이 집계합니다.

\[h_v^{(l)} = \text{CONCAT} \left( \text{AGG} \left( \left\{ m_u^{(l)}, \; u \in N(v) \right\} \right), m_v^{(l)} \right)\]

단일 레이어

이제 위에서 정리한 메시지 계산 함수와 메시지 집계 함수를 같이 두기만 하면 되는데요. 이 함수들은 모두 선형 연산을 하기 때문에 활성화 함수를 통해 표현력을 높이기 위한 비선형성을 더해주도록 하겠습니다. 이때 ReLU나 시그모이드를 사용할 수 있습니다.

전통적인 GNN 레이어 (1): GCN

\[h_v^{(l)} = \sigma \left( \sum_{u \in N(v)} W^{(l)} \frac{h_u^{(l-1)}}{|N(v)|} \right)\]

위 식에서 시그마가 메시지 집계, 시그마 뒤의 항이 메시지 계산 함수가 됩니다. 각각의 이웃으로부터 시그마 뒷 항을 계산하는데, 메시지 계산 시 $|N(v)|$로 정규화하는 개념입니다. 그리고 메시지 집계는 합 함수를 사용한 다음 시그모이드를 활성화 함수로 사용하였습니다. 그리고 노드 자신 스스로 합에 포함이 됩니다.

전통적인 GNN 레이어 (2): GraphSAGE

GraphSAGE는 GCN을 기반에 둔 모델입니다. GCN과의 차이점은 메시지 집계 함수인데요.

\[h_v^{(l)} = \sigma \left( W^{(l)} \cdot \text{CONCAT} \left( h_v^{(l-1)}, \text{AGG} \left( \left\{ h_u^{(l-1)}, \; \forall u \in N(v) \right\} \right) \right) \right)\]

일단 메시지는 $\text{AGG}(\cdot)$에서 계산합니다. 그리고 메시지 집계를 두 단계에 거쳐서 진행하죠. 우선 이웃 노드로부터 메시지를 집계합니다.

\[h_{N(v)}^{(l)} \leftarrow \text{AGG} \left( \left\{ h_u^{(l-1)}, \; \forall u \in N(v) \right\} \right)\]

그리고 노드 자기 자신과 추가로 집계를 하죠.

\[h_v^{(l)} \leftarrow \sigma \left( W^{(l)} \cdot \text{CONCAT} \left( h_v^{(l-1)}, h_{N(v)}^{(l)} \right) \right)\]

GraphSAGE에서의 이웃 집계

GraphSAGE에서 집계 함수는 세 가지가 있습니다.

• 평균
  • GCN과 동일한 방법으로 이웃들의 가중 평균을 계산합니다.
  • $\text{AGG} = \sum_{u \in N(v)} \frac{h_u^{(l-1)}}{|N(v)|}$
• 풀링(Pooling)
  • 메세지 계산으로 MLP를 사용하고 평균이나 최댓값으로 집계합니다.
  • $\text{AGG} = \text{Mean} \left( \left\{ \text{MLP} (h_u^{(l-1)}), \; \forall u \in N(v) \right\} \right)$
• LSTM
  • LSTM을 이용해서 집계할 때는 순서 불변성에 주의하여 이웃들의 순서를 섞은 다음에 적용합니다.
  • $\text{AGG} = \text{LSTM} \left( \left[ h_u^{(l-1)}, \; \forall \in \pi(N(v)) \right] \right)$

L2 정규화

선택적이지만 모든 레이어의 임베딩 벡터에 L2 정규화를 적용할 수 있습니다.

\[h_v^{(l)} \leftarrow \frac{h_v^{(l)}}{\|h_v^{(l)}\|_2}\]

L2 정규화를 하지 않으면 임베딩 벡터들은 서로 다른 스케일을 갖게 됩니다. 몇몇 경우에 임베딩 벡터에 대한 정규화가 성능 향상을 야기하기도 합니다. 정규화를 하게 되면 모든 벡터는 같은 L2-norm을 갖게 됩니다.

전통적인 GNN 레이어 (3): GAT

Graph Attention Networks (GAT)는 이웃 노드에 대한 중요도를 나타낸 attention weights를 추가한 모델입니다.

\[h_v^{(l)} = \sigma \left( \sum_{u \in N(v)} \alpha_{vu} W^{(l)} h_u^{(l-1)} \right)\]

위 식에서 $\alpha_{vu}$가 attention weights 입니다.

이미 위에서 다룬 GCN과 GraphSAGE는 $\alpha_{uv} = \frac{1}{|N(v)|}$인데, 중요도를 node degree로 두었다고 볼 수 있습니다. 이렇게 정의하면 이웃 노드가 모두 동등하게 중요하게 여겨지게 됩니다. 하지만 당연하게도 모든 이웃 노드는 같은 중요도를 가지지 않습니다. 어텐션을 활용하면 입력 데이터의 중요한 부분에 초점을 맞추고 나머지는 거의 무시합니다. 데이터에서 어떤 부분이 더 중요한지는 상황에 따라 다르고, 이는 학습을 통해서 알 수 있습니다.

어텐션 메커니즘

Attention coefficient

어텐션 메커니즘 $a$의 부산물로써 $a_{vu}$를 계산해봅시다. 우선 노드쌍 $u$와 $v$의 메시지를 기반하여 어텐션 계수 $e_{vu}$를 계산합니다. 이때 $e_{vu}$는 노드 $v$로 가는 $u$의 메시지의 중요도를 말합니다.

\[e_{vu} = a \left(W^{(l)} h_{u^{(l-1)}}, W^{(l)}h_v^{(l-1)} \right)\]

그리고 $e_{vu}$를 정규화하여 최종 어텐션 가중치인 $\alpha_{vu}$에 넣습니다. 이때 $\alpha_{vu}$를 계산할 때 $\sum_{u \in N(v)} \alpha_{vu} = 1$이 되도록 소프트맥스 함수를 사용합니다.

\[\alpha_{vu} = \frac{\exp(e_{vu})}{\sum_{k \in N(v)} \exp(e_{vk})}\]

Weighted sum based on final attention weight

마지막으로 최종 어텐션 가중치를 이용해 가중합을 계산합니다.

\[h_v^{(l)} = \sigma \left( \sum_{u \in N(v)} \alpha_{vu} W^{l} h_{u}^{(l-1)} \right)\]

Attention mechanism is also trained together with weight parameters in an “end-to-end” fashion

여기서 어텐션 메커니즘 $a$는 어떤 것도 가능합니다. 예를 들어 단순한 싱글 레이어 뉴럴 네트워크라고 했을 때 $a$는 가중치 파라미터 $W^{(l)}$과 함께 end-to-end 학습됩니다.

멀티 헤드 어텐션

멀티 헤드 어텐션은 어텐션 메커니즘의 학습 과정을 안정화합니다. 우선 여러 개의 어텐션 점수를 생성합니다.

\[\begin{aligned} h_v^{(l)}[1] &= \sigma\left( \sum_{u \in N(v)} \alpha_{vu}^1 W^{(l)}h_u^{(l-1)} \right) \\ h_v^{(l)}[2] &= \sigma\left( \sum_{u \in N(v)} \alpha_{vu}^2 W^{(l)}h_u^{(l-1)} \right) \\ h_v^{(l)}[3] &= \sigma\left( \sum_{u \in N(v)} \alpha_{vu}^3 W^{(l)}h_u^{(l-1)} \right) \end{aligned}\]

그리고 concatenation이나 합을 이용해서 결과를 집계합니다.

\[h_v^{(l)} = \text{AGG} \left( h_v^{(l)}[1], h_v^{(l)}[2], h_v^{(l)}[3] \right)\]

어텐션 메커니즘의 장점

어텐션 메커니즘을 사용하여 얻는 장점은 서로 다른 이웃이 다른 중요도를 얻게 된다는 점입니다. 뿐만 아니라 다음의 추가적인 장점도 갖고 있습니다.

• 계산 효율성(Computationally efficient)
  • 어텐션 계수 계산은 그래프의 모든 엣지에 대해서 병렬화할 수 있습니다.
• 저장 효율성(Storage efficient)
  • 희소 행렬은 $O(V + E)$ 이상의 공간을 사용하지 않고, 그래프의 크기와 상관 없이 고정적인 파라미터 수를 갖고 있습니다.
• 국소성(Localized)
  • 국소적인 네트워크 이웃에만 의존합니다.
• 귀납 가능성(Inductive capability)
  • Edge-wise 메커니즘과 공유 가능하며 전역적인 그래프 구조에 의존하지 않습니다.

실사례에서의 GNN 레이어

A suggested GNN layer

선형 레이어, 배치 정규화, 드롭아웃, 활성화 함수, 어텐션, 집계 레이어로 이루어지는 기본적인 GNN은 실무에서 좋은 시작점이 됩니다. 각각의 모듈은 여러 도메인에서 유용성이 입증된 바 있습니다. 배치 정규화는 뉴럴 네트워크 학습을 안정시켜주고 드롭아웃은 오버피팅을 방지해줍니다. 어텐션은 메시지의 중요성을 제어할 수 있습니다. 이제 각각의 모듈이 어떻게 활용되는지 확인해보도록 하겠습니다.

배치 정규화(Batch Normalization)

Batch normalization in GNN

배치 정규화의 목적은 뉴럴 네트워크 학습을 안정화하는 것입니다. 노드 임베딩의 배치가 주어졌을 때 평균을 0으로, 분산을 1로 만들어줍니다.

드롭아웃 (Dropout)

Dropout in GNN

드롭아웃은 뉴럴 네트워크가 오버피팅하는 것을 방지하기 위해 사용합니다. 학습 중에는 $p$의 확률로 임의의 뉴런을 꺼버리고 테스트 중에는 모든 뉴런을 학습에 사용합니다. GNN에서는 메시지 함수의 선형 레이어에 드롭아웃을 적용합니다.

활성화 함수(Activation)

활성화 함수로는 ReLU, 시그모이드, Parametric ReLU 등을 사용합니다. Parametric ReLU는 ReLU보다 성능이 더 좋다고 알려져 있습니다.

GNN에 레이어 쌓기

Stacking GNN layers sequentially

일반적으로 GNN을 구축할 때는 GNN 레이어를 순서대로 쌓습니다. 입력값으로는 초기화한 노드 피처 $x_v$를 받고 $L$개의 GNN 레이어를 거친 노드 임베딩 $h_v^{(L)}$ 을 결과로 얻습니다.

레이어 쌓기의 문제

하지만 이렇게 GNN 레이어를 많이 쌓게 되면 오버스무딩 문제(over-smoothing problem) 이 발생합니다. 오버스무딩이란 모든 노드 임베딩이 같은 값으로 수렴하는 문제를 말합니다. 우리가 노드 임베딩을 사용하는 이유는 노드마다 차이를 두기 위함이어서 큰 문제가 됩니다.

Receptive field of k-layer GNN

$k$ 개의 레이어를 사용한 GNN은 각 노드가 $k$-hop neighborhood의 수용 영역(receptive field) 를 가지게 됩니다. 레이어가 많으면 많을 수록 수용 영역은 넓어지게 되고, 임베딩은 수용 영역에 의해 결정됩니다. 만약 두 개의 노드가 매우 많이 겹치는 수용 영역을 가진다면 두 노드의 임베딩은 매우 비슷해집니다. 따라서 많은 레이어를 쌓으면 대부분의 노드가 하나의 수용 영역을 공유하게 되고, 이로 인해 노드 임베딩이 비슷해지는 오버스무딩 문제가 발생하는 것입니다.

이 문제를 해결하기 위해선 GNN 레이어를 쌓을 때 개수를 잘 조절해야 합니다. 레이어의 개수를 조절하기 위해 그래프의 직경과 같은 수용 영역에 대한 정보를 먼저 분석하고, 그보다 조금 더 많은 수의 레이어만을 쌓아야 합니다.

얕은 GNN의 표현력

얕은 GNN의 표현력을 높이는 방법은 무엇일까요? 첫 번째 방법은 GNN 레이어 내의 표현력을 높이는 것입니다. 위에서 다루었지만 변환 함수나 집계 함수는 하나의 선형 레이어에 하나만 들어갑니다. 따라서 우리는 집계 함수나 변환 함수를 조금 더 복잡한 뉴럴 네트워크로 만들 수 있을 것입니다.

Add layers that do not pass messages

두 번째 방법은 메시지를 전달하지 않는 레이어를 추가하는 것입니다. GNN은 반드시 GNN 레이어만 포함할 필요가 없습니다. 예를 들어 GNN 레이어들 앞뒤에 MLP 레이어를 넣을 수도 있습니다. GNN 레이어 앞에 넣을 때는 노드 피처를 인코딩하는 것이 중요할 때가 될 것이고, GNN 레이어 뒤에 넣을 때는 노드 임베딩에 대한 추론이나 변환이 중요할 때가 됩니다. 실제로도 이런 방식으로 레이어를 쌓는 것이 큰 도움이 됩니다.

스킵 커넥션(Skip Connection)

Skip connection for GNN

오버스무딩 문제를 잘 살펴보면 오히려 초기의 GNN 레이어에서 노드 임베딩에서 노드마다의 차이가 더 큰 것을 확인할 수 있습니다. 따라서 초기 레이어의 영향력을 키우기 위해서 GNN에 스킵 커넥션을 추가할 수도 있습니다.

How the skip connection works

스킵 커넥션은 일종의 혼합 모델을 생성합니다. $N$ 개의 스킵 커넥션이 있다면 모두 $2^N$ 개의 경로가 생기죠. 각 경로에는 최대 $N$ 개의 모듈이 있습니다. 우리는 자동적으로 얕은 GNN과 깊은 GNN의 합성 모델을 얻게 됩니다. 스킵 커넥션을 사용함현 일반적인 GCN 레이어는 다음과 같이 바뀝니다.

\[h_v^{(l)} = \sigma \left( \sum_{u \in N(v)} W^{(l)} \frac{h_u^{(l-1)}}{|N(v)|} + h_v^{(l-1)} \right)\]

Directly skip to the last layer

다른 옵션으로는 모든 스킵 커넥션을 집계 레이어 이전으로 보내는 방법이 있습니다.

GNN에서의 그래프 조작

우리는 지금까지 원천 입력 그래프를 연산 그래프로 가정했습니다. 하지만 이 가정을 만족시키기는 쉽지 않습니다. 피처 수준에서는 입력 그래프의 피처가 부족할 수도 있습니다. 구조 수준에서는 그래프가 너무 희소해서 메시지 전달이 충분치 않을 수도 있고, 그래프가 너무 조밀하여 메시지 전달의 비용이 너무 클 수도 있습니다. 또는 그래프가 너무 커서 계산 그래프를 GPU에 적합시키지 못할 수도 있습니다. 따라서 입력 그래프가 임베딩을 위한 최적의 연산 그래프가 될 가능성은 거의 없습니다. 이때 그래프를 조금 조작하여 문제를 해결할 수 있습니다.

• 그래프 피처 조작
  • 입력 그래프의 피처가 부족한 경우 피처 증강(feature augmentation) 수행
• 그래프 구조 조작
  • 그래프가 너무 희소한 경우 가상 노드/엣지를 추가
  • 그래프가 너무 조밀한 경우 메시지 전달 시 이웃을 샘플링
  • 그래프가 너무 큰 경우 임베딩을 계산할 때 서브그래프를 샘플링

그래프 피처 조작

만약 입력 그래프에 노드 피처가 없으면 어떻게 할까요? 사실 이런 경우는 꽤나 흔합니다. 특히 인접 행렬 정보만 있으면 피처가 없게 되죠. 가장 일반적인 방법은 다음과 같으며 각 방법은 장단이 있습니다.

1. 모든 노드에 상수를 부여하기
2. 각 노드에 고유 ID를 부여하고 원 핫 인코딩하기

	상수 노드 피처	원 핫 인코딩 노드 피처
표현력	중간 수준으로 모든 노드의 피처값이 같지만 GNN은 여전히 그래프의 구조를 학습할 수 있음	높은 수준으로 각 노드가 고유의 ID를 갖고 있기 때문에 노드마다의 정보를 저장할 수 있음
새로운 노드에 대한 일반화	새로운 노드에도 일반화하여 적용할 수 있음. 새로운 노드에 대해 같은 상수를 부여하면 됨	새로운 노드에 일반화할 수 없음. GNN이 새로운 노드에 대한 고유 ID를 찾을 수 없음.
계산 비용	1차원 피처만 필요하기 때문에 낮음	노드 개수만큼의 차원이 필요하므로 높음
유즈케이스	어떤 그래프에도 사용 가능하고 유도 학습 설정에도 가능함	작은 그래프에만 가능하며 새로운 노드가 없는 경우에만 가능

Cycle count in GNN

GNN은 특정 구조에 대한 학습이 어렵습니다. 그 예로 그래프 내 순환 구조에 대한 피처를 들 수 있습니다. GNN은 두 그래프에서 $v_1$을 구분하지 못합니다. 결국 두 그래프에서 $v_1$의 degree는 똑같이 2이기 때문입니다. 따라서 연산 그래프는 똑같은 이진 트리를 구성하게 됩니다. 이런 경우 순환 구조의 수를 노드 피처로 추가할 수 있습니다.

Cycle count feature in GNN

순환 구조의 크기를 0부터 시작하여 그 크기를 변수화시키면 됩니다. 첫 번째 그래프는 순환 구조의 크기가 3이므로 네 번째에, 두 번째 그래프는 순환 구조의 크기가 4이므로 다섯 번째에 값을 추가합니다.

이외에도 군집 계수, 페이지랭크(PageRank), 중심성 등 여러 가지 추가 피처를 사용할 수 있습니다.

그래프 구조 조작

가상 노드/엣지 추가

일반적으로 희소한 그래프에 대해서는 가상 노드나 가상 엣지를 추가합니다. 먼저 가상 엣지를 추가할 때 일반적인 접근법은 가상 엣지를 통해 2-hop neighbor를 연결하는 것입니다. 인접 행렬을 이용해 $A + A^2$만 계산해주면 됩니다.

가상 노드의 경우 모든 노드와 연결되도록 추가하면 됩니다. 그렇게 하면 모든 노드는 다른 노드와의 거리가 2가 됩니다. 결국 희소한 그래프에서의 메시지 전달에서 크게 효과를 볼 수 있습니다.

노드 이웃 샘플링

노드 이웃을 샘플링하여 조밀한 그래프에서 학습을 용이하게 할 수 있습니다. 위와 같이 생긴 그래프에서 메시지 전달에 참여하는 노드를 샘플링할 수 있습니다. 예를 들어 A 노드로 메시지를 전달하는 노드로 B와 D를 샘플링한다면 다음과 같습니다.

만약 A 노드로 메시지를 전달하는 노드가 C와 D인 경우라면 또 다른 그림이 됩니다.

이렇게 하더라도 모든 이웃이 사용되는 경우와 유사한 임베딩을 얻을 수 있습니다. 하지만 계산 비용을 확실하게 줄일 수 있고, 실제 시나리오에서도 좋은 성능을 보입니다.