Konprann konsyantizasyon Topoloji nan rezo neral graf: enpak sou jeneralizasyon ak estriktirèl

Tablo Lyen yo

Abstract ak 1 Entwodiksyon

2 Travay ki gen rapò

3 Kad

4 Rezilta prensipal yo

5 Yon etid ka sou distans ki pi kout

6 Konklizyon ak Diskisyon, ak Referans

7 Prèv teyorèm 1

8 Prèv teyorèm 2

9 Pwosedi pou rezoud ekwasyon. (6)

10 Eksperyans adisyonèl Detay ak rezilta

11 Lòt Aplikasyon Potansyèl

Résumé

Anpil vizyon òdinatè ak pwoblèm aprantisaj machin yo modle kòm travay aprantisaj sou graf, kote rezo neral graf (GNN) te parèt kòm yon zouti dominan pou aprann reprezantasyon done graf estriktire. Yon karakteristik kle nan GNN yo se itilizasyon estrikti graf yo kòm opinyon, sa ki pèmèt yo eksplwate pwopriyete topolojik nannan graf yo - ke yo rekonèt kòm konsyans topoloji GNN yo. Malgre siksè anpirik GNN yo, enfliyans konsyantizasyon topoloji sou pèfòmans jeneralizasyon rete enkonu, patikilyèman pou travay nivo ne ki diferan de sipozisyon done yo endepandan epi distribye idantik (IID). Definisyon egzak ak karakterizasyon konsyans topoloji GNN yo, espesyalman konsènan diferan karakteristik topolojik, yo toujou klè. Papye sa a prezante yon fondasyon konplè pou karakterize konsyans topoloji GNN yo atravè nenpòt karakteristik topolojik. Sèvi ak fondasyon sa a, nou mennen ankèt sou efè konsyans topoloji sou pèfòmans jeneralizasyon GNN. Kontrèman ak kwayans dominan ke amelyore konsyantizasyon topoloji GNN yo toujou avantaje, analiz nou an revele yon insight kritik: amelyore konsyans topoloji GNN yo ka enadvèrtans mennen nan jeneralizasyon enjis atravè gwoup estriktirèl, ki ta ka pa vle nan kèk senaryo. Anplis de sa, nou fè yon etid ka lè l sèvi avèk metrik graf intrinsèque, distans ki pi kout chemen an, sou divès kalite done referans. Rezilta anpirik etid ka sa a konfime lide teyorik nou an. Anplis, nou demontre aplikasyon pratik kad nou an lè nou itilize li pou atake pwoblèm demaraj frèt la nan aprantisaj aktif graf.

1 Entwodiksyon

Anpil pwoblèm nan vizyon òdinatè ak aprantisaj machin yo modle kòm travay aprantisaj sou graf. Pou egzanp, nan segmantasyon semantik, graf modèl relasyon ki genyen ant rejyon imaj diferan, amelyore presizyon ak segman kontèks-konsyan. Rezo neral graf (GNNs) te parèt kòm yon klas dominan nan modèl aprantisaj machin ki fèt espesyalman pou aprann reprezantasyon done graf estriktire. Yo te demontre siksè konsiderab nan adrese yon pakèt pwoblèm ki gen rapò ak graf nan divès domèn tankou chimi [10], byoloji [37], rezo sosyal [6, 22], jenerasyon graf sèn [46, 51] ak deteksyon relasyon vizyèl. [24,43,49]. Yon karakteristik defini nan GNN yo se itilizasyon yo nan yon apwòch espasyal atravè mesaj pase sou estrikti nan graf pou agrégation karakteristik. Sa pèmèt GNN yo prezève enfòmasyon estriktirèl oswa depandans (ki refere yo kòm konsyans topoloji) nan estrikti graf ki kache, sa ki pèmèt yo trè efikas nan travay tankou klasifikasyon ne. Fig. 1 montre pwosesis aprantisaj jeneral GNN yo.

Malgre pratik yo ak potansyèl yo, rete yon mank de konpreyansyon teyorik sou GNN, patikilyèman nan anviwònman klasifikasyon semi-sipèvize node kote depandans yo nan mitan done yo diferan anpil de lòt modèl aprantisaj machin [25]. Nan anviwònman sa a, objektif la se ogmante relasyon, jan estrikti graf la kaptire, pami done yo ak yon ti seri nœuds ki make pou predi etikèt pou nœuds ki rete yo. Pifò nan syans teyorik ki deja egziste nan GNN yo te konsantre sou koneksyon ki genyen ant mekanis mesaj-pase GNN yo ak tès izomorfis Weisfeiler-Lehman [19], ki vize konprann kapasite GNN yo diferansye estrikti graf diferan nan reprezantasyon yo aprann, li te ye. kòm pouvwa ekspresyon GNN yo. Enspire pa etid yo ekspresyon, yo souvan kwè ke ogmante konsyans topoloji se inivèsèl benefisye ak anpil etid konsantre sou pèmèt GNN yo prezève plis pwopriyete estriktirèl nan reprezantasyon aprann [29, 33, 48].

Sepandan, kòm GNN yo vin pi depandan ak sansib (konsyan) de estrikti graf kòm opinyon, yo ka montre pèfòmans jeneralizasyon diferan nan direksyon sèten sou-gwoup estriktirèl (sous-ansanm done diferan gwoupe pa resanblans estriktirèl ak seri fòmasyon an) nan done yo. Kantifikasyon jeneralizasyon GNN atravè sougwoup estriktirèl diferan yo rele jeneralizasyon sougwoup estriktirèl [25]. Konsiderasyon sa yo enpòtan anpil nan aplikasyon ak devlopman GNN. Pou egzanp, nan rezo entèraksyon pwoteyin-pwoteyin, sougwoup estriktirèl sa yo ka reprezante diferan konplèks molekilè, enfliyanse presizyon nan prediksyon entèraksyon. Menm jan an tou, konprann ki jan konsyans topoloji GNN yo enfliyanse jeneralizasyon se esansyèl lè elabore estrateji echantiyon pou fòmasyon. Nan ki pwen pèfòmans jeneralizasyon GNN yo enfliyanse pa karakteristik espesifik estriktirèl done graf yo se kritik nan deside konpozisyon an nan seri done fòmasyon. Malgre enpòtans li, yon konpreyansyon sou relasyon ki genyen ant konsyans topoloji GNN yo ak jeneralizasyon estriktirèl sougwoup li yo toujou manke. Anplis de sa, karakterize konsyans topoloji GNN yo poze yon defi, sitou lè nou konsidere ke diferan domèn ak travay ka priyorite aspè estriktirèl diferan. Se poutèt sa, yon fondasyon versatile nesesè pou evalye konsyans topoloji GNN an relasyon ak estrikti divès kalite.

Pou abòde espas sa a, nan papye sa a, nou pwopoze yon kad roman ki baze sou apwoksimatif embedding metrik pou etidye relasyon ki genyen ant jeneralizasyon estriktirèl sougwoup ak konsyans topoloji GNN nan kontèks klasifikasyon nœud semi-sipèvize. Kad yo pwopoze a pèmèt pou envestigasyon jeneralizasyon estriktirèl GNN yo ki gen rapò ak diferan sougwoup estriktirèl. Plis konkrètman, kontribisyon prensipal yo nan travay sa a yo rezime jan sa a.

1. Nou pwopoze yon kad roman, estrikti-agnostic lè l sèvi avèk embedding metrik apwoksimatif pou egzamine entèraksyon ki genyen ant jeneralizasyon estriktirèl sougwoup GNN yo ak konsyans topoloji. Fondasyon sa a se versatile, akomode divès kalite mezi estriktirèl tankou distans ki pi kout chemen, epi li mande sèlman mezi estriktirèl ki koresponn lan. Senplisite li nan estime faktè kle fè li aplikab ak jeneralize nan yon pakèt senaryo.

2. Atravè analiz fòmèl nan kad nou an, nou etabli yon lyen klè ant konsyans topoloji GNN ak pèfòmans jeneralizasyon yo (Teyorèm 1). Nou demontre tou ke pandan ke konsyans topoloji amelyore ranfòse ekspresyon GNN, li ka lakòz pèfòmans jeneralizasyon inegal, favorize sougwoup plis estriktirèl ki sanble ak seri fòmasyon an (Teyorèm 2). Pwopriyete estriktirèl sa yo ka danjere (ki lakòz pwoblèm enjis) oswa itil (enfòme desizyon konsepsyon) depann sou senaryo a. Sa a defi kwayans dominan ke ogmante konsyans topoloji inivèsèl benefisye GNNs [29, 33, 48], mete aksan sou enpòtans ki genyen nan konsidere relasyon ki genyen ant konsyans topoloji ak pèfòmans jeneralizasyon.

3. Nou valide fondasyon nou an atravè yon etid ka sou distans ki pi kout chemen, mete aksan sou pratik ak enpòtans li. Rezilta yo konfime rezilta teyorik nou yo, ki montre ke GNN ki gen plis konsyans sou distans ki pi kout yo briye nan klasifikasyon gwoup somè ki pi pre seri fòmasyon an. Anplis, nou montre kouman rezilta nou yo ka aplike pou bese pwoblèm kòmanse frèt nan aprantisaj aktif graf [11,15], mete aksan sou enplikasyon pratik kad nou an ak rezilta yo.