Pengantar Komprehensif untuk Graph Neural Networks (GNN)

Apa itu Graf?

Graf adalah jenis struktur data yang berisi simpul (node) dan sisi (edge). Sebuah simpul dapat berupa orang, tempat, atau benda, dan sisi mendefinisikan hubungan antar simpul. Sisi dapat berarah atau tidak berarah berdasarkan ketergantungan arah.

Pada contoh di bawah, lingkaran biru adalah simpul, dan panah adalah sisi. Arah sisi mendefinisikan ketergantungan antara dua simpul.

Gambar oleh Penulis

Mari kenali dataset Graf yang kompleks: Jazz Musicians Network. Dataset ini berisi 198 simpul dan 2742 sisi. Pada plot graf komunitas di bawah, warna simpul yang berbeda merepresentasikan berbagai komunitas musisi Jazz dan sisi yang menghubungkan mereka. Ada jejaring kolaborasi di mana seorang musisi memiliki hubungan di dalam dan di luar komunitas.

Plot Graf Komunitas oleh Jazz Musicians Network

Graf sangat baik dalam menangani masalah kompleks yang melibatkan hubungan dan interaksi. Graf digunakan dalam pengenalan pola, analisis jejaring sosial, sistem rekomendasi, dan analisis semantik. Membangun solusi berbasis graf adalah bidang tersendiri yang menawarkan wawasan kaya atas dataset yang kompleks dan saling terhubung.

Graf dengan NetworkX

Pada bagian ini, kita akan belajar membuat graf menggunakan NetworkX.

Kode di bawah dipengaruhi oleh blog Daniel Holmberg tentang Graph Neural Networks di Python.

1. Buat objek DiGraph milik networkx bernama "H"
2. Tambahkan simpul yang memiliki label, warna, dan ukuran berbeda
3. Tambahkan sisi untuk membentuk hubungan antara dua simpul. Misalnya, "(0,1)" berarti 0 memiliki ketergantungan berarah pada 1. Kita akan membuat hubungan dua arah dengan menambahkan "(1,0)"
4. Ekstrak warna dan ukuran dalam bentuk daftar
5. Plot graf menggunakan fungsi draw milik networkx

import networkx as nx
H = nx.DiGraph()

#adding nodes
H.add_nodes_from([
  (0, {"color": "blue", "size": 250}),

  (1, {"color": "yellow", "size": 400}),

  (2, {"color": "orange", "size": 150}),

  (3, {"color": "red", "size": 600})


])

#adding edges
H.add_edges_from([
  (0, 1),

  (1, 2),

  (1, 0),

  (1, 3),

  (2, 3),

  (3,0)


])

node_colors = nx.get_node_attributes(H, "color").values()
colors = list(node_colors)
node_sizes = nx.get_node_attributes(H, "size").values()
sizes = list(node_sizes)

#Plotting Graph
nx.draw(H, with_labels=True, node_color=colors, node_size=sizes)

Pada langkah berikutnya, kita akan mengonversi struktur data dari graf berarah menjadi tidak berarah menggunakan fungsi to_undirected().

#converting to undirected graph
G = H.to_undirected()
nx.draw(G, with_labels=True, node_color=colors, node_size=sizes)

Mengapa Menganalisis Graf Itu Sulit?

Struktur data berbasis graf memiliki kelemahan, dan data scientist harus memahaminya sebelum mengembangkan solusi berbasis graf.

1. Graf berada di ruang non-Euklides. Graf tidak berada di ruang 2D atau 3D, yang membuat data lebih sulit ditafsirkan. Untuk memvisualisasikan struktur dalam ruang 2D, Anda harus menggunakan berbagai alat reduksi dimensi.
2. Graf bersifat dinamis; tidak memiliki bentuk tetap. Bisa ada dua graf yang terlihat berbeda, tetapi bisa jadi keduanya memiliki representasi matriks ketetanggaan (adjacency) yang serupa. Hal ini menyulitkan analisis data dengan alat statistik tradisional.
3. Ukuran dan dimensi yang besar akan meningkatkan kompleksitas graf untuk interpretasi manusia. Struktur yang rapat dengan banyak simpul dan ribuan sisi lebih sulit dipahami dan diekstrak wawasannya.

Apa itu Graph Neural Network (GNN)?

Graph Neural Networks adalah jenis jaringan saraf khusus yang mampu bekerja dengan struktur data graf. GNN sangat dipengaruhi oleh Convolutional Neural Networks (CNN) dan graph embedding. GNN digunakan untuk memprediksi simpul, sisi, dan tugas-tugas berbasis graf.

• CNN digunakan untuk klasifikasi gambar. Serupa, GNN diterapkan pada struktur graf (kisi piksel) untuk memprediksi sebuah kelas.
• Recurrent Neural Networks digunakan dalam klasifikasi teks. Serupa, GNN diterapkan pada struktur graf di mana setiap kata adalah simpul dalam sebuah kalimat.

GNN diperkenalkan ketika Convolutional Neural Networks gagal mencapai hasil optimal karena ukuran graf yang sewenang-wenang dan strukturnya yang kompleks.

Gambar oleh Purvanshi Mehta

Graf masukan dilewatkan melalui serangkaian jaringan saraf. Struktur graf masukan diubah menjadi graph embedding, yang memungkinkan kita mempertahankan informasi tentang simpul, sisi, dan konteks global.

Kemudian vektor fitur simpul A dan C dilewatkan melalui lapisan jaringan saraf. Jaringan mengagregasi fitur-fitur ini dan meneruskannya ke lapisan berikutnya - neptune.ai.

Baca tutorial Deep Learning kami atau ikuti kursus Introduction to Deep Learning untuk mempelajari lebih lanjut tentang algoritma dan aplikasi deep learning.

Jenis-jenis Graph Neural Network

Ada beberapa jenis jaringan saraf, dan sebagian besar memiliki variasi Convolutional Neural Networks. Pada bagian ini, kita akan mempelajari GNN yang paling populer.

• Graph Convolutional Networks (GCN) mirip dengan CNN tradisional. GCN mempelajari fitur dengan memeriksa simpul-simpul tetangga. GNN mengagregasi vektor simpul, meneruskan hasilnya ke lapisan padat (dense), dan menerapkan non-linearitas menggunakan fungsi aktivasi. Singkatnya, GCN terdiri dari konvolusi graf, lapisan linear, dan fungsi aktivasi non-linear. Ada dua jenis utama GCN: Spatial Convolutional Networks dan Spectral Convolutional Networks.
• Graph Auto-Encoder Networks mempelajari representasi graf menggunakan encoder dan mencoba merekonstruksi graf masukan menggunakan decoder. Encoder dan decoder dihubungkan oleh lapisan bottleneck. Umumnya digunakan dalam prediksi tautan karena Auto-Encoder unggul dalam menangani ketidakseimbangan kelas.
• Recurrent Graph Neural Networks (RGNN) mempelajari pola difusi terbaik, dan dapat menangani graf multi-relasional di mana satu simpul memiliki banyak relasi. Jenis jaringan saraf graf ini menggunakan regularizer untuk meningkatkan kelicinan (smoothness) dan menghilangkan over-parameterization. RGNN menggunakan daya komputasi lebih sedikit untuk menghasilkan hasil yang lebih baik. RGNN digunakan untuk menghasilkan teks, penerjemahan mesin, pengenalan ucapan, pembuatan deskripsi gambar, penandaan video, dan rangkuman teks.
• Gated Graph Neural Networks (GGNN) lebih baik daripada RGNN dalam menjalankan tugas dengan ketergantungan jangka panjang. Gated Graph Neural Networks menyempurnakan Recurrent Graph Neural Networks dengan menambahkan gerbang pada simpul, sisi, dan waktu untuk ketergantungan jangka panjang. Mirip dengan Gated Recurrent Units (GRU), gerbang digunakan untuk mengingat dan melupakan informasi dalam berbagai keadaan.

Jika Anda tertarik mempelajari lebih lanjut tentang Recurrent Neural Networks (RNN), lihat kursus DataCamp. Kursus ini akan memperkenalkan Anda pada berbagai arsitektur model RNN, kerangka kerja Keras, dan aplikasi RNN.

Jenis-jenis Tugas pada Graph Neural Networks

Di bawah ini kami jabarkan beberapa jenis tugas GNN beserta contohnya:

• Klasifikasi Graf: digunakan untuk mengklasifikasikan graf ke dalam berbagai kategori. Aplikasinya antara lain analisis jejaring sosial dan klasifikasi teks.
• Klasifikasi Simpul (Node Classification): tugas ini menggunakan label simpul tetangga untuk memprediksi label simpul yang hilang dalam sebuah graf.
• Prediksi Tautan (Link Prediction): memprediksi tautan antara pasangan simpul dalam graf dengan matriks ketetanggaan yang tidak lengkap. Umumnya digunakan untuk jejaring sosial.
• Deteksi Komunitas: membagi simpul ke dalam berbagai klaster berdasarkan struktur sisi. Model belajar dari bobot sisi, jarak, dan objek graf secara serupa.
• Graph Embedding: memetakan graf ke dalam vektor, sambil mempertahankan informasi relevan tentang simpul, sisi, dan struktur.
• Generasi Graf: belajar dari distribusi sampel graf untuk menghasilkan struktur graf baru yang serupa.

Gambar oleh Penulis

Kekurangan Graph Neural Networks

Ada beberapa kelemahan dalam menggunakan GNN. Memahaminya akan membantu kita menentukan kapan menggunakan GNN dan bagaimana mengoptimalkan kinerja model pembelajaran mesin kita.

1. Sebagian besar jaringan saraf dapat dibuat sangat dalam untuk memperoleh kinerja lebih baik, sedangkan GNN adalah jaringan dangkal umumnya hanya dengan tiga lapisan. Ini membatasi kita untuk meraih kinerja terbaik pada dataset besar.
2. Struktur graf terus berubah, sehingga lebih sulit untuk melatih model di atasnya.
3. Penerapan model ke produksi menghadapi masalah skalabilitas karena jaringan ini mahal secara komputasi. Jika Anda memiliki struktur graf yang besar dan kompleks, akan sulit menskalakan GNN di produksi.

Apa itu Graph Convolutional Network (GCN)?

Mayoritas GNN adalah Graph Convolutional Networks, dan penting untuk memahaminya sebelum masuk ke tutorial klasifikasi simpul.

Konvolusi pada GCN sama dengan konvolusi pada convolutional neural networks. Konvolusi mengalikan neuron dengan bobot (filter) untuk belajar dari fitur data.

Konvolusi bertindak seperti jendela geser pada keseluruhan gambar untuk mempelajari fitur dari sel tetangga. Filter menggunakan pembagian bobot (weight sharing) untuk mempelajari berbagai fitur wajah dalam sistem pengenalan gambar - Towards Data Science.

Sekarang pindahkan fungsi yang sama ke Graph Convolutional Networks di mana model mempelajari fitur dari simpul-simpul tetangga. Perbedaan utama antara GCN dan CNN adalah GCN dikembangkan untuk bekerja pada struktur data non-Euklides di mana urutan simpul dan sisi dapat bervariasi.

CNN vs GCN | Sumber Gambar

Pelajari lebih lanjut tentang dasar-dasar CNN dengan mengikuti tutorial Convolutional Neural Networks (CNN) dengan TensorFlow.

Ada dua jenis GCN:

• Spatial Graph Convolutional Networks menggunakan fitur spasial untuk belajar dari graf yang berada di ruang spasial.
• Spectral Graph Convolutional Networks menggunakan dekomposisi Eigen dari matriks Laplacian graf untuk penyebaran informasi sepanjang simpul. Jaringan ini terinspirasi oleh penyebaran gelombang dalam sinyal dan sistem.

Bagaimana GNN Bekerja? Membangun Graph Neural Network dengan Pytorch

Kita akan membangun dan melatih Spectral Graph Convolution untuk model klasifikasi simpul. Sumber kode tersedia di DataLab workbook ini agar Anda dapat mencoba dan menjalankan model pembelajaran mesin berbasis graf pertama Anda.

Contoh kode dipengaruhi oleh dokumentasi Pytorch geometric.

Mulai

Kita akan memasang paket Pytorch karena pytorch_geometric dibangun di atasnya.

!pip install -q torch

Kemudian kita akan menggunakan versi torch untuk memasang torch-scatter dan torch-sparse. Setelah itu, kita akan memasang rilis terbaru pytorch_geometric dari GitHub.

%%capture
import os
import torch
os.environ['TORCH'] = torch.__version__
os.environ['PYTHONWARNINGS'] = "ignore"
!pip install torch-scatter -f https://data.pyg.org/whl/torch-${TORCH}.html
!pip install torch-sparse -f https://data.pyg.org/whl/torch-${TORCH}.html
!pip install git+https://github.com/pyg-team/pytorch_geometric.git

Dataset Planetoid Cora

Planetoid adalah dataset jaringan sitasi dari Cora, CiteSeer, dan PubMed. Simpul adalah dokumen dengan vektor fitur bag-of-words berdimensi 1433, dan sisi adalah tautan sitasi antar makalah penelitian. Ada 7 kelas, dan kita akan melatih model untuk memprediksi label yang hilang.

Kita akan memuat dataset Planetoid Cora, dan melakukan normalisasi baris pada fitur masukan bag-of-words. Setelah itu, kita akan menganalisis dataset dan objek graf pertama.

from torch_geometric.datasets import Planetoid
from torch_geometric.transforms import NormalizeFeatures

dataset = Planetoid(root='data/Planetoid', name='Cora', transform=NormalizeFeatures())

print(f'Dataset: {dataset}:')
print('======================')
print(f'Number of graphs: {len(dataset)}')
print(f'Number of features: {dataset.num_features}')
print(f'Number of classes: {dataset.num_classes}')

data = dataset[0]  # Get the first graph object.
print(data)

Dataset Cora memiliki 2708 simpul, 10.556 sisi, 1433 fitur, dan 7 kelas. Objek pertama memiliki 2708 mask untuk latih, validasi, dan uji. Kita akan menggunakan mask ini untuk melatih dan mengevaluasi model.

Dataset: Cora():
======================
Number of graphs: 1
Number of features: 1433
Number of classes: 7
Data(x=[2708, 1433], edge_index=[2, 10556], y=[2708], train_mask=[2708], val_mask=[2708], test_mask=[2708])

Klasifikasi Simpul dengan GNN

Kita akan membuat struktur model GCN yang berisi dua lapisan GCNConv, aktivasi relu, dan tingkat dropout 0,5. Model terdiri dari 16 saluran tersembunyi.

Lapisan GCN:

W(ℓ+1) adalah matriks bobot yang dapat dilatih pada persamaan di atas dan Cw,v menyatakan koefisien normalisasi tetap untuk setiap sisi.

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

class GCN(torch.nn.Module):
    def __init__(self, hidden_channels):
        super().__init__()
        torch.manual_seed(1234567)
        self.conv1 = GCNConv(dataset.num_features, hidden_channels)
        self.conv2 = GCNConv(hidden_channels, dataset.num_classes)

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

model = GCN(hidden_channels=16)
print(model)

>>> GCN(
    (conv1): GCNConv(1433, 16)
    (conv2): GCNConv(16, 7)
  )

Memvisualisasikan Jaringan GCN yang Belum Dilatih

Mari visualisasikan embedding simpul dari jaringan GCN yang belum dilatih menggunakan sklearn.manifold.TSNE dan matplotlib.pyplot. Visualisasi ini akan memplot embedding simpul 7 dimensi ke dalam scatter plot 2D.

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

def visualize(h, color):
    z = TSNE(n_components=2).fit_transform(h.detach().cpu().numpy())

    plt.figure(figsize=(10,10))
    plt.xticks([])
    plt.yticks([])

    plt.scatter(z[:, 0], z[:, 1], s=70, c=color, cmap="Set2")
    plt.show()

Kita akan mengevaluasi model lalu menambahkan data pelatihan ke model yang belum dilatih untuk memvisualisasikan berbagai simpul dan kategori.

model.eval()

out = model(data.x, data.edge_index)
visualize(out, color=data.y)

Melatih GNN

Kita akan melatih model selama 100 epoch menggunakan optimisasi Adam dan fungsi Cross-Entropy Loss.

Pada fungsi train, kita:

1. Mengosongkan gradien
2. Melakukan satu kali forward pass
3. Menghitung loss menggunakan simpul pelatihan
4. Menghitung gradien, dan memperbarui parameter

Pada fungsi test, kita:

1. Memprediksi kelas simpul
2. Mengambil label kelas dengan probabilitas tertinggi
3. Memeriksa berapa banyak nilai yang diprediksi dengan benar
4. Membuat rasio akurasi menggunakan jumlah prediksi benar dibagi jumlah total simpul.

model = GCN(hidden_channels=16)
optimizer = torch.optim.Adam(model.parameters(), lr=0.01, weight_decay=5e-4)
criterion = torch.nn.CrossEntropyLoss()

def train():
      model.train()
      optimizer.zero_grad()
      out = model(data.x, data.edge_index)
      loss = criterion(out[data.train_mask], data.y[data.train_mask])
      loss.backward()
      optimizer.step()
      return loss

def test():
      model.eval()
      out = model(data.x, data.edge_index)
      pred = out.argmax(dim=1)
      test_correct = pred[data.test_mask] == data.y[data.test_mask]
      test_acc = int(test_correct.sum()) / int(data.test_mask.sum())
      return test_acc


for epoch in range(1, 101):
    loss = train()
    print(f'Epoch: {epoch:03d}, Loss: {loss:.4f}')
GAT(
  (conv1): GATConv(1433, 8, heads=8)
  (conv2): GATConv(64, 7, heads=8)
)

.. .. .. ..
.. .. .. ..
Epoch: 098, Loss: 0.5989
Epoch: 099, Loss: 0.6021
Epoch: 100, Loss: 0.5799

Evaluasi Model

Sekarang kita akan mengevaluasi model pada dataset yang belum terlihat menggunakan fungsi test, dan seperti yang terlihat, kita memperoleh hasil yang cukup baik dengan akurasi 81,5%.

test_acc = test()
print(f'Test Accuracy: {test_acc:.4f}')


>>> Test Accuracy: 0.8150

Sekarang kita akan memvisualisasikan embedding keluaran dari model terlatih untuk memverifikasi hasil.

model.eval()
out = model(data.x, data.edge_index)
visualize(out, color=data.y)

Seperti yang terlihat, model terlatih menghasilkan pengelompokan simpul yang lebih baik untuk kategori yang sama.

Melatih Model GATConv

Pada bagian kedua, kita akan mengganti GCNConv dengan lapisan GATConv. Graph Attention Networks menggunakan lapisan self-attention bertopeng untuk mengatasi kelemahan GCNConv dan mencapai hasil terbaik.

Anda juga dapat mencoba lapisan GNN lainnya dan bereksperimen dengan optimisasi, dropout, dan jumlah saluran tersembunyi untuk memperoleh kinerja yang lebih baik.

Pada kode di bawah, kita hanya mengganti GCNConv dengan GATConv dengan 8 attention head pada lapisan pertama dan 1 pada lapisan kedua.

Kita juga akan menyetel:

• tingkat dropout menjadi 0,6
• saluran tersembunyi menjadi 8
• laju pembelajaran 0,005

Kami telah memodifikasi fungsi test untuk mencari akurasi pada mask tertentu (valid, test). Ini membantu kita mencetak skor validasi dan uji selama pelatihan model. Kami juga menyimpan hasil validasi dan uji untuk diplot sebagai grafik garis nanti.

from torch_geometric.nn import GATConv

class GAT(torch.nn.Module):
    def __init__(self, hidden_channels, heads):
        super().__init__()
        torch.manual_seed(1234567)
        self.conv1 = GATConv(dataset.num_features, hidden_channels,heads)
        self.conv2 = GATConv(heads*hidden_channels, dataset.num_classes,heads)

    def forward(self, x, edge_index):
        x = F.dropout(x, p=0.6, training=self.training)
        x = self.conv1(x, edge_index)
        x = F.elu(x)
        x = F.dropout(x, p=0.6, training=self.training)
        x = self.conv2(x, edge_index)
        return x

model = GAT(hidden_channels=8, heads=8)
print(model)

optimizer = torch.optim.Adam(model.parameters(), lr=0.005, weight_decay=5e-4)
criterion = torch.nn.CrossEntropyLoss()

def train():
      model.train()
      optimizer.zero_grad()
      out = model(data.x, data.edge_index)
      loss = criterion(out[data.train_mask], data.y[data.train_mask])
      loss.backward()
      optimizer.step()
      return loss

def test(mask):
      model.eval()
      out = model(data.x, data.edge_index)
      pred = out.argmax(dim=1)
      correct = pred[mask] == data.y[mask]
      acc = int(correct.sum()) / int(mask.sum())
      return acc

val_acc_all = []
test_acc_all = []

for epoch in range(1, 101):
    loss = train()
    val_acc = test(data.val_mask)
    test_acc = test(data.test_mask)
    val_acc_all.append(val_acc)
    test_acc_all.append(test_acc)
    print(f'Epoch: {epoch:03d}, Loss: {loss:.4f}, Val: {val_acc:.4f}, Test: {test_acc:.4f}')

.. .. .. ..
.. .. .. ..
Epoch: 098, Loss: 1.1283, Val: 0.7960, Test: 0.8030

Epoch: 099, Loss: 1.1352, Val: 0.7940, Test: 0.8050

Epoch: 100, Loss: 1.1053, Val: 0.7960, Test: 0.8040

Seperti terlihat, model kita tidak berkinerja lebih baik daripada GCNConv. Diperlukan optimisasi hiperparameter atau lebih banyak epoch untuk mencapai hasil terbaik.

Evaluasi Model

Pada bagian evaluasi, kita memvisualisasikan skor validasi dan pengujian menggunakan plot garis dari matplotlib.pyplot.

import numpy as np

plt.figure(figsize=(12,8))
plt.plot(np.arange(1, len(val_acc_all) + 1), val_acc_all, label='Validation accuracy', c='blue')
plt.plot(np.arange(1, len(test_acc_all) + 1), test_acc_all, label='Testing accuracy', c='red')
plt.xlabel('Epochs')
plt.ylabel('Accurarcy')
plt.title('GATConv')
plt.legend(loc='lower right', fontsize='x-large')
plt.savefig('gat_loss.png')
plt.show()

Setelah 60 epoch, akurasi validasi dan pengujian mencapai nilai stabil 0,8 +/-0,02.

Sekali lagi, mari visualisasikan pengelompokan simpul dari model GATConv.

model.eval()

out = model(data.x, data.edge_index)
visualize(out, color=data.y)

Seperti yang terlihat, lapisan GATConv menghasilkan hasil yang sama dalam pengelompokan pada kategori simpul yang sama.

Kita dapat mengurangi overfitting dengan menambahkan dataset validasi kedua dan meningkatkan kinerja model dengan bereksperimen menggunakan berbagai lapisan GCN dari pytoch_geometric.

Sumber kode tutorial tersedia pada DataLab workbook ini. Buat salinannya untuk Anda jalankan.

Tambahkan keahlian Deep Learning ke Résumé Anda dengan mengikuti jalur keahlian Deep Learning in Python. Jalur ini akan memperkenalkan Anda pada algoritma deep learning, Keras, Pytorch, dan kerangka kerja Tensorflow.