Teori dan Implementasi Graph Neural Network (GNN) dengan PyTorch Geometric untuk Data Non-Euclidean

Memahami Keterbatasan Neural Network Konvensional pada Data Non-Euclidean

Sebagian besar arsitektur deep learning yang kita kenal bekerja optimal pada data dengan struktur grid atau sekuens. Convolutional Neural Network (CNN) mengandalkan grid 2D dari piksel gambar untuk mengekstrak fitur spasial. Recurrent Neural Network (RNN) memanfaatkan urutan temporal dari data time series. Kedua pendekatan ini mengasumsikan bahwa data memiliki hubungan tetangga yang teratur dan terdefinisi dengan jelas.

Namun, banyak data di dunia nyata tidak mengikuti struktur ini. Data seperti social network, citation graph antar paper akademik, dan struktur molekul kimia termasuk dalam kategori data non-Euclidean. Hubungan antar entitas dalam data ini tidak teratur, tidak memiliki grid tetap, dan setiap node bisa memiliki jumlah tetangga yang berbeda-beda.

Secara teknis, data non-Euclidean direpresentasikan sebagai graph dengan tiga komponen utama. Node adalah entitas individual, edge adalah hubungan antar node, dan adjacency matrix mendefinisikan konektivitas antar node secara keseluruhan. Representasi ini memungkinkan kita memodelkan hubungan kompleks yang tidak bisa ditangkap oleh tensor grid konvensional.

Disinilah Graph Neural Network (GNN) hadir sebagai solusi. GNN dirancang secara khusus untuk bekerja dengan data graph, memungkinkan kita mengekstrak representasi bermakna dari struktur hubungan yang kompleks. Pendekatan ini membuka pintu untuk menyelesaikan masalah seperti klasifikasi node, predisi link, dan klasifikasi graph secara efisien.

Memahami Mekanisme Message Passing pada Graph Neural Network

Inti dari Graph Neural Network terletak pada mekanisme message passing. Setiap node dalam graph mengumpulkan informasi dari node-node tetangganya, mengagregasi informasi tersebut, lalu menggunakannya untuk memperbarui representasi dirinya sendiri. Mekanisme ini mirip dengan proses seorang karyawan yang mengumpulkan masukan dari rekan satu tim sebelum mengambil keputusan penting.

Proses message passing berlangsung dalam tiga tahap utama. Pertama, setiap node mengirimkan fiturnya ke semua node tetangga. Kedua, setiap node mengagregasi semua pesan yang diterima menggunakan fungsi seperti mean, sum, atau max. Ketiga, node mengkombinasikan representasi agregasi dengan representasinya sendiri melalui fungsi update yang bisa berupa neural network sederhana.

Jumlah iterasi message passing menentukan seberapa jauh informasi dapat menyebar dalam graph. Satu layer GNN memungkinkan node melihat informasi dari tetangga langsung (1-hop). Dua layer memperluas jangkauan hingga tetangga dari tetangga (2-hop). Prinsip ini mirip dengan receptive field pada CNN, namun dalam domain graph yang tidak teratur.

Perbedaan mendasar antara graph convolution dengan standard convolution terletak pada cara agregasi dilakukan. Standard convolution menggunakan kernel dengan bobot tetap yang digeser secara sistematis. Graph convolution mengagregasi fitur tetangga dengan bobot yang bisa dipelajari, dimana struktur adjacency menentukan node mana yang berpartisipasi dalam agregasi.

Gambar: Arsitektur Message Passing Layer dalam GNN — informasi dari node (V), edge (E), dan global (U) diproses melalui fungsi pooling (ρ) dan update (f) untuk menghasilkan representasi baru di layer berikutnya — Sumber: [Distill.pub](https://distill.pub/2021/gnn-intro/)

Setup PyTorch Geometric dan Eksplorasi Dataset Citation Graph

PyTorch Geometric (PyG) adalah library yang menyediakan implementasi efisien untuk berbagai arsitektur GNN. Library ini dibangun di atas PyTorch dan menyediakan API yang konsisten untuk memuat data graph, membangun model, serta menjalankan training.

Kita akan menggunakan dataset Cora, sebuah citation graph yang berisi paper akademik sebagai node dan kutipan antar paper sebagai edge. Setiap paper memiliki fitur bag-of-words, dan tujuannya adalah mengklasifikasikan paper ke dalam salah satu dari 7 kategori topik.

!pip install torch torch-geometric

from torch_geometric.datasets import Planetoid

dataset = Planetoid(root='/tmp/Cora', name='Cora')
data = dataset[0]

print(f"Dataset: {dataset}")
print(f"Number of nodes: {data.num_nodes}")
print(f"Number of edges: {data.num_edges}")
print(f"Feature dimension: {data.num_node_features}")
print(f"Number of classes: {dataset.num_classes}")
print(f"Train nodes: {data.train_mask.sum().item()}")
print(f"Test nodes: {data.test_mask.sum().item()}")

Output:

Dataset: Cora()
Number of nodes: 2708
Number of edges: 10556
Feature dimension: 1433
Number of classes: 7
Train nodes: 140
Test nodes: 1000

Setelah kode dijalankan, kita akan melihat statistik dataset Cora. Dataset ini memiliki 2708 node, 10556 edge, 1433 fitur per node, dan 7 kelas klasifikasi. Objek Data dari PyG menyimpan semua informasi penting: x untuk fitur node, edge_index untuk konektivitas graph dalam format COO, y untuk label, serta train_mask dan test_mask untuk membagi data training dan testing.

Implementasi Graph Convolutional Network untuk Node Classification

Graph Convolutional Network (GCN) yang diperkenalkan oleh Kipf & Welling adalah salah satu arsitektur GNN paling fundamental. GCN melakukan propagasi fitur antar node melalui normalized adjacency matrix, dimana setiap node menghitung rata-rata tertimbang dari fitur tetangganya.

import torch
import torch.nn.functional as F
from torch_geometric.nn import GCNConv

class GCN(torch.nn.Module):
    def __init__(self, in_channels, hidden_channels, out_channels):
        super().__init__()
        self.conv1 = GCNConv(in_channels, hidden_channels)
        self.conv2 = GCNConv(hidden_channels, out_channels)

    def forward(self, data):
        x, edge_index = data.x, data.edge_index
        x = self.conv1(x, edge_index)
        x = F.relu(x)
        x = F.dropout(x, p=0.5, training=self.training)
        x = self.conv2(x, edge_index)
        return F.log_softmax(x, dim=1)

device = torch.device('cuda' if torch.cuda.is_available() else 'cpu')
model = GCN(
    in_channels=dataset.num_node_features,
    hidden_channels=16,
    out_channels=dataset.num_classes
).to(device)

data = data.to(device)
optimizer = torch.optim.Adam(model.parameters(), lr=0.01, weight_decay=5e-4)

Arsitektur model kita terdiri dari dua layer GCNConv. Layer pertama memproyeksikan fitur input 1433 dimensi ke ruang hidden 16 dimensi. Layer kedua memproyeksikannya ke 7 dimensi output yang sesuai dengan jumlah kelas. Fungsi aktivasi ReLU dan dropout 50% diterapkan di antara kedua layer untuk mencegah overfitting.

Gambar: Arsitektur multi-layer Graph Convolutional Network (GCN) dengan first-order filters — input graph diproses melalui hidden layer dan ReLU activation untuk menghasilkan output berupa node embedding — Sumber: [Thomas Kipf](https://tkipf.github.io/graph-convolutional-networks/)

model.train()
for epoch in range(201):
    optimizer.zero_grad()
    out = model(data)
    loss = F.nll_loss(out[data.train_mask], data.y[data.train_mask])
    loss.backward()
    optimizer.step()

    if epoch % 40 == 0:
        pred = out.argmax(dim=1)
        acc = (pred[data.train_mask] == data.y[data.train_mask]).float().mean()
        print(f"Epoch {epoch:3d} | Loss: {loss:.4f} | Train Acc: {acc:.4f}")

Output:

Epoch   0 | Loss: 1.9496 | Train Acc: 0.1000
Epoch  40 | Loss: 0.0691 | Train Acc: 0.9857
Epoch  80 | Loss: 0.0344 | Train Acc: 1.0000
Epoch 120 | Loss: 0.0427 | Train Acc: 0.9929
Epoch 160 | Loss: 0.0368 | Train Acc: 1.0000
Epoch 200 | Loss: 0.0299 | Train Acc: 0.9929

Training loop ini menjalankan 200 epoch optimasi. Setiap epoch menjalankan forward pass untuk menghasilkan prediksi, menghitung negative log likelihood loss pada node training, dan melakukan backward pass untuk memperbarui bobot model. Kita memonitor loss dan akurasi setiap 40 epoch untuk melihat perkembangan training. Output yang diharapkan adalah penurunan loss secara konsisten dan peningkatan akurasi training hingga di atas 90%.

Evaluasi Model dan Interpretasi Representasi Node yang Dipelajari

Setelah training selesai, kita perlu mengevaluasi performa model pada node testing yang tidak pernah dilihat selama training. Ini memberikan gambaran objektif tentang kemampuan generalisasi model.

model.eval()
with torch.no_grad():
    out = model(data)
    pred = out.argmax(dim=1)
    acc = (pred[data.test_mask] == data.y[data.test_mask]).float().mean()

print(f"Test Accuracy: {acc:.4f}")

from sklearn.manifold import TSNE
import matplotlib.pyplot as plt

node_embeddings = model.conv1(data.x, data.edge_index).cpu().numpy()
tsne = TSNE(n_components=2, random_state=42)
emb_2d = tsne.fit_transform(node_embeddings)

plt.figure(figsize=(10, 8))
scatter = plt.scatter(
    emb_2d[:, 0], emb_2d[:, 1],
    c=data.y.cpu().numpy(), cmap='tab10', alpha=0.7
)
plt.colorbar(scatter)
plt.title("Visualisasi Node Embedding dengan t-SNE")
plt.show()

Output:

Test Accuracy: 0.8160

Kode ini menghitung akurasi pada test set, yang umumnya mencapai 75-80% untuk dataset Cora. Yang lebih menarik adalah visualisasi node embedding menggunakan t-SNE. Node embedding adalah representasi perantara yang dipelajari oleh layer GCN pertama.

Visualisasi ini menunjukkan apakah node dari kelas yang sama mengelompok dalam ruang embedding 2D. Pola clustering yang jelas mengindikasikan bahwa model berhasil mempelajari representasi yang diskriminatif untuk setiap kelas, meskipun hanya menggunakan informasi struktur graph dan fitur sparse.

Eksperimen dengan Arsitektur Graph Lain dan Best Practices

GCN bukan satu-satunya arsitektur GNN. Graph Attention Networks (GAT) memperkenalkan attention mechanism yang memungkinkan setiap node memberikan bobot berbeda pada tetangganya. Tidak seperti GCN yang menggunakan bobot seragam berdasarkan derajat node, GAT belajar menentukan tetangga mana yang paling relevan untuk setiap node.

GraphSAGE menawarkan pendekatan berbeda dengan melakukan sampling tetangga. Arsitektur ini sangat berguna untuk graph skala besar dimana memproses semua tetangga tidak memungkinkan. GraphSAGE mengagregasi informasi dari subset tetangga yang di-sampling, membuatnya lebih scalable untuk aplikasi industri.

Pemilihan arsitektur tergantung pada karakteristik data. GCN cocok untuk graph homogen dengan ukuran sedang. GAT unggul ketika hubungan antar node memiliki kepentingan yang bervariasi. GraphSAGE menjadi pilihan utama untuk graph dengan jutaan node.

Gambar: Graph Convolutional Layer — node mengagregasi informasi dari tetangga melalui fungsi pooling (ρ) dan memperbarui representasi melalui fungsi update (f) berbasis neural network — Sumber: [Distill.pub](https://distill.pub/2021/gnn-intro/)

Beberapa best practices penting dalam implementasi GNN. Normalisasi fitur node sebelum training sangat penting mengingat skala fitur yang bervariasi. Early stopping berdasarkan validation loss mencegah overfitting. Untuk graph besar, mini-batching menggunakan teknik seperti NeighborLoader dari PyG memungkinkan training yang efisien tanpa memuat seluruh graph ke memori.

Graph Neural Network membuka dimensi baru dalam deep learning untuk data non-Euclidean. Menguasai konsep dan implementasi GNN adalah langkah penting bagi kita yang ingin bekerja dengan data relasional kompleks. Di Rumah Coding, materi Graph Neural Network ini menjadi bagian dari bootcamp Deep Learning yang mencakup berbagai arsitektur modern. Tertarik mendalami GNN dan arsitektur deep learning lainnya bersama mentor yang berpengalaman? Bergabunglah dengan bootcamp Deep Learning di Rumah Coding.