3부 : GCN

Introduction

Vanilla GNN은 잘 동작한다. 하지만 문제가 있다. 이웃 정보를 그냥 더한다. 이 방식은 단순하지만, 그래프에서는 치명적인 문제가 발생한다. 그래서 등장한 것이 GCN이다.

이번 챕터에서는 Graph Convolutional Network(GCN)을 다룬다. GCN은 그래프 데이터를 다룰 때 가장 널리 사용되는 GNN 구조로, 그래프에서의 Convolution 연산을 효율적으로 근사한 모델이다.

이전 Chapter에서 구현한 Vanilla GNN은 단순히 이웃 정보를 합치는 구조였지만, 한계가 존재한다. 이번 챕터에서는 이러한 한계를 분석하고, 왜 GCN이 더 좋은 성능을 내는지 이해하는것이 목표이다.

Designing The Graph Convolutional Layer

문제상황 : 그래프에서 노드마다 이웃의 개수가 다르다

• 어떤 노드 : 이웃 3개
• 어떤 노드 : 이웃 1개
  즉, 데이터가 불균형 하다.

이웃이 많은 노드는 더 많은 정보를 받는다. 즉, 정보의 크기가 아니라 "연결 수"에 따라 값이 결정된다. 이것은 잘못된 학습이다.

기존 Vanilla GNN의 한계

기존 GNN Layer은 이 차이를 고려하지 않는다.
단순히 이웃 노드들의 feature을 더하는 방식이다.

$h_i = \sum_{j \in N_i} x_j W^T$

문제 발생

이방식의 문제는 Embedding을 할때, 이웃이 많은 노드는 embedding 값이 커지고, 이웃이 적은 노드는 embedding 값이 작다.
예를들어, 어떤 노드는 이웃이 1000개 일수 있는데, 어떤 노드는 이웃이 1개다.
이 경우:

$h_A \gg h_B$

이렇게 되면 Embedding 값을 서로 비교하기 어렵다.

해결 방안 : Normalization

이 문제를 해결하기 위해,
이웃 개수로 나누는 방식(Normalization)을 사용한다.

노드 i의 degree를 deg(i)라고 하면,

$h_i = \frac{1}{\deg(i)} \sum_{j \in N_i} x_j W^T$

기존에는 단순 합이었지만,이제 평균으로 하면서 이웃수에 관계 없이 안정적인 표현을 생성할 수 있다.

결국 GCN의 핵심은 하나다. "이웃 정보를 평균낸다"
합(sum)이 아니라, 평균(mean)을 사용한다.

행렬 형태

이전 Vanilla GNN Layer는 다음과 같이 표현되었다.

$H = \tilde{A}^T X W^T$

하지만, 이 방식은 Normalization이 적용되지 않은 형태이다.

Degree Matrix와 Normalization

1. Self-Loop 추가
   먼저, 인접 행렬에 자기 자신을 포함한다.

   $\tilde{A} = A + I$

• 부족했던 것
  이전식에서 부족했던 것은 다음이다:

  $\frac{1}{\deg(i)}$

즉, Normalization 계수가 부족했다.

2. Degree Matrix 정의
   이 계수를 만들기 위해 Degree Matrix D를 사용한다.

• D는 각 노드의 이웃 개수를 담는 행렬
• 대각선에만 값이 있음

예시 :

$D = \begin{pmatrix} 3 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 2 & 0 \\ 0 & 0 & 0 & 2 \end{pmatrix}$

의미 :

• 노드 1 -> 이웃 3개
• 노드 2 -> 이웃 1개
• 노드 3 -> 이웃 2개
• 노드 4 -> 이웃 2개

3. 핵심 아이디어

   D는 각 노드의 deg(i)를 담고 있다.

따라서 :

$D^{-1}$

를 사용하면,

$\frac{1}{\deg(i)}$

을 한번에 표현할 수 있다.

4. Inverse Degree Matrix

   $D^{-1} = \begin{pmatrix} \frac{1}{3} & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & \frac{1}{2} & 0 \\ 0 & 0 & 0 & \frac{1}{2} \end{pmatrix}$

의미 : 각 노드를 이웃 수로 나누는 효과

5. Normalization을 어디에 적용할까?
   이제 이 Normalization Matrix를 어디에 곱할지 결정해야 한다.
   두 가지 선택지가 있다:

• Row Normalization

  $\tilde{D}^{-1} \tilde{A} X W^T$

의미 :

• 각 노드 기준으로 정규화

• row마다 나눔

• Column Normalization

  $\tilde{A} \tilde{D}^{-1} X W^T$

의미:

• Feature 방향 기준으로 정규화
• Column마다 나눔

두 방식의 차이는 각 row의 합이 1이거나 각 Column의 합이 1이냐이다.

6. 행렬 곱 구현

   $\tilde{D}^{-1} \tilde{A} X W^T$

-> 이웃 정보를 잘 정규화 한다.

• 핵심문제 : 이웃이 많은 노드의 정보가 너무 쉽게 퍼진다.

해결방법 : Hybrid Normalization

GCN 논문에서는 이를 해결하기 위해 양쪽에서 정규화하는 방법을 제안한다.

• 최종 GCN 수식

  $H = \tilde{D}^{-\frac{1}{2}} \tilde{A} \tilde{D}^{-\frac{1}{2}} X W^T$

• Row Normalization : 받는 사람이 공평하게 받음

• Column Normalization : 주는 사람이 공평하게 나눔

GCN은 두가지 정규화 기법을 둘다 사용한다.

이 방식은 "많이 연결된 노드가 정보를 과하게 퍼뜨리는 것"을 막는다.

GCN은 "정보의 양"이 아니라 "정보의 비율"을 학습한다.

$\frac{1}{\sqrt{\deg(A)} \cdot \sqrt{\deg(B)}} = \frac{1}{\sqrt{4} \cdot \sqrt{1}} = \frac{1}{2}$

import torch
torch.manual_seed(1)
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)


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

# Create the Vanilla GNN model
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')

GCN(
(gcn1): GCNConv(1433, 16)
(gcn2): GCNConv(16, 7)
)
Epoch 0 | Train Loss: 1.932 | Train Acc: 15.71% | Val Loss: 1.94 | Val Acc: 15.20%
Epoch 20 | Train Loss: 0.099 | Train Acc: 100.00% | Val Loss: 0.75 | Val Acc: 77.80%
Epoch 40 | Train Loss: 0.014 | Train Acc: 100.00% | Val Loss: 0.72 | Val Acc: 77.20%
Epoch 60 | Train Loss: 0.015 | Train Acc: 100.00% | Val Loss: 0.71 | Val Acc: 77.80%
Epoch 80 | Train Loss: 0.017 | Train Acc: 100.00% | Val Loss: 0.71 | Val Acc: 77.00%
Epoch 100 | Train Loss: 0.016 | Train Acc: 100.00% | Val Loss: 0.71 | Val Acc: 76.40%
GCN test accuracy: 79.70%

Predicting Web Traffic With Node Regression

지금까지는 Classification 문제였다. 그렇다면, 숫자를 예측하는 Regression 문제에도 GCN을 쓸 수 있을까?

머신러닝에서 두 가지 주요 문제는 다음과 같다.

• Classification : 카테고리 예측
• Regression : 연속값 예측

Graph에서의 Regression

그래프 데이터에서도 동일하게 적용된다.

• Node Classification : 노드의 클래스 예측
• Node Regression : 노드의 숫자 값 예측

데이터셋

이번에 사용하는 데이터는 Wikipedia Network dataset이다.

• 노드 : 위키피디아 문서
• 엣지 : 문서 간 링크
• Feature : 단어 포함 여부

목표

각 노드에 대해 다음 값을 예측한다

2018년 12월 평균 월간 웹 트래픽 (log 값)

핵심 아이디어

그래프에서는 연결된 노드들이 서로 비슷한 특성을 가지는 경우가 많다.
따라서,

이웃 노드의 정보를 활용하면 더 정확한 값 예측이 가능하다.

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*4)
        self.gcn2 = GCNConv(dim_h*4, dim_h*2)
        self.gcn3 = GCNConv(dim_h*2, dim_h)
        self.linear = torch.nn.Linear(dim_h, dim_out)

    def forward(self, x, edge_index):
        h = self.gcn1(x, edge_index)
        h = torch.relu(h)
        h = F.dropout(h, p=0.5, training=self.training)
        h = self.gcn2(h, edge_index)
        h = torch.relu(h)
        h = F.dropout(h, p=0.5, training=self.training)
        h = self.gcn3(h, edge_index)
        h = torch.relu(h)
        h = self.linear(h)
        return h

    def fit(self, data, epochs): 
        optimizer = torch.optim.Adam(self.parameters(),
                                      lr=0.02,
                                      weight_decay=5e-4)

        self.train()
        for epoch in range(epochs+1):
            optimizer.zero_grad()
            out = self(data.x, data.edge_index)
            loss = F.mse_loss(out.squeeze()[data.train_mask], data.y[data.train_mask].float())
            loss.backward()
            optimizer.step()
            if epoch % 20 == 0:
                val_loss = F.mse_loss(out.squeeze()[data.val_mask], data.y[data.val_mask])
                print(f"Epoch {epoch:>3} | Train Loss: {loss:.5f} | Val Loss: {val_loss:.5f}")

    def test(self, data):
        self.eval()
        out = self(data.x, data.edge_index)
        return F.mse_loss(out.squeeze()[data.test_mask], data.y[data.test_mask].float())

# Create the Vanilla GNN model
gcn = GCN(dataset.num_features, 128, 1)
print(gcn) 

# Train
gcn.fit(data, epochs=200)

# Test
loss = gcn.test(data)
print(f'\nGCN test loss: {loss:.5f}\n')

GCN(
(gcn1): GCNConv(2325, 512)
(gcn2): GCNConv(512, 256)
(gcn3): GCNConv(256, 128)
(linear): Linear(in_features=128, out_features=1, bias=True)
)
Epoch 0 | Train Loss: 11.41758 | Val Loss: 11.05322
Epoch 20 | Train Loss: 11.30262 | Val Loss: 10.95968
Epoch 40 | Train Loss: 5.22662 | Val Loss: 4.69298
Epoch 60 | Train Loss: 1.14852 | Val Loss: 1.33060
Epoch 80 | Train Loss: 0.62642 | Val Loss: 0.81592
Epoch 100 | Train Loss: 0.47657 | Val Loss: 0.69224
Epoch 120 | Train Loss: 0.41453 | Val Loss: 0.65017
Epoch 140 | Train Loss: 0.36823 | Val Loss: 0.62350
Epoch 160 | Train Loss: 0.34970 | Val Loss: 0.66197
Epoch 180 | Train Loss: 0.33044 | Val Loss: 0.62604
Epoch 200 | Train Loss: 0.29097 | Val Loss: 0.60776
GCN test loss: 0.70021