Michael Bronstein melukis daripada topologi algebra dan mencadangkan struktur pengkomputeran rangkaian saraf graf baharu!

Artikel ini dikarang bersama oleh Cristian Bodnar dan Fabrizio Frasca, dan diterbitkan oleh C. Bodnar, F. Frasca dan lain-lain pada 2021 ICML "Weisfeiler and Lehman Go Topological: Information Transfer Simple Network" dan 2021 NeurIPS " Kertas Weisfeiler dan Lehman Go Cellular: CW Network" digunakan sebagai rujukan.

Artikel ini hanyalah sebahagian daripada perbincangan siri rangkaian saraf graf dari perspektif geometri pembezaan dan topologi algebra.

Graf boleh digunakan untuk memodelkan apa sahaja daripada rangkaian komputer kepada interaksi zarah di Large Hadron Collider. Graf ada di mana-mana kerana sifat diskret dan gabungannya, yang membolehkannya menyatakan hubungan abstrak sambil mudah dikira. Salah satu sebab popularitinya ialah graf mengasingkan geometri, iaitu di mana nod berada dalam ruang atau cara tepi melengkung, hanya meninggalkan gambaran bagaimana nod disambungkan.

Teori graf berasal daripada pemerhatian Leonhard Euler dalam buku 1741 "Geometria situs", di mana beliau menunjukkan Masalah Tujuh Jambatan Königsberg yang terkenal Tiada penyelesaian kepada masalah itu.

Nota ilustrasi: Masalah tujuh jambatan memerlukan mencari laluan pejalan kaki bulat di Königsberg tanpa melintasi jambatan itu beberapa kali. Seperti yang dikatakan oleh Euler, bentuk sebenar bandar Königsberg tidak penting, yang penting ialah bagaimana bahagian tanah yang berbeza (nod graf) disambungkan antara satu sama lain (tepi). Euler menunjukkan bahawa kitaran sedemikian wujud jika dan hanya jika semua nod mempunyai darjah genap. Selain itu, hanya lima daripada jambatan asal yang bertahan hingga ke zaman moden. Sumber: Wikipedia

Menariknya, penemuan Euler bukan sahaja menandakan permulaan teori graf, tetapi juga sering dianggap sebagai kelahiran topologi. Seperti graf, ahli topologi berminat dengan sifat ruang yang bebas daripada bentuk atau geometri khususnya.

Ungkapan moden idea-idea ini muncul dalam "Situs Analisis" tahun 1895, sebuah kertas mani oleh Henri Poincaré, yang kerjanya menyala perolakan Penerangan gabungan bentuk adalah menarik, dan invarian topologi boleh lebih mudah ditemui dan dikira daripada manifold ini.

Kapsyen: Leonhard Euler (1707-1783) dan Henri Poincaré (1854-1912)

Penerangan gabungan ini hari ini dikenali sebagai kompleks selular dan boleh dianggap sebagai generalisasi graf berdimensi tinggi.

Tidak seperti graf yang dibentuk oleh nod dan tepi, kompleks sel juga boleh mengandungi struktur atau "sel" berdimensi lebih tinggi: bucu ialah 0-sel, tepi ialah 1-sel, permukaan 2D ialah 2 -sel dll. Untuk membina kompleks sel, kita boleh melapisinya dengan melekatkan sempadan satu sel ke sel berdimensi rendah yang lain.

Dalam kes khas, apabila sel terdiri daripada simpleks (seperti tepi, segi tiga, tetrahedron, dll.), ruang ini juga dipanggil kompleks simpleks.

Rajah Nota: Graf boleh dilihat sebagai satu set bucu yang kita pasangkan tepi (1-sel). Begitu juga, kompleks sel tunggal dan kompleks sel boleh dilihat sebagai graf di mana kita menyambungkan 2-sel (ditunjukkan dalam warna biru), 3-sel (ditunjukkan dalam warna hijau), dsb.

1 Topologi dalam Pembelajaran Mesin dan Sains Data

Kami percaya bahawa orang ramai tidak perlu menunggu 400 tahun untuk topologi menjadi alat praktikal.

Struktur topologi seperti kompleks cetek telah digunakan dalam pembelajaran mesin dan sains data di bawah payung analisis data topologi (TDA), yang muncul pada tahun 1990-an, cuba menganalisis "bentuk data" dengan cara yang tidak sensitif metrik dan teguh kepada hingar.

Akar umbi TDA boleh dikesan kembali kepada kerja salah seorang ahli topologi paling prolifik, Leopold Vietnam Oris, pada akhir 1920-an. Walau bagaimanapun, teknologi ini terpaksa menunggu sehingga kemunculan pengkomputeran moden sebelum ia boleh digunakan secara besar-besaran.

Legenda: Diberi awan titik, persilangan antara sfera tertutup jejari tetap di sekeliling setiap titik menghasilkan kompleks ringkas. Dengan meningkatkan jejari sfera secara beransur-ansur, kita boleh mendapatkan urutan bersarang bagi kompleks ringkas. Sumber imej: Bastian Rieck.

Kuda kerja TDA ialah Persistent Homology (PH), kaedah untuk mengekstrak ciri topologi daripada awan titik. Memandangkan set data titik, PH mencipta jujukan bersarang bagi nombor kompleks mudah, di mana setiap nombor kompleks sepadan dengan skala tertentu awan titik asas di bawah analisis. Ia kemudian menjejaki pelbagai ciri topologi (cth., komponen yang disambungkan, gelung atau lubang) yang muncul dan hilang apabila skala secara beransur-ansur meningkat dan satu peralihan dari satu kompleks dalam urutan ke seterusnya.

Dalam era pembelajaran mendalam, homologi yang berterusan mempunyai "kehidupan kedua" kerana ia menunjukkan bahawa seseorang boleh merambat melaluinya, membolehkan Peranti TDA yang telah ditubuhkan disepadukan ke dalam kerangka pembelajaran mendalam.

Siri kerja baru-baru ini mencadangkan penggunaan penyederhanaan dan kompleks sel yang berbeza dalam pembelajaran mendalam geometri, sebagai ruang topologi asas yang lebih kaya untuk menyokong data dan pengiraan yang dilakukan.

Beberapa karya terawal untuk mengeksploitasi perspektif ini mencadangkan model konvolusi dan kaedah berjalan rawak yang beroperasi pada kompleks yang dipermudahkan. Seperti dalam artikel ini, model konvolusi boleh difahami sebagai contoh mudah dan konkrit pemindahan maklumat pada kompleks sel.

Memandangkan pengiraan didorong oleh struktur topologi ruang ini (iaitu, struktur kejiranan), kami memanggil kaedah pemindahan maklumat topologi ini. Dalam rangka kerja ini, unit bersebelahan, mungkin berbeza dimensi, bertukar maklumat, seperti yang ditunjukkan dalam rajah di bawah.

Ilustrasi: Gambarajah skematik pemindahan maklumat topologi. Anak panah biru menerangkan penyebaran maklumat "mendatar" antara sel bersebelahan di lapisan atas, iaitu sel pada sempadan sel berdimensi tinggi yang sama. Anak panah merah menggambarkan penyebaran maklumat "menegak", di mana sel menerima maklumat daripada sel berdimensi rendah di sempadannya. Pengiraan ini boleh ditafsirkan sebagai bentuk ensembel (boleh dibezakan) dengan meringkaskan maklumat daripada sel sempadan kepada perwakilan yang lebih kasar.

Beyond Graphs in GNNs​

Walaupun kompleks selular menyediakan struktur yang kaya, kita tidak boleh mengabaikan bahawa graf adalah yang paling biasa dalam objek topologi pembelajaran mesin, dan beberapa set data mengatasi mereka. Walau bagaimanapun, seseorang masih boleh mengeksploitasi ruang topologi yang menarik ini dengan mengubah graf input.

Kami memanggil menukar graf kepada ruang topologi dimensi tinggi "mengangkat", untuk menyerupai konsep nama yang sama dalam teori kategori. Ia adalah transformasi yang menambahkan sel berdimensi tinggi pada graf input dengan mengikut peraturan tertentu. Contohnya, graf boleh dinaikkan kepada kompleks sel dengan melampirkan sel berdimensi lebih tinggi pada setiap cenuram atau kitaran graf. Dengan melakukan ini, graf digantikan dengan ruang berbeza yang mempunyai lebih banyak struktur dan boleh menyediakan GNN dengan struktur pengiraan yang lebih baik daripada graf asal. Di bawah, kita membincangkan kelebihan khusus pendekatan ini.

Rajah Nota: Dengan melekatkan sempadan cakera tertutup dua dimensi pada gelung teraruh dalam rajah, ia boleh diperolehi daripada rajah Bina kompleks sel berdimensi tinggi.

Ciri dan struktur tertib tinggi

GNN biasanya menggunakan pandangan berpusat nod, dan data yang berada di tepi hanya dianggap sebagai maklumat tambahan untuk meningkatkan komunikasi antara bucu. Dalam pemindahan maklumat topologi, semua unit adalah warganegara kelas pertama. Tanpa mengira dimensi mereka, mereka diberikan perwakilan khusus, yang dibangunkan dengan bertukar maklumat dengan unit jiran. Ini menyediakan resipi untuk memodelkan struktur tertib tinggi tertentu dan interaksi di antara mereka secara eksplisit. Khususnya, ia menyediakan kaedah berprinsip untuk mengembangkan ciri tepi (iaitu 1 unit) graf input, yang merupakan masalah yang tidak dipertimbangkan oleh kelas model GNN yang besar.

Interaksi Aras Tinggi

Rajah mengikut takrifan perduaan ("berpasangan") dan tidak boleh mewakili perhubungan dan interaksi yang melibatkan lebih daripada dua objek . Ini boleh menjadi masalah apabila memodelkan sistem kompleks yang dicirikan oleh interaksi peringkat tinggi: contohnya, tiga bahan tindak balas dalam tindak balas kimia mungkin berinteraksi secara serentak. Dalam kompleks sel, keadaan ini boleh dikodkan dengan menyambungkan bahan tindak balas antara dua sel (iaitu, segitiga "diisi"). Oleh itu, aliran pengiraan model disesuaikan dengan kehadiran interaksi peringkat tinggi.

Ilustrasi: Ujian Sel Weisfeiler-Lehman (CWL), memanjangkan ujian WL klasik kepada kumpulan sel, setiap langkah algoritma Kedua-duanya cincang dengan sempurna warna sel bersebelahan (yang mungkin mempunyai dimensi berbeza).

Keekspresifan

Kuasa ekspresif maklumat yang melepasi GNN dihadkan oleh ujian isomorfisme graf Weisfeiler-Leman (WL), dan diketahui bahawa WL tidak boleh mengesan beberapa graf Substruktur, seperti segi tiga atau kitaran, tidak dapat dibezakan daripada graf bukan isomorfik yang sangat mudah.

Mengikut kertas sebelum ini (alamat kertas: https://arxiv.org/abs/2103.03212; https://arxiv.org/ abs /2106.12575), Versi selular ujian WL (CWL) boleh digunakan untuk menguji isomorfisme kompleks selular. Apabila ujian baharu ini dipadankan dengan prosedur mengangkat graf yang diterangkan di atas, didapati ia boleh membezakan kelas graf yang lebih besar daripada ujian WL. Oleh itu, dalam keadaan tertentu, proses pemindahan maklumat topologi mewarisi kelebihan ujian ini dan meningkatkan keupayaan ekspresi berbanding dengan GNN standard. Tidak mencukupi, terlalu licin dan kesesakan

GNN untuk pemindahan maklumat memerlukan n lapisan untuk membolehkan nod dan lompatan terpisah untuk berkomunikasi. Apabila hanya beberapa lapisan digunakan supaya nod yang berjauhan tidak dapat bertukar

maklumat, fenomena ini dipanggil underreach.

Sebaliknya, menggunakan terlalu banyak lapisan boleh menyebabkan pelicinan berlebihan dan maklumat boleh hilang dalam kesesakan struktur graf.

Kompleks sel boleh mengurangkan masalah ini kerana struktur kejiranan yang lebih kaya yang disebabkan oleh sel berdimensi tinggi mewujudkan pintasan antara nod yang mungkin berjauhan. Oleh itu, maklumat hanya perlu mengandungi beberapa langkah pengiraan untuk disebarkan agar sah.

Kapsyen: GNN memerlukan banyak lapisan untuk membolehkan nod yang berjauhan berkomunikasi (kiri). Sel berdimensi tinggi menukar topologi asas ruang dengan mencipta pintasan (kanan). Ini membolehkan nod jauh bertukar maklumat dalam beberapa langkah pemesejan. Pemodelan hierarki

Topologi

MaklumatPengiraan yang dilakukan dengan menghantar maklumat adalah berhierarki dan maklumat mengalir dari unit berdimensi rendah ke tinggi -unit dimensi unit dimensi dan belakang, boleh dianggap sebagai satu bentuk pengumpulan "menegak" (dan boleh dibezakan), dan bukannya pengumpulan "mendatar" dalam rangkaian neural graf standard. Ini mengekalkan bias induktif bagi kawasan graf "mampat" tanpa mengabaikan maklumat terperinci graf input yang akan membahayakan prestasi berasaskan pengumpulan GNN.

Kapsyen: Pemindahan maklumat topologi membolehkan maklumat wujud secara berlapis antara unit dimensi berbeza

Penjajaran domain

Aplikasi tertentu adalah konsisten secara semula jadi dengan struktur kompleks selular, contohnya, atom, ikatan, dan cincin kimia molekul boleh diwakili sebagai 0-sel, 1-sel, dan 2-sel, sambungan langsung antara struktur fizikal molekul. dan perwakilan kompleks sel Surat-menyurat membenarkan pemindahan maklumat topologi memanfaatkan sifat di atas, dan perwakilan ini juga menunjukkan hasil terkini yang dicapai oleh pemindahan maklumat topologi dalam tugas ramalan sifat molekul.

Aplikasi lain yang mempamerkan penjajaran yang baik mungkin termasuk manifold diskret (grid) dalam aplikasi grafik komputer, rangkaian sosial (cliques amat penting) atau graf spatial seperti Peta Google (Blok antara jalan boleh secara semula jadi diwakili sebagai sel "kubik").

Kapsyen: Kafein dimodelkan sebagai kompleks selular dua dimensi

2 Gabungan topologi dan geometri pembezaan

Dalam pemindahan maklumat topologi, banyak sambungan menarik dengan topologi algebra dan geometri pembezaan dikekalkan, membenarkan penggunaan alat Matematik setakat ini untuk graf dan pembelajaran mendalam geometri masih kurang diterokai sehingga kini.

Algebra lubang dan kesetaraan arah

Dalam topologi algebra, adalah perkara biasa untuk menggunakan kompleks ringkas terarah, di mana terdapat "orientasi" arbitrari untuk setiap simpleks, mis pilih nod sumber dan nod sasaran dalam setiap tepi, dan untuk setiap segi tiga kita memilih susunan untuk melintasi nodnya. Setelah arahan dipilih, pengendali algebra yang menarik boleh dilakukan pada bentuk kompleks, seperti mengira sempadan simpleks tertentu melalui "pengendali sempadan". Operasi algebra ini juga boleh digunakan untuk mencari "lubang" dalam kompleks ringkas - kawasan yang tidak mempunyai sempadan tetapi tidak berada di sempadan sesuatu yang lain. Di sebalik tabir, homologi berterusan bergantung pada pengiraan ini untuk mengesan ciri topologi.

Legenda: Operator sempadan yang digunakan pada 2-simplex menghasilkan segitiga. Menggunakan pengendali pada segi tiga sekali lagi, hasilnya adalah sifar, kerana segitiga adalah kitaran ia tidak mempunyai sempadan.

Pemindahan maklumat topologi boleh dilihat sebagai generalisasi (tidak linear) bagi pengendali algebra (seperti pengendali sempadan). Oleh itu, adalah perlu bahawa pemindahan maklumat topologi berkelakuan serupa: kami mahu output setiap lapisan bertindak balas "secara seragam" kepada perubahan dalam orientasi kompleks input. Dalam erti kata lain, kami mahu lapisan kami setara secara arah. Dalam kerja kami, kami mengkaji cara pemindahan maklumat

topologi memenuhi sifat ini dengan memilih fungsi pemindahan maklumat bukan linear dan maklumat topologi, serta dalam tetapan konvolusi tulen Ini telah dikaji. Membezakan ruang topologi Salah satu invarian topologi terawal yang diketahui, ciri Euler, pada asalnya digunakan untuk pengelasan pepejal Platonik, yang boleh kita takrifkan sebagai setiap jumlah seli bagi bilangan sel dalam dimensi. Yang menghairankan, jika dua kompleks selular adalah homeomorfik, jumlah ini akan konsisten walaupun ia adalah pendiskretan berbeza bagi ruang yang sama.

Menariknya, operasi pembacaan model pemindahan maklumat topologi memudahkan untuk mengira invarian topologi kerana ia menggunakan subsumption pada setiap unit dimensi Pemulihan invarian.

Oleh itu, model jenis ini secara struktur boleh membezakan ruang bukan isomorfik tertentu (iaitu, mempunyai ciri Euler yang berbeza). Dari perspektif pengiraan, ini boleh dilihat sebagai generalisasi ujian WL, di mana kita bukan sahaja berminat untuk menentukan sama ada dua kompleks selular adalah sama, tetapi juga sama ada ia isomorfik antara satu sama lain.

Teori Hodge Diskret

Teori Hodge Diskret memberikan penjelasan yang lebih geometri untuk sifat topologi kompleks selular. Apabila tanda ciri-ciri yang dikaitkan dengan sel-k bergantung pada orientasi sel-k, ciri-ciri ini boleh dilihat secara matematik sebagai versi diskret bagi bentuk-k pembezaan dalam geometri pembezaan (iaitu, unsur isipadu k-dimensi yang boleh bersepadu). Pengendali yang dipanggil Hoch Laplacian menyamaratakan Laplacian grafik dan beroperasi pada bentuk pembezaan ini. Dapat dibuktikan bahawa PDE resapan berdasarkan operator Laplacian ini akan menumpu dalam had kepada isyarat yang berkaitan dengan lubang komposit.

Legenda: Persamaan pembezaan separa resapan berdasarkan pengendali Hoch Laplace, menumpu kepada bentuk pembezaan awal Had unjuran pada isirong Laplacian. Imej ini menunjukkan bagaimana vektor eigen sifar Hoch Laplacian mengambil nilai tinggi di sekeliling lubang dalam kompleks.

Model rangkaian neural ringkas pertama sebenarnya berdasarkan model konvolusi Hoch Laplacian, yang seterusnya diilhamkan oleh pemprosesan isyarat topologi. Baru-baru ini, versi model konvolusi berdasarkan operator ini digunakan untuk menyelesaikan masalah NP-hard dalam topologi algebra pengiraan.

3 Pemikiran Akhir

Adakah ini hanya carta yang menyamar?

Makalah terkini berpendapat bahawa, antara lain, kaedah pemindahan maklumat topologi tidak lebih daripada GNN yang mengendalikan pemindahan maklumat pada graf yang diubah suai mengekodkan struktur kompleks selular. Ini benar untuk model konvolusi, di mana pengiraan pemindahan maklumat melibatkan pasangan sel.

Walau bagaimanapun, dalam bentuk yang paling umum, fungsi maklumat maklumat membenarkan sel berdimensi tinggi memodulasi maklumat yang dihantar antara sel berdimensi rendah pada sempadannya 🎜>MesejMaklumat. Secara umum, maklumat boleh dihantar melalui maklumat biasa pada graf, kerana satu tepi menghubungkan tepat dua nod dan 2 sel boleh menyambungkan sebarang bilangan tepi.

Dalam kedua-dua kes, pengiraan didorong oleh topologi ruang asas yang dilampirkan data. Kami percaya bahawa faedah menggunakan perspektif topologi ini mengenai pemindahan maklumat melangkaui pertimbangan pengiraan semata-mata. Sebagai tambahan kepada hubungan matematik yang berharga, ia membuka wacana penyelidikan kepada disiplin matematik dan pengiraan lain, memudahkan persenyawaan silang positif di kalangan komuniti kita yang sering terlalu monoton.

Apakah langkah seterusnya untuk pemindahan maklumat topologi?

Kami meramalkan dua hala tuju masa depan utama untuk kaedah pemindahan maklumat topologi:

Pertama, banyak seni bina dibangunkan dalam GNN selama ini ( Seperti perhatian mekanisme) boleh diterima pakai dalam ruang topologi baharu ini sambil mengeksploitasi ciri khusus mereka.

Kedua, lebih banyak objek dan alatan matematik daripada bidang topologi algebra (termasuk struktur seperti takal sarang lebah) akan memuaskan walaupun penyelidik ML yang paling bijak matematik, yang mungkin juga terdengar asing bagi mereka) akan diterima pakai oleh graf dan komuniti pembelajaran mendalam geometri.

Kaedah ini bukan sahaja dapat memberikan jawapan kepada masalah lama, tetapi juga membantu menyelesaikan masalah baharu seperti yang dikatakan oleh Robert Ghrist: "cabaran novel memerlukan matematik baru" (cabaran baharu memerlukan cabaran baharu matematik).

Atas ialah kandungan terperinci Michael Bronstein melukis daripada topologi algebra dan mencadangkan struktur pengkomputeran rangkaian saraf graf baharu!. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!