그래프 머신러닝: (5-2) GNN: 일반화된 집계 및 업데이트

(GRL) GNN: Generalized Aggregation and Update

Hamilton,W.L. Graph Representation Learning. 2020

Basic GNN은 여러 가지 방법으로 개선되고 일반화될 수 있다. 여기서는 aggregation과 update 작업을 일반화하고 개선할 수 있는 방법에 대해 알아보자.

Generalized Neighborhood Aggregation

Neighborhood Normalization

가장 기본적인 이웃 집계(aggreagation)는 단순히 이웃 임베딩의 합을 취하는 것이나, 이 방식은 불안정하고 노드 degree에 매우 민감할 수 있다. 예를 들어, 노드 \(u\)가 노드 \(u'\)보다 \(100\)배 많은 이웃(즉, 훨씬 더 높은 차수)이 있다고 가정 할 때 \(\left\| \sum_{v \in \mathcal{N}(u)} h_v \right\| \gg \left\| \sum_{v' \in \mathcal{N}(u')} h_{v'} \right\|\)라고 합리적으로 기대할 수 있다. 이러한 급격한 크기 차이로 인해 수치적 불안정성과 최적화의 어려움이 발생할 수 있다.

해결 방법으로 관련된 포함된 노드 degree에 따라 집계를 단순히 정규화하는 방법이 있다.

• 가장 단순한 방법은 합 대신 평균화 하는 것이다:

\[ \mathbf{m}_{\mathcal{N}(u)} = \frac{\sum_{v \in \mathcal{N}(u)} \mathbf{h}_v}{|\mathcal{N}(u)|} \]

• Kipf and Welling [2016a]에서 사용된 다음과 같은 대칭 정규화(symmetric normalization)와 같은 다른 정규화 factor도 있다:

\[ \mathbf{m}_{\mathcal{N}(u)} = \sum_{v \in \mathcal{N}(u)} \frac{\mathbf{h}_v}{\sqrt{|\mathcal{N}(u)| |\mathcal{N}(v)|}} \]

특히, 대칭 정규화 집계와 기본 GNN 업데이트 함수를 결합하면 spectral graph convolution의 1차(first-order) 근사(approximation)가 생성된다.

Graph Convolutional Networks (GCNs)

가장 널리 사용되는 그래프 신경망 모델 중 하나인 그래프 컨볼루션 네트워크(GCN)는 대칭 정규화 집계와 self-loop 업데이트 접근 방식을 사용한다.

GCN은 메시지 전달 함수를 다음과 같이 정의한다:

\[\mathbf{h}^{(k)}_u = \sigma \left( \mathbf{W}^{(k)} \sum_{v \in \mathcal{N}(u) \cup \{u\}} \frac{\mathbf{h}_v}{\sqrt{|\mathcal{N}(u)| |\mathcal{N}(v)|}} \right)\]

정규화는 꼭 필요할까?

• GNN을 사용할 때 안정적이고 강력한 성능을 얻으려면 적절한 정규화가 필수적일 수 있으나, 정규화로 인해 정보가 손실될 수도 있다는 점에 유의해야 한다.
• 예를 들어, 정규화 후에는 학습된 임베딩을 사용하여 서로 다른 degree의 노드를 구별하는 것이 어렵거나 불가능할 수 있으며, 다양한 다른 구조 그래프 특징이 정규화에 의해 가려질 수 있다.
• 일반적으로 정규화는 노드 피쳐 정보가 구조적 정보보다 훨씬 더 유용하거나, 최적화 중에 불안정을 초래할 수 있는 노드 degree 범위가 매우 넓은 작업에서 유용하다.

집합 집계(Set Aggregators)

이웃 집계 연산은 기본적으로 집합 함수(set function)이다. 이웃 임베딩 집합 {\(\mathbf{h}_v, \forall v \in \mathcal{N}(u)\)}이 주어지고, 이를 싱글 벡터 \(\mathbf{m}_{\mathcal{N}(u)}\)에 매핑해야 한다. {\(\mathbf{h}_v, \forall v \in \mathcal{N}(u)\)}이 집합이라는 사실은 실제로 매우 중요하다: 노드 이웃에는 자연적인 순서가 없으며, 따라서 정의하는 모든 집계 함수는 순열 불변(permutation invariant)이어야 한다.

Set Pooling(집합 풀링)

집계 함수를 정의하는 한 가지 원칙적인 접근 방식은 순열 불변 신경망(permutaion invariant neural network) 이론을 기반으로 한다.

예를 들어, Zaheer et al. [2017]은 다음 형식의 집계 함수가 범용적 집합 함수 근사기(universal set function approximator)임을 보여준다:

\[\mathbf{m}_{\mathcal{N}(u)} = MLP_{\theta} \left( \sum_{v \in \mathcal{N}(u)} MLP_{\phi} (\mathbf{h}_v) \right)\]

여기서, \(MLP_\theta\)는 학습가능 파라미터 \(\theta\)를 갖는 arbitraily deep multi-layer perceptron를 지칭한다.

즉, Zaheer et al. [2017]는 임베딩 집합을 단일 임베딩에 매핑하는 모든 순열 불변 함수는 위 방정식의 모델에 의해 임의의 정확도로 근사 될 수 있다.

단, 위 방정식을 기반으로 하는 집합 풀링(pooling) 접근 방식은 성능이 약간 향상되지만 사용되는 MLP의 깊이에 따라 과적합의 위험도 증가한다. 집합 풀링을 사용하는 경우 과적합의 위험을 감수할 정도로 overparameterized 되지 않기 때문에 단일 은닉층만 있는 MLP를 사용하는 것이 일반적이다.

Janossy Pooling

이웃 집계에 대한 풀링 방식을 설정하는 것은 기본적으로 집계 아키텍처 위에 MLP 계층을 추가하는 것으로, 이는 간단하지만 GNN의 용량을 증가시킨다. Janossy 풀링은 단순히 이웃 임베딩의 합계 또는 평균을 취하는 것보다 더 강력하다.

이웃 집계는 노드 이웃의 순서가 없기 때문에 순열 불변 함수를 사용해야 한다. 집합 풀링 접근 방식에서는 임베딩 집합을 단일 벡터로 줄이기 위해 합계, 평균 또는 요소별 최대값에 의존하여 순열 불변성을 달성했다. 이러한 감소를 피드포워드 신경망(즉, MLP)과 결합하여 모델을 더욱 강력하게 만들었다.

Janossy 풀링은 완전히 다른 방식을 사용한다. 순열에 민감한 함수를 적용하고 가능한 많은 순열에 대해 결과의 평균을 구한다.

\[m_{\mathcal{N}(u)} = MLP_{\theta} \left( \frac{1}{|\Pi|} \sum_{\pi \in \Pi} \rho_{\phi} (h_{v_1}, h_{v_2}, ..., h_{v_{|\mathcal{N}(u)|}}) \pi_j \right)\]

\(\pi_i \in \Pi\)는 permutation function을 나타내며, 집합 \(\{\mathbf{h}_v, \forall v \in \mathcal{N}(u)\}\)을 시퀀스 \((\mathbf{h}_{v_1},\mathbf{h}_{v_2}, \dots, \mathbf{h}_{v_{|\mathcal{N}(u)|}})_{\pi_i}\)로 매핑한다.

즉, \(\pi_i \in \Pi\)는 정렬되지 않은 이웃 임베딩 집합을 가져 와서 임의의 순서에 따라 임베딩을 순서대로 배치한다.

여기서, \(\rho_\pi\)는 신경망 같은 함수이며, 주로 LSTM을 쓴다.

Janossy 풀링은 다음 두 가지 접근 방식 중 하나를 사용한다: 1. Aggregator를 적용할 때마다 가능한 순열의 무작위 하위 집합을 샘플링하고 해당 무작위 하위 집합에 대해서만 합산한다. 2. 이웃 집합에서 노드의 canonical 순서를 사용한다(예: degree에 따라 노드를 내림차순으로 정렬).

이웃 어텐션(attention)

일반적인 형태의 집합 집계 외에도 GNN의 집계 층을 개선하기 위한 방법은 ’attention’이다[Bahdanau et al., 2015]. 각 이웃에 주의 가중치 또는 중요도를 할당하는 것이며, 이는 집계 단계에서 이 이웃의 영향력을 평가하는 데 사용된다.

Graph Attention Network (GAT) (Veličković et al. [2018])

\[m_{\mathcal{N}(v)}(u) = \sum_{v \in \mathcal{N}(u)} \alpha_{u,v} h_v\]

여기서, \(\alpha_{u,v}\)는 이웃 \(v \in \mathcal{N}(u)\)에 대한 어텐션을 나타낸다. GAT 논문에서 어텐션 가중치는 다음과 같이 정의한다:

\[\alpha_{u,v} = \frac{\exp(a^T [Wh_u \, \oplus \, Wh_v])}{\sum_{v' \in \mathcal{N}(u)} \exp(a^T [Wh_u \, \oplus \, Wh_{v'}])}\]

여기서, \(a\)는 학습 가능한 어텐션 벡터, \(W\)는 학습 가능한 행렬, \(\oplus\)는 concatenation operation이다.

또한, 여러 attention head를 더해 사용할 수 있다. Multi-head attention GNN 모델은 transfomer 아키텍처와 밀접한 관련이 있다. 사실, 기본 transfomer 레이어는 GNN이 완전히 연결된 그래프를 입력으로 수신한다고 가정하면 multi-head attention을 사용하는 GNN 레이어와 정확히 동일하다. 그러나 높은 시간복잡도를 요구한다는 단점이 있다.

Attention를 추가하는 것은 GNN 모델의 표현 능력을 증가시키는 데 유용한 전략이며, 특히 일부 이웃이 다른 이웃보다 더 많은 정보를 제공할 수 있음을 나타내는 사전 지식이 있는 경우에 유용하다.

Generalized Update Methods

지금까지 업데이트 작업이 노드의 현재 임베딩과 이웃의 메시지를 선형 조합하는 기본 GNN 접근 방식과 이웃 집계를 수행하기 전에 그래프에 자체 루프를 추가하는 자체 루프 접근 방식을 살펴보았다. 이제 업데이트 연산자에 대한 보다 다양한 일반화를 알아본다.

일반화된 업데이트 방법으로 해결할 수 있는 GNN의 일반적인 문제 중 하나는 오버 스무딩(over-smoothing)이다. 오버 스무딩은 GNN 메시지 전달을 여러 번 반복한 후 그래프의 모든 노드에 대한 표현이 서로 매우 유사해질 수 있다는 것이다. 이러한 경향은 기본 GNN 모델 및 self-loop 업데이트 접근 방식을 사용하는 모델에서 특히 일반적이다.

Concatenation and Skip-Connections

직관적으로, 메시지 전달 중에 노드 이웃에서 집계되는 정보가 업데이트된 노드 표현을 지배하기 시작하는 경우 오버 스무딩를 예상할 수 있다. 이러한 경우, 업데이트된 노드 표현(\(h^{k+1}_u\))은 이전 레이어(\(h^k_u\))의 노드 표현을 희생하여 이웃(\(\mathbf{m}_{\mathcal{N}(u)}\))에서 집계된 수신 메시지에 너무 강하게 의존한다. 이 문제를 완화하는 방법은 벡터 연결(Concatenation)이나 skip-connection을 사용해 업데이트 단계 중에 전달된 이전 메시지 라운드의 정보를 직접 보존하는 것이다.

가장 간단한 skip-connection update 중 하나는 메시지 패싱 중에 더 많은 노드 수준의 정보를 보존하기 위해 연결(concatenation)을 사용하는 것이다.

\[\text{UPDATE}_\text{concat}(h_u, m_{\mathcal{N}(u)}) = [\text{UPDATE}_\text{base}(h_u, m_{\mathcal{N}(u)}) \oplus h_u]\]

concatenation 외에도 선형 보간(interpolation) 방법과 같은 다른 형태의 skip-connection을 사용할 수도 있다.

\[\text{UPDATE}_\text{interpolate}(h_u, m_{\mathcal{N}(u)}) = \alpha_{1} \circ \text{UPDATE}_{\text{base}}(h_u, m_{\mathcal{N}(u)}) + \alpha_{2} \odot h_u\]

여기서, \(\alpha_1, \alpha_2 \in {[0,1]}^d\)는 gating vector(\(\alpha_2 = 1 - \alpha_1\))이며, \(\circ\)는 요소별 곱이다.

Gated Updates

또한, 집계 함수가 이웃으로부터 observation을 수신한 다음 각 노드의 hidden state를 업데이트하는 데 사용된다는 관점도 있다. observation을 기반으로 RNN 아키텍처의 hidden state를 업데이트하는 방법을 적용한다.

\[h_u^{(k)} = \text{GRU}(h_u^{(k-1)}, m^{(k)}_{\mathcal{N}(u)})\]

GRU cell 대신 LSTM cell에 기반할 수도 있다.

이 RNN 스타일의 업데이트의 파라미터는 항상 노드 간에 공유된다. 즉, 동일한 LSTM 또는 GRU 셀을 사용하여 각 노드를 업데이트한다.

이러한 게이트 업데이트는 deep GNN 아키텍처(예: 10개 이상의 레이어)를 용이하게 하고 over-smoothing를 방지하는 데 효과적이다. 일반적으로 프로그램 분석[Li et al., 2015] 또는 조합 최적화[Selsam et al., 2019]와 같이 예측 작업에 그래프의 전역 구조에 대한 복잡한 추론이 필요한 GNN 적용에 가장 유용하다.

Jumping Knowledge Connections

이전 섹션에서는 GNN의 최종 레이어의 출력을 사용하고 있다고 암시적으로 가정했다. 즉, 다운스트림 작업에서 사용하는 노드 표현 \(z_u\)가 GNN의 최종 레이어 노드 임베딩과 같다고 가정했다.

\[z_u = h_u^{(K)}, \quad \forall u \in \mathcal{V}\]

이러한 가정은 많은 GNN 방식에서 사용되었으며, 이 전략의 한계점으로 인한 oversmoothing을 제한하기 위해 residual 및 gated update가 많이 필요했다.

보완 전략으로 최종 계층 출력만 사용하는 것이 아니라 메시지 전달의 각 계층에서 표현을 활용하는 방법이 있다.

\[z_u = f_{JK}\left( h_u^{(0)} \oplus h_u^{(1)} \oplus \ldots \oplus h_u^{(K)} \right)\]

여기서, \(f_{JK}\)는 임의의 미분 함수로, jumping knowledge connection을 더한 함수이다. 많은 응용 분야에서 함수 \(f_{JK}\)는 단순히 항등 함수로 정의될 수 있으며, 이는 각 계층의 노드 임베딩을 연결하기만 하면 된다는 것을 의미한다. Xu et al. [2018]은 최대 풀링 접근 방식 및 LSTM 어텐션 레이어와 같은 다른 옵션도 고려한다.

참고자료

[1] Hamilton, W. L. (2020). Graph Representation Learning. Morgan & Claypool Publishers.