[머신 러닝/딥 러닝] 그래프 합성곱 신경망 (Graph Convolutional Network, GCN)

1. 그래프 데이터

대부분의 머신 러닝 알고리즘은 입력 데이터가 유클리드 공간 (Euclidean space)에 존재함을 가정하고 있다. 즉, 통계 데이터나 이미지처럼 입력 데이터가 벡터의 형태로 표현될 수 있어야 한다. 그러나 소셜 네트워크, 관계형 데이터베이스, 분자 구조 등과 같이 객체들과 그 객체들 간의 관계로 표현되는 데이터 (그림 1)는 기본적으로 아래와 같이 그래프로 표현된다.

그림 1. 다양한 종류의 그래프 데이터.

• 소셜 네트워크: 사용자는 node로 표현되며, 친구 관계에 있는 사용자은 edge로 연결된다.
• 관계형 데이터베이스: 하나의 데이터베이스 또는 테이블은 node로 표현되며, 데이터간의 연관성이 있거나 쿼리를 처리하기 위해 참조해야하는 데이터베이스 또는 테이블은 edge로 연결된다.
• 분자 구조: 각 원자는 node로 표현되며, 결합된 원자들 사이에는 결합을 나타내는 edge가 추가된다.

또한, 만약 사용자나 원자의 속성, 연결의 종류 등을 고려해야하는 경우에는 단순히 node와 edge로 이루어진 그래프가 아니라, node faeture matrix와 edge feature matrix가 추가된 속성 그래프 (attributed graph)로 데이터를 표현해야 한다. 이러한 형태의 그래프 데이터는 유클리드 공간에 존재하지 않으며, 직접적인 방식으로 벡터의 형태로 변환하는 것 또한 불가능하다. 따라서, 벡터 형태의 입력 데이터를 가정하는 기존의 인공신경망 (Artificial Neural Network, ANN)으로는 분자 구조와 같은 그래프 형태의 데이터를 처리할 수 없다는 문제점이 존재한다.

 

2. 이미지 데이터와 합성곱 (Convolution)

이미지 데이터는 그림 2와 같이 node 간의 연결이 규칙적이고, 각 node의 feature는 RGB로 표현되는 색상 코드인 그래프로 볼 수 있다.

그림 2. 이미지 데이터에 대한 그래프 표현.

이미 오래전부터 머신 러닝 분야에서는 이미지 데이터를 효과적으로 처리하기 위한 여러 방법들이 연구되어왔으며, 그 중에서도 convolution을 이용한 인공신경망인 합성곱 신경망 (Convolutional Neural Network, CNN)은 매우 뛰어난 성능을 보여주었다. 그래프에 대한 convolution을 심도 있게 이해하기 위해서는 먼저 CNN을 공부하는 것을 추천한다.

일반적인 벡터 형태의 데이터가 아닌, 이미지 데이터에서는 각 픽셀들의 위치가 그 자체로 매우 중요한 정보이기 때문에 데이터의 구조를 고려하는 것이 매우 중요하다. CNN은 이러한 이미지 데이터의 특성을 반영하기 위해 convolution을 이용하여 데이터의 구조를 고려한 분류 및 예측을 가능하게 만들었다.

데이터의 구조를 고려해야 한다는 점은 이미지뿐만 아니라 그래프 데이터에서도 매우 중요하기 때문에 이미지에 대한 convolution을 일반화하여 그래프 데이터에 적용하기 위한 연구가 머신 러닝 분야에서 활발히 진행되었다. 그래프 합성곱 신경망 (Graph Convolutional Network, GCN)은 이미지에 대한 convolution을 그래프 데이터로 확장한 머신 러닝 알고리즘이다.

 

3. Graph Convolution

GCN에서는 graph convolution을 이용하여 그래프에 포함된 node나 그래프 자체를 벡터 형태의 데이터로 변환한다. 기본적인 GCN에서는 node의 feature만을 고려하기 때문에 edge feature가 존재하는 그래프는 이 글에서 다루지 않는다. 따라서 그래프는 $G = (A, X)$와 같이 정의되며, $A \in \mathbb{R}^{N \times N}$는 각 node의 연결을 나타내는 인접 행렬 (Adjacency matrix)이고 $X \in \mathbb{R}^{N \times d}$는 node feature matrix이다. 이 때, $N$은 그래프에 포함된 node의 수, $d$는 node feature vector의 차원 (node feature의 수)이다.

그래프에 대한 convolution $\psi$는 $A$와 $X$를 입력 받아 $H \in \mathbb{R}^{N \times m}$라는 새로운 latent node feature matmrix를 생성한다. 이 때, $m$은 latent feature vector의 차원이다. 가장 기본적인 convolution은 다음과 같이 정의된다.

$$H = \psi(A, X) = \sigma(A X W) \tag{1}$$

이 때, $W \in \mathbb{R}^{d \times m}$는 학습이 가능한 weight matrix이며, GCN을 학습시킨다는 것은 이 weight matrix을 조정하는 것과 같다. 식 1에서 $\sigma$는 sigmoid나 ReLU와 같이 비선형적인 출력을 생성하기 위한 non-linear activation function이다.

Graph convolution 기본적인 개념은 어떠한 node의 latent vector를 해당 node의 neighbor로 표현하는 것이다. 예를 들어, 그림 3과 같이 3차원 node feature vector를 갖는 8개의 node로 구성된 그래프와 해당 그래프에 해당 인접 행렬이 주어졌을 때, 이 그래프에 대해 convolution을 적용하는 것을 생각해볼 수 있다.

그림 3. 예시 그래프와 해당 그래프에 대한 인접 행렬.

먼저, node feature matrix $X$와 weight matrix $W$를 곱함으로써 다음과 같은 $N \times m$ 차원의 node feature matrix을 얻을 수 있다. 이 때, $m=2$로 가정한다.

$$S = \begin{bmatrix} x_{11} & x_{12} & x_{13} \\ x_{21} & x_{22} & x_{23} \\ \vdots & \vdots & \vdots \\ x_{81} & x_{82} & x_{83} \end{bmatrix} \begin{bmatrix} w_{11} & w_{12} \\ w_{21} & w_{22} \\ w_{31} & w_{32} \end{bmatrix} = \begin{bmatrix} \sum_{i=1}^{3} w_{i1}x_{1i} & \sum_{i=1}^{3} w_{i2}x_{1i} \\ \sum_{i=1}^{3} w_{i1}x_{2i} & \sum_{i=1}^{3} w_{i2}x_{2i} \\ \vdots & \vdots \\ \sum_{i=1}^{3} w_{i1}x_{8i} & \sum_{i=1}^{3} w_{i2}x_{8i} \end{bmatrix} \tag{2}$$

그 다음, 인접 행렬 $A$와 $S$를 곱하면 아래의 그림 4와 같이 각 node의 latent feature vector는 해당 node의 neighbor node를 기반으로 계산된다.

그림 4. Graph convolution을 통한 노드 7번의 첫 번째 latent feature 생성.

그림 4에서 $s_{ij}$는 $\sum_{k=1}^{3} w_{kj} x_{ik}$와 같다. 이러한 방식으로 graph convolution $\psi(A, X) = \sigma(A X W)$를 통해 그래프에 존재하는 모든 node에 대한 $m$차원 latent feature matrix를 생성할 수 있다.

 

3.1. 인접 행렬의 한계점

위에서 설명한 것과 같이 인접 행렬 $A$를 그대로 이용하는 합성곱은 아래와 같은 두 가지 한계점이 존재한다.

• $A$에는 neighbor node와의 연결만 표현되어 있기 때문에 graph convolution 과정에서 해당 node 자체에 대한 정보는 latent feature vector를 만들 때 고려되지 않는다.
• 일반적으로 $A$는 정규화되어 있지 않기 때문에 feature vector와 $A$를 곱할 경우 feature vector의 크기가 불안정하게 변할 수 있다.

두 가지 문제점을 해결하기 위해 GCN을 구현할 때는 $A$에 self-loop를 추가하고, $A$를 $D^{-1/2} A D^{-1/2}$로 정규화한다. 이 때, $D$는 $A$의 차수 행렬 (degree matrix)이다. Self-loop가 추가된 인접 행렬을 $\tilde{A}$라고 하면, $\tilde{A}$는 다음과 같이 정의된다.

$$\tilde{A} = A + I \tag{3}$$

또한, $\tilde{A}$를 이용한 정규화된 graph convolution은 다음과 같이 정의된다.

$$\psi(\tilde{A}, X) = \sigma(\tilde{D}^{-1/2} \tilde{A} \tilde{D}^{-1/2} X W) \tag{4}$$

이 식에서 $\tilde{D}$는 $\tilde{A}$의 차수 행렬을 의미한다. 대부분의 딥 러닝 라이브러리에는 $A$에 self-loop를 추가하는 것과 $A$를 정규화하여 graph convolution을 적용하는 것이 구현되어있기 때문에 식 (4)가 정확히 어떻게 계산되는지 아는 것보다는 self-loop와 정규화를 적용하는 이유를 이해하는 것이 필요하다.

 

4. 그래프 합성곱 신경망 (GCN)

아래의 그림 5와 같이 GCN은 일반적으로 graph convolution으로 정의되는 graph convolution layer와 fully-connected layer로 구성된다.

그림 5. 일반적인 GCN의 구조.

그림 5에서 readout은 graph convolution layer를 통해 생성된 latent feature matrix를 그래프 전체를 표현하는 하나의 벡터로 변환하는 함수이다. 일반적으로 readout은 전체 node의 latent feature vector를 평균내어 그래프 전체를 표현하는 하나의 벡터를 생성한다. Graph classification/regression에서는 readout이 필수적이지만, node classification이나 link prediction에서는 readout이 없는 구조를 이용한다.

GCN에서 가장 중요한 부분은 graph convolution layer이다. Graph convolution layer를 통해 그래프 형태의 데이터는 행렬 형태의 데이터로 변환되기 때문에 graph convolution layer를 거친 그래프 형태의 데이터는 기존의 머신 러닝 알고리즘을 그대로 적용할 수 있게 변환된다.

각 graph convolution layer는 식 (4)와 거의 동일하게 하나의 graph convolution으로 정의된다. 따라서, $k$번째 graph convolution layer의 출력 $H^{(k)}$는 다음과 같이 정의된다.

$$H^{(k)} = \sigma(\tilde{D}^{-1/2} \tilde{A} \tilde{D}^{-1/2} H^{(k-1)} W^{(k)}) \tag{5}$$

위의 식에서 $H^{(k-1)}$은 이전 graph convolution layer의 출력이며, $W^{(k)}$는 해당 layer의 weight matrix이다. 첫 번째 graph convolution layer의 입력인 $H^{(0)}$는 입력 node feature matrix $X$와 같다. GCN은 이러한 graph convolution layer를 반복적으로 적용하여 그래프에 포함된 각 node들의 추상화된 latent feature를 추출해낸다.

 

5. 구현

GCN을 비롯한 graph neural network (GNN)을 직접 구현하는 것은 인접 행렬과 node feature matrix를 추출하는 것부터 여러 그래프의 batch를 만드는 것 까지 많은 어려움이 따른다. PyTorch를 기준으로는 Deep Graph Library (DGL)와 PyTorch Geometric이라는 라이브러리가 GNN과 이를 이용한 딥 러닝에 관한 여러 구현을 제공하고 있다.

 

6. Graph Neural Network (GNN)

GCN은 단순히 그래프 처리를 위한 인공신경망의 한 종류로써, GCN 이외에도 다양한 종류의 GNN이 존재한다. GNN의 종류와 성능은 기본적으로 그래프 데이터를 행렬로 변환하는 연산 (GCN에서는 graph convolution)의 정의에 의해 결정된다. 일반적으로 GNN에서는 이 연산을 aggregation function이라고 하며, aggregation function $\psi$는 다음과 같이 정의된다.

$$\psi(A, X, E) = f(A, X, E) \tag{6}$$

이 식에서 $E$는 edge들의 속성을 나타내는 edge feature matrix이다.

GCN에서는 $E$를 무시하고, $f$를 식 (4)와 같이 graph convolution으로 정의함으로써 그래프 데이터를 처리했다. 또 다른 대표적인 GNN 중 하나인 Graph Attention Network (GAT)에서는 마찬가지로 $E$를 무시하고, attention mechanism을 기반으로 $f$를 정의했다. 이외에도 Message Passing Neural Network (MPNN)에서는 $X$뿐만 아니라, $E$까지 고려한 aggregation function을 제안했다.