Prediksi Tautan — Inferensi Tautan Hilang dan Masa Depan dalam Jaringan
- Tahun
- 2003
- Jenis
- Network inference task
Teks ini adalah terjemahan mesin dan belum ditinjau. Baca versi asli dalam bahasa Inggris
Apa fungsinya?
Prediksi tautan adalah tugas analisis jaringan yang memperkirakan tautan mana yang hilang dari graf yang diamati atau tautan mana yang kemungkinan akan terbentuk di masa depan.
Diformalisasi oleh Liben-Nowell dan Kleinberg (2003, 2007), ini mencakup spektrum pendekatan — mulai dari indeks kesamaan struktural sederhana seperti Tetangga Umum, koefisien Jaccard, dan Adamic-Adar, hingga faktorisasi matriks, dan metode jaringan saraf graf (GNN) — dan dievaluasi dengan AUC dan Presisi Rata-rata untuk memperhitungkan rasio tautan nyata terhadap yang tidak ada yang sangat tidak seimbang.
Intuisi di balik metode
Dalam setiap jaringan dunia nyata, tautan yang tercatat hanya mewakili sebagian kecil dari koneksi yang sebenarnya: platform pertemanan kehilangan ikatan yang tidak diungkapkan, basis data kutipan menghilangkan makalah yang tidak terindeks, dan uji interaksi protein membiarkan banyak pasangan tidak teruji. Prediksi tautan bertanya: mengingat koneksi yang dapat kita lihat, pasangan yang tidak teramati mana yang paling mungkin terhubung? Inti intuisinya adalah bahwa dua node yang berbagi banyak tetangga umum, atau duduk berdekatan satu sama lain dalam ruang penyematan yang dipelajari, lebih mungkin terhubung daripada dua node yang berjauhan secara struktural. Indeks berbasis kesamaan membuat hal ini eksplisit dengan satu formula; pendekatan berbasis GNN mempelajari pola struktural mana yang terbaik memprediksi konektivitas dari contoh berlabel.
Sejarah
Tugas ini secara formal didefinisikan oleh Liben-Nowell dan Kleinberg dalam makalah SODA tahun 2003 dan versi JASIST yang diperluas tahun 2007, di mana mereka membandingkan indeks kesamaan struktural sederhana pada jaringan kolaborasi penulis dan menunjukkan bahwa topologi saja membawa sinyal prediktif yang kuat. Pekerjaan selanjutnya memperluas tugas ke faktorisasi matriks dan model generatif probabilistik. Bidang ini secara substansial dimajukan oleh Zhang dan Chen (2018), yang mengusulkan kerangka kerja Seal — mengekstrak subgraf penutup lokal dan mengklasifikasikannya dengan GNN — mendemonstrasikan bahwa fitur struktural yang dipelajari secara konsisten mengungguli indeks kesamaan buatan tangan di berbagai jaringan tolok ukur.
Kapan digunakan
Prediksi tautan cocok untuk masalah apa pun di mana jaringan tidak lengkap atau berkembang dan tujuannya adalah untuk memulihkan atau mengantisipasi tautan. Skenario yang cocok termasuk merekomendasikan koneksi baru di jejaring sosial, memprediksi kutipan atau kolaborasi di masa depan, menyimpulkan interaksi protein-protein, dan melengkapi graf pengetahuan. Metode ini membutuhkan setidaknya 50 node dan kepadatan tautan yang cukup agar pola struktural dapat dipelajari. Ketika kurang dari 20 node tersedia, analisis sentralitas adalah pilihan yang lebih aman. Bagian graf yang diamati harus representatif; jika mekanisme pengambilan sampel sangat bias, tautan yang disimpulkan mungkin mencerminkan artefak pengambilan sampel daripada struktur yang sebenarnya.
Batasan dan pertimbangan
- Kinerja sangat bergantung pada strategi pengambilan sampel negatif; strategi yang berbeda dapat menghasilkan kesimpulan yang berbeda dari model yang sama.
- Metode berbasis GNN memerlukan kumpulan tautan berlabel yang cukup besar dan sumber daya komputasi yang signifikan.
- Indeks struktural mengasumsikan bahwa kesamaan dalam topologi yang diamati menyiratkan konektivitas di masa depan, yang mungkin tidak berlaku dalam jaringan dengan struktur heterofilik.
- Pemisahan latih-uji temporal sangat penting tetapi memerlukan stempel waktu yang andal; tanpanya, kebocoran informasi meningkatkan kinerja yang tampak.
Syarat dari sumber tidak menggantikan tinjauan ilmiah independen atau validasi oleh mesin analisis.
Kelebihan
- Mencakup berbagai kompleksitas — indeks Jaccard atau Adamic-Adar sederhana tidak memerlukan pelatihan dan bekerja langsung pada topologi graf, sementara metode berbasis GNN mempelajari pola struktural yang kompleks.
- Indeks kesamaan bebas model cepat, dapat diinterpretasikan, dan kuat pada graf renggang dengan sinyal pelatihan terbatas.
- Pendekatan GNN menggeneralisasi dengan baik di berbagai domain (sosial, biologis, graf pengetahuan) dan menangkap topologi urutan lebih tinggi.
- Kerangka evaluasi AUC/AP kuat terhadap ketidakseimbangan kelas yang parah antara tautan nyata dan yang tidak ada.
Penerapan
- Rekomendasi teman atau koneksi di jejaring sosial (Facebook People You May Know, LinkedIn).
- Memprediksi kolaborasi penelitian atau hubungan kutipan di masa depan dalam jaringan akademik.
- Menyimpulkan interaksi protein-protein yang hilang dalam jaringan biologis dari data eksperimental parsial.
- Melengkapi graf pengetahuan dengan memprediksi relasi antar entitas.
- Prediksi interaksi obat-target dalam jaringan farmakologis.
Cara kerjanya
Cara kerjanya
Jaringan disusun dari tautan yang diamati dan dipartisi menjadi set pelatihan dan pengujian menggunakan pemisahan temporal atau acak. Pemisahan temporal lebih disukai kapan pun stempel waktu tersedia karena mencegah kebocoran informasi: tautan masa depan tidak boleh menginformasikan model tentang tautan masa lalu. Graf pelatihan adalah satu-satunya graf yang dapat diamati oleh metode penilaian.
Karena sebagian besar pasangan node tidak terhubung, mengevaluasi setiap pasangan yang absen tidak praktis. Strategi pengambilan sampel negatif memilih sekumpulan tautan yang tidak ada untuk berfungsi sebagai contoh negatif. Ukuran dan strategi pengambilan sampel (acak, pengambilan sampel negatif sulit, seimbang derajat) secara substansial memengaruhi kinerja yang terukur dan harus dilaporkan bersama dengan hasilnya.
Setiap pasangan kandidat menerima skor kemungkinan. Indeks struktural menghitung skor dari topologi graf yang diamati — Tetangga Umum menghitung tetangga bersama, Jaccard menormalkan hitungan tersebut dengan gabungan, dan Adamic-Adar memberi bobot tetangga bersama dengan log terbalik dari derajat mereka. Metode faktorisasi matriks menguraikan matriks ketetanggaan menjadi faktor laten yang hasil kali titiknya mendekati probabilitas tautan. Metode berbasis GNN, yang paling menonjol adalah kerangka kerja Seal oleh Zhang dan Chen (2018), mengekstrak subgraf lokal di sekitar setiap pasangan kandidat dan melatih pengklasifikasi graf untuk membedakan tautan nyata dari yang palsu, menangkap pola struktural urutan lebih tinggi yang dilewatkan oleh indeks sederhana.
Prediksi diberi peringkat berdasarkan skor dan dibandingkan dengan tautan positif dan negatif yang ditahan. AUC-ROC mengukur probabilitas bahwa pasangan positif acak diberi peringkat di atas pasangan negatif acak. Presisi Rata-rata (AP) merangkum presisi di seluruh peringkat penuh dan lebih informatif ketika contoh positif jarang terjadi. Kedua metrik harus dilaporkan; akurasi saja menyesatkan di bawah ketidakseimbangan kelas yang parah.
Kesalahan umum
- Membocorkan tautan masa depan ke dalam graf pelatihan — selalu gunakan pemisahan temporal atau acak yang ketat dan verifikasi tidak ada tautan uji yang muncul di matriks ketetanggaan pelatihan.
- Hanya melaporkan akurasi; karena non-tautan jauh melebihi jumlah tautan sebenarnya, akurasi hampir tidak berarti — selalu laporkan AUC dan AP.
- Mengabaikan strategi pengambilan sampel negatif saat membandingkan metode; mengubah pengambilan sampel dapat membalikkan peringkat antar model.
- Menerapkan prediksi tautan ke graf dengan kurang dari 20 node — dengan begitu sedikit node, pola struktural terlalu renggang untuk menghasilkan prediksi yang andal; lebih pilih analisis sentralitas sebagai gantinya.
- Memperlakukan graf yang diamati yang bias sebagai sampel representatif — jika tautan yang diamati secara sistematis menghilangkan jenis node tertentu, prediksi akan mewarisi bias tersebut.
Pertanyaan yang sering diajukan
Pendekatan mana yang harus saya pilih — indeks kesamaan atau GNN?
Indeks kesamaan (Tetangga Umum, Jaccard, Adamic-Adar) adalah titik awal yang baik: mereka tidak memerlukan pelatihan, dapat diinterpretasikan, dan berkinerja baik secara mengejutkan pada graf renggang. Metode berbasis GNN seperti Seal mengungguli indeks pada jaringan dengan struktur urutan lebih tinggi yang kompleks tetapi memerlukan jumlah tautan berlabel yang cukup dan lebih banyak sumber daya komputasi. Ketika data terbatas atau interpretasi penting, mulailah dengan indeks.
Bagaimana cara membagi graf untuk evaluasi tanpa membocorkan informasi?
Jika tautan Anda membawa stempel waktu, gunakan pemisahan temporal: latih pada tautan yang diamati sebelum waktu batas dan uji pada tautan yang terbentuk setelahnya. Tanpa stempel waktu, tahan sebagian acak dari tautan sebagai positif dan ambil jumlah tautan non-positif yang sama atau tetap sebagai negatif, pastikan tidak ada tautan yang ditahan muncul di matriks ketetanggaan pelatihan.
Mengapa AUC lebih disukai daripada akurasi?
Dalam setiap jaringan nyata, jumlah tautan yang absen jauh melebihi jumlah tautan yang ada — seringkali beberapa kali lipat. Model trivial yang memprediksi 'tidak ada tautan' untuk setiap pasangan mencapai akurasi yang hampir sempurna sambil tidak memprediksi apa pun yang berguna. AUC-ROC dan Presisi Rata-rata adalah metrik berbasis peringkat yang tidak sensitif terhadap ketidakseimbangan ini dan secara langsung mengukur kualitas peringkat.
Bisakah prediksi tautan diterapkan pada graf berarah atau berbobot?
Ya. Untuk graf berarah, skor dapat dihitung secara terpisah di setiap arah, dan beberapa kerangka kerja GNN secara native menangani ketetanggaan berarah. Untuk graf berbobot, indeks kesamaan dapat memasukkan bobot tautan dalam perhitungan lingkungan, dan metode GNN dapat menggunakan fitur tautan. Namun, sebagian besar studi tolok ukur dilakukan pada graf tak berbobot tak berarah, jadi kehati-hatian ekstra diperlukan saat mengadaptasi metode.
Metode terkait
Sumber
Liben-Nowell, D. & Kleinberg, J. (2007). The Link-Prediction Problem for Social Networks. Journal of the American Society for Information Science and Technology, 58(7), 1019-1031.
Buka referensi DOIDisalin.Zhang, M. & Chen, Y. (2018). Link Prediction Based on Graph Neural Networks. Advances in Neural Information Processing Systems (NeurIPS), 31.
Buka referensi publikasiDisalin.