Contents
1. GCN이란?
2. GCN 구현하기
3. 마무리
이전 포스팅에서 인접 행렬 정보를 반영한 신경망 모델인 GNN을 살펴보았습니다. 이때 일반적인 딥러닝 모델과 같이, 행렬곱 연산을 통해 노드의 정보를 학습했습니다. 이번 포스팅에서 알아볼 GCN (Graph Convolutional Networks)은 이웃 노드의 정보를 aggregation하는 방식으로 레이어를 구성합니다. GCN은 이름에서도 알 수 있듯이, CNN의 아이디어를 가져온 것입니다. 2017년에 논문을 통해 등장한 GCN은 현재 그래프 기반 연구에서 baseline이 되는 기법이라고 할 수 있습니다. 이러한 GCN의 기초 개념과 간단한 코드 구현을 살펴보겠습니다. 본 포스팅에서도 수식과 개념을 다루겠지만, 보다 엄밀하고 정확한 정보를 위해 논문을 참고하시면 좋을 것 같습니다.
참고: Kipf, T. N., & Welling, M. (2016). Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv:1609.02907.
1. GCN이란?
GCN은 Graph Convolutional Network의 약어로, 그래프 데이터를 분석하고 학습하기 위한 그래프 뉴럴 네트워크 구조입니다. 일반적인 신경망에서는 레이어 간에 입력과 가중치 행렬을 행렬곱하여 변환을 수행합니다. 그러나 GCN은 레이어 간의 그래프 구조를 고려하여 노드와 이웃 노드 간의 정보를 집계하는 방식으로 레이어를 구성합니다. GCN의 주요 아이디어는 각 노드의 표현(representation)을 계산하기 위해 이웃 노드의 정보를 사용하는 것입니다. 이를 위해 GCN은 주변 이웃 노드의 정보를 집계하고 이를 현재 노드의 표현에 반영합니다. 이러한 과정은 여러 레이어를 통해 반복되며, 각 레이어는 이웃 노드의 정보를 더 잘 이해하고 활용할 수 있도록 학습됩니다.
본 포스팅에서는 앞 포스팅에서 알아본 GNN의 기본 개념을 확장하는 방법으로, GCN에 대한 간단한 설명과 코드를 소개합니다.
아래 간단한 그래프 예시를 보면, 각 노드가 가진 이웃의 숫자는 서로 다릅니다. 예를 들어 A는 2개(B and C), B는 3개(A, D and E)입니다.
그러나 이전에 다루었던 간단한 GNN 예시에서는 이러한 이웃의 수를 고려하지 않고, 단순히 adjacency matrix를 입력 데이터와 가중치 행렬에 곱해주었습니다. 즉 이러한 레이어는 간단한 합 연산으로 아루어져 있고, normalization이 적용되지 않습니다. 아래는 노드 A의 임베딩을 계산하는 식을 보여줍니다.
$$ h_A = \sum_{i\in N_A} x_i W^T $$
그러나 만약, 노드 A가 1000개의 이웃을 가지고, 노드 B가 단 1개의 이웃을 갖는다면, 임베딩인 \(h_A\)는 \(h_B\)보다 훨씬 클 것입니다. 따라서 이러한 노드가 가진 이웃 수인 degree로 나누어 임베딩 값을 정규화 하는 방법을 생각해볼 수 있습니다. 식은 아래와 같습니다.
$$ h_A = \frac{1}{deg_{(i)}}\sum_{j\in N_A} x_j W^T $$
이를 아래 식과 같이 GNN의 행렬 연산으로 적용해보겠습니다. 여기서 \(tilda{A}\)는 \(A+I\)입니다.
$$H = \tilde{A}^T X W^T$$
위 식에 normalization을 적용하기 위해 degree 정보를 나타내는 degree matrix \(D\)를 나타내보겠습니다.
import numpy as np
np.random.seed(0)
D = np.array([
[3, 0, 0, 0],
[0, 1, 0, 0],
[0, 0, 2, 0],
[0, 0, 0, 2]
])이후 \( \frac{1}{degree(i)} \)를 계산하기 위해 inverse matrix를 구하는 linalg.inv() 함수를 사용합니다.
np.linalg.inv(D)
### result ###
array([[0.33333333, 0. , 0. , 0. ],
[0. , 1. , 0. , 0. ],
[0. , 0. , 0.5 , 0. ],
[0. , 0. , 0. , 0.5 ]])
여기에 degree 행렬에 self-loops를 추가한 단위 행렬을 더한 \({\tilde{D}}^{-1}\)은 아래 와 같습니다.
np.linalg.inv(D + np.identity(4))
### result ###
array([[0.25 , 0. , 0. , 0. ],
[0. , 0.5 , 0. , 0. ],
[0. , 0. , 0.33333333, 0. ],
[0. , 0. , 0. , 0.33333333]])
이제 서로 다른 이웃 개수를 보정할 수 있는 정규화를 위한 행렬을 구했습니다. 이제 이 행렬을 앞에서 본 행렬 곱에 적용합니다. 이때 degree 행렬을 곱하는 위치가 중요합니다. 다음과 같은 두 가지 방법이 있습니다.
정규화 행렬을 앞에 곱해주면 \(\tilde{D}^{-1}\tilde{A} X W^T\), feature의 모든 행이 정규화 됩니다.
정규화 행렬을 뒤에 곱해주면 \(\tilde{A}\tilde{D}^{-1} X W^T\), feature의 모든 열이 정규화 됩니다.
이해를 위해, 코드로 살펴보겠습니다.
행렬곱은 numpy.matmul()로 수행할 수 있습니다. 또는 @ 기호를 통해 Python이 제공하는 행렬 연산을 적용할 수도 있습니다.
위아래 값은 서로를 transpose한 것만 다른, 같은 값을 가집니다. 결과적으로 우리는 첫번째 행렬곱 순서가 노드 피처를 표현하기에 적합한 것을 알 수 있습니다.
A = np.array([
[1, 1, 1, 1],
[1, 1, 0, 0],
[1, 0, 1, 1],
[1, 0, 1, 1]
])
print(np.linalg.inv(D + np.identity(4)) @ A)
print()
print(A @ np.linalg.inv(D + np.identity(4)))### result ###
[[0.25 0.25 0.25 0.25 ]
[0.5 0.5 0. 0. ]
[0.33333333 0. 0.33333333 0.33333333]
[0.33333333 0. 0.33333333 0.33333333]]
[[0.25 0.5 0.33333333 0.33333333]
[0.25 0.5 0. 0. ]
[0.25 0. 0.33333333 0.33333333]
[0.25 0. 0.33333333 0.33333333]]
지금까지 각 노드의 이웃 수에 따른 정규화를 진행하는 과정을 알아보았습니다. 그러나 사실 GCN의 원 논문에서는 조금 더 복잡한 정규화 연산을 제안합니다. 이는 실제 neural network 연산 과정에서는 많은 이웃을 가진 노드의 피처가 비교적 쉽게 전파되기 때문에, 적은 이웃을 가진 노드에 높은 가중치를 주는 hybrid normalization가 적절하다고 말합니다. 식은 아래와 같습니다.
$$ H = \tilde{D}^{-\frac{1}{2}} \tilde{A}^T \tilde{D}^{-\frac{1}{2}} X W^T $$
이를 개별 임베딩에 적용한다면 다음과 같은 operation으로 나타낼 수 있습니다. 이때 모든 노드가 같은 수의 이웃을 가진다면, \( {\sqrt{deg(i)}\sqrt{deg(j)}} = deg(i)\) 라는 것을 알 수 있습니다.
$$h_i =\sum_{j\in N_i} \frac{1}{\sqrt{deg(i)}\sqrt{deg(j)}} x W^T$$
이렇게 graph convolutiona layer를 구성하기 위한 식을 살펴보았습니다. 이제 GCN 레이어를 GNN 아키텍처에 적용해보겠습니다.
2. GCN 구현하기
섹션 1에서는 GCN에서 degree 정보를 기준으로 normailzation 한다는 것을 강조했습니다. 그렇다면 데이터 세트의 degree 분포를 살펴보겠습니다. 앞 포스팅에서 소개한 Cora() 데이터과 Facebook Page-Page 데이터를 활용하겠습니다.
Cora dataset은 2708개의 노드를 가지고 있고, 각 노드의 이웃 수를 의미하는 degree 분포는 long-tail 분포를 가진 것을 확인할 수 있습니다.
from torch_geometric.datasets import Planetoid
from torch_geometric.utils import degree
from collections import Counter
import matplotlib.pyplot as plt
dataset = Planetoid(root=".", name="Cora")
data = dataset[0]
degrees = degree(data.edge_index[0]).numpy()
numbers = Counter(degrees)
fig, ax = plt.subplots()
ax.set_xlabel('Node degree')
ax.set_ylabel('Number of nodes')
plt.bar(numbers.keys(), numbers.values())
FacebookPagePage 데이터세트 역시 비슷한 분포를 가집니다.
from torch_geometric.datasets import FacebookPagePage
# Import dataset from PyTorch Geometric
dataset = FacebookPagePage(root=".")
data = dataset[0]
# Create masks
data.train_mask = range(18000)
data.val_mask = range(18001, 20000)
data.test_mask = range(20001, 22470)
# Get list of degrees for each node
degrees = degree(data.edge_index[0]).numpy()
# Count the number of nodes for each degree
numbers = Counter(degrees)
# Bar plot
fig, ax = plt.subplots()
ax.set_xlabel('Node degree')
ax.set_ylabel('Number of nodes')
plt.bar(numbers.keys(), numbers.values())
이어서 PyG의 GCN layer를 활용하여 Cora 데이터세트에 그래프 뉴럴 네트워크를 적용해보겠습니다.
- __init()__: 입력 데이터의 특성 개수, 히든 레이어의 차원, 출력 결과 값의 차원을 입력 받는다. 이후 2개의 GCN 레이어를 쌓는다.
- forward(): 데이터에서 노드를 나타내는 x와 엣지를 나타내는 edge_index를 입력받는다. log softmax를 통해 classification을 수행한다.
- fit(), test(): 이전 포스팅 참고
import torch
import torch.nn.functional as F
from torch_geometric.nn import GCNConv
dataset = Planetoid(root=".", name="Cora")
data = dataset[0]
# 정확도 함수
def accuracy(y_pred, y_true):
"""Calculate accuracy."""
return torch.sum(y_pred == y_true) / len(y_true)
from torch_geometric.nn import GCNConv
class GCN(torch.nn.Module):
"""Graph Convolutional Network"""
def __init__(self, dim_in, dim_h, dim_out):
super().__init__()
self.gcn1 = GCNConv(dim_in, dim_h)
self.gcn2 = GCNConv(dim_h, dim_out)
def forward(self, x, edge_index):
h = self.gcn1(x, edge_index)
h = torch.relu(h)
h = self.gcn2(h, edge_index)
return F.log_softmax(h, dim=1)
def fit(self, data, epochs):
criterion = torch.nn.CrossEntropyLoss()
optimizer = torch.optim.Adam(self.parameters(),
lr=0.01,
weight_decay=5e-4)
self.train()
for epoch in range(epochs+1):
optimizer.zero_grad()
out = self(data.x, data.edge_index)
loss = criterion(out[data.train_mask], data.y[data.train_mask])
acc = accuracy(out[data.train_mask].argmax(dim=1),
data.y[data.train_mask])
loss.backward()
optimizer.step()
if(epoch % 20 == 0):
val_loss = criterion(out[data.val_mask], data.y[data.val_mask])
val_acc = accuracy(out[data.val_mask].argmax(dim=1),
data.y[data.val_mask])
print(f'Epoch {epoch:>3} | Train Loss: {loss:.3f} | Train Acc:'
f' {acc*100:>5.2f}% | Val Loss: {val_loss:.2f} | '
f'Val Acc: {val_acc*100:.2f}%')
@torch.no_grad()
def test(self, data):
self.eval()
out = self(data.x, data.edge_index)
acc = accuracy(out.argmax(dim=1)[data.test_mask], data.y[data.test_mask])
return acc구성된 신경망에 대해 100 에포크 훈련을 진행하고, 테스트 세트에 적용하겠습니다. 히든 레이어의 피처 수는 16입니다.
# 인스턴스 저장 및 100 에포크 훈련
gcn = GCN(dataset.num_features, 16, dataset.num_classes)
print(gcn)
# Train
gcn.fit(data, epochs=100)
# Test
acc = gcn.test(data)
print(f'\nGCN test accuracy: {acc*100:.2f}%\n')### result ###
GCN(
(gcn1): GCNConv(1433, 16)
(gcn2): GCNConv(16, 7)
)
Epoch 0 | Train Loss: 1.935 | Train Acc: 19.29% | Val Loss: 1.94 | Val Acc: 13.60%
Epoch 20 | Train Loss: 0.095 | Train Acc: 100.00% | Val Loss: 0.83 | Val Acc: 76.60%
Epoch 40 | Train Loss: 0.015 | Train Acc: 100.00% | Val Loss: 0.79 | Val Acc: 76.40%
Epoch 60 | Train Loss: 0.015 | Train Acc: 100.00% | Val Loss: 0.75 | Val Acc: 76.80%
Epoch 80 | Train Loss: 0.017 | Train Acc: 100.00% | Val Loss: 0.74 | Val Acc: 77.20%
Epoch 100 | Train Loss: 0.015 | Train Acc: 100.00% | Val Loss: 0.74 | Val Acc: 77.60%
GCN test accuracy: 80.10%
다음은 페이스북 데이터 세트를 불러오고, 훈련을 진행하겠습니다. 히든 레이어의 피처 수는 16입니다.
# Load Facebook Page-Page
dataset = FacebookPagePage(root=".")
data = dataset[0]
data.train_mask = range(18000)
data.val_mask = range(18001, 20000)
data.test_mask = range(20001, 22470)
# Train GCN
gcn = GCN(dataset.num_features, 16, dataset.num_classes)
print(gcn)
gcn.fit(data, epochs=100)
acc = gcn.test(data)
print(f'\nGCN test accuracy: {acc*100:.2f}%\n')상당히 좋은 정확도를 보여주고 있습니다.
### result ###
GCN(
(gcn1): GCNConv(128, 16)
(gcn2): GCNConv(16, 4)
)
Epoch 0 | Train Loss: 1.490 | Train Acc: 23.92% | Val Loss: 1.51 | Val Acc: 23.76%
Epoch 20 | Train Loss: 0.437 | Train Acc: 85.01% | Val Loss: 0.43 | Val Acc: 86.19%
Epoch 40 | Train Loss: 0.318 | Train Acc: 89.57% | Val Loss: 0.32 | Val Acc: 89.54%
Epoch 60 | Train Loss: 0.276 | Train Acc: 91.18% | Val Loss: 0.28 | Val Acc: 91.00%
Epoch 80 | Train Loss: 0.253 | Train Acc: 92.25% | Val Loss: 0.26 | Val Acc: 91.90%
Epoch 100 | Train Loss: 0.239 | Train Acc: 92.86% | Val Loss: 0.25 | Val Acc: 92.35%
GCN test accuracy: 91.82%
3. 마무리
이번 포스팅에서는 앞에서 알아본 기초적인 GNN 레이어를 개선하여 노드의 degree를 정규화 하는 GCN 기법을 소개했습니다. 또한 PyG에서 제공하는 gcn 레이어를 활용하여 기본적인 아키텍를 구성하고 Cora 및 Facebook Page-Page 데이터세트에 적용했습니다. 정규화 를 적용한 그래프 뉴럴 네트워크는 높은 정확도 점수를 보여주는 것을 확인할 수 있었습니다. 다음 포스팅에서는 그래프 어텐션 네트워크(GAT)를 소개합니다. 즉, 이웃 노드를 중요도에 따라 구분하여 한 단계 나은 알고리즘을 소개할 예정입니다. 이상으로 포스팅 마치겠습니다. 감사합니다.
Reference
Hands-On Graph Neural Networks Using Python, published by Packt.
Kipf, T. N., & Welling, M. (2016). Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv:1609.02907.
'Graph > Graph with Code' 카테고리의 다른 글
| 7. GraphSAGE 이해 및 코드 구현 (7) | 2023.06.30 |
|---|---|
| 6. Graph Attention Networks (GATs) 기초 및 코드 구현 (0) | 2023.06.29 |
| 4. GNN 기초 (직접 코드로 구현하기) (0) | 2023.06.27 |
| 3. 노드 임베딩 (Node2Vec으로 간단한 추천시스템 구현) (0) | 2023.06.26 |
| 2. 그래프 기본 개념 (0) | 2023.06.25 |