Rangkaian saraf graf telah diterbitkan dalam sub-jurnal Alam, tetapi ia telah didedahkan bahawa ia adalah 104 kali lebih perlahan daripada algoritma biasa Penanya: Adakah ia ketinggian baru?

GNN ialah bidang yang sangat popular sejak beberapa tahun kebelakangan ini. Baru-baru ini, kertas sub-jurnal Nature mencadangkan kaedah untuk menggunakan GNN untuk menyelesaikan masalah pengoptimuman gabungan, dan mendakwa bahawa prestasi pengoptimum GNN adalah setara atau bahkan melebihi penyelesai sedia ada. Walau bagaimanapun, kertas kerja ini telah menarik beberapa keraguan: sesetengah orang menunjukkan bahawa prestasi GNN ini sebenarnya tidak sebaik algoritma tamak klasik, dan kelajuannya jauh lebih perlahan daripada algoritma tamak (untuk masalah dengan satu juta pembolehubah, tamak algoritma adalah lebih baik daripada GNN 104 kali lebih pantas). Oleh itu, orang yang ragu-ragu berkata, "Kami tidak melihat sebarang alasan yang baik untuk menggunakan GNN ini untuk menyelesaikan masalah ini, ia seperti menggunakan tukul besi untuk memecahkan kacang." keunggulan kaedah tersebut.

Dalam beberapa tahun kebelakangan ini, rangkaian saraf telah menyelesaikan banyak masalah sukar dalam aplikasi dan sains asas, termasuk masalah pengoptimuman gabungan diskret, yang juga merupakan asas untuk pemahaman kita tentang had pengkomputeran.

Kajian 2022 Martin JA Schuetz et al. "Pengoptimuman gabungan dengan rangkaian saraf graf yang diilhamkan fizik" [4] dicadangkan untuk menggunakan rangkaian neural graf tanpa pengawasan (GNN) yang diilhamkan oleh fizik untuk Pendekatan ini nampaknya menjanjikan untuk menyelesaikan masalah pengoptimuman gabungan pada graf dan telah diterbitkan dalam jurnal berimpak tinggi (Nature Machine Intelligence). Kajian itu menguji prestasi GNN pada dua masalah pengoptimuman standard: potongan maksimum dan set bebas maksimum (MIS). Pengoptimum GNN yang baru dicadangkan ini mempunyai sifat yang sangat bagus: ia boleh diperluaskan kepada banyak masalah contoh yang lebih besar.

Alamat kertas: https://arxiv.org/pdf/2107.01188.pdf

Walau bagaimanapun, kertas baru baru-baru ini "Memecahkan kacang dengan tukul besi: apabila rangkaian saraf graf moden lebih teruk daripada algoritma tamak klasik" telah mempersoalkan penyelidikan Martin JA Schuetz et al., dengan alasan bahawa Martin JA Schuetz et al. Pengoptimum GNN ialah "memecahkan kacang dengan tukul besi, sama seperti memukul nyamuk dengan mortar", yang membazir sumber dan mempunyai hasil yang buruk.

Alamat kertas: https://arxiv.org/abs/2206.13211

Masalah MIS ditakrifkan seperti berikut: Memandangkan graf biasa rawak tidak terarah (d-RRG) dengan n nod dan darjah ditetapkan kepada d, set bebas (IS) merujuk kepada subset bucu yang tidak mengandungi jiran terdekat. pasangan ; Masalah MIS memerlukan mencari IS terbesar, yang saiznya dipanggil α. MIS ialah masalah NP-hard, tetapi seseorang ingin mencari algoritma untuk mencari IS dengan saiz sehampir mungkin kepada maksimum dalam masa polinomial. Tambahan pula, algoritma yang baik tidak seharusnya mengalami kemerosotan prestasi untuk nilai n yang lebih besar.

GNN baharu yang dicadangkan oleh Martin JA Schuetz et al boleh mencari IS untuk graf yang sangat besar (n≤ 10^6): masa berjalan algoritma adalah berkadar dengan saiz masalah: t. ∼ n^ 1.7, dan prestasi algoritma kekal stabil apabila n meningkat, seperti ditunjukkan dalam Rajah 1 di bawah.

​

Walau bagaimanapun, apabila membandingkan prestasi GNN yang dicadangkan dengan algoritma lain yang tersedia, kajian ini hanya membandingkan dengan Boppana- Algoritma penghampiran Halldorsson (BH) [8] telah dibandingkan Apabila n≤500, algoritma ini mempunyai masa berjalan t∼n^2.9. ​

Sebenarnya terdapat banyak algoritma lain untuk mengira IS yang jauh lebih pantas daripada BH, dan kajian itu harus membandingkan pengoptimum GNN yang dicadangkan dengan algoritma ini. Antaranya, algoritma yang paling mudah ialah algoritma tamak (GA) [9]. Selepas algoritma tamak berasaskan darjah (DGA) dioptimumkan, masa berjalan adalah hampir linear dengan bilangan nod n. ​

Kajian ini membandingkan pengoptimum GNN (terbuka) dan DGA (pepejal) yang dicadangkan oleh Martin JA Schuetz et al untuk mencari MIS pada d-RRG dengan d=3 dan d=5 prestasi. Seperti yang ditunjukkan dalam Rajah 1 (kanan), dari hubungan antara masa berjalan dan saiz masalah (bilangan nod), DGA jauh lebih baik daripada GNN Masa berjalan yang pertama adalah hampir berkadar dengan bilangan nod n. Terdapat hubungan linear (eksponen ialah 1.15 mungkin disebabkan oleh kesan pra-asimptotik), manakala masa berjalan GNN mempunyai hubungan hampir kuadratik dengan bilangan nod n.

Kajian ini percaya bahawa dakwaan Martin JA Schuetz et al. bahawa "prestasi pengoptimum berdasarkan rangkaian saraf graf adalah bersamaan atau lebih baik daripada penyelesai sedia ada, dan mempunyai keupayaan untuk mengatasi model SOTA semasa. "Boleh diperluaskan kepada masalah dengan berjuta-juta pembolehubah" tidak dapat menahan penelitian dan tidak konsisten dengan keputusan percubaan sebenar Martin JA Schuetz dan yang lain harus menyemak kertas itu. ​

Kajian ini menghuraikan prestasi DGA dan percaya bahawa algoritma tamak mudah ini harus dianggap sebagai penanda aras minimum, dan prestasi mana-mana algoritma baharu mestilah sekurang-kurangnya lebih baik daripada DGA Bakat yang baik diterima pakai.

Sudah tentu, DGA hanyalah algoritma yang sangat mudah, dan terdapat banyak algoritma standard lain yang lebih baik daripada DGA. Makalah 2019 Maria Chiara et al. "Algoritma Monte carlo sangat berkesan dalam mencari set bebas terbesar dalam graf rawak jarang" menyediakan kajian mendalam tentang prestasi berbilang algoritma untuk menyelesaikan masalah MIS. ​

Berdasarkan perkara ini, kajian ini menimbulkan persoalan: "Apabila menilai algoritma pengoptimuman baharu, apakah masalah yang benar-benar sukar yang harus digunakan sebagai penanda aras untuk menguji prestasi algoritma?"

Sebagai contoh, kajian ini percaya bahawa MIS pada d-RRG d16. Di sini keputusan untuk d=20 dan d=100 boleh dibandingkan dengan keputusan yang diberikan dalam kertas 2019 "Algoritma Monte carlo sangat berkesan dalam mencari set bebas terbesar dalam graf rawak jarang".

Jelas sekali, algoritma pengoptimuman yang baik harus diselesaikan dalam masa polinomial adalah lebih baik jika hubungannya adalah linear . , dan kualiti tidak sepatutnya menurun apabila n meningkat.

Kajian menyimpulkan: Pada masa ini, pengoptimum berasaskan rangkaian saraf (seperti yang dicadangkan oleh Martin JA Schuetz et al.) tidak memenuhi keperluan di atas dan tidak boleh bersaing dengan algoritma standard mudah untuk menyelesaikan masalah pengoptimuman yang sukar. Adalah penting untuk meneroka sama ada rangkaian saraf boleh memenuhi keperluan ini, atau sama ada terdapat sebab yang lebih mendalam untuk kegagalannya.

Atas ialah kandungan terperinci Rangkaian saraf graf telah diterbitkan dalam sub-jurnal Alam, tetapi ia telah didedahkan bahawa ia adalah 104 kali lebih perlahan daripada algoritma biasa Penanya: Adakah ia ketinggian baru?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!