Kunzwisisa Kuzivikanwa kweTopology muGraph Neural Networks: Mhedzisiro paGeneralization uye Chimiro.

Table of Links

Abstract uye 1 Sumo

2 Basa Rinoenderana

3 Framework

4 Migumisiro Yakakura

5 Chidzidzo cheNzira Ipfupi-Path Distance

6 Mhedziso uye Kukurukurirana, uye Nongedzero

7 Humbowo hweTheorem 1

8 Humbowo hweTheorem 2

9 Nzira Yokugadzirisa Eq. (6)

10 Zvimwe Zviedzo Details uye Mibairo

11 Zvimwe Zvingangoitwa Zvishandiso

Abstract

Mazhinji ekuona komputa uye matambudziko ekudzidza muchina anoteedzerwa semabasa ekudzidza pamagirafu, uko magirafu neural network (GNNs) akabuda sechishandiso chikuru chekudzidza zvinomiririra yegraphstructured data. Chinhu chakakosha cheGNNs kushandisa kwavo zvimiro zvegirafu sekuisa, zvichivagonesa kushandisa magirafu' emukati meiyo topological zvimiro-zvinozivikanwa seruzivo rwepamusoro peGNNs. Zvisinei nekubudirira kwesimba kweGNNs, pesvedzero yeruzivo rwetopology pamusoro pekuita kwegeneralization inoramba isina kuongororwa, kunyanya kune node-level mabasa anosiyana kubva mufungidziro yekuti data rakazvimiririra uye rakagovaniswa zvakafanana (IID). Iyo chaiyo tsananguro uye hunhu hweiyo topology kuziva kweGNNs, kunyanya nezve akasiyana epamusoro maficha, hazvisati zvanyatsojeka. Iri bepa rinounza hwaro hwakazara kuratidza ruzivo rwepamusoro peGNNs pane chero chimiro chepamusoro. Tichishandisa chimiro ichi, tinoongorora mhedzisiro yekuzivikanwa kwetopology paGNN generalization performance. Kusiyana nechitendero chiripo chekuti kusimudzira ruzivo rwepamusoro peGNNs kunogara kuchibatsira, ongororo yedu inoratidza muono wakakomba: kuvandudza ruzivo rwepamusoro peGNNs zvinogona kutungamira mukusaenzana kuzere kumapoka ezvimiro, izvo zvingave zvisingadiwi mune mamwe mamiriro. Pamusoro pezvo, isu tinoitisa chidzidzo chenyaya tichishandisa iyo intrinsic graph metric, ipfupi-nzira chinhambwe, pane akasiyana mabhenji madhata. Mhedzisiro yemhedzisiro yenyaya iyi yenyaya inosimbisa maonero edu edzidziso. Uyezve, isu tinoratidza kushanda kunoshanda kwechimiro chedu nekushandisa kugadzirisa dambudziko rekutanga rinotonhora mukudzidza kwegirafu.

1 Nhanganyaya

Matambudziko mazhinji mukuona komputa uye kudzidza muchina anoteedzerwa semabasa ekudzidza pamagirafu. Semuenzaniso, mune semantic segmentation, magirafu anoenzanisira hukama pakati penzvimbo dzakasiyana dzemifananidzo, achiwedzera kurongeka uye kupatsanurwa kwekuziva mamiriro. Graph neural networks (GNNs) yabuda sekirasi ine simba yemamodhi ekudzidza emuchina akagadzirirwa kudzidzira kumiririra yedata rakaumbwa negraph. Vakaratidza kubudirira kukuru mukugadzirisa matambudziko akasiyana-siyana ane chokuita negirafu munzvimbo dzakasiyana-siyana dzakadai semakemikari [10], biology [37], social networking [6, 22], scene graph generation [46, 51] uye kuona hukama hwehukama. [24,43,49]. Chinotsanangudza chimiro cheGNNs kushandisa kwavo nzira yepakati kuburikidza nemeseji inopfuudza pachimiro chegirafu chekuunganidza zvinhu. Izvi zvinoita kuti maGNNs achengetedze ruzivo rwezvimiro kana zvinotsamira (zvinonzi ruzivo rwetopology) kubva kune iri pasi pechimiro chegirafu, zvichivabvumira kuti vashande zvakanyanya mumabasa akadai sekuronga node. Mufananidzo 1 unoratidza maitiro ese ekudzidza eGNNs.

Pasinei nekuita kwavo uye kugona kwavo, kuchine kushaikwa kwekunzwisisa kwedzidziso nezveGNNs, kunyanya mune semi-inotariswa node classification marongero apo kutsamira pakati pe data kunosiyana zvakanyanya kubva kune mamwe mamodeli ekudzidza muchina [25]. Muchigadziro ichi, chinangwa ndechekuwedzera hukama, sekutorwa nechimiro chegirafu, pakati pe data uye seti diki yemanodhi akanyorwa kufanofembera mavara emanodhi asara. Zvizhinji zvezvidzidzo zviripo zvedzidziso zveGNNs zvakatarisana nekubatana pakati penzira yekupfuura meseji yeGNNs uye Weisfeiler-Lehman isomorphism bvunzo [19], nechinangwa chekunzwisisa kugona kweGNNs kusiyanisa akasiyana magirafu zvimiro mune zvakadzidzwa zvinomiririra, zvinozivikanwa. sesimba rinoratidza reGNNs. Kufemerwa nezvidzidzo zvekutaura, zvinotendwa kuti kuwedzera ruzivo rwetopology kunobatsira pasi rose uye zvidzidzo zvakawanda zvinotarisa pakugonesa maGNN kuchengetedza mamwe maumbirwo ezvivakwa mukumiririra kwakadzidzwa [29, 33, 48].

Nekudaro, sezvo maGNN anowedzera kuvimba uye anonzwisisa (kuziva) kwechimiro chegirafu sekuisa, anogona kuratidza maitiro akasiyana ezvekuita kune mamwe madiki ezvimiro (akasiyana data subset akaunganidzwa nekufanana kwechimiro kune yekudzidziswa seti) mukati me data. Iyo quantification yeGNN generalization kumapoka akasiyana ezvimiro anonzi structural subgroup generalization [25]. Kufunga kwakadaro kwakakosha mukushandiswa kweGNN uye kusimudzira. Semuyenzaniso, mukati meprotein-protein interaction network, aya madiki ezvimiro anogona kumiririra akasiyana mamolecular complexes, achipesvedzera chokwadi chekudyidzana kufanotaura. Saizvozvo, kunzwisisa kuti kuziva kwetopology kweGNNs kunopesvedzera kuita generalization kwakakosha sei pakuronga nzira dzesampling dzekudzidzisa. Mwero wekuita kwekuita kweGNNs kunokonzerwa nemaitiro chaiwo e data yegraph yakakosha pakusarudza kuumbwa kwemaseti ekudzidzisa. Zvisinei nekukosha kwayo, kunzwisisa kwehukama pakati pekuziva kwetopology yeGNNs uye kuumbwa kwayo kweboka diki kuchiri kushomeka. Uyezve, kuratidza ruzivo rwepamusoro peGNNs zvinounza dambudziko, kunyanya tichifunga kuti nzvimbo dzakasiyana uye mabasa anogona kukoshesa akasiyana zvimiro. Naizvozvo, chimiro chakasiyana-siyana chinodiwa kuongorora ruzivo rwepamusoro peGNNs maererano nezvimiro zvakasiyana.

Kuti tigadzirise gaka iri, mubepa rino, tinopa zano renovel rakavakirwa pakufungidzira metric kumisikidzwa kuti tidzidze hukama huripo pakati pezvimiro zveboka diki uye ruzivo rwetopology rweGNNs mumamiriro ekusatarisirwa node classification. Iyo yakarongwa sisitimu inobvumira kuferefetwa kweiyo structural subgroup generalization yeGNNs maererano neakasiyana madiki mapoka. Kunyanya, mipiro mikuru yebasa iri inopfupikiswa sezvizvi.

1. Tinopa zano renovel, structure-agnostic framework tichishandisa approximate metric embedding kuongorora kudyidzana pakati peGNN's'structural subgroup generalization uye topology kuziva. Iyi dhizaini inoshanda zvakasiyana-siyana, inoenderana nematanho akasiyana-siyana senge nhambwe-pfupi-nzira, uye inoda chete chiyero chinoenderana. Kureruka kwaro mukufungidzira zvinhu zvakakosha kunoita kuti zvishande uye zvigone kuitika kune akasiyana siyana ezviitiko.

2. Kuburikidza nekuongorora kwakarongeka mukati megadziriro yedu, tinogadza hukama hwakajeka pakati pekuziva kweGNN topology nekuita kwavo kwese (Theorem 1). Isu tinoratidza zvakare kuti nepo kukwidziridzwa kweruzivo rwetopology kuchiwedzera kutaura kweGNN, zvinogona kukonzera kusaenzana kwekuita kwekuita, tichifarira mapoka madiki zvakanyanya kufanana neseti yekudzidziswa (Theorem 2). Zvivakwa zvakadaro zvinogona kukuvadza (kukonzera kusaruramisira) kana kubatsira (kuzivisa sarudzo dzekugadzira) zvichienderana nemamiriro ezvinhu. Izvi zvinopikisa chitendero chiripo chekuti kuwedzera kweruzivo rwetopology kunobatsira pasi rose maGNNs [29, 33, 48], ichisimbisa kukosha kwekufunga nezvehukama pakati pekuziva kwetopology uye kuita kwese.

3. Isu tinosimbisa chimiro chedu kuburikidza nechidzidzo chenyaya papfupi-nzira daro, tichiratidza kushanda kwayo uye kukosha kwayo. Mhedzisiro yacho inotsigira zvatakawana, zvichiratidza kuti maGNN ane ruzivo rwakakura rwemadaro mapfupi anokunda mukuisa mapoka evertex padyo neseti yekudzidziswa. Uyezve, tinoratidza kuti zvatinowana zvingashandiswa sei kuderedza dambudziko rekutanga rinotonhora mune girafu rinoshingaira kudzidza [11,15], kusimbisa zvinorehwa nemaitiro edu nemigumisiro.