Skip to content
Kembali ke hasil pencarian

Jaringan Saraf Graf — GCN / GAT / GraphSAGE

Tahun
2017–2018 (major variants)
Jenis
Deep learning on graph-structured data

Teks ini adalah terjemahan mesin dan belum ditinjau. Baca versi asli dalam bahasa Inggris

Ukuran huruf

Apa fungsinya?

Jaringan Saraf Graf (GNN) adalah arsitektur pembelajaran mendalam yang beroperasi langsung pada data terstruktur graf dengan menggabungkan fitur node dengan informasi struktural melalui penyebaran pesan lingkungan secara iteratif.

Tiga varian kanonik — Jaringan Konvolusional Graf (GCN) yang diperkenalkan oleh Kipf dan Welling pada tahun 2017, Jaringan Perhatian Graf (GAT) yang diperkenalkan oleh Veličković dkk. pada tahun 2018, dan GraphSAGE — berbeda dalam cara mereka mengagregasi informasi tetangga: GCN menerapkan konvolusi spektral pada keseluruhan adjasensi, GAT memberi bobot tetangga dengan skor perhatian yang dipelajari, dan GraphSAGE mengambil sampel serta mengagregasi lingkungan lokal secara induktif, memungkinkan generalisasi ke node yang belum terlihat.

Intuisi di balik metode

Bayangkan setiap node dalam graf sebagai orang dalam jaringan sosial. Orang tersebut memiliki profilnya sendiri (fitur), tetapi siapa yang mereka kenal juga banyak bercerita tentang mereka. GNN memungkinkan setiap node berulang kali mengumpulkan pesan dari tetangganya, mencampur pesan tersebut dengan informasinya sendiri, dan memperbarui representasinya — lapis demi lapis. Setelah beberapa putaran pertukaran gaya gosip ini, embedding setiap node mencerminkan tidak hanya dirinya sendiri tetapi juga subgraph lokal di sekitarnya. GCN melakukan ini dengan rata-rata simetris tetap dari tetangga; GAT memutuskan tetangga mana yang lebih dipercaya dengan mempelajari bobot perhatian; GraphSAGE mengambil sampel subset tetap dari tetangga dan mempelajari fungsi agregasi yang dapat diterapkan pada node yang belum pernah dilihat sebelumnya.

Sejarah

Dasar-dasar penerapan jaringan saraf pada graf diletakkan oleh Scarselli dkk. (2009), tetapi era GNN modern dimulai dengan Jaringan Konvolusional Graf Kipf dan Welling (2017), yang menyederhanakan konvolusi graf spektral menjadi aproksimasi orde pertama yang efisien menggunakan perkalian adjasensi normalisasi simetris. Setahun kemudian, Veličković dkk. (2018) memperkenalkan Jaringan Perhatian Graf, menggantikan rata-rata tetap GCN dengan koefisien perhatian yang dapat dipelajari pada setiap tepi — memungkinkan model untuk secara selektif memberi bobot pada tetangga. Bersamaan, Hamilton dkk. (2017) mengusulkan GraphSAGE, kerangka kerja induktif yang mengambil sampel lingkungan berukuran tetap dan mempelajari fungsi agregasi yang dapat ditransfer ke node yang belum terlihat, membuat GNN praktis untuk graf besar dan dinamis. Ketiga makalah ini menetapkan paradigma penyebaran pesan yang sekarang mendasari sebagian besar penelitian GNN.

Kapan digunakan

Gunakan GNN ketika data Anda secara alami terstruktur graf — jaringan sosial, jaringan kutipan, graf molekuler, graf pengetahuan, atau pengaturan apa pun di mana hubungan antar entitas membawa sinyal prediktif. Anda memerlukan matriks fitur node dan daftar tepi. Minimal sekitar 50 node diperlukan untuk pelatihan yang bermakna. GNN berlaku untuk klasifikasi node (memprediksi label untuk setiap node), prediksi tautan (menyimpulkan tepi yang hilang), dan klasifikasi graf (menetapkan label ke seluruh graf). Asumsi homofili — node yang terhubung cenderung berbagi label yang sama — secara implisit dieksploitasi oleh GCN dan GAT standar; jika graf Anda heterofilik, pertimbangkan arsitektur yang dirancang untuk pengaturan tersebut. Untuk graf besar, pelatihan *full-batch* tidak memungkinkan karena keterbatasan memori dan pengambilan sampel lingkungan *mini-batch* (gaya GraphSAGE) diperlukan. Jika graf Anda memiliki kurang dari 20 node, metrik sentralitas tradisional adalah pilihan yang lebih tepat.

Batasan dan pertimbangan

  • Over-smoothing: menumpuk banyak lapisan GNN mendorong semua embedding node menuju nilai umum, membatasi kedalaman efektif menjadi sekitar 2–4 lapisan dalam praktik.
  • Skalabilitas: GCN dan GAT *full-batch* memerlukan penyimpanan seluruh matriks adjasensi dan matriks fitur dalam memori, yang tidak mungkin dilakukan untuk graf yang sangat besar tanpa pengambilan sampel atau partisi.
  • Asumsi homofili yang tertanam dalam agregasi standar menurunkan kinerja pada graf heterofilik di mana tetangga cenderung memiliki label yang berbeda.
  • Ukuran sampel minimum ~50 node diperlukan; lebih sedikit node membuat model tanpa sinyal yang cukup untuk mempelajari representasi yang bermakna.

Syarat dari sumber tidak menggantikan tinjauan ilmiah independen atau validasi oleh mesin analisis.

Kelebihan

  • Secara bersamaan memanfaatkan fitur node dan topologi graf, mengungguli metode yang hanya menggunakan salah satunya.
  • Mekanisme perhatian GAT menyediakan skor kepentingan per tepi, menambahkan interpretasi pada agregasi.
  • GraphSAGE bersifat induktif dan dapat digeneralisasi ke node dan graf yang tidak terlihat selama pelatihan, memungkinkan penerapan pada jaringan yang berkembang.
  • Kerangka kerja penyebaran pesan terpadu mencakup klasifikasi node, prediksi tautan, dan klasifikasi graf dengan tulang punggung arsitektur yang sama.

Penerapan

  • Klasifikasi node dalam jaringan kutipan — memprediksi topik sebuah makalah berdasarkan konten dan tautan kutipannya.
  • Penemuan obat — memprediksi sifat molekuler dengan memperlakukan atom sebagai node dan ikatan kimia sebagai tepi.
  • Sistem rekomendasi — memodelkan pengguna dan item sebagai graf bipartit dan memprediksi interaksi pengguna-item melalui prediksi tautan.
  • Deteksi penipuan dalam jaringan transaksi keuangan — mengidentifikasi node anomali berdasarkan fitur dan struktur lingkungannya.
  • Penyelesaian graf pengetahuan — menyimpulkan hubungan yang hilang antara entitas dalam basis pengetahuan skala besar.

Cara kerjanya

Cara kerjanya

1

Graf didefinisikan oleh matriks fitur node X (satu baris per node, satu kolom per atribut) dan daftar tepi (atau matriks adjasensi) A. Tepi tak berarah adalah standar untuk GCN dan GAT; GraphSAGE juga mendukung graf berarah. Loop diri biasanya ditambahkan ke A sehingga setiap node disertakan dalam agregasinya sendiri.

2

Atribut node mentah dinormalisasi dan, jika perlu, disematkan ke dalam ruang vektor kontinu. Atribut tepi, jika ada, dapat dimasukkan sebagai sinyal tambahan. Hasilnya adalah matriks fitur padat yang akan ditransformasi oleh setiap lapisan GNN.

3

Setiap lapisan GNN menghitung representasi node baru dengan mengagregasi fitur tetangga node dan menggabungkannya dengan fitur node itu sendiri melalui matriks bobot yang dapat dipelajari dan aktivasi non-linear. GCN menerapkan perkalian adjasensi yang dinormalisasi (konvolusi spektral); GAT menghitung koefisien perhatian softmax untuk setiap tepi sehingga tetangga yang berpengaruh berkontribusi lebih banyak; GraphSAGE secara acak mengambil sampel lingkungan berukuran tetap dan menerapkan agregator diferensiabel (rata-rata, LSTM, atau pooling). Menumpuk L lapisan memungkinkan informasi mengalir sejauh L lompatan, tetapi menumpuk terlalu banyak lapisan menyebabkan *over-smoothing*, di mana semua embedding node konvergen ke nilai yang sama.

4

Embedding node akhir dimasukkan ke dalam kepala spesifik tugas. Untuk klasifikasi node, lapisan softmax menetapkan probabilitas kelas untuk setiap node. Untuk prediksi tautan, produk dalam atau MLP menilai kemungkinan tepi antara dua embedding node. Untuk klasifikasi graf, pooling global (jumlah, rata-rata, atau hierarkis) mengagregasi semua embedding node menjadi satu vektor tingkat graf sebelum lapisan klasifikasi.

5

Kinerja model diukur pada set uji yang ditahan menggunakan metrik yang sesuai dengan tugas: akurasi atau F1 untuk klasifikasi node dan graf, AUC-ROC untuk prediksi tautan. Karena kumpulan data graf seringkali berukuran terbatas, evaluasi transduktif (masker latih/validasi/uji pada graf yang sama) atau pemisahan induktif (subgraf terpisah) harus sesuai dengan skenario penerapan.

Kesalahan umum

  • Menambahkan terlalu banyak lapisan GNN menyebabkan *over-smoothing*: semua embedding node konvergen dan model kehilangan kekuatan diskriminatif. Jaga jumlah lapisan pada 2–4 dan pantau varians embedding.
  • Pelatihan pada graf penuh tanpa *mini-batch* tidak memungkinkan karena keterbatasan memori untuk jaringan besar; gunakan pengambilan sampel tetangga gaya GraphSAGE atau partisi graf untuk graf dengan lebih dari beberapa ribu node.
  • Menerapkan GCN yang dilatih secara transduktif secara langsung ke node baru yang belum terlihat saat inferensi adalah salah; gunakan metode induktif seperti GraphSAGE jika penerapan Anda memerlukan generalisasi ke node baru.
  • Mengabaikan asumsi homofili pada graf heterofilik menghasilkan hasil yang buruk; periksa koefisien asortativitas graf sebelum memilih varian GNN standar.
  • Dengan kurang dari 20 node, pelatihan GNN menghasilkan representasi yang tidak dapat diandalkan; lebih pilih analisis sentralitas konvensional dalam rezim tersebut.

Pertanyaan yang sering diajukan

Varian GNN mana yang harus saya mulai — GCN, GAT, atau GraphSAGE?

GCN adalah *baseline* paling sederhana dan bekerja dengan baik pada graf homofilik skala kecil hingga menengah di mana semua node diketahui saat pelatihan. GAT lebih disukai ketika kepentingan tetangga bervariasi dan Anda menginginkan bobot perhatian yang dapat diinterpretasikan. GraphSAGE adalah pilihan yang tepat ketika Anda perlu menggeneralisasi ke node yang belum terlihat selama pelatihan atau ketika graf terlalu besar untuk pemrosesan *full-batch*.

Apa itu *over-smoothing* dan bagaimana cara menghindarinya?

*Over-smoothing* terjadi ketika banyak lapisan GNN menyebabkan semua embedding node konvergen ke nilai yang sama, menghilangkan informasi diskriminatif. Dalam praktik, 2–4 lapisan biasanya optimal. Teknik seperti koneksi residual, jaringan pengetahuan lompatan (*jumping knowledge networks*), dan DropEdge dapat membantu jika arsitektur yang lebih dalam diperlukan.

Apakah GNN memerlukan data berlabel untuk semua node?

Tidak. GCN dan GAT umumnya digunakan dalam pengaturan *semi-supervised* di mana hanya sebagian kecil node yang memiliki label; struktur graf menyebarkan informasi dari node berlabel ke node yang tidak berlabel. GraphSAGE juga dapat dilatih dalam mode *fully supervised* atau *unsupervised* tergantung pada tugasnya.

Seberapa besar graf yang dibutuhkan?

Minimal sekitar 50 node diperlukan untuk pelatihan GNN yang bermakna. Dengan kurang dari 20 node, model tidak dapat mempelajari representasi yang andal dan analisis berbasis sentralitas tradisional lebih tepat. Untuk graf dengan jutaan node, pengambilan sampel tetangga *mini-batch* (seperti pada GraphSAGE) atau metode partisi graf diperlukan untuk menjaga penggunaan memori tetap dapat dikelola.

Metode terkait

Sumber

  1. Kipf, T.N. & Welling, M. (2017). Semi-Supervised Classification with Graph Convolutional Networks. International Conference on Learning Representations (ICLR).

    Buka referensi DOI
    Disalin.
  2. Veličković, P., Cucurull, G., Casanova, A., Romero, A., Liò, P., & Bengio, Y. (2018). Graph Attention Networks. International Conference on Learning Representations (ICLR).

    Buka referensi DOI
    Disalin.
  3. Hamilton, W.L. (2020). Graph Representation Learning. Morgan & Claypool.

    Buka referensi DOI
    Disalin.