Chapter 5. The Graph Neural Network Model

Graph Representation Learning Book 읽고 정리하기 시리즈 중 네 번째 이야기. 부디 완주하게 기도해주세요 !

5.0 Gentle Introduction

Chapter 3까지 배웠던 노드 임베딩 기법들은 각 노드의 속성값 (attribute 또는 feature)을 사용하지 않는다는 한계점이 있었다. 이번 챕터에서는 그래프의 구조 뿐만 아니라 노드의 속성값도 고려하여 노드 임베딩 벡터를 만들 수 있는 그래프 신경망 (Graph Neural Network)에 대해서 알아본다.

지금까지 우리는 그래프 데이터를 머신러닝 모델에 입력하기 위해 많은 노력을 해왔다. 지금부터는 딥러닝에 그래프 데이터를 입력할 수 있는 방법들에 대해 알아본다. 다층 퍼셉트론 (Multilayer perceptron, MLP)은 정해진 크기의 벡터를 입력 받는다. MLP에 그래프 $\mathcal{G}=(\mathcal{V}, \mathcal{E})$를 입력할 수 있는 가장 간단한 방법은 인접행렬 $\mathbf{A}$를 쭉 펼쳐서 벡터로 만드는 것이다. 즉, \[\mathbf{z}_{\mathcal{G}}=\text{MLP}(\mathbf{A}[1] \oplus \mathbf{A}[2] \oplus \cdots \oplus \mathbf{A}[| \mathcal{V}|]), \quad \quad (5.1)\]

이때, $\mathbf{A}[u] \in \mathbb{R}^{\mid \mathcal{V} \mid}$는 인접행렬의 $u$번째 행이고, $\oplus$는 벡터를 한 줄로 쭉 연결 (concatenate)하는 연산이다. $\mathbf{z}_{\mathcal{G}}$는 그래프 $\mathcal{G}$를 MLP에 통과시켜서 얻은 결과물이다.

여기서 가장 큰 문제점은 노드에 어떤 순서를 부여하여 인접행렬을 만들었다는 것이다. 노드의 순서를 뒤섞으면 인접행렬도 뒤섞인 순서에 맞게 바뀌게 된다. 하지만 인접행렬이 나타내는 그래프는 여전히 동일하다. 같은 그래프를 나타내지만 노드 순서만 바뀐 인접행렬을 상상해보자. 이 인접행렬을 MLP에 통과시킬 경우 원래와 다른 결과를 출력해줄 것이다. 그래서 식 $(5.1)$과 같은 전략은 그래프를 상대로는 적합하지 않다.

우리는 노드 순서가 뒤바뀌어도 여전히 같은 결과를 출력해주는 함수를 원한다. 아니면 적어도 결과물의 순서를 뒤바꿔서 원래의 결과물로 만들어 줄 수 있는 함수를 원한다. 첫 번째 같은 함수를 permutation invariant 함수라고 부르고 두 번째 함수는 permutation equivariant 함수라고 부른다.

행렬 $\mathbf{P}$를 permutation 행렬이라고 하자. 어떤 행렬 $\mathbf{A}$에 permutation 행렬을 왼쪽에 곱하면 $\mathbf{P}\mathbf{A}$는 $\mathbf{A}$에서 행의 순서만 바뀐 행렬이 된다. 반대로 오른쪽에 곱하면 $\mathbf{A}$에서 열의 순서만 바뀐 행렬이 된다.

한편, 그래프의 경우 노드의 순서가 바뀌게 되면 인접행렬의 행과 열이 모두 바뀌게 된다. 따라서 인접행렬 $\mathbf{A}$에서 노드 순서가 바뀔 경우 새로운 인접행렬은 $\mathbf{P}\mathbf{A}\mathbf{P}^\top$가 된다. 그래프에 대해서 permutation invariant한 함수 $f$는 다음의 성질을 만족시킨다. (이때, 함수 $f:\mathbb{R}^{\mid \mathcal{V} \mid \times \mid \mathcal{V} \mid}\rightarrow \mathbb{R}^{\mid \mathcal{V} \mid}$는 인접행렬을 입력 받아서 노드마다 어떤 값을 주는 벡터를 출력해주는 함수이다.) \[f(\mathbf{P} \mathbf{A} \mathbf{P}^\top)=f(\mathbf{A}) \quad \quad (\text{Permutation Invariance}) \quad \quad (5.2)\]

즉, 노드 순서가 뒤바뀐 인접행렬을 넣었을 때 함수값이 그냥 인접행렬을 넣었을 때의 함수값과 똑같다는 것이다. 한편, permutation equivariant한 함수 $f$는 다음의 성질을 만족시킨다. \[f(\mathbf{P} \mathbf{A} \mathbf{P}^\top)=\mathbf{P}f(\mathbf{A}) \quad \quad (\text{Permutation Equivariant}) \quad \quad (5.3)\]

즉, 노드 순서를 바꿨던대로 $f(\mathbf{A})$의 원소의 순서를 바꿔준 것과 $f(\mathbf{P}\mathbf{A}\mathbf{P}^\top)$이 같다는 것이다. 정리하자면, 우리는 permutation invariant한 함수나 아니면 적어도 permutation equivariant한 성질을 같는 딥러닝 모델을 고려해야 한다.

5.1 Neural Message Passing

지금까지 등장한 GNN 모델들은 정말 다양한 동기로부터 만들어졌다. 하지만 그들 모두가 공유하고 있는 한 가지 구조가 있다. 바로 신경망 메세지 전달 (Neural Message Passing) 구조이다. 신경망 메세지 전달이란 뉴럴 네트워크를 통하여 노드끼리 메세지 벡터를 교환하는 것을 말한다.

5.1.1 Overview of the Message Passing Framework

노드 $u$의 $k$ 번째 hidden state 벡터를 $\mathbf{h}^{(k)}_u$라고 하자. $k+1$ 번째 hidden state $\mathbf{h}^{(k+1)}_u$는 노드 $u$의 이웃 노드로부터 전달 받은 정보들을 취합 (AGGREGATE)하고 업데이트 (UPDATE)하여 만들어진다. 즉, \[\begin{matrix} \mathbf{h}^{(k+1)}_u &=& \text{UPDATE}^{(k)} \;(\mathbf{h}^{(k)}_u, \text{AGGREGATE}^{(k)}(\{ \mathbf{h}^{(k)}_v:v \in \mathcal{N}(u) \}) & (5.4) \\ & = & \text{UPDATE}^{(k)} \;(\mathbf{h}^{(k)}_u, \mathbf{m}^{(k)}_{\mathcal{N}(u)}) & (5.5) \end{matrix}\]

이때, AGGREGATE와 UPDATE는 임의의 미분 가능한 함수이다. AGGREGATE 함수와 UPDATE 함수를 어떻게 선택하느냐에 따라서 GNN 알고리즘이 다양하게 구분될 수 있다. 두 함수에 대한 다양한 예시를 이번 장에서 마주치게 될 것이다. $\mathbf{m}_{\mathcal{N}(u)}$은 노드 $u$의 이웃 노드의 정보를 취합하여 만든 메세지 벡터이다.

우리는 먼저 $k=0$일 때 각 노드 $u$의 임베딩 벡터를 $u$의 feature 벡터로 설정한다. 즉, $\mathbf{h}^{(0)}_u=\mathbf{x}_u, \; \forall u \in V$ 이다. 다음으로 다음의 신경망 메세지 전달을 반복한다. 각 $k$번 째 레이어 (또는 반복이라고도 말함)에서 하는 일은 다음과 같다.

• AGGREGATE 함수는 $u$의 이웃 노드 $\mathcal{N}(u)$들의 hidden state 집합을 입력 받아서 메세지 벡터 $\mathbf{m}^{(k)}_{\mathcal{N}(u)}$를 만든다.
• UPDATE 함수는 메세지 벡터 $\mathbf{m}^{(k)}_{\mathcal{N}(u)}$와 노드 $u$의 $k$ 번째 hidden state $\mathbf{h}^{(k)}_u$를 입력 받아서 hidden state를 업데이트한다.

위의 설명에서 한 가지 주목해야 할 점은 AGGREGATE 함수가 $\mathcal{N}(u)$들의 hidden state 집합을 입력 받는다는 것이다. 한 집합 안에서 원소들의 순서가 뒤섞여도 여전히 같은 집합이다. 따라서 AGGREGATE 함수는 입력 받는 hidden state들의 순서에 상관 없이 일정한 결과를 계산해줘야 한다 (permutation invariance). 또는 최소한 계산된 결과를 다시 뒤섞어서 순서를 맞춰줄 수 있어야 한다(permutation equivariance).

$K$번의 메세지 반복을 마치고 얻은 각 노드 $u$의 임베딩 벡터 $\mathbf{h}^{(K)}_u$를 노드 $u$의 임베딩 벡터로 사용하게 된다. 즉, $\mathbf{z}_u=\mathbf{h}^{(K)}_u, \; \forall u \in V$이다.

5.1.2 Motivations and Intuitions

GNN에서 메세지 전달을 한 번 진행하면 한 노드가 이웃 노드들의 정보를 반영하여 벡터를 만들게 된다. 메세지 전달을 두 번 진행하면 한 노드에 대하여 이웃 노드의 이웃 노드의 정보까지 반영하여 임베딩 벡터가 만들어지게 된다. 이렇게 메세지 전달이 많이 반복될 수록 한 노드에 대하여 더 멀리 떨어진 이웃 노드의 정보를 반영하여 벡터를 만들 수 있게 된다.

그럼 어떤 정보를 반영하는 것일까? 노드 $u$의 $k$ 번째 hidden state $\mathbf{h}^{(k)}_u$는 크게 두 가지 정보를 반영하게 된다.

• 그래프 안의 구조적인 정보. $\mathbf{h}^{(k)}_u$는 노드 $u$의 $k$-hop 이웃 노드 정보를 반영하고 있다.
• feature 기반 정보: $\mathbf{h}^{(k)}_u$은 노드 $u$의 $k$-hop 이웃 노드의 feature 벡터 정보를 반영하고 있다.

이웃한 데이터로부터 feature 벡터를 취합한다는 점에서 합성곱 신경망 (CNN)과 유사하다고 볼 수 있다. CNN은 정해진 크기의 패치 안의 feature 정보를 취합 (합성곱)한다는 점과 GNN은 이웃 노드의 정보를 취합한다는 점에서 차이가 있다.

The Basic GNN

이번 장에서는 가장 간단한 AGGREGATE 함수와 UPDATE 함수를 사용하여 기초적인 GNN 모델을 만들어 볼 예정이다. 다음과 같이 $k$ 번째 레이어에서의 GNN 메세지 전달식을 생각해보자. (앞으로 이 모델을 GNN 기초 모델이라고 부르겠다.) \[\mathbf{h}^{(k)}_u=\sigma\left(\mathbf{W}^{(k)}_{\text{self}}\mathbf{h}^{(k-1)}_u+\mathbf{W}^{(k)}_{\text{neigh}}\sum\limits_{v \in \mathcal{N}(v)}\mathbf{h}^{(k-1)}_v+\mathbf{b}^{(k)}\right), \quad \quad (5.7)\]

이때, $\mathbf{W}^{(k)}_{\text{self}}, \mathbf{W}^{(k)}_{\text{neigh}} \in \mathbb{R}^{d^{(k)} \times d^{(k-1)}}$는 학습 가능한 파라미터로 이루어진 행렬이다. $d^{(k-1)}$차원 hidden state 벡터들을 $d^{(k)}$차원 벡터로 변환해주는 역할을 한다. $\sigma$ 함수는 벡터를 입력 받아 원소마다 비선형함수를 적용하는 함수이다. 대표적으로 tanh나 ReLU이 있을 것이다. $\mathbf{b}^{(k)} \in \mathbb{R}^{d^{(k)}}$는 편향 벡터 (bias term)로 학습 가능한 파라미터 벡터이다. 편향 벡터는 표기의 편의를 위해 생략해주기도 하지만, 실제 구현에서는 큰 역할을 한다.

• 파라미터 행렬과 편향 벡터를 $k$에 따라 구분지었지만, 매 $k$마다 같은 파라미터 행렬과 편향 벡터를 공유하여 사용해주기도 한다.

식 $(5.7)$에서 이웃 노드들의 hidden state들을 단순 합해주는 것이 바로 AGGREGATE 함수이다. 즉, \[\mathbf{m}^{(k)}_{\mathcal{N}(u)}=\text{AGGREGATE}^{(k)}\left(\{ \mathbf{h}^{(k-1)}_v:v \in \mathcal{N}(u) \}\right)=\sum\limits_{v \in \mathcal{N}(u)}\mathbf{h}^{(k-1)}_v, \quad \quad (5.8)\]

한편, UPDATE 함수는 노드의 이전 hidden state 벡터와 메세지 벡터를 각각 변환해주고 편향 벡터와 함께 더해주어 비선형 함수를 적용시키는 함수이다. 즉, \[\text{UPDATE}^{(k)} \;(\mathbf{h}^{(k)}_u, \mathbf{m}^{(k)}_{\mathcal{N}(u)})=\sigma\left(\mathbf{W}^{(k)}_{\text{self}}\mathbf{h}^{(k-1)}_{u}+\mathbf{W}^{(k)}_{\text{neigh}}\mathbf{m}^{(k)}_{}+\mathbf{b}^{(k)}\right), \quad \quad (5.9)\]

5.1.4 Message Passing with Self-loops

GNN 모델을 조금 더 간략하게 만들기 위한 방법으로 노드마다 자기 자신으로 가는 셀프 루프를 추가해주는 방법이 있다. 셀프 루프를 추가하면 자신의 이웃 노드에 자신도 포함되게 된다. 따라서 자신의 hidden state 벡터를 AGGREGATE 함수에서 사용할 수 있게 된다. 그렇게 되면 자신의 hidden state 벡터와 메세지 벡터를 합쳐주는 UPDATE 함수를 생략해도 된다. 즉, \[\mathbf{h}^{(k)}_u=\text{AGGREGATE}\left(\{ \mathbf{h}^{(k-1)}_v:v \in\mathcal{N}(u) \cup \{u\}\}\right), \quad \quad (5.12)\]

AGGREGATE 함수가 $\mathcal{N}(u) \cup {u}$을 대상으로 계산을 하겠다는 것이다. 물론, 자기 자신의 정보와 이웃 노드의 정보에 각각 다른 연산을 취해주는 원래 버전보다는 모델의 표현력 (expressivity)이 감소한다는 단점이 있지만, 반대로 말하면 오버피팅을 방지해줄 수 있다는 것이기도 하다. 셀프 루프를 추가해서 GNN을 수행하는 기법들을 앞으로 셀프 루프 GNN (self-loop GNN)으로 부를 것이다.

예를 들어 식 $(5.7)$에서 셀프 루프를 추가한다는 것은 $\mathbf{W}_{\text{self}}$와 $\mathbf{W}_{\text{neigh}}$을 서로 같은 파라미터 행렬로 사용하는 것과 동일한 것으로 볼 수 있다 (노드의 hidden state 벡터와 메세지 벡터에 정확히 동일한 연산을 취해주기 때문이다.). 이를 그래프 단위 메세지 전달식으로 나타내면 다음과 같다. \[\mathbf{H}^{(k)}=\sigma\left((\mathbf{I}+\mathbf{A})\mathbf{H}^{(k-1)}\mathbf{W}^{(k)}\right). \quad \quad (5.13)\]

5.2 Generalized Neighborhood Aggregation

식 $(5.7)$은 기초적인 GNN 모델이지만 꽤 좋은 성능을 보일 뿐만 아니라 이론적으로도 연구가 잘 되어 있다. 하지만 우린 아직 목마르다. 이번 섹션에서는 다양한 AGGREGATE 함수에 대해 알아볼 것이다.

5.2.1 Neighborhood Normalization

GNN 기초 모델에서 사용한 AGGREGATE 함수 (식 $5.8$)는 이웃 노드들의 이전 hidden state들을 모두 더해준 것이였다. 그럼 이웃이 많은 노드의 hidden state 벡터는 자연스럽게 크기가 커질 것이다. 이는 GNN 모델을 학습시킬 때 수렴을 저해할 수 있다. 만약 노드 $u$의 차수가 노드 $u’$보다 100배 더 많다고 생각해보자. 그럼 $\lVert \sum_{v\in\mathcal{N}(u)}\mathbf{h}_v \rVert » \lVert \sum_{v’\in\mathcal{N}(u’)}\mathbf{h}_{v’} \rVert$일 것이다. 벡터의 크기가 큰 영역은 다른 영역보다 그레디언트의 스케일이 크기 때문에 안정적인 최적화를 저해할 수 있다.

생각해볼 수 있는 가장 쉬운 해결 방법은 식 $(5.8)$을 노드 차수로 나눠주는 것이다. 즉, \[\mathbf{m}_{\mathcal{N}(u)}=\frac{\sum_{v \in \mathcal{N}(u)}\mathbf{h}_v}{\mid \mathcal{N}(u) \mid} \quad \quad (5.14)\]

다른 해결 방법은 Kipf and Welling, 2016a [4]에서 제안했던 symmetric normalization 을 사용하는 것이다. 즉, \[\mathbf{m}_{\mathcal{N}(u)}=\sum\limits_{v \in \mathcal{N}(u)}\frac{\mathbf{h}_v}{\sqrt{\mid \mathcal{N}(u) \mid \mid \mathcal{N}(v) \mid}} \quad \quad (5.15)\]

책에서는 symmetric normalization과 GNN 기초 모델의 UPDATE 함수 (식 $5.9$)를 합친 것이 spectral graph convolution에 대한 1차 근사치라는 것도 언급하고 있다.

어떤 문제에서는 차수가 높은 노드가 의외로 유용하지 않을 수 있다. 예를 들어, 논문 인용 네트워크 안에서 논문들을 군집화하는 문제를 생각해보자. 저명한 논문은 분야를 가리지 않고 인용이 많이 되기 때문에 군집화할 때 썩 유용한 정보는 아닐 것이다. 이런 관점에서는 정규화를 하는 것이 타당해보인다.

하지만, 그렇다고 정규화가 무조건 좋은 것은 아니다. 정규화를 하면 정보 손실이 발생한다. 정규화를 포함한 GNN으로 노드 임베딩을 한다고 생각해보자. 그럼 노드들의 차수와 관련된 특징들이 무시된채로 임베딩 벡터가 만들어질 수 있다. 사실, GNN 기초 모델에 식 $(5.14)$의 정규화를 적용하는 것보다 그냥 식 $(5.8)$의 AGGRAGATE를 사용하는 것이 더 좋다고 한다. 이와 관련된 이론적인 내용들은 Chapter $7$에서 다뤄볼 예정이라고 한다.

그럼 도대체가 정규화를 하라는건가 말라는건가. 정답이 딱 정해져 있지는 않지만, 그래프의 구조적인 특징들보다 노드의 속성 벡터가 더 중요한 경우 정규화가 유용하다고 한다. 또는 노드 차수 때문에 모델 학습이 잘 안 될 경우도 정규화를 하는게 좋다고 한다.

5.2.2 Set Aggregators

섹션 $5.2.1$에서는 정규화 관점에서 AGGREGATE 함수를 바라보았다면, 이번 섹션에서는 permutation invariant 관점에서 AGGREGATE 함수를 다뤄볼 것이다. AGGREGATE 함수는 집합 $\{ \mathbf{h}_v : v \in \mathcal{N}(u) \}$를 입력 받아서 메세지 벡터 $\mathbf{m}_{\mathcal{N}(u)}$를 출력해준다. 여기서 주목해야할 점은 집합을 입력 받는다는 것이다. 집합은 원소의 순서를 아무리 뒤죽박죽 섞어도 여전히 같은 집합이다. 따라서 AGGREGATE 함수는 집합 안의 순서가 달라지더라도 같은 결과를 출력해줘야 한다. 이와 같은 성질은 permutation invariant라고 한다.

Set pooling

Universal approximation theorem에 의하면 다층퍼셉트론 (MLP)을 사용하여 모든 함수에 근사할 수 있다. 대충 말하자면 이론적으로 MLP를 사용하여 모든 함수를 만들어 낼 수 있다는 것이다. 이와 유사하게 아래 식 $(5.17)$의 AGGREGATE 함수를 사용하면 이론적으로 모든 permutation invariant 함수에 근사할 수 있다고 한다. \[\mathbf{m}_{\mathcal{N}(u)}=\text{MLP}_{\theta}\left(\sum\limits_{v \in \mathcal{N}( u)}\text{MLP}_\phi(\mathbf{h}_v) \right) \quad \quad (5.17)\]

이웃 노드 $v \in \mathcal{N}(u)$ 마다 hidden state $\mathbf{h}_v$를 $\text{MLP}_\phi$에 통과시켜 $\text{MLP}_\phi(\mathbf{h}_v)$를 얻는다. 그리고 모든 $\text{MLP}_\phi(\mathbf{h}_v)$를 더해준 것을 또 다른 $\text{MLP}_\theta$에 통과시키는 행위를 하면 모든 permutation invariant 함수에 근사할 수 있다는 것이다.

식 $(5.17)$에 있는 덧셈 $\sum_{v \in \mathcal{N}(u)}$이 permutation invariant한 연산이다. $a+b+c$ 나 $a+c+b$, $b+a+c$ 등 더하기 순서를 바꾼다고 해서 결과가 달라지지 않기 때문이다. 따라서 hidden state의 순서가 어떻게 되어 있든 $\sum_{v \in \mathcal{N}(u)}$을 통과하고 나면 모두 같은 벡터가 된다. 따라서, 식 $(5.17)$의 AGGREGATE 함수는 permutation invariant 하다. 식 $(5.17)$에서 덧셈 대신 element-wise 최대값이나 최소값 등 다른 permutation invariant한 연산을 사용해도 괜찮다. 그리고 식 $(5.17)$에 섹션 $5.2.1$에서 다뤘던 정규화 방법들도 추가해도 좋다.

한편, 책에서는 set pooling이 무엇인지 정의가 나와있지는 않지만, 식 $(5.17)$이 set pooling인 것 같다. Set pooling을 사용할 경우 성능 향상이 조금 있지만, 반대로 오버피팅이 발생할 수도 있다. 그래서 보통 set pooling을 할 때는 하나의 히든 레이어를 갖는 MLP를 사용하는 것이 일반적이라고 한다.

Janossy pooling

Set pooling에서는 각 이웃 노드의 hidden state를 MLP에 통과시켜 주었다. 그리고 출력된 벡터를 모두 더해주어 permutation invariant 성질을 만족할 수 있었다. 하지만 hidden state를 MLP에 하나씩 통과시켜 주는 것은 각 hidden state가 독립이라는 전제를 깔고 있다. 우리는 더 이상 MLP를 사용하고 싶지 않다.

Janossy pooling는 MLP를 고집하지 않고 순서 변화에 민감한 함수를 사용한다. 순서 변화에 민감한 함수의 가장 대표적인 예는 LSTM이다. LSTM은 들어오는 hidden state들의 순서에 따라 결과가 달라지는 모델이다. 순서 변화에 민감한 함수를 사용하는 대신 모든 순서에 대해서 함수값을 구한다. 그리고 함수값들의 평균값을 이용하게 된다.

$\pi \in \Pi$를 집합을 입력 받아서 순서를 갖고 있는 수열로 만들어주는 permutation 함수라고 하자. $\Pi$는 모든 permutation 함수가 살고 있는 공간이다. 예를 들어, 원소가 8개인 집합의 경우 원소를 나열하는 모든 경우의 수는 $8!$이 될 것이다. 이 경우 $\Pi$에는 $8!$개의 $\pi$가 살고 있는 것이다. 즉, $\pi$는 집합 $\{ \mathbf{h}_v : v \in \mathcal{N}(u) \}$를 입력 받아 순서가 존재하는 수열 $(\mathbf{h}_{v_1}, \mathbf{h}_{v_2}, \cdots, \mathbf{h}_{v_{\mid \mathcal{N}(u)}\mid})_\pi$를 출력해준다. Janossy pooling은 다음과 같은 AGGREGATE 함수를 사용한다. \[\mathbf{m}_{\mathcal{N}(u)}=\text{MLP}_\theta \left(\frac{1}{\mid \Pi \mid}\sum\limits_{\pi \in \Pi}\rho_\phi((\mathbf{h}_{v_1}, \mathbf{h}_{v_2}, \cdots, \mathbf{h}_{v_{\mid \mathcal{N}(u)}\mid})_\pi) \right) \quad \quad (5.18)\]

여기서 $\rho_\phi$는 순서에 민감한 함수로서 보통 LSTM을 사용한다. 식 $(5.18)$처럼 모든 순서를 고려하여 평균낼 수 있다면 이 역시 이론적으로 모든 permutation invariant 함수에 근사할 수 있다고 한다. 하지만 큰 네트워크의 경우 모든 순서를 고려한다는 것은 불가능할 것이다. 그래서 Janossy pooling에서는 다음 두 가지 방법을 선택한다.

• 임의의 순서만 몇 개 샘플링해서 그것들로만 함수값을 구하고 평균을 낸다.
• cononical하게 정렬된 순서에 대해서만 함수값을 구하고 평균을 낸다.
  • cononical 정렬은 노드를 차수에 대하여 내림차순으로 정렬하는 것 같다.
  • 모든 순서를 고려하는 것이 아니라 적어도 차수가 정렬된 순서만 고려하겠다는 것이다. 차수를 기준으로 노드를 정렬할 경우 동일한 차수를 갖는 노드들에 대해서만 순서를 결정해주면 된다.
  • 예를 들어, 원소가 8개인 집합의 경우 원소를 나열하는 모든 경우의 수는 $8!$이다. 이때, 차수가 1, 2, 3, 4인 노드가 각각 2개씩 있다고 하자. 그럼, 차수를 기준으로 노드가 정렬된 경우의 수는 $2! \times 2! \times 2! \times 2!$이 된다.

5.2.3 Neighborhood Attention

자연어처리 분야에서 어텐션을 이용하여 성공하는 사례가 늘어나면서 GNN에도 어텐션이 도입되었다. 계속 반복해서 말하지만, 노드 $u$의 hidden state $\mathbf{h}_u$를 만들 때 이웃 노드 $v$의 hidden state $\mathbf{h}_v$들을 취합하여 만든다. 여기서 어텐션을 사용한다는 것은 $\mathbf{h}_u$와 $\mathbf{h}_v$ 사이의 어텐션 스코어를 계산하고, 그 스코어만큼 가중치를 주어 $\mathbf{h}_v$들을 합한다는 것이다. 즉, \[\mathbf{m}_{\mathcal{N}(u)}=\sum\limits_{v \in \mathcal{N}(u)}\alpha_{u, v}\mathbf{h}_v \quad \quad (5.19)\]

여기서 $\alpha_{u, v}$는 $u$와 $v$ 사이의 어텐션 점수이다. 어텐션 점수는 $v$를 얼마나 집중해서 볼 것이냐를 나타낸다고 생각해도 좋다. 초기 어텐션 점수는 단순히 두 벡터의 내적이었다. 즉, 자신과 유사한 벡터를 더 많이 반영하여 내 벡터를 만들겠다는 취지였다.

Graph Attention Network (GAT) 논문에서는 다음과 같은 어텐션 점수를 사용한다. \[\alpha_{u, v}=\frac{\exp\left( \mathbf{a}^\top[\mathbf{W}\mathbf{h}_u\oplus\mathbf{W}\mathbf{h}_v]\right)}{\sum_{v' \in \mathcal{N}(u)}\exp\left( \mathbf{a}^\top[\mathbf{W}\mathbf{h}_u\oplus\mathbf{W}\mathbf{h}_{v'}]\right)} \quad \quad (5.20)\]

여기서 $\mathbf{a}$는 학습 가능한 어텐션 벡터, $\mathbf{W}$는 학습 가능한 행렬, 그리고 $\oplus$는 두 벡터를 한 줄로 쭉 연결 (concatenation)해주는 연산이다. 다음과 같은 bilinear 어텐션 스코어도 가능하다. \[\alpha_{u, v}=\frac{\exp\left(\mathbf{h}_u^\top \mathbf{W} \mathbf{h}_v\right)}{\sum_{v' \in \mathcal{N}(u)}\exp\left( \mathbf{h}_u^\top \mathbf{W} \mathbf{h}_{v'} \right)} \quad \quad (5.21)\]

MLP를 사용하는 어텐션 스코어도 있다. \[\alpha_{u, v}=\frac{\exp\left(\text{MLP}(\mathbf{h}_u, \mathbf{h}_v)\right)}{\sum_{v' \in \mathcal{N}(u)}\exp\left(\text{MLP}(\mathbf{h}_u, \mathbf{h}_{v'}) \right)} \quad \quad (5.22)\]

여기서 MLP는 스칼라 값을 출력해줘야 한다.

지금까지는 가중치 행렬 $\mathbf{W}$ 하나만 사용해서 노드쌍 $(u,v)$마다 하나의 어텐션 스코어를 계산해주었다. 물론, 가중치 행렬을 $K$개 사용하여 노드쌍 $(u, v)$마다 $K$개의 어텐션 스코어를 만들어 줄 수도 있다. 이런 구조를 multi-head attention라고 부르며, Transformer 논문에서 소개되었다. 즉, \[\mathbf{m}_{\mathcal{N}(u)}=[\mathbf{a}_1 \oplus \mathbf{a}_2 \oplus \cdots \oplus \mathbf{a}_K] \quad \quad (5.23)\] \[\mathbf{a}_k=\mathbf{W}_k\sum\limits_{v \in \mathcal{N}(u)}\alpha_{u, v, k}\mathbf{h}_v \quad \quad (5.24)\]

여기서 $\alpha_{u, v, k}$는 위에서 알아보았던 어텐션 스코어들로 구하면 된다.

식 $(5.24)$의 가중치 행렬 $\mathbf{W}_k$ 표기가 적절하지 않다고 생각한다. $\mathbf{W}_k$ 표기는 식 $(5.20)$ ~ 식 $(5.22)$에서 $\alpha_{u, v, k}$를 구할 때 사용하는 것이 바람직하다고 생각한다. 식 $(5.24)$에서는 $\mathbf{U}_k$ 등 다른 표기를 사용했어야 할 것 같다.

어텐션을 이용하여 AGGREGATE 함수를 사용하면 GNN의 벡터 표현력 (representational power)이 증가한다고 한다. 특히, 이웃 노드 중에서도 더 유용한 노드들과 덜 유용한 노드들이 있는 경우 어텐션을 사용하는 것이 더욱 효과적이라고 한다. 한편, 어텐션을 사용할 경우 노드쌍 $(u, v)$마다 어텐션 점수를 계산해야 하기 때문에 시간 복잡도가 높다는 단점이 있다.

5.3 Generalized Update Methods

섹션 $5.2$에서는 다양한 AGGREGATE 방법에 대해 알아보았다. 섹션 $5.3$에서는 다양한 UPDATE 방법에 대해 알아본다. 그 동안 주로 AGGREGATE 방법에 대한 연구들이 주목 받은 것은 사실이다. 하지만 UPDATE 방법도 GNN 모델의 성능을 결정하는 중요한 요소이기 때문에 잘 알아두어야 한다. 본격적으로 UPDATE 방법을 다루기 전에 GNN 모델들이 겪고 있는 고질병인 Over-smoothing에 대해 알아보자.

5.3.0 Over-smoothing

Over-smoothing 문제는 노드들의 hidden state 벡터가 GNN 레이어를 통과하면서 점점 비슷해지는 현상을 말한다. 이 문제는 특히 GNN 기초 모델 (식 $5.7$)과 self-loop를 사용하는 GNN 모델 (식 $5.13$)에서 더 자주 발생한다고 한다. GNN 레이어를 많이 통과할수록 노드들의 hidden state 벡터가 비슷해지기 때문에 over-smoothing 문제는 더 깊은 GNN 모델을 사용할 수 없게 만든다. 따라서 그래프 안에서 더 넓은 구조적인 정보를 활용할 수 없게 된다.

섹션 $5.3.1$부터는 over-smoothing을 완화할 수 있는 방법들에 대해 알아본다. 섹션 $5.3.0$의 남은 부분은 over-smoothing이 발생하는 이유를 설명하고자 한다. 이론적인 설명이 짙은 반면 중요도는 높지 않다고 생각하기 때문에 바로 섹션 $5.3.1$으로 넘어가도 괜찮다. 앞으로의 설명이 보이고 싶은 목적지는 다음과 같다.

• 모든 노드가 어떤 한 노드 $v$의 마지막 hidden state 벡터 $\mathbf{h}^{(K)}_v$에 미치는 영향이 서로 비슷하다.
• 모든 노드 $v$에 대해서 위가 성립하여, 모든 노드의 hidden state 벡터가 서로 유사하다.

먼저, 노드 $u$의 초기 특징 벡터 $\mathbf{h}^{(0)}_u=\mathbf{x}_u$가 노드 $v$의 $K$ 번째 hidden state 벡터 $\mathbf{h}^{(K)}_v$에 미치는 영향력을 측정해야 한다. 직관적으로 $\mathbf{x}_u$가 아주 조금 변했을 때 $\mathbf{h}_v^{(K)}$가 많이 변한다면 $\mathbf{x}_u$의 영향력이 크다는 것을 알 수 있다. 따라서 $\mathbf{x}_u$가 $\mathbf{h}_v^{(K)}$에 미치는 영향력을 다음과 같이 정의한다. \[I_K(u,v)=\mathbf{1}^{\top}\left( \frac{\partial \mathbf{h}_v^{(K)}}{\partial\mathbf{h}_u^{(0)}} \right) \mathbf{1} \quad \quad (5.25)\]

$\frac{\partial \mathbf{h}_v^{(K)}}{\partial\mathbf{h}_u^{(0)}}$을 Jacobian 행렬이라고 부른다. $\mathbf{h}_v^{(K)}$의 각 원소들을 $\mathbf{h}_u^{(0)}$의 각 원소들로 미분한 값을 저장해놓은 행렬이라고 생각하면 된다. $\mathbf{1}$은 모든 원소가 1인 벡터이다. 식 $(5.25)$처럼 행렬의 양 옆에 $\mathbf{1}^\top$와 $\mathbf{1}$을 곱해주면 행렬을 모든 원소를 더하게 된다. 요컨데 Jacobian 행렬의 모든 원소를 더한 것을 “노드 $u$의 초기 특징 벡터가 노드 $v$의 최종 hidden state 벡터에 미치는 영향력”으로 사용하는 것이다.

그리고 다음 AGGREGATE 함수를 사용하는 GNN 모델을 생각해보자. \[\text{AGGREGATE}(\{ \mathbf{h}_v, \forall v \in \mathcal{N}(u) \cup \{ u \}\})=\frac{1}{f_n(\mid \mathcal{N}(u) \cup \{ u \}\mid)}\sum\limits_{v \in \mathcal{N}(u) \cup \{ u \}}\mathbf{h}_v, \quad \quad (5.26)\]

여기서 $f:\mathbb{R}^{+}\rightarrow\mathbb{R}^{+}$는 임의의 미분가능한 정규화 함수이다. 식이 많이 복잡하지만 쉽게 self-loop를 포함하고 있는 간단한 GNN 모델으로 생각해도 좋다. 식 $(5.26)$을 만족하는 GNN 모델은 다음을 만족한다고 한다. \[I_K(u,v) \propto p_{\mathcal{G}, K}(v|u), \quad \quad (5.27)\]

여기서 $p_{\mathcal{G}, K}(v \mid u)$는 노드 $u$에서 시작하여 길이 $K$의 랜덤 워크를 했을 때 노드 $v$를 방문할 확률이다. 쉽게 말해서 self-loop를 갖고 있는 간단한 GNN 모델에 대해서 식 $I_K(u,v)$는 노드 $u$에서 시작한 길이 $K$의 랜덤 워크에서 노드 $v$를 방문할 확률에 비례한다는 것이다.

여기까지는 큰 문제가 없어 보인다. 하지만 GNN 레이어가 많아질 수록, 즉 $K$가 점점 커질 수록 $p_{\mathcal{G}, K}(v \mid u)$가 랜덤 워크의 stationary distribution으로 수렴한다는 점이 문제이다. Stationary distribution은 그래프에서 랜덤 워킹을 무한 번 했을 때 각 노드에 방문할 확률 분포이다. 이는 랜덤 워크를 시작한 노드와 상관 없이 일정하다. 이는 다시 말하면 깊은 GNN을 통과하게 되면 노드 $u$가 노드 $v$의 얼마나 가까운지는 상관 없이 $u$의 stationary distribution 확률값만큼 영향을 미친다는 것이다. 즉, local neighborhood 정보를 잃게 된다.

여기에 더해서 어떤 네트워크에 차수가 매우 높은 노드를 포함하고 있으면 stationary distribution이 거의 균등 (almost-uniform) 분포로 수렴한다는 것이 증명되어 있다. 위의 문단과 현재 문단을 합쳐보자.

• 깊은 GNN의 경우
• $\mathbf{x}_u$가 $\mathbf{h}_v^{(K)}$에 stationary distribution의 확률값만큼 영향력을 미친다.
• 그런데 그 영향력은 모든 노드가 균등한 값을 갖는다.

즉, 그래프 안의 각 노드에 대한 영향력이 모든 노드가 같다는 것이다. 굉장히 어지러운데, 모든 노드가 모든 노드에 대해 미치는 영향력이 같다는 것이다. 따라서 레이어가 지나갈 수록 hidden state 벡터가 점점 유사해지는 것이다.

Self-loop를 포함하는 간단한 GNN 모델에 대해 내용을 전개하였다. 하지만 self-loop를 포함하지 않더라도 식 $(5.9)$에서 $\lVert \mathbf{W}^{(k)}_{\text{self}} \rVert \le \lVert \mathbf{W}^{(k)}_{\text{neigh}} \rVert$인 간단한 GNN 모델에 대해서도 해당 내용들이 확장될 수 있다고 한다.

요약하건데, GNN 레이어를 지나갈 수록 local neighborhood 정보를 점점 잃게되며 노드들의 hidden state 벡터들이 점점 비슷해지는 현상을 over-smoothing이라고 한다.

5.3.1 Concatenation and Skip Connections

섹션 $5.3.1$에서는 over-smoothing이 발생하는 직관적인 이유를 다음과 같이 말하고 있다.

• GNN 레이어를 통과할수록 각 노드의 고유한 정보가 점점 사라지게 된다.
• 즉, 다음 hidden state 벡터 $\mathbf{h}_u^{(k+1)}$ 업데이트가 이웃 노드로부터 취합한 정보 $\mathbf{m}_{\mathcal{N}(u)}$에 강하게 의존적일 경우, 그래서 현재 hidden state 벡터 $\mathbf{h}_u^{(k)}$의 정보가 거의 무시될 경우에 발생한다.

Over-smoothing을 완화할 수 있는 방법 중 하나는 vector concatenation 또는 skip connection을 사용하는 것이다. 두 방법은 현재 정보를 직접적으로 보존하면서 상태를 업데이트하는 것이다. 지금까지 보았던 일반적인 UPDATE 함수를 $\text{UPDATE}_{\text{base}}$라고 표기하자. Vector concatenation은 다음과 같이 수행된다. \[\text{UPDATE}_{\text{concat}}(\mathbf{h}_u,\mathbf{m}_{\mathcal{N}(u)})=[\text{UPDATE}_{\text{base}}(\mathbf{h}_u, \mathbf{m}_{\mathcal{N}(u)})\;\oplus\;\mathbf{h}_u], \quad \quad (5.28)\]

일반적인 업데이트 함수를 사용해서 만든 벡터와 현재 hidden state 벡터를 쭉 결합 ($\oplus$) 한 벡터를 다음 hidden state로 사용하겠다는 것이다. 식 $(5.28)$과 같이 결합을 이용한 UPDATE 방법은 GraphSAGE에서 소개되었다. 그리고 GraphSAGE는 이런 종류의 UPDATE 함수를 사용한 최초의 연구라는 평가를 받고 있다고 한다.

두 벡터를 결합하는 대신 가중합하는 방법도 있다. 이런 방법을 linear interpolation method라고 하며 다음과 같은 UPDATE 함수를 사용한다. \[\text{UPDATE}_{\text{interpolate}}(\mathbf{h}_u,\mathbf{m}_{\mathcal{N}(u)})=\mathbf{\alpha}_1\circ\text{UPDATE}_{\text{base}}(\mathbf{h}_u, \mathbf{m}_{\mathcal{N}(u)})\;+ \;\mathbf{\alpha}_2 \circ\mathbf{h}_u, \quad \quad (5.29)\]

여기서 $\mathbf{\alpha}_1, \mathbf{\alpha}_2 \in [0, 1]^{d}$, $\mathbf{\alpha}_1+\mathbf{\alpha}_2=\mathbf{1}$이며 게이팅 벡터 (gating)라고 한다.

• $\mathbf{\alpha}_1, \mathbf{\alpha}_2 \in [0, 1]^{d}$: 모든 원소의 값이 0이상 1이하인 $d$-차원 벡터
• $\mathbf{\alpha}_1+\mathbf{\alpha}_2=\mathbf{1}$: 두 벡터의 합은 모든 원소가 $1$인 벡터
• 게이팅 벡터: 정보를 얼마만큼 흘려 보낼 것인지 게이트 역할. 게이트는 톨게이트를 생각하면 쉽다.

여기서 게이팅 벡터 $\mathbf{\alpha}_1$를 다양한 방법으로 결정해줄 수 있다.

• $\mathbf{\alpha}_1$를 그냥 학습 가능한 파라미터로 설정하고 같이 최적화한다.
• 현재 hidden state 벡터를 입력 받아서 $\mathbf{\alpha}_1$을 출력해주는 다층 퍼셉트론 모델을 사용한다.
• 현재 hidden state 벡터를 입력 받아서 $\mathbf{\alpha}_1$을 출력해주는 단일층 GNN 모델을 사용한다.

vector concatenation과 skip connections 방법은 over-smoothing을 완화시켜줄 뿐만 아니라 모델 학습에 안정성을 더해준다고 한다. 특히 노드 분류 문제에 유용하다고 한다. 그리고 이웃 노드의 정보가 중요한 homophily를 가정하는 문제에서도 큰 성능 향상을 보인다고 한다.

5.3.2 Gated Updates

UPDATE 함수는 노드 $u$의 이전 hidden state $\mathbf{h}_u^{(k-1)}$와 이웃 노드 정보를 취합한 메시지 벡터 $\mathbf{m}_{\mathcal{N}(u)}^{(k)}$를 입력 받는 함수이다. 한편, RNN (Recurrent Neural Networks, 순환 신경망)은 이전 hidden state $\mathbf{h}_{t-1}$와 현재 데이터 $\mathbf{x}_t$를 입력 받아 다음 hidden state $\mathbf{h}_t$를 만드는 벡터이다. 그리고 $\mathbf{h}_{t-1}$과 $\mathbf{x}_t$의 정보를 각각 얼마만큼 사용할 것인지 결정해주는 게이트를 추가해준 것이 GRU (Gated recurrent unit)과 LSTM (Long short-term memory)이다.

우리는 $\mathbf{h}_u^{(k-1)}$를 이전 RNN 계열 모델의 $\mathbf{h}_{t-1}$으로, $\mathbf{m}_{\mathcal{N}(u)}^{(k)}$을 $\mathbf{x}_t$로 입력해주는 UPDATE 함수를 사용할 수 있다. 예를 들어 GRU를 이용한 UPDATE 함수는 다음과 같다. \[\mathbf{h}_u^{(k)}=\text{GRU}\left(\mathbf{h}_u^{(k-1)}, \mathbf{m}_{\mathcal{N}(u)}^{(k)}\right), \quad \quad (5.30)\]

우리는 GRU 뿐만 아니라 RNN 계열 모델을 UPDATE 함수에 사용할 수 있다. 특히, 게이트 개념이 있는 모델을 사용할 경우 Gated update라고 부르는 것 같다. 기존 RNN 계열 레이어에서는 매 시점 같은 가중치 행렬을 사용한다. 즉, 한 레이어에서 모든 데이터와 hidden state들에 대해 같은 가중치 행렬이 곱해진다. RNN 계열 UPDATE 함수를 사용하는 GNN에서도 마찬가지이다.

Gated update는 깊은 GNN 모델을 사용할 수 있게 해줄 뿐만 아니라 over-smoothing 문제도 완화시켜준다고 한다. 그리고 프로그램 분석, 조합 최적화 등 그래프 전체적인 구조에 대한 복잡한 추론이 필요한 예측 문제에서 좋은 성능을 보인다고 한다.

5.3.3 Jumping Knowledge Connections

그 동안 우리는 GNN의 마지막 레이어까지 통과한 hidden state를 노드의 임베딩 벡터로 사용했다. 즉, \[\mathbf{z}_u=\mathbf{h}_u^{(K)}, \forall u \in \mathcal{V}. \quad \quad (5.31)\]

Over-smoothing 문제에서 본 것처럼 많은 레이어를 통과한 hidden state 벡터일수록 local neighborhood 정보를 점점 잃게 된다. 그래서 skip connection이나 gated update를 사용해야 했다. 하지만 jumping knowledge (JK) connection은 모든 레이어에서의 hidden state를 사용하여 최종 노드 임베딩 벡터를 만들게 된다. \[\mathbf{z}_u=f_{\text{JK}}\left(\mathbf{h}_u^{(0)}\oplus\mathbf{h}_u^{(1)}\oplus\cdots\oplus\mathbf{h}_u^{(K)}\right), \quad \quad (5.32)\]

여기서 $f_{\text{JK}}$는 임의의 미분 가능한 함수이다. 모든 레이어에서의 hidden state들을 하나의 벡터로 쭉 결합한 뒤 인공 신경망 등의 $f_{\text{JK}}$를 통과시켜 최종 임베딩 벡터 $\mathbf{z}_u$를 얻게 된다. 보통 $f_{\text{JK}}$를 적용하지 않고 결합된 벡터 그 자체를 임베딩 벡터로 사용한다고 한다. JK connection은 대부분의 모든 문제에서 성능 향상을 보여준다고 한다.

5.4 Edge Features and Multi-relational GNNs

지금까지의 접근법들은 한 종류의 관계만 엣지로 표현하는 simple 그래프에만 사용될 수 있었다. 섹션 $5.4.1$에서는 노드와 노드 사이에두 종류 이상의 관계 (엣지)를 가질 수 있는 Multi-relational 그래프에 적용할 수 있는 방법들에 대해 알아본다. 섹션 $5.4.2$에서는 엣지에 feature가 있는 그래프를 다루는 방법에 대해 알아본다.

5.4.1 Relational Graph Neural Networks

Multi relational 그래프에 적용하기 위하여 가장 먼저 제안된 GNN은 바로 Relational Graph Convolutional Network (RGCN)이다. RGCN은 AGGREGATE 단계에서 관계마다 서로 다른 가중치 행렬을 사용한다. \[\mathbf{m}_{\mathcal{N}(u)}=\sum\limits_{\tau \in \mathcal{R}}\sum\limits_{v \in \mathcal{N}_{\tau}(u)}\frac{\mathbf{W}_\tau\mathbf{h}_v}{f_n(\mathcal{N}_\tau(u), \mathcal{N}_\tau(v))}, \quad \quad (5.33)\]

여기서 $\tau$는 한 종류의 관계를, $\mathcal{R}$은 모든 관계의 집합을, $\mathcal{N}_\tau{(u)}$는 $u$와 관계 $\tau$ 로 연결되어 있는 이웃 노드 집합을, $f_n(\mathcal{N}_\tau(u), \mathcal{N}_\tau(v))$는 집합 $\mathcal{N}\tau(u)$와 $\mathcal{N}\tau(v)$의 크기에 대한 임의의 정규화 함수이다. 일반적인 GNN과 크게 다른 점은 없다. 정규화를 포함한다는 점과 이웃 노드의 정보 $\mathbf{h}_v$를 연결된 관계에 따라서 다른 가중치 행렬로 변환해주고 취합한다는 점만 다르다.

Parameter sharing

RGCN은 관계 $\tau$마다 가중치 행렬 $\mathbf{W}_\tau$가 따로 있기 때문에 파라미터 개수가 증가한다는 단점이 있다. 이로 인해 관계의 종류가 굉장히 많은 그래프에 대해서는 훈련 시간도 많이 필요할 뿐만 아니라 오버피팅이 발생할 수도 있다. 따라서 RGCN의 가중치 행렬 $\mathbf{W}_\tau$를 $b$개의 기저 행렬 $\mathbf{B}_i$의 선형결합으로 구하게 된다. \[\mathbf{W}_\tau=\sum\limits_{i=1}^b\alpha_{i, \tau}\mathbf{B}_i, \quad \quad (5.34)\]

$\mid \mathcal{R} \mid$개의 행렬 $\mathbf{W}_\tau$을 학습하지 않고, $b$개의 기저 행렬 $\mathbf{B}_i$을 학습한다. 그리고 $\mathbf{B}_i$의 선형결합으로 $\mid \mathcal{R} \mid$개의 행렬 $\mathbf{W}_\tau$을 만드는 것이다. 여기서 $b < \tau$이어야 파라미터 개수를 줄이는 효과가 있을 것이다. 선형결합의 계수 $\alpha_{i, \tau}$도 학습해야 할 파라미터이다. 모든 $\tau$에 대해서 기저 행렬을 공유하기 때문에 parameter sharing 방법이라고 부른다. parameter sharing을 사용한 메세지 벡터 계산은 다음과 같다. \[\mathbf{m}_{\mathcal{N}(u)}=\sum\limits_{\tau \in \mathcal{R}}\sum\limits_{v \in \mathcal{N}_{\tau}(u)}\frac{\mathbf{\alpha}_{\tau}\times_1\mathcal{B}\times_2\mathbf{h}_v}{f_n(\mathcal{N}_\tau(u), \mathcal{N}_\tau(v))}, \quad \quad (5.35)\]

여기서 $\mathcal{B}=(\mathbf{B}_1,\cdots,\mathbf{B}_b)$는 기저 행렬들을 쌓아올린 텐서이고, $\mathbf{\alpha}_\tau=(\alpha_{1, \tau}, \cdots, \alpha_{b, \tau})^T$는 $\mathbf{W}_\tau$를 만들기 위한 선형결합의 계수 벡터이다. $\times_i$는 mode $i$를 따라서 텐서 곱을 수행하는 연산자이다.

Extensions and variations

이 외에 RGCN의 확장체나 변형체가 많이 있으니 관심이 있는 분들은 찾아서 보라는 문단인 것 같다.

5.4.2 Attention and Feature Concatenation

Multi relational 그래프는 일반적인 그래프에서 엣지마다 feature 벡터를 갖고 그래프라고 생각해도 된다. 이때 엣지 $(u, \tau, v)$에 대한 feature 벡터 $\mathbf{e}_{(u, \tau, v)}\in \mathbb{R}^{\mid \mathcal{R} \mid}$는 $\tau$ 번째 원소만 1이고 나머지 원소는 0인 원핫벡터가 될 것이다. 따라서 엣지마다 feature 벡터를 갖고 있는 그래프가 더 일반적인 그래프라고 할 수 있다.

책에서는 엣지 feature를 다룰 수 있는 방법으로 어텐션과 벡터 결합을 언급하고 있다. 먼저 벡터 결합의 경우 AGGREGATE 단계에서 이웃 노드의 정보 $\mathbf{h}_v$와 엣지 feature 벡터 $\mathbf{e}_{(u, \tau, v)}$를 단순히 결합하는 방법이다. \[\mathbf{m}_{\mathcal{N}}(u)=\text{AGGREGATE}\left(\{ \mathbf{h}_v \oplus \mathbf{e}_{(u, \tau, v)}: \forall v \in \mathcal{N}(u)\}\right), \quad \quad (5.36)\]

어텐션을 이용하는 방법은 설명 없이 논문 Sinha et al., 2019 [5]만 참조하고 있다. 관심 있는 분들께서는 찾아보면 좋을 것 같다.

5.5 Graph Pooling

우리는 GNN의 마지막 레이어의 출력값을 각 노드 임베딩 벡터로 사용하였다. 하지만 특정 문제에서는 노드 레벨에서의 벡터가 아니라 그래프 레벨의 벡터가 필요할 것이다. GNN으로 얻게 된 노드 임베딩 벡터 $\mathbf{z}_u, \; \forall u \in \mathcal{V}$를 사용해서 그래프 레벨 벡터 $\mathbf{z}_{\mathcal{G}}$를 만드는 문제를 graph pooling이라고 부른다.

Set pooling approaches

생각해볼 수 있는 가장 쉬운 방법은 노드 레벨 벡터들의 합이나 평균을 사용하는 것이다. \[\mathbf{z}_{\mathcal{G}}=\frac{\sum\limits_{v \in \mathcal{V}}\mathbf{z}_v}{f_n(|\mathcal{V}|)}, \quad \quad (5.37)\]

여기서 $f_n$은 임의의 정규화 함수이다. 노드 레벨 벡터의 합을 사용한다면 $f_n(\mid\mathcal{V}\mid)=1$일 것이고, 평균을 사용한다면 $f_n(\mid\mathcal{V}\mid)=\mid\mathcal{V}\mid$일 것이다. 비합리적인 방법으로 생각되지만, 작은 그래프를 다루는 문제에서는 제법 잘 작동한다고 한다.

조금 더 세련되고, 최신식이며, 복잡한 방법으로는 어텐션과 LSTM을 사용하는 방법이 있다. 이 방법에서는 다음과 같은 과정을 $t=1,2,\cdots,T$에 대해서 반복한다. \[\begin{matrix} \mathbf{q}_t & = & \text{LSTM}(\mathbf{o}_{t-1}, \mathbf{q}_{t-1}), & \quad \quad (5.38) \\ e_{v,t} & = & f_a(\mathbf{z}_v, \mathbf{q}_t), & \quad \quad (5.39) \\ a_{v,t} & =& \frac{\exp(e_{v, t})}{\sum_{u \in \mathcal{V}} \exp(e_{u,t})}, & \quad \quad (5.40) \\ \mathbf{o}_{t} & = & \sum\limits_{v \in \mathcal{V}}a_{v, t}\mathbf{z}_v. & \quad \quad (5.41) \end{matrix}\]

우선, $\mathbf{q}_0$과 $\mathbf{o}_0$은 영벡터에서 시작한다.

• $t$ 시점의 $\mathbf{o}_t$는 노드 임베딩 벡터들의 가중합으로 계산된다. 이때 가중치 $a_{v,t}$를 어텐션 스코어라고 부른다. (식 $5.41$)
• 노드 $v$의 $t$에 대한 어텐션 스코어 $a_{v,t}$는 $e_{v, t}$의 정규화된 버전이다. (식 $5.40$)
• 노드 $v$의 $t$에 대한 정규화되지 않은 어텐션 스코어 $e_{v,t}$는 노드 임베딩 벡터 $\mathbf{z}_v$와 쿼리 벡터 $\mathbf{q}_t$의 어텐션 연산 $f_a$에 의해 계산된다. 어텐션 연산의 예는 벡터 내적이다. 보통은 트랜스포머 논문에서 나오는 어텐션을 사용하지 않을까 싶다. (식 $5.39$)
• 위 과정을 통해 $\mathbf{o}_t$를 얻는다. 다음으로 $t$ 시점의 $\mathbf{q}_t$는 $\mathbf{o}_{t-1}$과 $\mathbf{q}_{t-1}$을 LSTM에 넣어서 계산한다. (식 $5.48$)

위 과정을 반복해서 얻은 모든 $\mathbf{o}_1, \mathbf{o}_2, \cdots,\mathbf{o}_T$를 벡터 결합하여 그래프 레벨 벡터로 사용한다. \[\mathbf{z}_\mathcal{G}=\mathbf{o}_1\oplus\mathbf{o}_2\oplus\cdots\oplus\mathbf{o}_T. \quad \quad (5.42)\]

확실히 세련되고 최신적이며 복잡하다. 한번 써보고 싶은데 이 방법을 소개한 논문이 언급되어 있지 않아서 못 사용할 것 같다.

Graph coarsening approaches

위에서 알아본 두 가지 방법은 노드 임베딩 벡터을 취합하여 그래프 레벨 벡터를 계산한다. 각각의 노드 임베딩 벡터에 그래프의 구조적인 정보가 반영되어 있겠지만 취합 과정에서는 그래프 정보를 적극 활용하지 않는다. Graph coarsening 접근 방법은 그래프의 구조적인 정보까지 활용하여 그래프 레벨 벡터를 계산하게 된다.

Graph coarsening을 이용한 그래프 레벨 벡터 계산 방법은 다음과 같다.

• 현재 그래프에 GNN을 적용해서 노드 임베딩 행렬 $\mathbf{Z}$를 얻는다.
• $\mathbf{Z}$에 군집화 알고리즘을 적용하여 노드들을 여러 개의 군집으로 나눈다.
• 각 군집들을 하나의 노드로 갖는 간략화된 그래프를 만든다.
• 간략화된 그래프에 대해 위 과정을 반복한다.
• 반복을 통해 노드 개수가 적당히 줄어들면 마지막으로 GNN을 적용하여 노드 임베딩 벡터를 계산한다. 그리고 이 노드 임베딩 벡터에 graph pooling 기법을 적용해서 그래프 레벨 벡터를 구하게 된다.

이 방법은 CNN의 max pooling에서 영감을 받았다고 한다. CNN에서 max pooling을 통해 이미지의 해상도를 점점 낮추며 특징을 뽑는 것과 유사하다. 노드를 점점 합치면서 그래프를 계층적으로 만들어서 GNN을 적용한다는 것이다. 이 방법은 GNN을 반복적을 적용하여 그래프의 구조적인 정보를 반영할 수 있다는 장점이 있다. 하지만 학습이 불안정하다는 단점이 있다.

함수 $\mathbf{f}_c: \mathcal{G} \times \mathbb{R}^{\mid\mathcal{V}\mid \times d} \rightarrow \mathbb{R}^{\mid\mathcal{V}\mid\times c}$를 그래프 $\mathcal{G}$와 노드 임베딩 행렬 $\mathbf{Z}$를 입력 받아서 $\mathcal{G}$의 노드들이 각 군집에 속할 확률 (또는 군집과의 연관성)을 출력해주는 함수라고 하자. (하나의 그래프에 대해 알고리즘을 적용할텐데 왜 굳이 $\mathcal{G}$를 입력 받는지 의아하다.)

그리고 $\mathbf{S}=\mathbf{f}_c(\mathcal{G}, \mathbf{Z})$을 군집 할당 행렬이라고 부르다. 군집 할당 행렬의 각 원소 $\mathbf{S}[u, i]$는 노드 $u$가 군집 $i$에 속할 확률 쯤으로 해석하면 된다. $\mathbf{f}_c$의 대표적인 예는 인접행렬을 섹션 $2.3.3$에서 배운 generalized spectral clusering이 있을 것이다. 하지만 지금 소개하는 방법은 GNN을 적용해서 나온 임베딩 벡터를 기반으로 클러스터링을 하는 것 같다. (책에서 표현이 너무 모호하게 나와서 확실히 어떤 벡터를 군집화에 사용하는지 잘 모르겠다.)

행렬 $\mathbf{S}$를 인접행렬의 양옆에 곱하는 연산을 생각해보자 \[\mathbf{A}^{\text{new}}=\mathbf{S}^\top \mathbf{A} \mathbf{S} \in \mathbb{R}^{c \times c}, \quad \quad (5.44)\]

위 연산을 잘 생각해보면 $\mathbf{A}^{\text{new}}$는 각 군집과 군집 사이의 연결성을 나타낸다. 한편, \[\mathbf{X}^{\text{new}}=\mathbf{S}^\top\mathbf{X}\in\mathbb{R}^{c \times d}, \quad \quad (5.45)\]

$\mathbf{X}^{\text{new}}$는 각 군집에 속한 노드들의 feature들을 가중합한 것이기 때문에, 각 군집의 feature 벡터로 이해할 수 있다. $\mathbf{A}^{\text{new}}$와 $\mathbf{S}^{\text{new}}$를 사용해서 지금까지의 과정을 반복하면서 점점 작은 그래프를 만들게 된다.

5.6 Generalized Message Passing

지금까지 우리는 AGGREGATE와 UPDATE를 할 때 이웃 노드의 정보만을 사용했다. 하지만 이웃 노드 정보 뿐만 아니라 엣지 정보, 그래프 정보까지 쓰고 싶다면 어떻게 해야할까? 섹션 $5.6$에서는 노드 feature, 엣지 feature, 그래프 feature까지 사용할 수 있는 일반적인 GNN 구조에 대해 알아볼 것이다. \[\begin{matrix} \mathbf{h}_{(u,v)}^{(k)} & = & \text{UPDATE}_{\text{edge}}\left( \mathbf{h}_{(u, v)}^{(k-1)}, \mathbf{h}_{u}^{(k-1)}, \mathbf{h}_{v}^{(k-1)}, \mathbf{h}_{\mathcal{G}}^{(k-1)} \right) & \quad \quad(5.46) \\ \mathbf{m}_{\mathcal{N}(u)} & = & \text{AGGREGATE}_{\text{node}} \left( \{ \mathbf{h}_{(u,v)}^{(k)}, \forall v \in \mathcal{N}(u) \}\right) & \quad \quad (5.47) \\ \mathbf{h}_u^{(k)}&=& \text{UPDATE}_{\text{node}} \left( \mathbf{h}_u^{(k-1)}, \mathbf{m}_{\mathcal{N}(u)}, \mathbf{h}_{\mathcal{G}}^{(k-1)}\right) & \quad \quad (5.48) \\ \mathbf{h}_{\mathcal{G}}^{(k)} & = & \text{UPDATE}_{\text{graph}}\left( \mathbf{h}_{\mathcal{G}}^{(k-1)}, \{ \mathbf{h}_u^{(k)}, \forall u \in \mathcal{V}\}, \{ \mathbf{h}_{(u,v)}^{(k)}, \forall (u,v) \in \mathcal{E}\}\right). & \quad \quad (5.49) \end{matrix}\]

기본적으로 각 노드에 대한 hidden state $\mathbf{h}_u^{(k)}$, 각 엣지에 대한 hidden state $\mathbf{h}_{(u,v)}^{(k)}$, 그리고 그래프에 대한 hidden state $\mathbf{h}_\mathcal{G}^{(k)}$가 있다.

• 식 $(5.49)$부터 보자. 그래프에 대한 hidden state는 자신의 이전 hidden state, 모든 노드의 hidden state, 모든 엣지의 hidden state를 사용해서 만든다.
• 그리고 각 노드가 취합할 정보는 이웃 노드 정보가 아니라 해당 노드에 연결된 엣지의 정보이다. (식 $5.47$)
• 노드에 대한 hidden state는 자신의 이전 hidden state, 취합한 메세지 벡터, 그리고 그래프의 hidden state를 사용하여 만든다. (식 $5.48$)
• 마지막으로 엣지에 대한 hidden state는 자신의 이전 hidden state, 양 쪽 노드의 hidden state, 그리고 그래프의 hidden state를 사용해서 만든다. (식 $5.49$)

여기서 UPDATE 함수와 AGGRAGATE 함수는 지금까지 배운 것을 자유롭게 사용하면 된다.

참고문헌

[1] https://pixabay.com/ko/illustrations/지구-회로망-3537401/

[2] Hamilton, William L.,Graph Representation Learning, Synthesis Lectures on Artificial Intelligence and Machine Learning, 14, pp.1-159

[3] CS224W: Machine Learning with Graphs

[4] T.N. Kipf and M. Welling. Semi-supervised classification with graph convolutional networks. In ICLR, 2016a.

[5] K. Sinha, S. Sodhani, J. Dong, J. Pineau, and W. Hamilton. CLUTRR: A diagnostic benchmark for inductive reasoning from text. In EMNLP, 2019.