Rangkaian saraf berbilang graf bersepadu

1. GNN dari perspektif bersatu

1. Paradigma penyebaran GNN sedia ada

Bagaimana GNN merambat di ruang udara? Seperti yang ditunjukkan dalam rajah di bawah, ambil nod A sebagai contoh:

Mula-mula ia akan mengenal pasti jirannya Maklumat nod N (A) diagregatkan menjadi : >N(A)(1) digabungkan, dan kemudian melalui fungsi transformasi (iaitu Trans(· ) dalam formula), perwakilan tahap seterusnya bagi A diperoleh hN(A)( 2). Ini adalah paradigma penyebaran GCN yang paling asas. Selain itu, terdapat proses pembiakan terpisah:

Dua ini Apa bezanya?

Dalam paradigma perambatan decoupled, pengekstrak ciri, iaitu fungsi transformasi, mula-mula digunakan untuk mengekstrak ciri awal, dan kemudian ciri yang diekstrak dimasukkan ke dalam fungsi pengagregatan untuk pengagregatan Anda boleh melihatnya Kaedah ini memisahkan pengekstrakan ciri dan pengagregatan, iaitu, penyahgandingan dicapai. Kelebihan ini ialah:

Anda boleh secara bebas mereka bentuk fungsi transformasi sebelumnya dan menggunakan mana-mana model.

Banyak lapisan boleh ditambah semasa pengagregatan untuk mendapatkan maklumat sambungan yang lebih jauh, tetapi kami tidak akan menghadapi risiko penparameteran berlebihan, kerana dalam fungsi pengagregatan Terdapat tiada parameter untuk dioptimumkan.

Di atas ialah dua paradigma utama, dan output pembenaman nod boleh menggunakan lapisan terakhir rangkaian atau baki bahagian tengah lapisan .

Melalui semakan di atas kita dapat melihat bahawa terdapat dua sumber maklumat asas dalam GNN:

• Struktur topologi rangkaian: Secara amnya, atribut maklumat pelbagai struktur graf boleh ditangkap.
• Ciri-ciri nod: secara amnya termasuk isyarat frekuensi rendah dan frekuensi tinggi nod.

2. Rangka kerja pengoptimuman bersatu

Berdasarkan mekanisme penyebaran GNN, kita boleh mencari bahawa, GNN sedia ada mempunyai dua matlamat yang sama:

• Ekod maklumat berguna daripada ciri nod.
• Gunakan keupayaan melicinkan topologi.

Jadi bolehkah kita menggunakan bahasa matematik untuk menerangkan kedua-dua matlamat ini? Seseorang telah mencadangkan rangka kerja bersatu pengoptimuman GNN berikut yang diwakili oleh formula:

Item pertama dalam matlamat pengoptimuman:

ialah istilah pemadanan ciri dan matlamatnya adalah untuk membuat nod yang dipelajari Menunjukkan bahawa Z sedekat mungkin dengan ciri asal H, dan F₁, F₂ ialah gambar yang boleh direka bentuk kernel Convolution secara bebas. Apabila kernel lilitan ialah matriks identiti I, ia bersamaan dengan penapis semua-laluan apabila kernel lilitan ialah matriks 0, ia adalah penapis laluan rendah, dan apabila kernel lilitan ialah matriks Laplacian L, ia adalah penapis laluan tinggi.

Sebutan kedua bagi matlamat pengoptimuman secara rasmi adalah jejak matriks, dan fungsinya ialah sebutan biasa pada graf perbezaan antara jejak dan biasa Bagaimana dengan perhubungan? Sebenarnya, item kedua dikembangkan ke dalam bentuk berikut:

Maksudnya ialah tangkap gambar Tahap perbezaan ciri antara mana-mana dua nod bersebelahan mewakili kelancaran graf. Meminimumkan matlamat ini adalah sama dengan menjadikan saya dan jiran saya lebih serupa.

3 Gunakan rangka kerja pengoptimuman bersatu untuk memahami GNN sedia ada

GNN kebanyakannya mengoptimumkan matlamat ini ia dalam situasi yang berbeza:

Apabila parameter:

Apabila matlamat pengoptimuman menjadi:

Cari terbitan separa dan dapatkan:

Mari kita ambil di atas diperolehi Hasilnya boleh diperolehi dengan lebih lanjut pengembangan:

Ini bermakna lapisan Kth Semua perwakilan nod adalah sama dengan proses penyebaran perwakilan nod lapisan K-1 pada matriks bersebelahan Selepas terbitan sehingga tamat, akan didapati bahawa ia adalah sama dengan ciri awal X merambat K kali pada matriks bersebelahan selepas melengkapkan transformasi ciri W*. Sebenarnya, ini ialah model GCN atau SGC dengan lapisan tak linear dialih keluar.

Apabila parameter F₁=F₂=I, ζ=1, ξ=1/α - 1, α∈(0,q], dan apabila memilih penapis lulus semua, matlamat pengoptimuman menjadi:

Pada masa ini, kita juga mencari terbitan separa bagi Z dan menetapkan terbitan separa bersamaan dengan 0 untuk mendapatkan bentuk tertutup penyelesaian objektif pengoptimuman:

Dengan menukar sedikit hasil, anda boleh mendapatkan yang berikut formula:

Kita dapati bahawa formula di atas mewakili proses penyebaran ciri nod pada PageRank yang diperibadikan Itulah model PPNP.

juga merupakan model sedemikian jika anda menggunakan turunan kecerunan untuk mencarinya, dan tetapkan Saiz langkah ialah b, dan istilah lelaran ialah terbitan separa bagi fungsi objektif pada masa k-1 berkenaan dengan Z.

Bila

anda boleh dapatkan:

Ini ialah model APPNP. Latar belakang kemunculan model APPNP ialah operasi songsang matriks dalam model PPNP adalah terlalu rumit, dan APPNP menggunakan penghampiran berulang untuk menyelesaikannya. Ia juga boleh difahami bahawa APPNP boleh menumpu kepada PPNP kerana kedua-duanya datang dari rangka kerja yang sama.

4 Rangka kerja GNN Baharu

Selagi kami mereka bentuk istilah kesesuaian baharu Osesuai, dan Reka Bentuk istilah biasa graf yang sepadan Oreg, dan tambahkan proses penyelesaian baharu untuk mendapatkan model GNN baharu.

① Contoh 1: Daripada penapisan semua laluan kepada penapisan laluan rendah

Seperti yang dinyatakan sebelum ini, semua- lulus penapisan Kernel lilitan bawah F1=F2=Saya , apabila kernel lilitan ialah Laplacian Matriks L ialah penapis laluan tinggi. Jika GNN yang diperoleh dengan menimbang dua situasi ini boleh mengekod maklumat laluan rendah:

Bila

boleh mendapatkan penyelesaian yang tepat:

Begitu juga, kita boleh menyelesaikan secara berulang:

5 >

Istilah biasa yang disebut dalam rangka kerja bersatu sebelumnya adalah bersamaan dengan biasa L2, yang bersamaan dengan mengira maklumat perbezaan antara mana-mana dua titik pada graf. Sesetengah penyelidik merasakan bahawa regularisasi L2 adalah terlalu global dan akan menyebabkan kelancaran keseluruhan graf cenderung untuk sama, yang tidak sepenuhnya konsisten dengan realiti. Oleh itu, adalah dicadangkan untuk menambah istilah biasa L1 Istilah biasa L1 akan menghukum perubahan yang agak besar dalam graf.

Bahagian sebutan biasa L1 ialah:

Ringkasnya, rangka kerja bersatu di atas memberitahu kita:

Kita boleh memahami GNN dari perspektif yang lebih makro
Kita boleh bermula dari rangka kerja bersatu ini untuk mereka bentuk GNN baharu

Walau bagaimanapun, rangka kerja bersatu ini hanya boleh disesuaikan dengan struktur graf homogen Seterusnya, mari kita lihat struktur graf berbilang hubungan yang lebih biasa.

2. Model GNN Hubungan

1. Apa yang dipanggil graf berbilang hubungan merujuk kepada graf dengan jenis tepi lebih besar daripada 1, seperti yang ditunjukkan dalam rajah di bawah.

Rajah pelbagai perhubungan jenis ini sangat meluas di dunia nyata, seperti dalam molekul kimia Pelbagai jenis ikatan molekul, seperti perhubungan yang berbeza antara orang dalam rajah perhubungan sosial. Untuk graf sedemikian kita boleh menggunakan Rangkaian Neural Graf Relasional untuk memodelkan. Idea utama adalah untuk mengagregat graf secara individu dengan hubungan N untuk mendapatkan hasil pengagregatan N, dan kemudian mengagregatkan hasil N.

Formulanya ialah:

Anda boleh melihat pengagregatan dilakukan dalam dua langkah Pertama, pilih perhubungan r daripada semua perhubungan R, dan kemudian cari perhubungan yang mengandungi ini hubungan.

r

ialah berat yang digunakan untuk menimbang pelbagai perhubungan. Oleh itu, dapat dilihat bahawa apabila bilangan hubungan dalam graf meningkat, matriks berat

Wr juga akan meningkat, yang akan membawa kepada masalah lebih-parameterisasi ( Over-parameterization). Selain itu, pembahagian rajah perhubungan topologi mengikut perhubungan juga boleh membawa kepada kelancaran yang berlebihan.

2. CompGCN

Untuk menyelesaikan masalah penparameteran berlebihan, CompGCN menggunakan pengekod hubungan vektor untuk menggantikan Matriks hubungan N:

Pengekod mengandungi perhubungan dalam tiga arah: ke hadapan, belakang dan gelung kendiri:

Setiap lelaran turut mengemas kini pembenaman perhubungan.

Tetapi reka bentuk heuristik ini, dan pengekod parametrik sedemikian juga Akan menyebabkan parameterisasi yang berlebihan. Kemudian, berdasarkan pertimbangan di atas, kami mendapat titik permulaan kerja kami: Bolehkah kami mereka bentuk GNN yang lebih dipercayai dari perspektif matlamat pengoptimuman, dan pada masa yang sama menyelesaikan masalah GNN sedia ada.

3 Rangkaian saraf graf pelbagai hubungan bersepadu

GNN EMR kami diterbitkan tahun ini terutamanya akan bermula daripada Tiga aspek dibincangkan tentang cara kami mereka bentuk GCN yang sesuai untuk graf pelbagai perhubungan:

• Cara mereka bentuk algoritma pengoptimuman bersepadu yang sesuai
• Mekanisme penghantaran mesej
• Cara model GNN direka

1 Algoritma pengoptimuman bersepadu

Algoritma pengoptimuman ini perlu memenuhi dua keperluan:

• Dapat menangkap berbilang perhubungan pada graf secara serentak
• Dapat memodelkan kepentingan perhubungan yang berbeza pada graf

Istilah tetap graf pelbagai hubungan bersepadu yang kami cadangkan pada graf berbilang hubungan adalah seperti berikut:

Istilah biasa ini juga untuk menangkap keupayaan melicinkan isyarat graf, tetapi matriks bersebelahan ini ditangkap di bawah perhubungan r dan tertakluk kepada normalisasi Parameter terhalang μ_r adalah untuk memodelkan kepentingan perhubungan tertentu. Sebutan kedua ialah regularisasi bentuk normal kedua bagi vektor pekali, iaitu untuk menjadikan vektor pekali lebih seragam.

Untuk menyelesaikan masalah kelicinan yang berlebihan, kami menambah istilah yang sesuai untuk memastikan maklumat ciri asal tidak hilang. Jumlah bagi sebutan padanan dan sebutan biasa ialah:

seperti yang dinyatakan dalam sebelumnya bab Berbanding dengan rangka kerja bersatu, fungsi objektif yang kami reka di sini termasuk dua pembolehubah: pembetulan nod Z dan parameter matriks hubungan μ. Oleh itu, ia juga merupakan satu cabaran untuk mendapatkan mekanisme penyebaran mesej berdasarkan matlamat pengoptimuman sedemikian.

2. Terbitan mekanisme penghantaran mesej

Di sini kami menggunakan strategi pengoptimuman berulang:

• Mula-mula betulkan perwakilan nod Z, dan kemudian optimumkan parameter μ
• Kemudian optimumkan nod berdasarkan hasil μ sebelumnya lelaran Mewakili Z

Apabila nod tetap mencirikan Z, keseluruhan objektif pengoptimuman merosot kepada fungsi objektif hanya berkaitan dengan μ, tetapi ini adalah jalur Fungsi objektif terkurung:

Ini sebenarnya kekangan simpleks (kekangan dalam cembung A standard fungsi μ pada simplex). Untuk jenis masalah ini, kita boleh menggunakan Algoritma Keturunan Entropik Cermin untuk menyelesaikannya. Mula-mula kami akan mencari pemalar, dan kemudian mengemas kini pekali berat di bawah setiap perhubungan Keseluruhan proses kemas kini adalah serupa dengan algoritma penurunan kecerunan eksponen.

Membetulkan pekali perhubungan μ untuk mengemas kini Z, kemudian matlamat pengoptimuman merosot kepada yang berikut Borang ini:

Dengan cara ini kita mencari terbitan separa bagi fungsi objektif berkenaan kepada Z, dan biarkan Jika terbitan separa adalah sama dengan 0, kita boleh mendapatkan:

Maka penyelesaian bentuk tertutup bagi Z ialah:

Begitu juga, kita boleh menggunakan lelaran untuk mendapatkan penyelesaian anggaran. mekanisme pemesejan kita boleh membuktikan bahawa reka bentuk ini boleh mengelakkan Smooth yang berlebihan dan mengelakkan lebihan parameter Di bawah kita boleh melihat proses pembuktian.

Matriks PageRank berbilang hubungan asal ditakrifkan seperti berikut:

Atas dasar ini, matriks PageRank berbilang hubungan yang diperibadikan menambah kebarangkalian untuk mengembalikan nodnya sendiri:

Dengan menyelesaikan persamaan pekeliling di atas, anda boleh mendapatkan matriks PageRank diperibadikan berbilang hubungan:

Kami benarkan:

Anda boleh dapatkan:

Ini Itulah penyelesaian bentuk tertutup yang diperolehi oleh penyelesaian yang dicadangkan kami. Maksudnya, mekanisme penyebaran kami boleh bersamaan dengan penyebaran ciri H pada matriks PageRank yang diperibadikan nod. Kerana dalam mekanisme penyebaran ini, nod boleh kembali ke nodnya sendiri dengan kebarangkalian tertentu, yang bermaksud bahawa maklumatnya sendiri tidak akan hilang semasa proses penghantaran maklumat, dengan itu menghalang masalah pelicinan yang berlebihan.

Selain itu, model kami juga mengurangkan fenomena lebihan parameterisasi, kerana seperti yang dapat dilihat dari formula, untuk setiap hubungan model kami hanya mempunyai A boleh dipelajari pekali μ_r , Berbanding dengan nombor daripada parameter pengekod sebelumnya, atau matriks berat w_r, magnitud parameter kami hampir boleh diabaikan. Rajah berikut menunjukkan seni bina model yang kami reka:

di mana RCL ialah parameter yang dipelajari langkah , dan langkah Pro ialah langkah penyebaran ciri. Kedua-dua langkah ini bersama-sama membentuk lapisan pemesejan kami. Jadi bagaimanakah kita mengintegrasikan lapisan pemesejan kita ke dalam DNN tanpa memperkenalkan lebih banyak parameter tambahan? Kami juga mengikuti idea reka bentuk penyahgandingan: mula-mula gunakan MLP untuk mengekstrak ciri input, dan kemudian melalui berbilang lapisan lapisan menghantar mesej yang kami reka bentuk berbilang lapisan tidak akan membawa kepada pelicinan berlebihan. Hasil pemindahan akhir diproses oleh MLP untuk melengkapkan klasifikasi nod dan boleh digunakan untuk tugas hiliran. Gunakan formula untuk menyatakan proses di atas seperti berikut:

f(X;W) bermakna Ciri input diekstrak melalui MLP, dan EnMP(K) berikut bermakna hasil pengekstrakan dihantar melalui lapisan K mesej, g _θ mewakili MLP terperingkat.

Dalam perambatan belakang kami hanya perlu mengemas kini parameter dalam dua MLP, manakala parameter dalam EnMP kami dipelajari semasa proses perambatan hadapan Ya, ada tidak perlu mengemas kini sebarang parameter EnMP semasa proses penyebaran ke belakang.

Kita boleh membandingkan parameter mekanisme yang berbeza Kita dapat melihat bahawa parameter EMR-GNN kami terutamanya datang daripada dua MLP sebelum dan selepas, dan pekali hubungan. Apabila bilangan lapisan lebih besar daripada 3, kita boleh tahu bahawa bilangan parameter EMR-GNN adalah kurang daripada GCN, malah kurang daripada graf heterogen lain.

Dengan bilangan parameter yang begitu kecil, EMR-GNN kami beroperasi pada nod yang berbeza seperti mengikuti Tahap terbaik masih boleh dicapai di bawah tugas pengelasan.

Selain itu, kami juga membandingkan perubahan dalam ketepatan klasifikasi struktur rangkaian yang berbeza selepas bilangan lapisan meningkat Seperti yang ditunjukkan dalam rajah di bawah, apabila bilangan lapisan meningkat kepada 64, model kami boleh masih mengekalkan tahap ketepatan yang tinggi, manakala RGCN asal akan menghadapi memori yang tidak mencukupi apabila bilangan lapisan meningkat kepada lebih daripada 16 lapisan, dan adalah mustahil untuk menindih lebih banyak lapisan ini disebabkan oleh terlalu banyak parameter. Prestasi model GAT merosot kerana terlalu licin.

Selain itu, kami juga mendapati bahawa EMR-GNN kami berprestasi lebih baik di bawah saiz data yang lebih kecil Ia boleh mencapai ketepatan klasifikasi keseluruhan sampel, manakala RGCN jatuh banyak.

Kami juga menganalisis sama ada pekali hubungan μr yang dipelajari oleh EMR-GNN benar-benar bermakna, jadi apakah yang bermakna? Kami mahukan pekali perhubungan μ_r perhubungan pekali Memberi lebih berat kepada hubungan penting dan kurang berat kepada hubungan tidak penting. Keputusan analisis kami ditunjukkan dalam rajah di bawah:

Histogram hijau mewakili Kesan pengelasan di bawah perhubungan tertentu Jika ketepatan pengelasan lebih tinggi di bawah perhubungan tertentu, kita boleh menganggap perhubungan itu penting. Lajur biru mewakili pekali perhubungan yang dipelajari oleh EMR-GNN kami. Daripada perbandingan biru-hijau, kita dapat melihat bahawa pekali hubungan kita boleh mencerminkan kepentingan hubungan itu.

Akhirnya kami juga membuat paparan visual seperti yang ditunjukkan di bawah:

Anda dapat melihat bahawa pembenaman nod yang dilatih oleh EMR-GNN boleh membawa maklumat berstruktur nod, yang boleh menjadikan nod daripada jenis yang sama lebih padat dan jenis yang berbeza sebanyak mungkin Secara berasingan, sempadan pembahagian lebih jelas daripada rangkaian lain.

4 Ringkasan

1 Kami menggunakan perspektif yang bersatu untuk memahami GNN

2 Kami cuba mereka bentuk GNN berbilang hubungan baharu dari perspektif fungsi objektif

① We First, rangka kerja pengoptimuman bersepadu telah direka

② Berdasarkan rangka kerja pengoptimuman sedemikian, kami memperoleh mekanisme penghantaran mesej

③ Mekanisme penghantaran mesej dengan sebilangan kecil parameter digabungkan dengan MLP untuk mendapatkan EMR-GNN

3 mempunyai Apakah faedahnya?

① Ia bergantung pada matlamat pengoptimuman yang boleh dipercayai, jadi keputusan yang diperolehi boleh dipercayai, dan prinsip asasnya boleh dijelaskan secara matematik

② Ia boleh menyelesaikan masalah terlalu licin GNN Relation sedia ada

③ Menyelesaikan masalah lebihan parameter

④ Mudah dilatih, hasil yang lebih baik boleh diperolehi dengan parameter yang lebih kecil

5 sesi Soal Jawab

S1: Adakah terdapat perbezaan antara pembelajaran pekali hubungan dan mekanisme perhatian?

A1: Pembelajaran pekali hubungan di sini ialah proses kemas kini yang diperolehi melalui rangka kerja pengoptimuman, dan perhatian adalah proses yang perlu dipelajari berdasarkan perambatan belakang, jadi dari segi pengoptimuman, kedua-duanya Terdapat perbezaan asas.

S2: Bagaimanakah kebolehgunaan model pada set data berskala besar?

A2: Kami menganalisis kerumitan model dalam lampiran, dari segi kerumitan, kami berada pada tahap yang sama dengan RGCN, tetapi bilangan parameter akan menjadi lebih kecil daripada RGCN , jadi model kami lebih sesuai untuk set data berskala besar.

S3: Bolehkah rangka kerja ini menggabungkan maklumat tepi?

A3: Boleh disepadukan ke dalam istilah sesuai atau istilah biasa.

S4: Di manakah saya harus mempelajari asas matematik ini?

A4: Sebahagian daripadanya adalah berdasarkan kerja sebelumnya, dan sebahagian lagi teori matematik yang berkaitan dengan pengoptimuman juga berdasarkan beberapa kertas pengoptimuman klasik.

S5: Apakah perbezaan antara rajah hubungan dan rajah heterogen?

A5: Graf hubungan ialah graf heterogen, tetapi kita biasanya memikirkan graf heterogen yang mana jenis nod atau jenis tepi lebih besar daripada 1. Dalam rajah perhubungan, kami amat mengambil berat tentang kategori perhubungan yang lebih besar daripada 1. Dapat difahami bahawa yang terakhir termasuk yang pertama.

S6: Bolehkah latihan kumpulan mini disokong?

A6: Disokong.

S7: Adakah hala tuju penyelidikan masa depan GNN lebih cenderung kepada terbitan matematik yang ketat dan boleh ditafsir berbanding reka bentuk heuristik?

J7: Kami merasakan bahawa terbitan matematik boleh tafsir yang ketat ialah kaedah reka bentuk yang boleh dipercayai.

Atas ialah kandungan terperinci Rangkaian saraf berbilang graf bersepadu. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!