Bagaimana untuk menjana graf 'baik'? Kajian sistematik model generatif dalam untuk penjanaan graf

https://www.zhuanzhi.ai/paper/a904f0aa0762e65e1dd0b8b464df7168

>

Kemajuan terkini dalam model generatif dalam untuk penjanaan graf ialah langkah penting ke arah meningkatkan kesetiaan graf yang dijana dan membuka jalan untuk jenis aplikasi baharu. Kertas kerja ini memberikan gambaran keseluruhan kesusasteraan dalam bidang model generatif dalam untuk penjanaan graf. Pertama, definisi formal dan pengetahuan awal model generatif dalam untuk penjanaan graf diberikan kedua, klasifikasi model generatif dalam untuk penjanaan graf tanpa syarat dan bersyarat masing-masing dicadangkan dan kerja sedia ada masing-masing dibandingkan dan dianalisis. Berikutan ini, gambaran keseluruhan metrik penilaian dalam bidang khusus ini akan diberikan. Akhir sekali, aplikasi penjanaan peta mendalam diringkaskan dan lima hala tuju penyelidikan yang menjanjikan ditunjukkan.

Pengenalan

Graf ada di mana-mana di dunia nyata, mewakili objek dan hubungannya, seperti rangkaian sosial, rangkaian petikan, rangkaian biologi, rangkaian pengangkutan, dsb. Graf juga diketahui mempunyai struktur kompleks yang mengandungi nilai asas yang kaya [1]. Usaha yang ketara telah dilakukan dalam bidang ini, menghasilkan kesusasteraan yang kaya dan kaedah untuk menangani pelbagai masalah graf.

Pekerjaan ini boleh dibahagikan kepada dua kategori: 1) Meramal dan menganalisis corak graf yang diberikan. 2) Ketahui pengedaran graf yang diberikan dan jana lebih banyak graf baru. Jenis pertama merangkumi banyak bidang penyelidikan, termasuk klasifikasi nod, klasifikasi graf dan ramalan pautan. Banyak kerja telah dilakukan di kawasan ini sejak beberapa dekad yang lalu. Berbanding dengan jenis masalah pertama, jenis masalah kedua adalah berkaitan dengan masalah penjanaan graf, yang juga menjadi fokus artikel ini.

Penjanaan graf termasuk proses pemodelan dan penjanaan graf dunia sebenar, yang mempunyai aplikasi dalam beberapa bidang, seperti memahami rangkaian sosial [2], [3], [4] Interaksi dinamik dalam, pengesanan anomali [5], pemodelan struktur protein [6], [7], penjanaan dan terjemahan kod sumber [8], [9], penghuraian semantik [10]. Disebabkan aplikasinya yang luas, pembangunan model graf generatif mempunyai sejarah yang kaya, menghasilkan model yang terkenal seperti graf rawak, model dunia kecil, model blok stokastik dan model rangkaian Bayesian, yang berdasarkan struktur priori. andaian [11 ] Hasilkan graf. Model generatif graf ini [12], [13], [14] bertujuan untuk memodelkan keluarga graf pra-pilihan seperti graf rawak [15], rangkaian dunia kecil [16] dan graf tanpa skala [12]. Walau bagaimanapun, disebabkan kesederhanaan dan sifat buatan tangan mereka, model graf rawak ini selalunya mempunyai keupayaan terhad untuk memodelkan kebergantungan kompleks dan hanya boleh memodelkan beberapa sifat statistik graf.

Kaedah ini biasanya berfungsi dengan baik untuk sifat yang prinsip yang dipratentukan disesuaikan, tetapi biasanya tidak berfungsi dengan baik untuk sifat lain. Contohnya, model rangkaian kenalan boleh memuatkan wabak influenza tetapi bukan ketersambungan berfungsi dinamik. Walau bagaimanapun, dalam banyak bidang, sifat dan prinsip generatif rangkaian sebahagian besarnya tidak diketahui, seperti yang menerangkan mekanisme penyakit mental, serangan siber dan penyebaran perisian hasad dalam rangkaian otak. Untuk contoh lain, graf Erdos-Renyi tidak mempunyai taburan darjah berat yang biasa bagi kebanyakan rangkaian dunia sebenar. Tambahan pula, penggunaan andaian priori mengehadkan teknik tradisional ini daripada meneroka lebih banyak aplikasi dalam domain skala yang lebih besar di mana pengetahuan priori tentang graf sentiasa tidak tersedia.

Memandangkan batasan teknik penjanaan graf tradisional, cabaran terbuka yang utama ialah membangunkan kaedah yang boleh mempelajari model generatif secara langsung daripada koleksi graf yang diperhatikan, yang merupakan peningkatan dalam penjanaan graf. Satu langkah penting untuk kesetiaan. Ia membuka jalan untuk jenis aplikasi baharu, seperti penemuan ubat baharu [17], [18], dan pemodelan struktur protein [19], [20], [21]. Kemajuan terkini dalam model generatif mendalam, seperti pengekod auto variasi (VAEs) [22] dan rangkaian adversarial generatif (GAN) [23], telah dicadangkan untuk menjana graf Banyak model pembelajaran mendalam telah diformalkan untuk Menjana graf adalah bidang yang menjanjikan model generatif mendalam, yang menjadi tumpuan kajian ini.

Pelbagai kerja lanjutan telah dijalankan dalam penjanaan peta mendalam, daripada penjanaan graf sekali kepada proses penjanaan graf berjujukan, menyesuaikan diri dengan pelbagai strategi pembelajaran generatif mendalam. Kaedah ini bertujuan untuk menangani satu atau beberapa cabaran di atas melalui kerja dalam bidang yang berbeza, termasuk pembelajaran mesin, bioinformatik, kecerdasan buatan, kesihatan manusia dan perlombongan rangkaian sosial. Walau bagaimanapun, kaedah yang dibangunkan dalam bidang penyelidikan yang berbeza sering menggunakan perbendaharaan kata yang berbeza dan pendekatan masalah dari perspektif yang berbeza.

Tambahan pula, terdapat kekurangan prosedur penilaian standard dan komprehensif untuk mengesahkan model generatif dalam yang dibangunkan untuk graf. Untuk tujuan ini, kertas kerja ini menyediakan tinjauan sistematik model generatif dalam untuk penjanaan graf. Tujuannya adalah untuk membantu penyelidik antara disiplin memilih teknologi yang sesuai untuk menyelesaikan masalah dalam bidang aplikasi mereka, dan yang lebih penting, untuk membantu penyelidik penjanaan graf memahami prinsip asas penjanaan graf dan mengenal pasti peluang penyelidikan terbuka dalam bidang penjanaan graf dalam. Untuk pengetahuan terbaik kami, ini ialah semakan komprehensif pertama model generatif mendalam untuk penjanaan graf. Di bawah, kami meringkaskan sumbangan utama ulasan ini:

Kertas kerja ini mencadangkan taksonomi model generatif dalam untuk penjanaan graf, dikelaskan mengikut penetapan dan pendekatan masalah. Kelebihan, keburukan, dan hubungan antara subkategori yang berbeza dibentangkan. Model generatif dalam untuk penjanaan graf dan model generatif dalam asas diterangkan, dianalisis dan dibandingkan secara terperinci.

• Kami meringkaskan dan mengklasifikasikan prosedur dan metrik penilaian sedia ada, keputusan pada set data penanda aras dan model penjanaan mendalam yang sepadan untuk tugas penjanaan graf.
• Kami memperkenalkan bidang aplikasi model generatif kedalaman graf sedia ada, dan potensi manfaat serta peluang yang mereka bawa kepada aplikasi ini.
• Kami membentangkan beberapa isu terbuka dan menjanjikan hala tuju penyelidikan masa depan dalam bidang model generatif dalam untuk penjanaan graf.

Model penjanaan kedalaman tanpa syarat untuk penjanaan graf

Penjanaan peta kedalaman tanpa syarat Matlamatnya ialah untuk mempelajari taburan pmodel(G) melalui model generatif dalam daripada set graf nyata yang diperhatikan yang disampel daripada taburan sebenar p(G). Mengikut gaya proses penjanaan, kita boleh membahagikan kaedah ini kepada dua cabang utama: (1) Penjanaan berjujukan: menjana nod dan tepi dalam urutan; (2) Penjanaan satu kali: membina model graf kebarangkalian mengikut perwakilan matriks dan menjana semua sekaligus nod dan tepi. Kedua-dua kaedah menjana graf mempunyai kelebihan dan kekurangan. Penjanaan berurutan, sambil melaksanakan keputusan tempatan generasi sebelumnya dengan cekap, menghadapi kesukaran untuk mengekalkan kebergantungan jangka panjang. Oleh itu, beberapa sifat global graf (seperti sifat bebas skala) sukar untuk disertakan. Tambahan pula, kerja sedia ada pada penjanaan jujukan adalah terhad kepada susunan jujukan yang telah ditetapkan, meninggalkan peranan pilih atur. Kaedah penjanaan satu pukulan boleh menjana dan memperhalusi keseluruhan graf secara serentak (iaitu, nod dan tepi) melalui berbilang lelaran, dengan itu memodelkan sifat global graf, tetapi memakan masa kerana keperluan untuk memodelkan secara kolektif hubungan global antara nod . Kerumitan biasanya melebihi O(N2), menjadikan kebanyakan kaedah sukar untuk skala kepada graf yang besar.

Model penjanaan kedalaman bersyarat untuk penjanaan graf

Matlamat penjanaan peta kedalaman bersyarat adalah berdasarkan set realiti yang diperhatikan. graf G dan maklumat tambahannya yang sepadan (iaitu keadaan y) mempelajari pmodel taburan bersyarat(G|y). Maklumat tambahan boleh berupa label kategori, konteks semantik, graf daripada ruang pengedaran lain, dsb. Berbanding dengan penjanaan peta kedalaman tanpa syarat, sebagai tambahan kepada cabaran dalam menjana peta, penjanaan bersyarat juga perlu mempertimbangkan cara mengekstrak ciri daripada keadaan tertentu dan menyepadukannya ke dalam penjanaan peta.

Oleh itu, untuk memperkenalkan model penjanaan peta kedalaman bersyarat sedia ada secara sistematik, kami menerangkan terutamanya cara kaedah ini mengendalikan keadaan. Memandangkan syarat boleh menjadi sebarang bentuk maklumat tambahan, ia dibahagikan kepada tiga jenis, termasuk graf, jujukan dan konteks semantik, seperti yang ditunjukkan dalam bahagian kuning pokok taksonomi dalam Rajah 1

Atas ialah kandungan terperinci Bagaimana untuk menjana graf 'baik'? Kajian sistematik model generatif dalam untuk penjanaan graf. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!