Belajar dan berfikir tentang pengkomputeran graf

Perisian yang baik tidak ditemui melalui analisis program dan semakan ralat, tetapi dibina oleh orang yang betul.

Graf telah menjadi objek pengkomputeran yang semakin penting Struktur graf ialah abstraksi perhubungan kumpulan dan boleh menerangkan pelbagai objek dan perhubungan. Teras pengkomputeran graf ialah cara memodelkan data ke dalam struktur graf dan cara mengubah penyelesaian masalah kepada masalah pengkomputeran pada struktur graf Apabila masalah melibatkan analisis korelasi, pengkomputeran graf selalunya boleh membuat penyelesaian kepada masalah secara semula jadi dinyatakan sebagai satu siri operasi dan pengiraan pada struktur graf. Sebagai contoh, algoritma PageRank berdasarkan struktur graf pautan halaman web digunakan untuk mendapatkan berat halaman web, yang digunakan sebagai rujukan untuk kedudukan enjin carian Data tingkah laku pengguna struktur graf digunakan untuk mendapatkan tepat analisis keutamaan kumpulan dan hasil pengesyoran produk yang diperibadikan.

1. Apakah pengkomputeran graf?

Pengkomputeran graf ialah teknologi yang mengkaji perkara dalam dunia manusia dan hubungan antara benda, dan menerangkan, mencirikan, menganalisis dan mengiranya. Gambar di sini adalah "graf", bukan gambar "imej", yang berasal dari teori graf dalam matematik.

Graf ialah kaedah sambungan yang paling fleksibel, membenarkan entiti disambungkan tanpa sekatan. Pengkomputeran graf bukan sekadar teknologi, tetapi cara memahami dunia. Data graf boleh menerangkan dengan baik hubungan antara perkara, termasuk menerangkan arah dan sifat sambungan. Dari perspektif struktur data, graf ialah ungkapan asli perhubungan antara perkara. Pada tahap tertentu, pangkalan data hubungan harus dipanggil pangkalan data jadual, manakala pangkalan data graf harus dipanggil pangkalan data hubungan. Pengkomputeran graf yang ditakrifkan secara meluas merujuk kepada pelbagai pemprosesan berdasarkan data graf, termasuk pangkalan data graf.

Teknologi pengkomputeran graf menyelesaikan masalah kecekapan rendah dan kos tinggi bagi pertanyaan berkaitan dalam mod pengkomputeran tradisional Ia sepenuhnya menggambarkan perhubungan dalam domain masalah dan mempunyai keupayaan analisis data yang kaya, cekap dan tangkas , ciri-cirinya adalah sebagai berikut:

• Model data berdasarkan abstraksi graf
• Abstraksi selari model data graf
• Pengoptimuman sistem model graf

Untuk pengkomputeran graf , kos prestasi, mekanisme toleransi kesalahan dan kebolehskalaan semuanya sangat penting.

2. Melihat pengkomputeran graf daripada perkembangan sejarah

Pengkomputeran graf boleh dikesan kembali ke pangkalan data berstruktur pokok pada tahun 1960-an dan 1980-an, model dan teknologi berorientasikan graf. muncul seperti LDM (model data logik), dsb. Sehingga tahun 2007, pangkalan data graf komersial pertama Neo4j telah ditubuhkan, menandakan pengkomputeran graf memasuki peringkat pembangunan.

Permulaan sebenar penyelidikan pengkomputeran graf ialah pembangunan MapReduce, model pengkomputeran untuk pemprosesan selari data besar oleh Google pada tahun 2004. Pelancaran model ini membawa impak revolusi yang besar pada pemprosesan selari data besar. Selepas itu, pada tahun 2006, pasukan Apache Hadoop memperkenalkan Sistem Fail Teragih Hadoop (HDFS) dan rangka kerja Hadoop MapReduce baharu. Pada tahun 2009, Makmal AMP di Universiti California, Berkeley membangunkan sistem Spark.

Sejak 2010, hala tuju penyelidikan pengkomputeran graf seperti seni bina teragih berskala besar, sokongan berbilang modal dan reka bentuk bahasa pertanyaan graf telah menarik perhatian secara beransur-ansur. Google mencadangkan Pregel, sistem pengkomputeran graf teragih yang direka untuk ciri-ciri algoritma graf, mengikut model pengkomputeran BSP kemudian pasukan projek CMU Select Laboratory GraphLab mencadangkan model pengkomputeran GAS. . Walaupun pregel dan GraphLab adalah kedua-dua rangka kerja pemprosesan untuk pengiraan pembelajaran mesin yang kompleks dan digunakan untuk pengiraan lelaran, kaedah pelaksanaannya mengambil laluan yang berbeza: Pregel adalah berdasarkan mekanisme penghantaran mesej blok besar, dan GraphLab adalah berdasarkan Mekanisme perkongsian memori telah mempunyai kesan yang mendalam terhadap reka bentuk seterusnya sistem pengkomputeran graf lain.

Google mencadangkan konsep graf pengetahuan pada Mei 2012, yang merupakan cara baharu untuk menghubungkan maklumat Unit asasnya ialah "entiti-perhubungan-entiti" tiga kali ganda, dan entiti disambungkan melalui Perhubungan saling berkait untuk membentuk. struktur pengetahuan rangkaian. Teras penubuhan graf pengetahuan ialah mekanisme penaakulan pengetahuan komputer, dan pengkomputeran graf menyediakan sokongan teknikal asas yang penting untuknya.

Dengan pertumbuhan pesat volum data pada tahun 2015, pasaran aplikasi dibuka secara beransur-ansur, dan permintaan untuk skalabiliti dan kecekapan sistem pengkomputeran graf terus meningkat. Penyelidikan akademik dan industri dalam bidang pengkomputeran graf di China telah mula membangunkan sistem dan platform pengkomputeran grafnya sendiri secara beransur-ansur, seperti Gemini Universiti Tsinghua dan sebagainya.

Dalam beberapa tahun kebelakangan ini, dengan perkembangan teknologi kecerdasan buatan, rangkaian saraf graf juga telah menunjukkan bakat mereka dalam industri.

3. Melihat pengkomputeran graf daripada model rangka kerja

Rangka kerja pengkomputeran graf pada asasnya mengikut model pengkomputeran BSP (Sejajar Segerak Pukal). Ciri unik mekanisme penyegerakan pukal mod BSP terletak pada pengenalan konsep superstep. Proses pengiraan terdiri daripada satu siri supersteps global Setiap superstep merangkumi tiga peringkat: pengiraan selari (pengiraan tempatan), komunikasi global (komunikasi data bukan tempatan), dan penyegerakan pagar (menunggu kelakuan komunikasi tamat).

Mod BSP mempunyai ciri-ciri berikut:

membahagikan pengiraan kepada supersteps satu demi satu, dengan berkesan mengelakkan kebuntuan

memisahkan pemproses dan penghala, menekankan Ia memisahkan tugas pengkomputeran dan tugas komunikasi, dan penghala hanya melengkapkan penghantaran mesej dari titik ke titik dan tidak menyediakan fungsi seperti pemasangan, replikasi dan penyiaran, yang bukan sahaja menutupi topologi rangkaian interkoneksi tertentu, tetapi juga memudahkan protokol komunikasi

Gunakan mod segerak untuk melaksanakan penyegerakan global dan tahap berbutir kasar yang boleh dikawal dalam perkakasan untuk melaksanakan algoritma selari segerak yang digabungkan dengan ketat.

Sesetengah rangka kerja pengkomputeran graf perwakilan adalah seperti berikut:

• Neo4j-APOC: Berdasarkan pangkalan data graf, ia menyokong beberapa algoritma graf asas , versi yang diedarkan bukan sumber terbuka.
• Pregel: dicadangkan oleh Google pada tahun 2009, ia merupakan pengasas model pengkomputeran graf, dan banyak karya berikutnya telah dipengaruhi oleh ideanya. Bukan sumber terbuka.
• Giraph: Pelaksanaan sumber terbuka Facebook berdasarkan idea Pregel.
• Gemini: Universiti Tsinghua telah melaksanakan beberapa penambahbaikan berdasarkan idea Pregel, dengan prestasi cemerlang. Hanya demo percuma disediakan, versi komersial bukan sumber terbuka.
• KnightKing: Rangka kerja pengkomputeran graf yang direka khas untuk algoritma Walker walking, yang tidak universal.
• GraphX: Rangka kerja pengkomputeran graf yang dilaksanakan oleh Yayasan Apache berdasarkan Spark, dengan aktiviti komuniti yang tinggi.
• GraphLab (PowerGraph): perisian komersial, bukan sumber terbuka. Telah diperoleh oleh Apple.
• Plato: Pelaksanaan sumber terbuka C++ Tencent berdasarkan idea Gemini dan KnightKing Ia merupakan rangka kerja pengkomputeran graf berprestasi tinggi, berskala dan mudah dipasang.

4 Melihat pengiraan graf dari perspektif algoritma

Algoritma graf merujuk kepada kaedah mudah yang menggunakan bucu dan tepi tertentu untuk mencari jawapan, termasuk graf tidak terarah, graf terarah dan rangkaian Boleh menggunakan banyak algoritma graf yang biasa digunakan. Untuk data graf, algoritma traversal (depth/breadth first) adalah asas untuk algoritma lain. Algoritma graf biasa termasuk PageRank, laluan terpendek, cawangan bersambung, set bebas maksimum, pokok rentang minimum dan Penyebaran Kepercayaan Bayesian. Pohon rentang minimum graf selalunya mewakili kos terendah atau kos minimum dalam kehidupan, dan algoritma Prim dan algoritma Kruskal biasanya digunakan. Penemuan komuniti, laluan terpendek, pengisihan topologi dan laluan kritikal juga mempunyai algoritma yang sepadan.

Algoritma graf termasuk teknologi analisis data yang pelbagai seperti carian, pemadanan, pengelasan dan penilaian Ia boleh dibahagikan secara kasar kepada dua kategori daripada dimensi struktur algoritma: algoritma berpusatkan traversal dan algoritma berpusat pengiraan. Algoritma traversal-centric perlu merentasi graf dari bucu tertentu dengan cara tertentu, dan terdapat sejumlah besar akses rawak. Algoritma berpusatkan pengiraan memerlukan sejumlah besar operasi dalam kitaran lelaran, dan mempunyai lokaliti data yang agak baik.

5 Pengkomputeran graf dari perspektif seni bina komputer

Pengkomputeran graf secara amnya adalah pengiraan dipacu data, dan struktur pengkomputeran tidak boleh diramalkan dengan tepat sebelum ini. berjalan. , tidak ada corak yang jelas dalam bentuk, dan sukar untuk membahagikannya dengan cekap dan berkualiti tinggi. Mekanisme caching sedia ada selalunya hanya boleh mempercepatkan capaian data dengan lokaliti yang baik, dan akses kepada sejumlah besar data selalunya akan meletakkan pemproses dalam keadaan menunggu I/O.

Beban kerja pengkomputeran graf adalah kompleks dan tidak ada satu beban kerja pengkomputeran graf yang paling mewakili. Tepi yang menghubungkan bucu hanyalah subset kecil daripada kemungkinan sambungan yang tidak terkira banyaknya dan sangat tidak teratur. Dalam proses pengkomputeran graf, lokaliti spatiotemporal membaca dan menulis sukar untuk difahami, dan penghunian lebar jalur sukar untuk diramalkan.

Kebanyakan algoritma mungkin menduduki kurang daripada 50% lebar jalur memori. Apakah yang mengehadkan penggunaan lebar jalur memori? Pemproses perlu mendapatkan arahan, terdapat ruang antara tetingkap arahan, dan operan daftar perlu menunggu sehingga operan tersedia, dan kebergantungan yang berkaitan tidak akan dikeluarkan. Disebabkan oleh kadar pukulan arahan yang tinggi, keselarian pada tahap memori mungkin dikurangkan, menjadikannya sukar untuk menggunakan lebar jalur memori platform sepenuhnya. Nisbah penggunaan data cache yang rendah bermakna sukar untuk aplikasi mendapat manfaat daripada lokaliti spatial dan strategi prefetching data akan menjadi tidak berkesan. Prafetch data secara amnya membantu meningkatkan prestasi, tetapi ia juga menjana sejumlah besar operasi prefetch yang tidak berguna. Untuk aplikasi dengan lebar jalur memori atau kapasiti cache yang terhad, pengambilan data mungkin menyebabkan pembaziran sumber tertentu. Dalam kes pengkomputeran berbilang benang, mencetuskan akses memori jauh dengan kependaman yang lebih tinggi juga akan mengimbangi faedah berbilang benang.

Apakah jenis teras pemproses yang diperlukan untuk pengkomputeran graf? Secara amnya, seni bina dengan banyak teras pengkomputeran kecil dan bilangan benang yang tinggi digunakan, yang sesuai untuk memproses pengiraan graf besar yang pemproses berbilang teras tradisional tidak mahir. Dalam pengiraan serentak berbilang graf, terdapat dua strategi: peruntukan dikongsi dan peruntukan eksklusif. Strategi peruntukan dikongsi bermakna setiap permintaan m diproses secara selari menggunakan n teras logik, dan OS menguruskan penukaran permintaan yang berbeza pada teras logik. Strategi peruntukan eksklusif merujuk kepada memperuntukkan n/m teras logik kepada setiap permintaan supaya teras logik tidak perlu bertukar antara tugas. Strategi peruntukan eksklusif lebih sesuai untuk pengiraan graf serentak biasanya boleh mengurangkan masa berjalan keseluruhan untuk permintaan serentak yang sama. Pertikaian rendah cache susunan semula mungkin menjadi sebab mengapa strategi eksklusif lebih baik daripada strategi kongsi dalam senario pengkomputeran graf serentak.

Mengenai penggunaan kuasa yang disebabkan oleh pengiraan graf, perubahan beban membawa kepada turun naik kuasa sistem, dan situasi berperingkat puncak dan lembah akan berlaku. Meningkatkan tugas serentak akan mengubah nisbah puncak ke palung dan meningkatkan penggunaan kuasa. Secara umumnya, dari segi penggunaan kuasa CPU, algoritma berpusatkan pengiraan menggunakan sejumlah besar tenaga setiap arahan secara purata, manakala algoritma berpusatkan traversal mempunyai kesan sebaliknya dari segi penggunaan kuasa memori, algoritma berpusat pengiraan menggunakan lebih sedikit memori. Purata penggunaan tenaga adalah kecil, dan sebaliknya berlaku untuk algoritma traversal-centric.

Kebanyakan aplikasi berasaskan pengkomputeran graf mempunyai kekangan memori, tetapi terdapat juga penggunaan memori yang tidak mencukupi disebabkan oleh pengehadan komponen teras. Urutan aktif yang mencukupi mencipta akses serentak, yang boleh meningkatkan penggunaan. Lebih banyak utas diperlukan, tetapi disebabkan oleh ketidakseimbangan antara utas, mereka mungkin tidak digunakan dengan cekap Strategi selari yang lebih berskala perlu disediakan untuk mengoptimumkan penggunaan memori lebar jalur tinggi pemproses berbilang teras. Penggunaan kuasa dan tingkah laku penggunaan tenaga adalah berbeza daripada perspektif arahan dan perspektif pengiraan puncak, memerlukan kaedah pengurusan kuasa yang tepat, dan pelarasan yang meluas mungkin tidak berkesan.

6. Lihat pengiraan graf daripada sistem

Berdasarkan senario penggunaan sistem pengkomputeran graf berskala besar dan perbezaan dalam seni bina platform pengkomputeran, ia boleh dibahagikan kepada graf memori mesin tunggal sistem pengkomputeran dan sistem graf memori luaran mesin tunggal Sistem pengkomputeran, sistem pengkomputeran graf memori teragih dan sistem pengkomputeran graf memori luaran.

Sistem pemprosesan graf memori mesin tunggal ialah sistem pemprosesan graf yang berjalan dalam persekitaran mesin tunggal dan menampan semua data graf ke dalam memori. Sistem pemprosesan graf memori luaran yang berdiri sendiri ialah algoritma graf yang cekap di mana sistem pemprosesan graf berjalan dalam persekitaran yang berdiri sendiri dan secara berterusan berinteraksi dengan memori dan cakera melalui pengiraan data graf. Sistem ingatan teragih ialah sistem pemprosesan graf yang berjalan dalam persekitaran kluster teragih, dan semua data graf dimuatkan ke dalam memori. Sistem pengkomputeran graf memori luaran yang diedarkan mengembangkan sistem luar teras mesin tunggal ke dalam kelompok dan boleh memproses graf dengan tepi pada susunan trilion.

7 Melihat pengkomputeran graf daripada AI

Rangkaian saraf graf (GNN) yang dihasilkan oleh gabungan AI dan pengkomputeran graf kini merupakan bidang yang pesat membangun dan penting. Bagaimana untuk menggabungkan data hubungan antara pelbagai entiti dengan rangkaian saraf? Rangkaian saraf graf menggunakan pembelajaran perwakilan Melalui struktur graf, setiap nod atau tepi pertama kali diwakili oleh vektor, dan kemudian diproses menggunakan rangkaian saraf. Ini memperluaskan skop penggunaan rangkaian saraf dan memperkenalkan hubungan antara entiti ke dalam pemprosesan AI.

Rangkaian saraf graf boleh dilihat sebagai proses pembelajaran ciri graf, seperti ciri perwakilan nod atau ciri perwakilan tahap graf Secara umumnya, ia mengambil sifat dan struktur graf sebagai input dan output a set nod yang dikemas kini. Secara amnya proses ini juga dipanggil operasi penapisan graf. Penapisan graf mengemas kini ciri nod tetapi tidak mengubah struktur graf. Pembangunan rangkaian saraf graf dibangunkan daripada motivasi teori yang berbeza Sebagai contoh, jika GNN dianggap sebagai generalisasi lilitan jarak bukan Euclidean, ia dibangunkan berdasarkan isyarat graf; algoritma lulus yang dicadangkan melalui analogi kepada penaakulan kebarangkalian dalam model grafik.

Sama ada kaedah spektrum atau pemikiran berasaskan ruang, rangkaian saraf graf akhirnya boleh disatukan menjadi rangka kerja berdasarkan penghantaran mesej. Idea asas rangka kerja penghantaran mesej GNN ialah pada setiap lelaran, setiap nod mengagregatkan maklumat nod jirannya. Apabila bilangan lelaran bertambah, setiap nod mengandungi julat maklumat yang lebih besar pada graf. Contohnya, selepas k lelaran, nod pusat boleh mendapatkan maklumat jiran k-hopnya. Idea utama ialah menjana perwakilan nod berdasarkan struktur graf dan maklumat ciri yang diketahui. GNN menggunakan maklumat ciri struktur dan nod pada graf untuk menjana perwakilan benam dalam, manakala kaedah benam graf tradisional hanya menggunakan maklumat struktur graf untuk menjana benam lapisan melalui carian jadual.

7.1 GNN VS MLP/CNN/RNN

Jiran nod dalam data graf mempunyai dua ciri, satu ialah nombor tidak pasti, dan satu lagi ialah susunan tidak pasti, jadi MLP/ CNN/RNN tidak boleh mengendalikan data bukan Euclidean tersebut secara langsung dan hanya boleh dimodelkan dengan GNN. Malah, GNN boleh dianggap sebagai model yang lebih umum Sebagai contoh, RNN adalah bersamaan dengan GNN pada graf linear, dan Transformer adalah bersamaan dengan GNN pada graf lengkap.

7.2 GNN VS Graph Embedding

Banyak kaedah Graph Embedding telah muncul sebelum GNN dan digunakan secara meluas dalam fasa ingat semula vektor bagi perkhidmatan carian , daripada Item2Vec asal kepada Node2Vec berdasarkan penambahbaikan kehomogenan dan struktur pengimbangan, kepada MetaPath2Vec berdasarkan penambahbaikan kepelbagaian graf, dan pengenalan data atribut untuk mengurangkan keterlaluan data tingkah laku, kaedah ini mempunyai semua Ikut Paradigma Langkau-Gram.

Berbanding dengan kaedah ini, GNN boleh dilatih hujung ke hujung dalam kombinasi dengan tugas sasaran, manakala Pembenaman Graf lebih seperti latihan pra, dan Pembenaman yang dipelajarinya tidak semestinya berkaitan dengan tugas sasaran , terutamanya dalam saiz sampel Dalam senario perniagaan yang besar, Pembenaman yang diperolehi melalui latihan hujung ke hujung adalah lebih berkesan daripada Pembenaman yang diperoleh melalui latihan pra.

Struktur rangkaian hierarki GNN mudah digabungkan dengan teknologi pembelajaran mendalam yang lain, seperti GCN+Attentinotallow=GAT. GNN boleh digunakan untuk tugas Induktif, iaitu, apabila struktur graf berubah dan beberapa nod baharu ditambah, jika ia merupakan kaedah Pembenaman Graf, model perlu dilatih semula dan GNN boleh menggunakan kaedah yang serupa dengan Nod GraphSage -Persampelan Bijak, menggunakan model yang sudah terlatih secara langsung menyimpulkan nod baharu, dan pelbagai ciri boleh digunakan dalam proses penghantaran mesej.

7.3 GNN VS Feature Concat & Penapisan Kolaboratif & Kehilangan Kedekatan

Ciri Concat bermaksud penyambungan ciri bersama-sama dan kemudian mempelajari maklumat perkaitan atribut urutan pertama melalui persimpangan ciri . Penapisan Kolaboratif juga boleh mempelajari maklumat korelasi tingkah laku peringkat pertama melalui gelagat sejarah pengguna. Kehilangan Kehampiran bermakna menambah istilah biasa pada fungsi kehilangan untuk menjadikan nod bersebelahan lebih serupa, tetapi di satu pihak ia adalah cara yang tersirat, sebaliknya jika anda ingin memastikan bahawa hubungan persamaan peringkat tinggi dipelajari, anda perlu menambah lebih kompleks Istilah biasa pesanan K juga merupakan salah satu titik permulaan apabila GCN dicadangkan. Berbanding dengan tiga kaedah ini, GNN secara eksplisit boleh mempelajari maklumat korelasi tertib tinggi dengan menyusun berbilang lapisan.

Terdapat syarat utama yang mesti dipenuhi dalam reka bentuk rangkaian neural graf, iaitu invarian pilih atur atau kesetaraan pilih atur, iaitu fungsi yang direka tidak dipengaruhi oleh susunan nod atau susunan input apabila memproses data graf Transform domain berada dalam susunan yang sama.

8. Ringkasan

Graf ialah kaedah sambungan yang paling fleksibel, membenarkan entiti disambungkan tanpa sekatan. Pengkomputeran graf ialah bidang yang mengkaji cara mengira, menyimpan dan mengurus data graf dengan cekap dalam jumlah data yang besar. Ia boleh digunakan pada pelbagai senario perniagaan, seperti pengurusan risiko pasaran modal, penyelidikan sains hayat, penyampaian penjagaan kesihatan, pemantauan. dan bertindak balas terhadap kemalangan jalan raya , pengurusan infrastruktur pintar, dsb. Pengkomputeran graf yang memproses data berskala besar dengan cekap boleh menggalakkan pembangunan bidang aplikasi yang muncul seperti analisis rangkaian sosial, analisis web semantik, analisis rangkaian maklumat biologi dan pemprosesan bahasa semula jadi.

[Rujukan]

"Pengkomputeran Grafik Kepintaran Buatan", Institut Penyelidikan Kepintaran Buatan Universiti Tsinghua, Institut Penyelidikan Kepintaran Buatan Zhiyuan Beijing, Pusat Penyelidikan Bersama Kejuruteraan Tsinghua untuk Kepintaran Pengetahuan, 2019- 2

​​https://www.php.cn/link/c9e5c2b59d98488fe1070e744041ea0e​​

​​https://www.php.cn / pautan/d40d35b3063c11244fbf38e9b55074be​​

​​https://www.php.cn/link/315f006f691ef2e689125614ea>​ https : //www.php.cn/link/51d1cd3a02276948f566e6ea0a7d78cb​

​

Atas ialah kandungan terperinci Belajar dan berfikir tentang pengkomputeran graf. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!