Skip to content
Kembali ke hasil pencarian

Embedding Jaringan — Node2Vec, DeepWalk, LINE

Tahun
2014 (DeepWalk); 2016 (Node2Vec)
Jenis
Representation learning / unsupervised network method

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

Ukuran huruf

Apa fungsinya?

Embedding jaringan adalah keluarga metode pembelajaran representasi yang memetakan setiap node dari sebuah graf ke dalam vektor padat berdimensi rendah sambil mempertahankan properti struktural jaringan.

Pendekatan ini diformalkan untuk data jejaring sosial oleh Perozzi, Al-Rfou, dan Skiena dengan DeepWalk (2014), yang mengadaptasi model skip-gram Word2Vec ke jalan acak pada graf, dan diperluas oleh Grover dan Leskovec dengan Node2Vec (2016), yang memperkenalkan jalan acak bias yang menyeimbangkan eksplorasi luas-pertama dan dalam-pertama. Embedding ini mengubah data relasional menjadi vektor fitur yang dapat dikonsumsi langsung oleh pengklasifikasi dan algoritma pengelompokan pembelajaran mesin standar.

Intuisi di balik metode

Sebuah graf terdiri dari node dan edge, tetapi sebagian besar algoritma pembelajaran mesin mengharapkan tabel angka. Embedding jaringan memecahkan masalah terjemahan. Sama seperti Word2Vec mempelajari makna kata dengan melihat kata mana yang muncul berdekatan dalam kalimat, DeepWalk mempelajari makna node dengan melihat node mana yang muncul berdekatan dalam jalan acak melintasi graf. Hasilnya adalah koordinat dalam ruang vektor — node yang secara struktural serupa atau sering dikunjungi bersama akan berakhir berdekatan. Setelah setiap node memiliki vektor, Anda dapat memasukkan vektor-vektor tersebut ke dalam pengklasifikasi, mengelompokkannya dengan k-means, atau memvisualisasikannya dengan UMAP, tanpa menulis kode khusus graf apa pun.

Sejarah

Ide menerapkan Word2Vec ke data terstruktur graf diperkenalkan oleh Perozzi, Al-Rfou, dan Skiena dalam DeepWalk (KDD 2014), yang menunjukkan bahwa jalan acak pada graf sosial dapat menggantikan fitur buatan tangan untuk klasifikasi node. Grover dan Leskovec memperluas ini dalam Node2Vec (KDD 2016) dengan memperkenalkan jalan acak bias urutan kedua yang diparameterisasi oleh p dan q, memberikan kontrol eksplisit atas trade-off antara eksplorasi lingkungan berbasis homofili dan berbasis kesetaraan struktural. Sekitar periode yang sama, Tang et al. mengusulkan LINE (WWW 2015), yang mempelajari embedding dengan mengoptimalkan tujuan kedekatan urutan pertama dan kedua secara langsung daripada melalui jalan acak, membuatnya cocok untuk graf yang sangat besar. Bersama-sama, ketiga metode ini mendirikan bidang pembelajaran representasi jaringan dan menginspirasi arsitektur jaringan saraf graf berikutnya.

Kapan digunakan

Embedding jaringan sesuai ketika Anda memiliki graf dengan setidaknya 50 node dan Anda memerlukan fitur vektor kontinu untuk tugas hilir seperti klasifikasi node, prediksi tautan, atau pengelompokan node. Metode ini cocok untuk graf tak berbobot maupun berbobot, dan menangani struktur berarah atau tidak berarah. Pilih DeepWalk ketika baseline jalan acak seragam yang sederhana sudah cukup. Pilih Node2Vec ketika Anda ingin menyetel keseimbangan antara homofili dan kesetaraan struktural melalui parameter p dan q. Jika Anda perlu menyematkan node baru yang belum pernah terlihat sebelumnya pada waktu inferensi tanpa pelatihan ulang, pilih metode induktif seperti GraphSAGE; embedding jaringan dalam bentuk standarnya bersifat transduktif. Metode ini tidak memerlukan atribut node yang terdistribusi normal.

Batasan dan pertimbangan

  • Transduktif: model tidak dapat menyematkan node yang tidak ada selama pelatihan tanpa pelatihan ulang penuh.
  • Sensitivitas hiperparameter: dimensi embedding, panjang jalan, jumlah jalan, ukuran jendela, p, dan q semuanya memengaruhi kualitas embedding dan memerlukan penyetelan.
  • Jalan acak tidak menangkap struktur graf urutan lebih tinggi (misalnya, hyperedge atau edge multi-relasional) tanpa ekstensi.
  • Kinerja menurun pada graf yang sangat kecil (kurang dari 50 node) di mana korpus jalan terlalu jarang untuk mempelajari statistik yang andal.

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

Kelebihan

  • Mengonversi data graf relasional menjadi vektor berpanjang tetap yang kompatibel dengan setiap alur kerja pembelajaran mesin standar.
  • Parameter p dan q Node2Vec memungkinkan analis menyetel keseimbangan antara embedding yang peka terhadap komunitas dan peka terhadap peran.
  • Bobot edge dapat dimasukkan ke dalam probabilitas jalan, menangkap kekuatan hubungan tanpa langkah pemodelan tambahan.
  • Menskalakan ke graf besar melalui pengambilan sampel jalan acak yang efisien dan prosedur pelatihan skip-gram.

Penerapan

  • Klasifikasi node dalam jaringan kutipan, platform sosial, atau graf interaksi biologis.
  • Prediksi tautan — mengidentifikasi edge yang hilang atau di masa depan dengan membandingkan kesamaan embedding node.
  • Deteksi komunitas dengan mengelompokkan vektor node menggunakan metode k-means atau hierarkis.
  • Deteksi anomali — node yang embeddingnya merupakan outlier dalam ruang vektor dapat mewakili peran struktural yang tidak biasa.
  • Sistem rekomendasi di mana pengguna dan item adalah node dalam graf interaksi bipartit atau multipel.

Cara kerjanya

Cara kerjanya

1

Proses dimulai dengan graf G di mana node adalah entitas dan edge mewakili hubungan. Edge dapat berarah atau tidak berarah dan dapat membawa bobot yang nantinya akan memengaruhi probabilitas lintasan. Jika bobot edge ada, bobot tersebut dimasukkan dalam probabilitas jalan; jika tidak ada, semua edge menerima bobot yang sama. Pada tahap ini, analis juga memilih varian algoritma — DeepWalk untuk jalan acak seragam, Node2Vec untuk jalan bias yang dikontrol oleh parameter p (kembali) dan q (masuk-keluar), atau LINE ketika kedekatan lingkungan urutan pertama dan kedua harus dipelajari secara terpisah. Pilihan antara rezim parameter Node2Vec dipandu oleh properti jaringan yang diharapkan: homofili (node serupa terhubung, sehingga eksplorasi luas-pertama lebih disukai, q < 1) atau kesetaraan struktural (node dengan peran serupa mungkin berjauhan, sehingga eksplorasi dalam-pertama lebih disukai, p < 1).

2

Dimulai dari setiap node, algoritma mensimulasikan serangkaian jalan acak dengan panjang tetap (biasanya 30 langkah) dan mengulanginya berkali-kali (biasanya 200 jalan per node). Setiap jalan menghasilkan urutan pengenal node yang analog dengan kalimat kata. Dalam DeepWalk, node berikutnya dipilih secara seragam dari tetangga. Dalam Node2Vec, node berikutnya dipilih sesuai dengan probabilitas transisi yang dibiaskan oleh p dan q: kembali ke node sebelumnya dihukum oleh 1/p, tetap pada jarak yang sama adalah 1, dan bergerak lebih jauh dikontrol oleh 1/q. Kumpulan semua jalan membentuk korpus urutan node yang mengkodekan topologi graf.

3

Korpus urutan node dimasukkan ke dalam model skip-gram (arsitektur yang sama dengan Word2Vec). Untuk setiap node dalam sebuah jalan, model memprediksi node konteks di sekitarnya dalam jendela (biasanya 10 langkah). Melalui penurunan gradien stokastik, model mempelajari representasi vektor padat berdimensi tetap — umumnya 64 atau 128 — untuk setiap node sedemikian rupa sehingga node yang muncul bersama dalam jalan memiliki vektor yang serupa. Dimensi adalah hiperparameter: dimensi yang lebih besar menangkap lebih banyak struktur tetapi meningkatkan komputasi dan risiko overfitting pada graf kecil.

4

Setelah dilatih, model menyediakan satu vektor embedding per node. Vektor-vektor ini digunakan sebagai fitur untuk klasifikasi node (memasukkannya ke dalam regresi logistik atau pengklasifikasi neural), prediksi tautan (membandingkan vektor pasangan node kandidat), atau deteksi komunitas (mengelompokkan vektor). Embedding bersifat transduktif: mereka tetap untuk node yang dilihat selama pelatihan. Jika node baru harus di-embed setelah pelatihan, metode induktif seperti GraphSAGE harus digunakan, karena model Node2Vec atau DeepWalk standar tidak dapat digeneralisasi ke node yang belum terlihat tanpa pelatihan ulang.

Kesalahan umum

  • Menerapkan model Node2Vec ke node baru yang tidak ada dalam graf pelatihan — model tidak akan memiliki vektor untuk mereka; gunakan metode induktif (misalnya, GraphSAGE) ketika embedding transduktif tidak dapat diterima.
  • Menggunakan p=1, q=1 default (setara dengan DeepWalk) tanpa memeriksa apakah jaringan mengikuti pola homofili atau kesetaraan struktural — menyetel p dan q ke pola yang diharapkan dapat secara substansial meningkatkan kinerja tugas hilir.
  • Memperlakukan dimensi embedding sebagai konstanta tetap: pada graf kecil, dimensi 64 atau 128 dapat menyebabkan overfitting; mulai dari yang lebih rendah dan validasi pada tugas hilir.
  • Mengabaikan persyaratan sampel minimum: graf dengan kurang dari 50 node menghasilkan korpus jalan yang terlalu tipis untuk melatih embedding yang andal.

Pertanyaan yang sering diajukan

Apa perbedaan antara DeepWalk, Node2Vec, dan LINE?

DeepWalk menggunakan jalan acak seragam dan model skip-gram Word2Vec — ini adalah baseline paling sederhana. Node2Vec menambahkan jalan acak bias yang dikontrol oleh p dan q, memungkinkan analis untuk menyetel apakah jalan menjelajahi seperti pencarian luas-pertama (homofili) atau pencarian dalam-pertama (kesetaraan struktural). LINE sama sekali tidak menggunakan jalan acak; ia mengoptimalkan tujuan kedekatan urutan pertama dan kedua secara langsung pada daftar edge, yang lebih skalabel ke graf yang sangat besar tetapi mengorbankan sinyal lingkungan berbasis jalan.

Bagaimana cara memilih parameter p dan q di Node2Vec?

p mengontrol kemungkinan kembali ke node sebelumnya (p rendah = lebih sedikit backtracking), dan q mengontrol radius eksplorasi (q < 1 mendukung eksplorasi keluar, q > 1 menjaga jalan tetap dekat dengan sumber). Jika Anda mengharapkan node dalam komunitas yang sama menjadi serupa (homofili), atur q < 1 untuk membiarkan jalan menjelajah keluar. Jika Anda mengharapkan node dengan peran struktural yang sama menjadi serupa meskipun berjauhan, atur p < 1 untuk mendorong eksplorasi dalam-pertama. Validasi kedua rezim pada tugas hilir.

Bisakah saya menyematkan node baru setelah pelatihan tanpa melatih ulang seluruh model?

Node2Vec dan DeepWalk standar bersifat transduktif: matriks embedding hanya mencakup node yang dilihat selama pelatihan. Untuk generalisasi induktif ke node baru yang belum pernah terlihat, gunakan metode jaringan saraf graf induktif seperti GraphSAGE, yang mempelajari fungsi agregasi atas lingkungan node yang dapat diterapkan ke node mana pun pada waktu inferensi.

Berapa banyak dimensi yang harus saya gunakan untuk embedding?

Pilihan paling umum adalah 64 dan 128, dan ini bekerja dengan baik untuk graf sedang hingga besar. Untuk graf kecil (50–200 node) mulailah dengan dimensi yang lebih rendah (16 atau 32) untuk menghindari overfitting, dan evaluasi kualitas embedding dengan mengukur kinerja tugas hilir (misalnya, akurasi klasifikasi node) daripada hanya kesalahan rekonstruksi.

Metode terkait

Sumber

  1. Grover, A. & Leskovec, J. (2016). Node2Vec: Scalable Feature Learning for Networks. Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), 855-864.

    Buka referensi DOI
    Disalin.
  2. Perozzi, B., Al-Rfou, R., & Skiena, S. (2014). DeepWalk: Online Learning of Social Representations. Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), 701-710.

    Buka referensi DOI
    Disalin.