10. GNN을 활용한 그래프 생성 코드 구현하기

 

Contents
1. 전통적인 그래프 생성 기법
1.1 The Erdős–Rényi model
1.2 The small-world model
2. GNN 기반 그래프 생성 기법
2.1 Graph variational autoencoders
2.2 Generative adversarial networks

 

본 포스팅에서는 새로운 그래프를 생성하기 위한 그래프 생성 기법을 알아보겠습니다. 그래프 생성은 여러 분야에서 사용됩니다. 예를 들어, 분자 구조 생성, 소셜 네트워크 분석, 도로 네트워크 모델링 등 다양한 응용 분야가 있습니다. 또한, 데이터 증강, 이상 탐지, 약물 발견 등에 주요하게 사용됩니다. GNN을 활용한 그래프 생성은 두 가지 유형으로 구분할 수 있습니다. 첫 번째는 기존의 그래프 데이터를 학습하여 유사한 구조의 새로운 그래프를 생성하는 방법입니다. 이 방법은 기존의 그래프에 대한 특징을 학습하고, 이를 기반으로 새로운 그래프를 생성합니다. 두 번째 방법은 랜덤한 그래프를 생성한 후, GNN을 사용하여 그래프를 수정하는 방법입니다. 이 방법은 초기에 무작위로 생성된 그래프를 기반으로 GNN을 사용하여 그래프를 수정하고 발전시킵니다. GNN 기반그래프 생성을 알아보기 전에 먼저 전통적인 그래프 생성 방법론부터 소개하겠습니다.

 

1. 전통적인 그래프 생성 기법

1.1 The Erdős–Rényi model

The Erdős–Rényi model은 그래프 생성의 대표적인 기법 중 하나입니다. 이 모델은 평균 엣지의 개수와 노드 간의 연결을 무작위로 생성하는 방식으로 동작합니다. 구체적으로는 다음과 같은 단계를 따릅니다.

 

1. 노드 집합을 초기화합니다. 이때, 노드의 개수는 주어진 그래프의 크기에 따라 결정됩니다.
2. 모든 가능한 엣지를 고려하여 각각의 엣지에 대해 확률적으로 연결할지 말지를 결정합니다.
   이때, 연결될 확률은 동일합니다.
3. 확률적으로 결정된 엣지들을 통해 그래프를 생성합니다. 이때, 엣지의 개수는 평균 엣지 개수에 따라 결정됩니다.

Erdős–Rényi model은 \(G(n, p)\) 모델과 \(G(n, M)\) 모델 두 가지 방법이 있습니다.

\(G(n, p)\) 모델은 먼저 노드와 노드를 연결할 확률이 부여합니다. 이러한 확률에 따라, 모든 노드를 서로 무작위로 연결하여 최종 그래프를 생성합니다. 이러한 확률 \(p\)는 생성하고자 하는 네트워크의 밀도, density를 의미한다고 생각할 수도 있습니다. 그렇다면 Erdős–Rényi model을 통해 그래프를 생성해보겠습니다.

 

먼저 필요한 라이브러리를 불러옵니다.

이후 networkx의 nx.erdos_renyi_graph를 통해 (노드 개수, 연결될 확률, 랜덤 시드)를 지정해줍니다.

nx.circular_layout()는 그래프를 시각화하기 위한 그래프의 구조를 지정합니다.

본 예제에서는 circle 형태의 그래프를 생성하겠습니다.

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 deepchem==2.7.1

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

import networkx as nx
import matplotlib.pyplot as plt

G = nx.erdos_renyi_graph(10, 0.9, seed=0)
pos = nx.circular_layout(G)
nx.draw(G, pos=pos)

 

G = nx.erdos_renyi_graph(10, 0.2, seed=0)
pos = nx.circular_layout(G)
nx.draw(G, pos=pos)

 

\(G(n, p)\) 모델에서는 n개의 노드와 m개의 링크를 갖는 모든 그래프 중에서 무작위로 그래프를 선택합니다. 예를 들어, 노드가 3개이고, 엣지가 2개인 경우 가능한 그래프는 세 가지가 존재합니다. 이중에서 랜덤하게 그래프를 하나 생성합니다.

G = nx.gnm_random_graph(3, 2, seed=3)
pos = nx.circular_layout(G)
nx.draw(G, pos=pos)

1.2 The small-world model

The small-world model은 실제 존재하는 그래프 구조와 같이, 생물학적, 기술적, 사회적 네트워크의 동작을 모방랍니다. 주요 개념은 실제 세계의 네트워크가 완전히 무작위적이지도 않고, 완전히 규칙적이지도 않다는 것입니다). 이는 앞의 Erdős–Rényi model과의 차이점 입니다. The small-world 모델은 다음과 같은 특징을 가진 그래프를 생성합니다.

 

1. Short paths: 네트워크 내의 임의의 두 노드 사이의 평균 거리가 상대적으로 작아져 정보가 네트워크 전체에 빠르게 퍼지는 것이 쉬워집니다.
2. High clustering coefficients:: 네트워크의 노드들은 서로 연결되어 있어 밀집된 노드 군집을 형성합니다.

 

그렇다면 대표적으로 Watts– Strogatz model을 구현해보겠습니다. 이 모델은 다음과 같은 단계를 거칩니다.

 

1. 지정된 노드 개수로 그래프를 초기화합니다
2. 각 노드는 가장 가까운 k 개의 이웃 노드와 연결됩니다.
3. 노드 i와 노드 j가 연결될 확률 p는, 노드 i와 다른 무작위 노드 k 사이의 확률로 재연결됩니다.

G = nx.watts_strogatz_graph(10, 4, 0.5, seed=0)
pos = nx.circular_layout(G)
nx.draw(G, pos=pos)

 

2. GNN 기반 그래프 생성 기법

GNN 기반 그래프 생성 모델은 전통적인 기법보다 표현력이 뛰어난 딥러닝 기반 아키텍처입니다. 본 섹션에서는 VAE, GAN 및 autoregressive models을 사용하여 그래프를 생성하는 방법을 구현하겠습니다.

 

2.1 Graph variational autoencoders

지난 포스팅, 그래프를 활용한 링크 예측에서 본 것처럼, VAE는 인접 행렬을 근사화하는 데 사용됩니다. GVAE (Graph variational autoencoders) 모델은 인코더와 디코더, 두 가지 모듈로 구성됩니다. 인코더 모듈은 잠재 정규 분포의 평균과 분산을 학습하기 위해 첫 번째 레이어를 공유하는 두 개의 GCN을 사용합니다. 이후, 디코더는 학습된 분포를 샘플링하여 잠재 변수 간의 내적을 수행합니다. 마지막으로, 인접 행렬을 근사하기 위해, \( \tilde{A} = \sigma(Z^TZ) \)를 구합니다. 이 개념은 지난 포스팅을 참고하시면 좋을 것 같습니다. 이러한 예측된 행렬 \(\tilde{A}\)를 가지고 새로운 그래프를 생성할 수 있습니다.

 

발전된 GVAE 노드와 엣지 특성을 출력하기도 합니다. 가장 인기 있는 VAE 기반 그래프 생성 모델 중 하나인 GraphVAE가 이러한 예시입니다.

 

GraphVAE에서 사용하는 그래프는  G= (A, E, F)로 표현할 수 있습니다. 인접 행렬인 A, 엣지 속성 텐서인 E, 그리고 노드 속성 행렬로 F가 있습니다. GraphVAE는 미리 정의된 노드 수를 갖는 그래프의 확률적 버전을 학습합니다. 이 확률적 버전에서는 \( \tilde{A} \)에는 노드 \(\tilde{A}_{a,a}\)와 엣지 \(\tilde{A}_{a,b}\)의 확률이 포함되어 있으며,  \( \tilde{E} \)에는 엣지의 클래스 확률이, \(\tilde{F}\)에는 노드의 클래스 확률이 포함됩니다. GVAE와 비교하여 GraphVAE의 인코더는 edge-conditional graph convolutions(ECC)을 갖는 피드 포워드 네트워크이고, 디코더는 세 개의 출력을 갖는 다층 퍼셉트론(MLP)입니다. 전체 아키텍처는 다음 그림과 같습니다.

 

 

이제, VGAE 모델을 구현해보고, 근사된 인접 행렬로 그래프를 생성해보겠습니다.

import torch
import torch_geometric.transforms as T
from torch_geometric.datasets import Planetoid

device = torch.device('cuda' if torch.cuda.is_available() else 'cpu')

transform = T.Compose([
    T.NormalizeFeatures(),
    T.ToDevice(device),
    T.RandomLinkSplit(num_val=0.05, num_test=0.1, is_undirected=True, split_labels=True, add_negative_train_samples=False),
])

dataset = Planetoid('.', name='Cora', transform=transform)

train_data, val_data, test_data = dataset[0]

 

from torch_geometric.nn import GCNConv, VGAE

class Encoder(torch.nn.Module):
    def __init__(self, dim_in, dim_out):
        super().__init__()
        self.conv1 = GCNConv(dim_in, 2 * dim_out)
        self.conv_mu = GCNConv(2 * dim_out, dim_out)
        self.conv_logstd = GCNConv(2 * dim_out, dim_out)

    def forward(self, x, edge_index):
        x = self.conv1(x, edge_index).relu()
        return self.conv_mu(x, edge_index), self.conv_logstd(x, edge_index)

model = VGAE(Encoder(dataset.num_features, 16)).to(device)
optimizer = torch.optim.Adam(model.parameters(), lr=0.01)

def train():
    model.train()
    optimizer.zero_grad()
    z = model.encode(train_data.x, train_data.edge_index)
    loss = model.recon_loss(z, train_data.pos_edge_label_index) + (1 / train_data.num_nodes) * model.kl_loss()
    loss.backward()
    optimizer.step()
    return float(loss)

@torch.no_grad()
def test(data):
    model.eval()
    z = model.encode(data.x, data.edge_index)
    return model.test(z, data.pos_edge_label_index, data.neg_edge_label_index)

for epoch in range(301):
    loss = train()
    val_auc, val_ap = test(val_data)
    if epoch % 50 == 0:
        print(f'Epoch: {epoch:>3} | Val AUC: {val_auc:.4f} | Val AP: {val_ap:.4f}')

val_auc, val_ap = test(val_data)
print(f'\nTest AUC: {val_auc:.4f} | Test AP: {val_ap:.4f}')

 

모델의 예측 정확도는 다음과 같습니다.

### result ###

Epoch:   0 | Val AUC: 0.6848 | Val AP: 0.7087
Epoch:  50 | Val AUC: 0.6522 | Val AP: 0.6739
Epoch: 100 | Val AUC: 0.7546 | Val AP: 0.7562
Epoch: 150 | Val AUC: 0.7894 | Val AP: 0.7968
Epoch: 200 | Val AUC: 0.8477 | Val AP: 0.8508
Epoch: 250 | Val AUC: 0.8452 | Val AP: 0.8500
Epoch: 300 | Val AUC: 0.8462 | Val AP: 0.8493

Test AUC: 0.8462 | Test AP: 0.8493

 

이제 예측된 인접 행렬로 새로운 그래프에 대한 구조를 생성할 수 있습니다.

z = model.encode(test_data.x, test_data.edge_index)
adj = torch.where((z @ z.T) > 0.9, 1, 0)
adj

### result ###
tensor([[1, 1, 1,  ..., 0, 1, 1],
        [1, 1, 1,  ..., 0, 1, 1],
        [1, 1, 1,  ..., 0, 1, 1],
        ...,
        [0, 0, 0,  ..., 0, 0, 0],
        [1, 1, 1,  ..., 0, 1, 1],
        [1, 1, 1,  ..., 0, 1, 1]])

 

2.2 Generative adversarial networks

Generative adversarial network (GAN)은 VAE와 마찬가지로 유명한 생성 모델입니다. GAN은 두 개의 서로 다른 목표를 가진 모듈을 사용합니다. 첫 번째 신경망은 새로운 데이터를 생성하는 생성자(generator)이고, 두 번째 신경망은 각 샘플을 실제 또는 가짜로 분류하는 판별자(discriminator)입니다.

 

2018년에 제안된 molecular GAN(MolGAN)은 분자 구조 생성에 유명한 GAN 기반 모델입니다. 이 모델은 WGAN과 그라디언트 패널티를 결합하여 그래프 구조화된 데이터를 직접 처리하며, 원하는 화학적 속성을 가진 분자를 생성하기 위한 강화 학습 목적을 갖습니다.. MolGAN의 아키텍처는 다음 그림과 같습니다.

 

이 프레임워크는 세 가지 구조로 구성됩니다..

• Generator: 노드 행렬 X와 엣지와 bonds type 정보를 담은 인접 행렬 A을 출력하는 다층 퍼셉트론(MLP)입니다. 생성자는 WGAN 및 강화 학습 손실의 선형 조합을 사용하여 학습됩니다.
• Discriminator: 생성자의 그래프와 데이터셋의 그래프를 입력받아, 그 둘을 구별하는 방법을 학습합니다. 판별자는 WGAN 손실만을 사용하여 학습됩니다.
• Reward network: 각 그래프에 점수를 부여합니다. 실제 점수를 기반으로 MSE를 통해 사용하여 학습됩니다.

Discriminator와 reward network는 GNN에서 Relational-GCN을 사용합니다.Relational-GCN은 여러 개의 엣지 유형을 지원하는 GCN 변형입니다. 여러 graph convolution 레이어를 거친 후, 노드 임베딩은 그래프 수준 벡터로 집계됩니다.

 

그렇다면 MolGAN 모델을 통해 새로운 분자 구조를 생성해보겠습니다.

이 섹션에서는 화학 그래프에 특화된 DeepChem 라이브러리와 tensorflow를 사용합니다.

!pip install deepchem==2.7.1

import pandas as pd
import numpy as np
from tensorflow import one_hot

import deepchem as dc
from deepchem.models.optimizers import ExponentialDecay
from deepchem.models import BasicMolGANModel as MolGAN
from deepchem.feat.molecule_featurizers.molgan_featurizer import GraphMatrix

from rdkit import Chem
from rdkit.Chem import Draw
from rdkit.Chem import rdmolfiles
from rdkit.Chem import rdmolops
from rdkit.Chem.Draw import IPythonConsole

사용하는 데이터셋은 tox21 데이터로 6,000개의 화학 compounds로 구성됩니다. 본 예제에서는 간소화된, simplified molecular-input line-entry system (SMILES) 데이터를 사용하겠습니다. SMILES 데이터는 아래 예시와 같이 간소화 되게 나타납니다.

 

_, datasets, _ = dc.molnet.load_tox21()
df = pd.DataFrame(datasets[0].ids, columns=['smiles'])
df

### result ###
	smiles
0	CC(O)(P(=O)(O)O)P(=O)(O)O
1	CC(C)(C)OOC(C)(C)CCC(C)(C)OOC(C)(C)C
2	OC[C@H](O)[C@@H](O)[C@H](O)CO
3	CCCCCCCC(=O)[O-].CCCCCCCC(=O)[O-].[Zn+2]
4	CC(C)COC(=O)C(C)C
...	...
6259	CC1CCCCN1CCCOC(=O)c1ccc(OC2CCCCC2)cc1
6260	Cc1cc(CCCOc2c(C)cc(-c3noc(C(F)(F)F)n3)cc2C)on1
6261	O=C1OC(OC(=O)c2cccnc2Nc2cccc(C(F)(F)F)c2)c2ccc...
6262	CC(=O)C1(C)CC2=C(CCCC2(C)C)CC1C
6263	CC(C)CCC[C@@H](C)[C@H]1CC(=O)C2=C3CC[C@H]4C[C@...
6264 rows × 1 columns

 

• 최대 원자가 15개인 분자구조만 다룰 예정입니다.
• featurizer를 통해 smiles 스트링을 input feature로 바꿉니다.
• features = 부분은 유효한 데이터만 필터링 합니다.
• 이후 gan= 부분에서 DeepChem 포멧으로 MolGAN 모델을 불러옵니다.

max_atom = 15

featurizer = dc.feat.MolGanFeaturizer(max_atom_count=max_atom)
molecules = [x for x in df['smiles'].values if Chem.MolFromSmiles(x).GetNumAtoms() < max_atom]

features = []
for x in molecules:
    mol = Chem.MolFromSmiles(x)
    new_order = rdmolfiles.CanonicalRankAtoms(mol)
    mol = rdmolops.RenumberAtoms(mol, new_order)
    feature = featurizer.featurize(mol)
    if feature.size != 0:
        features.append(feature[0])
        
# Remove invalid molecules
features = [x for x in features if type(x) is GraphMatrix]

# Create MolGAN
gan = MolGAN(learning_rate=ExponentialDecay(0.001, 0.9, 5000), vertices=max_atom)

# Create dataset
dataset = dc.data.NumpyDataset(X=[x.adjacency_matrix for x in features], y=[x.node_features for x in features])
dataset

### result ###
<NumpyDataset X.shape: (2107, 15, 15), y.shape: (2107, 15), w.shape: (2107, 1), task_names: [ 0  1  2 ... 12 13 14]>

 

이후 iterable한 mini-batch로 데이터 셋을 구성하고 25에포크 학습을 진행합니다.

학습된 모델에 대하 1,000개의 분자 구조를 만듭니다.

def iterbatches(epochs):
    for i in range(epochs):
        for batch in dataset.iterbatches(batch_size=gan.batch_size, pad_batches=True):
            adjacency_tensor = one_hot(batch[0], gan.edges)
            node_tensor = one_hot(batch[1], gan.nodes)
            yield {gan.data_inputs[0]: adjacency_tensor, gan.data_inputs[1]: node_tensor}
            
# Train model
gan.fit_gan(iterbatches(25), generator_steps=0.2, checkpoint_interval=5000)

# Generate 1000 samples
generated_data = gan.predict_gan_generator(1000)
generated_mols = featurizer.defeaturize(generated_data)

 

마지막으로 생성된 그래프들이 유효한지 체크합니다.

valid_mols = [x for x in generated_mols if x is not None]
print (f'{len(valid_mols)} valid molecules (out of
{len((generated_mols))} generated molecules)')

### result ###
31 valid molecules (out of 1000 generated molecules)

 

코드 구현을 통해 알아본 분자 생성 이외에도 그래프 생성 기법은 다양한 응용 분야에서 활용될 수 있습니다. 예를 들어, 소셜 네트워크 분석에서 GNN을 사용하여 새로운 친구 관계를 예측하고 사회 네트워크를 발전시킬 수 있습니다. 이상으로 GNN을 활용한 그래프 생성에 대한 블로그 포스팅을 마치겠습니다. 감사합니다.

 

Reference 

• Hands-On Graph Neural Networks Using Python, published by Packt.
• Kipf, T. N., & Welling, M. (2016). Variational graph auto-encoders. arXiv preprint arXiv:1611.07308.
• Simonovsky, M., & Komodakis, N. (2018). Graphvae: Towards generation of small graphs using variational autoencoders. In Artificial Neural Networks and Machine Learning–ICANN 2018: 27th International Conference on Artificial Neural Networks, Rhodes, Greece, October 4-7, 2018, Proceedings, Part I 27 (pp. 412-422). Springer International Publishing.
• De Cao, N., & Kipf, T. (2018). MolGAN: An implicit generative model for small molecular graphs. arXiv preprint arXiv:1805.11973.