Perpustakaan struktur data grafik python

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

Grafik hanyalah sekumpulan elemen yang terhubung satu sama lain

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.

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

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

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

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

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

Jika 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

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

Menggunakan 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

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

Sekarang 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

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

Apakah ada struktur data grafik di Python?

Bagaimana Anda menerapkan grafik dalam struktur data dengan Python?

Pustaka mana yang digunakan untuk memplot bagan dengan Python?

Bagaimana Anda memvisualisasikan grafik dalam struktur data dengan Python?