12. Temporal graph 코드로 알아보기

 

Contents
1. Dynamic graphs
2. EvolveGCN: 웹 트래픽 예측하기
3. 코로나 확산 예측하기

 

이전 포스팅까지는 노드와 엣지가 변하지 않는, 고정된 그래프를 대상으로 했습니다. 그러나 실제로는 시간이 지나면서 새로운 노드가 생기기도 하고, 노드 간의 연결 상태가 변하기도 합니다. 예를 들어, 소셜 네트워크에서는 사람들이 다른 사용자를 팔로우, 언팔로우하는 경우가 있습니다. 추천 시스템에서는 사용자들이 새로운 아이템들을 구매하면서 사용자와 아이템 간의 연결 상태가 지속적으로 변할 것입니다. 이러한 동적 요소는 이전에 설명한 GNN 아키텍처를 사용하여 표현할 수 없습니다. 대신, 정적 그래프를 동적 그래프로 변환하기 위해 새로운 시간적 차원을 포함해야 합니다. 이러한 동적 네트워크를 표현하기 위해 Temporal Graph Neural Networks, T-GNNs을 사용합니다. 

 

1. Dynamic graphs

시간에 따라 동적으로 변화하는 dynamic graph는 다양한 분야에서 활용됩니다. 예를 들어, 웹 트래픽을 예측하거나 감염병의 진행을 예측하고, 추천 시스템에서 세션 기반 예측에도 사용됩니다. 이러한 시계열 예측은 보통 노드 간의 관계를 예측하는 link prediction 작업을 수행합니다. 이는 과거의 그래프 구조의 변화를 학습하여 이후 새로운 시점의 그래프를 예측하는 구조로, 머신러닝에서 시계열 예측과 같은 방식입니다. Dynamic graph의 구조를 두 가지로 분류할 수 있습니다.

 

• Static graphs with temporal signals: 기반이 되는 그래프의 구조는 변하지 않지만, 그래프 내부의 노드 피처, 엣지들이 변화합니다.
• Dynamic graphs with temporal signals: 그래프 구조와 노드 피처, 엣지, 노드의 레이블까지 모든 그래프 구성 요소가 시간에 따라 동적으로 변화합니다.

 

이 두가지 타입의 dynamic 그래프를 예제를 통해 코드로 알아보겠습니다.

 

2. EvolveGCN: 웹 트래픽 예측하기

이번 예제에서는 static graphs with temporal signals 그래프의 예시로, 위키피디아 글의 트래픽 데이터를 가지고 temporal GNN을 적용해 보겠습니다. 위키 피디아 글들이 연결된 시계열 데이터를 통해 새로운 예측에 대한 traffic forecasting을 수행합니다. 먼저 적용할 temporal GNN 아키텍처인 EvloveGCN을 소개하겠습니다. 

 

EvolveGCN은 GNN 구조에 딥러닝에서 시계열 데이터를 학습하는 RNN 구조를 적용한 것입니다. EvolveGCN의 특징은 RNN을 GCN의 파라미터 자체로 적용했다는 것입니다. 여기서는 GCN 구조가 시간이 지날수록 진화(evolve)합니다. 이러한 구조는 temporal node embedding을 생성하기 위해 적용되었습니다. 아래는 EvloveGCN의 그림입니다.

이 아키텍처는 두 가지 변형을 취합니다.

 

• EvolveGCN-H: 적용된 recurrent neural network가 이전 GCN 파라미터와 현재 노드 임베딩을 고려합니다. 이는 예측에 노드 피처가 중요한 영향을 미칠 경우 사용됩니다.
• EvolveGCN-O: 적용된 recurrent neural network가 오직 이전 GNC 파라미터만 고려합니다. 이는 그래프 구조 자체가 중요한 영향을 미칠 경우 사용됩니다.

 

EvolveGCN-H은 보통 RNN 계열의 GRU를 적용합니다. 아래 식을 통해 GRU 모델이 t시점의 l번째 GCN의 가중치 행렬을 업데이트 합니다.

$$  W_t^{(l)} = GRU(H_t^{(l)}, W_{t-1}^{(l)}) $$

\(H_t^{(;)}\)은 t시점에서 l번째 GCN 레이어의 노드 임베딩입니다. \(W_{t-1}^{(l)}\)은 이전 타임 스텝에서 l번째 GCN 레이어의 노드 임베딩입니다. 생성된 GCN 가중치 행렬은 다음 레이어의 노드 임베딩을 계산하기 위해 사용됩니다.

$$ H_t^{l+1} = GCN(A_t, H_t^{l}, W_t^{t})  $$

 

이를 그림으로 표현하면 다음과 같습니다.

 

EvolveGCN을 통해 웹트래픽을 예측하는 예제를 구현해 보겠습니다.

 

사용하는 데이터는 static graph with a temporal signal 구조입니다. WikiMaths 데이터셋은 1,068개의 기사를 나타내는 노드로 구성됩니다. 노드 피처는 과거의 데일리 방문 횟수입니다. 엣지의 가중치는 출발 노드에서 도착 노드까지의 연결된 링크의 수입니다. 본 데이터셋을 통해 Wikipedia 페이즈의 방문 횟수를 예측하는 것이 목표입니다.

 

PyTorch Geometric Temporal 라이브러리를 통해 시계열 그래프를 구현하겠습니다.

 

먼저 필요한 라이브러리를 불러오고 데이터셋을 불러옵니다.

WikiMaths 데이터셋에서 dataset[0]은 t=0 시점의 그래프입니다.

dataset[100]은 t=100 시점의 그래프, dataset[500]은 t=500 시점의 그래프입니다. train-test 비율은 0.5로 설정했습니다.

이때 데이터가 랜덤 하게 분할되는 것이 아니라, trainset은 데이터 셋에서 앞선 시점의 데이터, testset은 뒤 시점의 데이터로 분리됩니다.

import torch
!pip install -q torch-scatter~=2.1.0 torch-sparse~=0.6.16 torch-cluster~=1.6.0 torch-spline-conv~=1.2.1 torch-geometric==2.2.0 -f https://data.pyg.org/whl/torch-{torch.__version__}.html
!pip install -q torch-geometric-temporal==0.54.0

torch.manual_seed(0)
torch.cuda.manual_seed(0)
torch.cuda.manual_seed_all(0)
torch.backends.cudnn.deterministic = True
torch.backends.cudnn.benchmark = False

from torch_geometric_temporal.signal import temporal_signal_split
from torch_geometric_temporal.dataset import WikiMathsDatasetLoader
from torch_geometric_temporal.nn.recurrent import EvolveGCNH


from torch_geometric_temporal.signal import temporal_signal_split
from torch_geometric_temporal.dataset import WikiMathsDatasetLoader
from torch_geometric_temporal.nn.recurrent import EvolveGCNH

import pandas as pd
import matplotlib.pyplot as plt
from tqdm import tqdm

dataset = WikiMathsDatasetLoader().get_dataset()
train_dataset, test_dataset = temporal_signal_split(dataset, train_ratio=0.5)

dataset[0]

### result ###

Data(x=[1068, 8], edge_index=[2, 27079], edge_attr=[27079], y=[1068])

 

Static 그래프이기 때문에 노드와 엣지의 차원은 변하지 않습니다. 하지만 temporal signal 이기 때문에 세부적인 값을 달라집니다. 1,068개의 모든 노드를 시각화하기는 힘들기 때문에, 각 시점에서 모든 노드의 평균과 표준 편차를 시각화하겠습니다. 또한 시계열적으로 변하는 그래프이기 때문에 이동 평균을 도입했습니다. 

mean_cases = [snapshot.y.mean().item() for snapshot in dataset]
std_cases = [snapshot.y.std().item() for snapshot in dataset]
df = pd.DataFrame(mean_cases, columns=['mean'])
df['std'] = pd.DataFrame(std_cases, columns=['std'])
df['rolling'] = df['mean'].rolling(7).mean()

plt.figure(figsize=(10,5))
plt.plot(df['mean'], 'k-', label='Mean')
plt.plot(df['rolling'], 'g-', label='Moving average')
plt.grid(linestyle=':')
plt.fill_between(df.index, df['mean']-df['std'], df['mean']+df['std'], color='r', alpha=0.1)
plt.axvline(x=360, color='b', linestyle='--')
plt.text(360, 1.5, 'Train/test split', rotation=-90, color='b')
plt.xlabel('Time (days)')
plt.ylabel('Normalized number of visits')
plt.legend(loc='upper right')

 

Temporal GNN은 node_count와 input dimension 두 가지 파라미터를 입력받습니다.

본 예제에서는 EvolveGCN-H와 Linear 두 가지 레이어로 이루어진 GNN 아키텍처를 구현했습니다.

import torch
torch.manual_seed(0)

class TemporalGNN(torch.nn.Module):
    def __init__(self, node_count, dim_in):
        super().__init__()
        self.recurrent = EvolveGCNH(node_count, dim_in)
        self.linear = torch.nn.Linear(dim_in, 1)

    def forward(self, x, edge_index, edge_weight):
        h = self.recurrent(x, edge_index, edge_weight).relu()
        h = self.linear(h)
        return h

# dataset[0].x.shape[0]: Num nodes
# dataset[0].x.shape[1]: Dim nodes

model = TemporalGNN(dataset[0].x.shape[0], dataset[0].x.shape[1])
optimizer = torch.optim.Adam(model.parameters(), lr=0.01)
model.train()

# Training 50 epochs
for epoch in tqdm(range(50)):
    for i, snapshot in enumerate(train_dataset):
        y_pred = model(snapshot.x, snapshot.edge_index, snapshot.edge_attr)
        loss = torch.mean((y_pred-snapshot.y)**2)
        loss.backward()
        optimizer.step()
        optimizer.zero_grad()

# Evaluation
model.eval()
loss = 0
for i, snapshot in enumerate(test_dataset):
    y_pred = model(snapshot.x, snapshot.edge_index, snapshot.edge_attr)
    mse = torch.mean((y_pred-snapshot.y)**2)
    loss += mse
loss = loss / (i+1)
print(f'MSE = {loss.item():.4f}')

### result ###

100%|██████████| 50/50 [07:29<00:00,  8.98s/it]
MSE = 0.7645

 

예측된 그래프의 노드 평균과 표준편차를 시각화해 보겠습니다.

y_preds = [model(snapshot.x, snapshot.edge_index, snapshot.edge_attr).squeeze().detach().numpy().mean() for snapshot in test_dataset]

plt.figure(figsize=(10,5), dpi=300)
plt.plot(df['mean'], 'k-', label='Mean')
plt.plot(df['rolling'], 'g-', label='Moving average')
plt.plot(range(360,722), y_preds, 'r-', label='Prediction')
plt.grid(linestyle=':')
plt.fill_between(df.index, df['mean']-df['std'], df['mean']+df['std'], color='r', alpha=0.1)
plt.axvline(x=360, color='b', linestyle='--')
plt.text(360, 1.5, 'Train/test split', rotation=-90, color='b')
plt.xlabel('Time (days)')
plt.ylabel('Normalized number of visits')
plt.legend(loc='upper right')

 

3. 코로나 확산 예측하기

이번 장에서는 코로나 확산 예측에 temporal graph를 적용하겠습니다. 사용하는 데이터셋은 2020년 3월 3일부터 5월 12일까지 129개의 영국 NUTS 3 지역에서 보고된 COVID-19 사례 수를 나타냅니다. 데이터는 Facebook 애플리케이션을 설치한 휴대폰에서 수집된 이동 데이터 입니다. 이 예제의 목표는 각 노드(지역)에서 1일 후의 감염병 사례의 수를 예측하는 것입니다.

 

데이터 셋은 영국 지역을 \(G = (V, E)\)로 나타냅니다. 그래프에서 각 노드의 feature는 해당 지역의 이전 날 코로나 감염 수를 의미합니다. 엣지는 undirected로 엣지 가중치 \(w_{v,u}^{(t)}\)를 가진 \((v,u)\) 엣지는 지역 v에서 지역 u로 이동한 \(t\)시점의 사람 수를 의미합니다. 이때 그래프에서 self-loop는 같은 지역 내에서 이동한 사람입니다.

 

코로나 확산 예측을 위해 메시지 파싱 네트워크와(MPNN) LSTM 네트워크를 결합한 MPNN-LSTM 모델을 사용하겠습니다.

먼저, 모델은 입력 노드의 feature와 엣지 인덱스, 가중치를 GCN 레이어에 입력받습니다. 이후 Batch normalization과 dropout 레이어를 거칩니다. 이러한 일련의 과정이 두 번 반복됩니다. 이후 노드 임베딩 매트릭스 \(H^{(t)}\)를 생성합니다. 이후 \(H^{(1)}, ..., H^{(T)}\)의 노드 임베딩 시퀀스를 만들고, 이를 각 time step에서의 MPNN에 적용합니다. 최종적으로 linear transformation을 통해 \(t+1\) 시점의 예측을 수행합니다. 모델의 전체적인 과정은 아래와 같습니다.

 

 

먼저 데이터셋을 불러오고, 각 time step에서 모든 노드의 평균과 표준 편차를 시각화하여 전체적인 데이터 경향을 살펴보겠습니다.

import pandas as pd
import matplotlib.pyplot as plt
from torch_geometric_temporal.dataset import EnglandCovidDatasetLoader
from torch_geometric_temporal.signal import temporal_signal_split

dataset = EnglandCovidDatasetLoader().get_dataset(lags=14)
train_dataset, test_dataset = temporal_signal_split(dataset, train_ratio=0.8)

mean_cases = [snapshot.y.mean().item() for snapshot in dataset]
std_cases = [snapshot.y.std().item() for snapshot in dataset]
df = pd.DataFrame(mean_cases, columns=['mean'])
df['std'] = pd.DataFrame(std_cases, columns=['std'])
                         
plt.figure(figsize=(10,5))
plt.plot(df['mean'], 'k-')
plt.grid(linestyle=':')
plt.fill_between(df.index, df['mean']-df['std'], df['mean']+df['std'], color='r', alpha=0.1)
plt.axvline(x=38, color='b', linestyle='--', label='Train/test split')
plt.text(38, 1, 'Train/test split', rotation=-90, color='b')
plt.xlabel('Reports')
plt.ylabel('Mean normalized number of cases')

 

이후 모델을 생성하기 위해 MPNN-LSTM 모델을 불러옵니다.

이 모델은 input dimension, hidden dimension, number of nodes 세 가지 파라미터를 입력으로 받습니다.

위 설명대로 dropout 레이어와 linear 레이어를 생성했습니다.

 

forward() 함수는 edge weights를 추가적으로 입력받습니다.

이 모델은 dynamic graph를 다루기 때문에, forward()의 edge_index와 edge_weight가 각 time step마다 제공됩니다.

Linear층에는 활성화 함수로 tanh를 적용했습니다.

from torch_geometric_temporal.nn.recurrent import MPNNLSTM

class TemporalGNN(torch.nn.Module):
    def __init__(self, dim_in, dim_h, num_nodes):
        super().__init__()
        self.recurrent = MPNNLSTM(dim_in, dim_h, num_nodes, 1, 0.5)
        self.dropout = torch.nn.Dropout(0.5)
        self.linear = torch.nn.Linear(2*dim_h + dim_in, 1)

    def forward(self, x, edge_index, edge_weight):
        h = self.recurrent(x, edge_index, edge_weight).relu()
        h = self.dropout(h)
        h = self.linear(h).tanh()
        return h

model = TemporalGNN(dataset[0].x.shape[1], 64, dataset[0].x.shape[0])
print(model)

생성된 모델은 두 개의 batch_norm layer와 두 개의 LSTM 레이어로 구성됩니다.

### result ###

TemporalGNN(
  (recurrent): MPNNLSTM(
    (_convolution_1): GCNConv(14, 64)
    (_convolution_2): GCNConv(64, 64)
    (_batch_norm_1): BatchNorm1d(64, eps=1e-05, momentum=0.1, affine=True, track_running_stats=True)
    (_batch_norm_2): BatchNorm1d(64, eps=1e-05, momentum=0.1, affine=True, track_running_stats=True)
    (_recurrent_1): LSTM(128, 64)
    (_recurrent_2): LSTM(64, 64)
  )
  (dropout): Dropout(p=0.5, inplace=False)
  (linear): Linear(in_features=142, out_features=1, bias=True)
)

 

100 에포크 학습 결과 1.4567의 MSE를 얻었습니다.

optimizer = torch.optim.Adam(model.parameters(), lr=0.001)
model.train()

# Training
for epoch in tqdm(range(100)):
    loss = 0
    for i, snapshot in enumerate(train_dataset):
        y_pred = model(snapshot.x, snapshot.edge_index, snapshot.edge_attr)
        loss = loss + torch.mean((y_pred-snapshot.y)**2)
    loss = loss / (i+1)
    loss.backward()
    optimizer.step()
    optimizer.zero_grad()

# Evaluation
model.eval()
loss = 0
for i, snapshot in enumerate(test_dataset):
    y_pred = model(snapshot.x, snapshot.edge_index, snapshot.edge_attr)
    mse = torch.mean((y_pred-snapshot.y)**2)
    loss += mse
loss = loss / (i+1)
print(f'MSE: {loss.item():.4f}')

### result ###
100%|██████████| 100/100 [00:26<00:00,  3.84it/s]
MSE: 1.4567

 

이번 포스팅에서는 시간에 따라 변하는 새로운 유형의 그래프 네트워크를 소개했습니다. 이 시간적 구성 요소는 시계열 예측과 관련된 많은 응용 분야에 사용됩니다. 또한 두 가지 GNN 아키텍처를 코드로 구현했습니다. 먼저, GCN 파라미터를 업데이트하기 위해 GRU 또는 LSTM 네트워크를 사용하는 EvolveGCN 아키텍처를 구현했습니다. 이를 웹 트래픽 예측 작업에서 적용한 결과를 알아보았습니다. 또한, 코로나 예측을 위해 MPNN-LSTM 아키텍처를 사용했습니다. 이상으로 temporal 그래프에 대한 설명을 마치겠습니다. 감사합니다.

 

 

Reference 

• Hands-On Graph Neural Networks Using Python, published by Packt.
• A. Pareja et al., EvolveGCN: Evolving Graph Convolutional Networks for Dynamic Graphs. arXiv, 2019. DOI: 10.48550/ARXIV.1902.10191.openai.com
• A. Pareja et al., EvG. Panagopoulos, G. Nikolentzos, and M. Vazirgiannis. Transfer Graph Neural Networks for Pandemic Forecasting. arXiv, 2020. DOI: 10.48550/ARXIV.2009.08388.olveGCN: Evolving Graph Convolutional Networks for Dynamic Graphs. arXiv, 2019. DOI: 10.48550/ARXIV.1902.10191.openai.com