Meskipun tampilan luarnya bagus dan lembut dari modul Python biasa, algoritme inti dan struktur data alat grafik ditulis dalam C++, dengan mempertimbangkan kinerja. Sebagian besar waktu, Anda dapat mengharapkan algoritme berjalan secepat jika alat grafik adalah pustaka C/C++ murni. Lihat perbandingan performa
Dukungan OpenMP
Banyak algoritma diimplementasikan secara paralel menggunakan OpenMP, yang memberikan kinerja luar biasa pada arsitektur multi-core, tanpa menurunkannya pada mesin single-core
Visualisasi yang Kuat
Gambar grafik Anda dengan mudah, menggunakan berbagai algoritme dan format keluaran (termasuk ke layar). Graph-tool memiliki algoritme tata letaknya sendiri dan rutinitas menggambar interaktif yang serbaguna berdasarkan cairo dan GTK+, tetapi juga dapat berfungsi sebagai antarmuka yang sangat nyaman untuk paket graphviz yang luar biasa
Didokumentasikan Sepenuhnya
Setiap fungsi dalam modul didokumentasikan dalam docstrings dan dokumentasi online, yang penuh dengan contoh
Saya sedang menulis aplikasi python yang akan banyak menggunakan struktur data grafik. Tidak ada yang sangat rumit, tapi saya pikir semacam perpustakaan grafik / grafik-algoritma akan membantu saya. Saya sudah mencari-cari di Google, tetapi saya tidak menemukan apa pun yang secara khusus menarik bagi saya
Ada yang punya rekomendasi bagus?
Grafik adalah entitas data matematika yang relatif lama yang merupakan kumpulan elemen yang terhubung. Karena grafik adalah struktur yang sangat fleksibel dan memungkinkan Anda menyimpan informasi dalam bentuk yang akrab dan nyaman bagi manusia, grafik selalu digunakan dalam ilmu dan teknologi komputer. Dengan munculnya pembelajaran mesin dan pembelajaran mendalam, grafik semakin populer dengan menciptakan bidang pembelajaran mesin grafik
Dalam posting ini, saya ingin berbagi dengan Anda pustaka Python paling berguna yang pernah saya gunakan untuk analisis grafik/jaringan, visualisasi, dan pembelajaran mesin. Hari ini, kami akan meninjau
- NetworkX untuk analisis grafik umum;
- PyVis untuk visualisasi grafik interaktif langsung di browser Anda;
- PyG dan DGL untuk menyelesaikan berbagai tugas pembelajaran mesin grafik
Sebelum itu, izinkan saya memberi tahu Anda beberapa kata tentang teori graf dan pembelajaran mesin graf dan memberikan beberapa sumber belajar yang mungkin berguna bagi Anda. Jika Anda tidak tahu apa itu graph atau graph machine learning, itu adalah kesempatan bagus untuk membuka tabir kerahasiaan
Teori Grafik dan Pembelajaran Mesin Grafik. perkenalan singkatGrafik hanyalah sekumpulan elemen yang terhubung satu sama lain
Contoh grafik. Area publik
Namun, fakta bahwa elemen-elemen ini (disebut node) dapat berisi informasi apa pun dan dapat dihubungkan dengan cara apa pun (dengan tepian) menjadikan grafik sebagai struktur data yang paling umum. Memang, data kompleks apa pun yang kita kenal dapat direpresentasikan sebagai grafik sederhana. misalnya, gambar — sebagai kisi piksel atau teks — sebagai urutan (atau rangkaian) kata
Anda mungkin bertanya-tanya. apakah grafik sangat penting? . Bayangkan situasi berikut. Anda perlu mengunjungi daftar kota, katakanlah untuk pariwisata atau untuk bekerja. Anda memiliki informasi tentang jarak dari satu kota ke kota lain, atau katakanlah, biaya tiket untuk moda transportasi yang berbeda — bahkan lebih menarik. Bagaimana cara membuat rute yang optimal, yaitu membelanjakan uang seminimal mungkin atau berkendara dengan jarak minimum?
Bagi saya, tugasnya cukup praktis — setidaknya pikirkan penerapannya di bidang logistik. Dan, ini adalah contoh soal yang tidak bisa diselesaikan tanpa bantuan grafik. Pikirkan tentang bagaimana Anda akan merepresentasikan data dan dalam hal apa pun, Anda masih akan sampai pada grafik berbobot (grafik yang sisi-sisinya memiliki beberapa nilai, disebut bobot). Ngomong-ngomong, jika setiap kota perlu dikunjungi tepat satu kali, tugas ini berubah menjadi masalah salesman keliling (TSP) yang terkenal, yang tidak mudah diselesaikan. Salah satu alasannya adalah jumlah rute yang memungkinkan tumbuh sangat cepat, dan bahkan untuk 7 kota sudah ada 360 kota.
Solusi untuk TSP dengan 7 kota menggunakan pencarian brute force.
Teori grafik (berasal dari abad ke-18) terlibat dalam studi grafik dan memecahkan berbagai masalah grafik. menemukan jalur yang mungkin atau optimal dalam grafik, membangun dan meneliti pohon (jenis grafik khusus), dan seterusnya. Teori graf berhasil digunakan dalam ilmu sosial, kimia, biologi, dan bidang lainnya. Namun dengan perkembangan komputer, proses penggunaan grafik telah mencapai level lain
Yang benar-benar penting adalah basis ini. sekumpulan elemen terkait, seringkali dengan elemen dan jenis koneksi yang berbeda, sangat berguna untuk memodelkan tugas dan kumpulan data dunia nyata. Ini adalah tempat di mana pembelajaran mesin grafik masuk ke dalam gambar (walaupun tugas-tugas luar biasa telah diselesaikan sebelumnya juga). Setelah umat manusia mengumpulkan kumpulan data yang sesuai dan mengembangkan teknologi untuk memodelkannya (seperti Graph Convolutional Networks (GCNs), dengan analogi dengan Convolutional Neural Networks (CNNs)) menjadi mungkin untuk menyelesaikan berbagai tugas grafik
- Tugas tingkat simpul, seperti klasifikasi simpul — tetapkan label untuk setiap simpul dalam grafik. Kita akan melihat contoh sedikit di bawah — membagi sekelompok orang menjadi dua kelompok, mengetahui bagaimana mereka berkomunikasi satu sama lain; . Intuisi di sini berasal dari ilmu sosial, yang mengatakan bahwa kita bergantung pada lingkungan kita. Memang, setiap entitas dapat diklasifikasikan lebih efektif dengan mempertimbangkan tidak hanya beberapa fitur tetapi juga data tentang lingkungannya. Misalnya, jika teman Anda merokok, kemungkinan besar Anda akan merokok, dan jika teman Anda pergi ke gym, kemungkinan besar Anda akan pergi ke gym.
- Tugas tingkat tepi, seperti prediksi tepi — memprediksi apakah dua node memiliki tepi atau, lebih sering, memprediksi jenis tepi (grafik yang memiliki beberapa jenis tepi disebut multigraf). Tugas ini sangat menarik untuk grafik pengetahuan, yang kita lihat dalam beberapa menit
- Tugas tingkat grafik. Ini bisa berupa klasifikasi grafik, pembuatan grafik, dan sebagainya. Bidang ini sangat berguna untuk biologi dan kimia karena molekul dapat secara efektif direpresentasikan sebagai grafik. Klasifikasi molekul (menentukan apakah molekul memiliki sifat tertentu) atau pembuatan molekul (dan terutama pembuatan obat) terdengar jauh lebih keren daripada beberapa "tugas tingkat grafik"
Mari kita lihat contoh grafik dari kehidupan nyata. Salah satu kumpulan data grafik yang paling terkenal adalah kumpulan data klub karate. Di sini, setiap simpul adalah satu orang (anggota klub), dan setiap sisi mewakili dua anggota yang berinteraksi di luar klub
Visualisasi kumpulan data klub karate.
Masalah umum adalah menemukan dua kelompok orang di mana klub berpisah setelah pertengkaran antara dua instruktur (sekarang kita dapat memperlakukannya sebagai klasifikasi simpul biner (atau 2 kelas)). Kumpulan data dikumpulkan kembali pada tahun 1977 dan menjadi contoh klasik dari jaringan sosial manusia atau struktur komunitas
Jenis grafik lain, yang dapat ditafsirkan oleh manusia, dan karenanya sangat berguna untuk model pembelajaran mesin adalah grafik pengetahuan. Dalam grafik pengetahuan, sebuah node adalah beberapa entitas atau konsep dan edge mewakili pengetahuan tentang interaksi sepasang entitas. Dengan demikian, struktur node-edge-node menyimpan fakta tertentu tentang dunia atau sistem tertentu
Contoh sederhana grafik pengetahuan.
Grafik pengetahuan pada contoh di atas berisi dua jenis sisi. adalah dan makan dan dengan demikian multigraf yang kami perkenalkan sebelumnya. Struktur Dogs-is-Animals memberi kita pengetahuan bahwa kumpulan "anjing" adalah subhimpunan dari kumpulan "binatang", atau, dalam istilah yang lebih sederhana, bahwa anjing adalah binatang
Wikidata adalah basis pengetahuan gratis yang sangat besar dari Wikipedia, yang terus diperbarui dan sekarang memiliki lebih dari 100 juta node. Ada lebih dari 400 jenis edge, beberapa di antaranya merupakan bagian dari, berbeda dari, kebalikan dari, populasi, dan lokasi, jadi pasti masuk akal
20 edge relasi teratas di basis pengetahuan wikidata untuk tahun 2020. Area publik
Basis pengetahuan yang sangat besar itu berisi banyak informasi tentang dunia di sekitar kita. Masih menakjubkan bagi saya bagaimana umat manusia mengumpulkan data ini, dan bahwa mesin sekarang dapat memprosesnya
Satu hal lagi yang tidak bisa saya diamkan adalah kemampuan visualisasi wikidata yang indah. Misalnya, di sini Anda dapat melihat plot konektivitas negara bagian Amerika Serikat. Perhatikan bahwa ini tidak digambar oleh siapa pun, ini hanyalah subgraf dari keseluruhan grafik wikidata. kami hanya mengambil negara bagian Amerika sebagai simpul dan P47 (berbatasan dengan) sebagai tepi
Konektivitas negara bagian AS. Area publik
Lihatlah Pembuat Grafik Wikidata dan visualisasi lainnya. Izinkan saya mengarahkan Anda ke beberapa di antaranya yang menurut saya menghibur
- Peta hubungan antara guru dan murid dari Socrates hingga akhir Periode Helenistik
- Garis waktu interaktif dengan peristiwa sejarah
- Pohon keluarga Pan Pan panda
Tahu Lebih Banyak tentang Grafik
Jika setelah ikhtisar singkat itu Anda sekarang tertarik pada grafik dan ingin tahu lebih banyak tentangnya, saya merujuk Anda ke Pengantar Lembut yang luar biasa untuk Graph Neural Networks oleh Google Research. Dalam artikel ini, Anda dapat menemukan lebih banyak contoh dan visualisasi interaktif
Periksa kursus Algoritma Teori Graf oleh freeCodeCamp. org untuk berbagai ikhtisar algoritma teori graf atau Stanford CS224W. Pembelajaran Mesin dengan kursus Grafik untuk memulai perjalanan pembelajaran mesin grafik Anda
Setelah pengantar singkat itu, mari kita mulai dengan pustaka Python
NetworkX — Analisis Grafik UmumJika Anda harus melakukan beberapa operasi pada grafik dan Anda menggunakan Python sebagai bahasa pemrograman Anda, kemungkinan besar Anda akan menemukan pustaka NetworkX dengan cukup cepat. Ini mungkin perpustakaan yang paling mendasar dan umum digunakan untuk analisis jaringan yang menyediakan berbagai fungsi
- Struktur data untuk menyimpan dan mengoperasikan grafik dan multigraf yang tidak diarahkan atau diarahkan;
- Banyak algoritma graf yang diimplementasikan;
- Alat visualisasi dasar
Perpustakaannya cukup intuitif dan mudah digunakan. Selain itu, sebagian besar fundamental, seperti struktur data grafik, akan tetap sama atau setidaknya serupa untuk semua pustaka grafik populer. Untuk kejelasan, Anda dapat membuat grafik sederhana dan memvisualisasikannya dengan kode berikut
Visualisasi dasar NetworkX. Gambar oleh Penulis
Dalam hal algoritme, networkx cukup kuat dan menerapkan ratusan algoritme grafik
Untuk meringkas, ini adalah perpustakaan yang efisien, dapat diskalakan, dan kuat, yang pasti akan berguna bagi Anda jika Anda berurusan dengan analisis grafik
Referensi
NetworkX - dokumentasi NetworkX
NetworkX adalah paket Python untuk membuat, memanipulasi, dan mempelajari struktur, dinamika, dan fungsi…
jaringanx. org
PyVis — Visualisasi Grafik InteraktifMenggunakan networkx untuk visualisasi grafik bisa sangat bagus untuk grafik kecil tetapi jika Anda membutuhkan lebih banyak fleksibilitas atau interaktivitas, lebih baik Anda memberi kesempatan pada PyVis. Situasinya mirip dengan matplotlib vs plotly. Menggunakan matplotlib untuk visualisasi yang cepat dan langsung tidak apa-apa, tetapi jika Anda perlu berinteraksi dengan bagan Anda atau mempresentasikannya kepada orang lain, lebih baik Anda menggunakan alat yang lebih canggih
PyVis dibangun di perpustakaan VisJS dan menghasilkan visualisasi interaktif di browser Anda dengan kode sederhana. Mari plot grafik yang sama seperti pada contoh di atas
Kode ini akan membuat file graph.html. Dengan membukanya, Anda akan dapat berinteraksi dengan visualisasi Anda. perbesar, seret, dan banyak lagi
Contoh visualisasi PyVis. Gif oleh Penulis
Terlihat menarik, bukan? . Periksa tutorial resmi yang akan memandu Anda melalui kemampuan perpustakaan utama
Referensi
Visualisasi jaringan interaktif — pyvis 0. 1. 3. 1 dokumentasi
pyvis. readthedocs. io
Pembelajaran Mesin Grafik DGL dan PyGSekarang mari beralih ke topik yang lebih lanjut — pembelajaran mesin grafik. Saya akan menyebutkan dua perpustakaan paling populer untuk itu. DGL dan PyG
DGL (Deep Graph Library) awalnya dirilis pada tahun 2018. Berbeda dengan PyG (PyTorch Geometric), yang dibangun di atas PyTorch dan karenanya hanya mendukung tensor PyTorch, DGL mendukung beberapa kerangka kerja pembelajaran mendalam, termasuk PyTorch, TensorFlow, dan MXNet
Kedua perpustakaan mengimplementasikan sel-sel Graph Neural Network (GNN) yang populer seperti GraphSAGE, GAT (Graph Attention Network), GIN (Graph Isomorphism Network), dan lainnya. Tidak akan sulit untuk membuat model dari blok yang telah dibuat sebelumnya — prosesnya sangat mirip dengan PyTorch atau TensorFlow biasa
Inilah cara Anda membuat model GCN 2 lapis untuk klasifikasi simpul di PyG
Dan kode yang sama untuk DGL
Kedua cuplikan kode tersebut cukup mudah jika Anda terbiasa dengan pembelajaran mendalam dan PyTorch
Seperti yang Anda lihat, definisi model sangat mirip untuk kedua pustaka. Lingkaran pelatihan kemudian dapat ditulis pada PyTorch biasa untuk PyG dan memerlukan beberapa modifikasi untuk DGL (karena objek grafik DGL menyimpan seluruh kumpulan data, dan Anda harus menangani rangkaian pelatihan/validasi/pengujian menggunakan masker biner)
Ada sedikit perbedaan dalam representasi data di sini. Anda dapat melihatnya setidaknya berdasarkan parameter masukan yang berbeda untuk metode forward. Memang, PyG menyimpan semuanya sebagai tensor PyTorch dan DGL memiliki objek grafik terpisah yang harus Anda gunakan, dan di bawah terpal, ini mengikuti gaya NetworkX yang lebih klasik
Namun, itu bukan masalah besar — Anda dapat mengonversi objek grafik PyG ke grafik DGL dan sebaliknya dengan beberapa baris kode. Pertanyaan yang lebih penting adalah. bagaimana lagi mereka berbeda?
DGL vs PyG
Mencoba mencari tahu perpustakaan mana yang lebih baik, Anda akan terus menemukan jawaban yang sama — "coba keduanya dan putuskan mana yang terbaik untuk Anda". Oke, tapi bagaimana perbedaannya?
Dan mereka benar-benar. Apalagi Anda melihatnya sendiri dengan melihat kodenya beberapa menit yang lalu. Namun tentu saja, Anda dapat menemukan beberapa perbedaan yang digali lebih dalam. di sini adalah daftar sumber yang bagus termasuk beberapa pemikiran oleh penulis perpustakaan, dan ini adalah perbandingan yang cukup rinci di sisi yang berbeda
Secara umum, jawabannya adalah mencoba keduanya. Faktanya, DGL memiliki lebih banyak API level rendah dan bisa lebih sulit digunakan dalam arti mengimplementasikan ide-ide baru. Tapi ini membuatnya lebih fleksibel. DGL tidak terbatas pada jaringan penyampaian pesan (Graph Convolutional Networks klasik) dan menerapkan beberapa konsep yang tidak dapat disediakan oleh PyG, misalnya, Tree-LSTM
PyTorch Geometric, di sisi lain, membuat API-nya semudah mungkin dan kemudian mendapatkan lebih banyak popularitas di kalangan peneliti yang dapat dengan cepat mengimplementasikan ide-ide baru, i. e. sel GNN baru. Di masa lalu, PyG menjadi semakin populer karena pembaruan penting dengan PyG 2. 0 dan tim kolaborator yang aktif dan kuat, termasuk Stanford University
Jumlah kueri penelusuran DGL vs PyG selama 5 tahun terakhir. Area publik
Jadi saya tetap mendorong Anda untuk mencoba keduanya, memberi PyG kesempatan terlebih dahulu
Jika Anda sedang mengerjakan masalah grafik yang relatif familiar (baik itu klasifikasi node, klasifikasi grafik, dll. ), keduanya PyG dan memiliki sejumlah besar sel GNN yang diimplementasikan. Juga dengan PyG, akan lebih mudah bagi Anda untuk mengimplementasikan GNN Anda sendiri sebagai bagian dari riset apa pun
Namun, jika Anda ingin mendapatkan kendali penuh atas apa yang terjadi di balik terpal atau mengimplementasikan sesuatu yang lebih rumit daripada kerangka penyampaian pesan, pilihan Anda kemungkinan besar akan jatuh pada DGL.
Referensi
- Situs web resmi PyG, dokumentasi PyG
- Situs web resmi DGL, dokumentasi DGL
Target audiens artikel ini (orang yang tertarik dengan grafik) cukup kecil. Yah, pembelajaran mesin adalah bidang ilmu komputer yang cukup muda, dan pembelajaran mesin grafik bahkan lebih muda. Yang terakhir terutama menarik perhatian komunitas riset, tetapi, percaya atau tidak, ini digunakan dalam aplikasi dunia nyata yang penting seperti sistem rekomendasi dan studi biologi/kimia.
Bagaimanapun, saya harap materi ini menarik atau bermanfaat bagi Anda — apakah Anda sedang mencari sesuatu yang spesifik atau baru mempelajari sesuatu yang baru hari ini. Sebagai rangkuman, hari ini kami mengulas secara singkat apa itu graph dan graph machine learning, dan melihat library-library berikut