Graph Neural Network 시작하기

GNN은 Graph Neural Network의 약자로 그래프 신경망이다. 일단 GNN을 알기 위해서는 당연히 그래프가 어떤 것인지 알고 있어야 한다. 그래프는 $G = (V, E)$로 나타내며 V는 꼭짓점(vertex)의 집합, E는 에지(edge)의 집합이다. 에지 집합 중 하나인 $e=u,v$는 $u$와 $v$를 연결해주는 연결 고리를 의미하며 $u,v$는 꼭짓점이다. 이때 $u,v$를 이웃이라 부르고 두 꼭짓점은 인접하다고 한다. 

 

에지에는 방향이 있을 수도 있고 없을 수도 있는데 그래프의 모든 에지에 방향이 존재한다면 이를 유향 그래프(directed graph), 방향이 없는 경우에는 무향 그래프(undirected graph)라고 부른다. 꼭짓점 $v$의 차수는 $v$에 연결된 에지의 수를 의미하고 $d(v)$로 표기한다. 

 

그래프를 다루기 이전에 그래프에서 주로 사용하는 행렬에 대해서 먼저 알아보자. 

 

1. 인접행렬(adjacency matrix)

\[ |V| = n, \ \ A\in \mathbb{R}^{n\times n} \]

\[ A_{ij} = \begin{cases} 1, & \{ v_i, v_j \} \in E \ \text{and} \ i \neq j \\ 0, & \text{otherwise} \end{cases} \]이때 $A$는 인접행렬을 의미하며, $|V|$는 꼭짓점의 개수를 의미한다. 무향 그래프의 인접행렬은 대칭이다. 

 

 

2. 차수행렬(degree matrix)

\[ |V| = n, \ \ D \in \mathbb{R}^{n \times n} \]

\[ D_{ii} = d(v_i) \]

 

3. 라플라시안 행렬(Laplacian matrix)

무향 그래프 $G = (V, E)$의 라플라시안 행렬은 다음과 같다. 

\[ |V| = n, \ \ L \in \mathbb{R}^{n \times n} \]

\[ L = D - A \]

\[ L^{\text{sym}}_{ij} = \begin{cases} d(v_i), & i=j \\ -1, & \{v_i, v_j\} \in E \ \text{and} \ i \neq j \\ 0, & \text{otherwise} \end{cases} \]

$D$는 diagonal degree matrix를 의미한다.

 

 

4. 대칭 정규화 라플라시안(symmetric normalized Laplacian)

\[ \begin{equation} \begin{split} \label{eq1} L^{\text{sym}} & = D^{-\frac{1}{2}}LD^{-\frac{1}{2}} \\ & = I - D^{-\frac{1}{2}}AD^{-\frac{1}{2}} \end{split} \end{equation} \]

\[L^{\text{sym}}_{ij} = \begin{cases} 1, & i=j \ \text{and} \ d(v_i) \neq 0 \\ -\frac{1}{\sqrt{d(v_i)\cdot d(v_j)}}, & \{v_i, v_j\} \in E \ and \ i \neq j \\ 0, & \text{otherwise} \end{cases} \]

 

5. 랜덤 워크 정규화 라플라시안(random walk normalized Laplacian)

\[ L^{\text{rw}} = D^{-1} L = I - D^{-1} A \]

\[ L^{\text{rw}}_{ij} = \begin{cases} 1, & i=j \ and \ d(v_i) \neq 0 \\ - \frac{1}{d(v_i)}, & \{ v_i, v_j \} \in E \ and \ i \neq j \\ 0, & \text{otherwise} \end{cases} \]

 

 

GNN

그래프에서 노드 v는 특징과 관련된 노드로 자연스럽게 정의된다. GNN의 최종 목표는 각 노드의 State embedding $\mathbf{h}_v \in \mathbb{R}^s$ 를 학습하는 것이다. 이때 $\mathbf{h}_v$는 해당 노드와 주변 노드의 정보를 포함하고 있으며, $\mathbf{o}_v$를 얻을 때 사용한다. $\mathbf{o}_v$는 v의 출력값을 의미한다. 

 

 

그렇다면 $\mathbf{h}_v$와 $\mathbf{o}_v$는 어떻게 계산할 수 있을까? 먼저 이웃으로부터 노드의 상태를 업데이트하기 위해 노드들끼리 공유하는 local transition function $f$를 사용하고, 노드의 출력값을 계산하기 위해 local output function $g$를 사용한다. 

\[ \mathbf{h}_v = f(\mathbf{x}_v, \mathbf{x}_{co[v]}, \mathbf{h}_{ne[v]}, \mathbf{x}_{ne[v]}) \]

\[ \mathbf{o}_v = g(\mathbf{h}_v, \mathbf{x}_v) \]

이때 $co[v]$는 v와 연결된 에지 집합이고, $ne[v]$는 v와 인접한 노드 집합을 의미한다. $\mathbf{x}_v$는 input feature를 의미한다. 위의 그림으로 예시를 들자면, 노드 1의 feature는 $\mathbf{x}_1$이고, $co[1]= \{ (1,4), (6,1), (1,2), (1,3) \}$, $ne[1]=\{2, 3, 4, 6\}$일 것이다. 

 

딥러닝에서는 계산의 용이성 때문에 행렬을 많이 사용하는데, 위 경우를 행렬로 변환하면 다음과 같다. 

\[ \mathbf{H} = \text{F}(\mathbf{H}, \mathbf{X}) \]

\[ \mathbf{O} = \text{G}(\mathbf{H}, \mathbf{X_N})\]

이때 $\mathbf{H}, \mathbf{O}, \mathbf{X}, \mathbf{X_N}$는 각각 state embedding, output embedding, input embedding, input feature이고, $\text{F}$와 $\text{G}$는 각각 $f$와 $g$를 쌓은 버전이라고 할 수 있다. 이때 $\mathbf{H}$는 고정점(Fixed point)이며, $\text{F}$가 축약 사상(Contraction map)이라면 유일하게 정의되고 우리는 이것을 바나흐 고정점 정리(Banach fixed-point theorem) 혹은 바나흐 축약사상 정리(Banach Contraction mapping theorem)라고 부른다. 

 

 

바나흐 고정점 정리(Banach fixed-point theorem)

GNN에서는 바나흐 고정점 정리를 바탕으로 반복 계산법을 사용하고 있기 때문에 이해를 돕기 위해 바나흐 고정점 정리를 먼저 알아보자. 바나흐 고정점 정리는 축약 사상에 대해 고정점이 하나만 존재한다는 정리이다. 위에서 언급한 내용과 일치하는 것을 확인할 수 있다. 바나흐 고정점 정리는 총 2가지의 정의를 만족하여야 한다. 

 

1. 거리공간 $\text{X}$에서 점 $x \in \text{X}$와 사상(mapping) $\text{T} : \text{X} \rightarrow \text{X}$에 대해 $\text{T}(x) = x$이 성립하면 $x$를 고정점이라고 한다. 

 

2. 거리공간 $(\text{X}, \rho)$에서 사상 $\text{T}$에 대해 다음이 성립하는 $c<1$이 존재한다면 이러한 립쉬츠 사상(Lipschitz mapping)을 축약 사상(contraction)이라고 한다. 

\[ \rho(\text{T}(u), \text{T}(v) \le c\ \cdot \ \rho(u,v)\ \ \ \forall u,v \in \text{X} \]

Banach Contraction Principle

완비거리공간 $\text{X}$와 축약 사상 $\text{T}:\text{X} \rightarrow \text{X}$에 대해 $\text{T}$의 고정점은 오직 하나만 존재한다. 

 

'완비'는 Completeness 이며, 수열의 끝, 즉 수렴점이 거리공간 안에 존재함을 보장한다는 뜻을 의미한다. 하나의 직선 또는 곡선처럼 끊김없는 구조를 갖는 것을 의미한다. 완비성을 증명할 때에는 일반적으로 코시 수열(Cauchy Sequence)를 많이 사용하는데 코시 수열은 주어진 수열의 극한을 모른다고 하더라도 사용할 수 있기 때문이다. 이는 나중에 다루어 보자..

 

 

 

다시 돌아와 GNN에서 바나흐 고정점 정리를 사용하는 방법을 보자. GNN에서는 다음과 같은 반복 계산법을 사용하고 있다. 

\[ \mathbf{H}^{t+1} = \text{F}(\mathbf{H}^t, \mathbf{X})\]

이때 $\text{H}^t$는 $\mathbf{H}$를 t번 반복한 결과값을 의미한다. 임의의 초깃값 $\mathbf{H}^0$에 대해 $\mathbf{H}^{t+1} = \text{F}(\mathbf{H}^t, \mathbf{X})$는 $\mathbf{H} = \text{F}(\mathbf{H}, \mathbf{X})$로 빠르게 수렴하게 된다. 하나의 고정점으로 찾아가는 것이다. 

 

그렇다면 GNN에서는 $f$와 $g$를 어떤 방식으로 학습할까? GNN은 노드 $v$의 정보 $\mathbf{t}_v$가 주어졌을 때 다음과 같이 목적함수를 정의한다. 

\[ \mathcal{J}= \sum_{v \in P}(\mathbf{t}_v - \mathbf{o}_v)\]

이때 $P$는 $\mathbf{t}_v$가 정의된 노드의 집합을 의미한다. $\mathbf{t}_v$는 딥러닝에서의 정답 라벨과 같은 개념으로 받아들이면 이해하는데 도움이 될 것이다. GNN에서도 동일하게 목적함수를 최적화하는 방식으로 경사하강법을 사용한다. state embedding $\mathbf{h}_v^t$는 $\mathbf{h}_v$를 구하는 식으로 시간 $T$까지 반복적으로 업데이트하며 고정점의 근사값을 구한다. 똑같이 가중치에 대해 Gradient를 계산하고 업데이트하면서 최적화한다. 

 

 

 

한계점

GNN은 매우 강력한 모델인 것으로 보이지만 몇 가지 문제점이 존재한다.

• 첫 번째로는 GNN을 계산하기 위해서는 바나흐 고정점 정리를 통해 똑같은 수식을 반복적으로 계산하며 최적화하고 있다. 이는 노드의 은닉 상태를 반복적으로 업데이트 하기 때문에 비효율적인 방식이다.
• 두 번째로는 그래프를 구성하는 요소인 노드를 가지고만 계산하고 있기에 에지에도 중요한 정보가 있을 수 있지만 Vanila GNN에서는 이를 계산할 수 없다. 에지의 은닉 상태를 어떻게 학습해야 하는지도 중요한 문제이다. 
• 마지막으로는 반복 시행하는 T가 아주 큰 경우에는 고정점의 분포가 비슷한 값들을 가지게 되고, 각 노드의 정보가 잘 구별되지 않기 때문에 노드의 표현을 학습할 때 고정점을 사용하는 것이 적합하지 않다. 

 

이와 같은 문제로 인해 Vanila GNN의 한계를 극복하는 여러 변형 모델이 나왔으며 대표적인 모델로는 GGNN(Gated Graph Neural Network), R-GCN(Relational Graph Convolution Network)가 있다. 

 

 

Vanila GNN의 기본적인 내용은 이로써 마친다. 바나흐 고정점 정리는 GNN을 시작할 때 기본적으로 이해해야할 내용이며, 이를 제대로 이해하기 위해서는 '코시 수열'과 '완비성'에 대해서 보다 깊게 다루고, 바나흐 고정점 정리를 한 번 증명해보면 된다.