Pag-unawa sa Topology Awareness sa Graph Neural Networks: Mga Epekto sa Generalization at Structural

Talaan ng mga Link

Abstract at 1 Panimula

2 Kaugnay na Gawain

3 Balangkas

4 Pangunahing Resulta

5 Isang Pag-aaral ng Kaso sa Pinakamaikling Layo sa Landas

6 Konklusyon at Talakayan, at Mga Sanggunian

7 Katibayan ng Theorem 1

8 Katibayan ng Teorama 2

9 Pamamaraan para sa Paglutas ng Eq. (6)

10 Mga Detalye at Resulta ng Karagdagang Eksperimento

11 Iba pang Potensyal na Aplikasyon

Abstract

Maraming problema sa computer vision at machine learning ang na-modelo bilang mga gawain sa pag-aaral sa mga graph, kung saan ang mga graph neural network (GNNs) ay lumitaw bilang isang nangingibabaw na tool para sa pag-aaral ng mga representasyon ng graphstructured data. Ang isang pangunahing tampok ng mga GNN ay ang kanilang paggamit ng mga istruktura ng graph bilang input, na nagbibigay-daan sa kanila na samantalahin ang mga likas na katangian ng topological ng mga graph—na kilala bilang kaalaman sa topology ng mga GNN. Sa kabila ng mga empirikal na tagumpay ng mga GNN, ang impluwensya ng kamalayan sa topology sa pagganap ng generalization ay nananatiling hindi ginagalugad, lalo na para sa mga gawain sa antas ng node na nag-iiba mula sa pagpapalagay na ang data ay independyente at identically distributed (IID). Ang tumpak na kahulugan at paglalarawan ng kamalayan sa topology ng mga GNN, lalo na tungkol sa iba't ibang mga tampok na topological, ay hindi pa rin malinaw. Ang papel na ito ay nagpapakilala ng isang komprehensibong balangkas upang makilala ang kamalayan sa topology ng mga GNN sa anumang tampok na topological. Gamit ang framework na ito, sinisiyasat namin ang mga epekto ng kamalayan sa topology sa pagganap ng generalization ng GNN. Taliwas sa umiiral na paniniwala na ang pagpapahusay sa kaalaman sa topology ng mga GNN ay palaging kapaki-pakinabang, ang aming pagsusuri ay nagpapakita ng isang kritikal na pananaw: ang pagpapabuti ng kaalaman sa topology ng mga GNN ay maaaring hindi sinasadyang humantong sa hindi patas na paglalahat sa mga istrukturang grupo, na maaaring hindi ninanais sa ilang mga sitwasyon. Bukod pa rito, nagsasagawa kami ng case study gamit ang intrinsic graph metric, ang pinakamaikling distansya ng landas, sa iba't ibang benchmark na dataset. Ang mga empirical na resulta ng case study na ito ay nagpapatunay sa aming mga teoretikal na pananaw. Bukod dito, ipinapakita namin ang praktikal na applicability ng aming framework sa pamamagitan ng paggamit nito upang harapin ang malamig na problema sa pagsisimula sa graph active learning.

1 Panimula

Maraming problema sa computer vision at machine learning ang namodelo bilang mga gawain sa pag-aaral sa mga graph. Halimbawa, sa semantic segmentation, ang mga graph ay nagmomodelo ng mga ugnayan sa pagitan ng iba't ibang rehiyon ng larawan, na nagpapahusay sa katumpakan at context-aware na segmentation. Ang mga graph neural network (GNN) ay lumitaw bilang isang nangingibabaw na klase ng mga modelo ng machine learning na partikular na idinisenyo para sa pag-aaral ng mga representasyon ng graph-structured data. Nagpakita sila ng malaking tagumpay sa pagtugon sa isang malawak na hanay ng mga problemang nauugnay sa graph sa iba't ibang mga domain tulad ng chemistry [10], biology [37], social networking [6, 22], pagbuo ng scene graph [46, 51] at pagtuklas ng visual na relasyon. [24,43,49]. Ang isang pagtukoy sa katangian ng mga GNN ay ang kanilang paggamit ng spatial na diskarte sa pamamagitan ng pagpasa ng mensahe sa istruktura ng graph para sa pagsasama-sama ng tampok. Nagbibigay-daan ito sa mga GNN na mapanatili ang impormasyon sa istruktura o mga dependency (tinukoy bilang kamalayan sa topology) mula sa pinagbabatayan na istraktura ng graph, na nagpapahintulot sa kanila na maging lubos na epektibo sa mga gawain tulad ng pag-uuri ng node. Ang Fig. 1 ay naglalarawan ng pangkalahatang proseso ng pag-aaral ng mga GNN.

Sa kabila ng kanilang pagiging praktikal at potensyal, nananatili ang kakulangan ng teoretikal na pag-unawa tungkol sa mga GNN, lalo na sa semi-supervised na setting ng pag-uuri ng node kung saan ang mga dependency sa data ay naiiba nang malaki sa iba pang mga modelo ng pag-aaral ng makina [25]. Sa setting na ito, ang layunin ay gamitin ang mga ugnayan, gaya ng nakuha ng istraktura ng graph, kasama ng data at isang maliit na hanay ng mga may label na node upang mahulaan ang mga label para sa natitirang mga node. Karamihan sa mga umiiral na teoretikal na pag-aaral ng mga GNN ay nakatuon sa koneksyon sa pagitan ng mekanismo ng pagpasa ng mensahe ng mga GNN at ng Weisfeiler-Lehman isomorphism test [19], na naglalayong maunawaan ang kakayahan ng mga GNN na pag-iba-ibahin ang iba't ibang mga istruktura ng graph sa mga natutunang representasyon, na kilala. bilang nagpapahayag na kapangyarihan ng mga GNN. Sa inspirasyon ng mga pag-aaral ng pagpapahayag, karaniwang pinaniniwalaan na ang pagtaas ng kamalayan sa topology ay kapaki-pakinabang sa pangkalahatan at maraming mga pag-aaral ang nakatuon sa pagpapagana ng mga GNN na mapanatili ang higit pang mga katangian ng istruktura sa natutunan na representasyon [29, 33, 48].

Gayunpaman, habang nagiging mas umaasa ang mga GNN sa at sensitibong (nakakaalam) sa istruktura ng graph bilang input, maaari silang magpakita ng iba't ibang pagganap ng generalization patungo sa ilang mga structural subgroup (mga natatanging subset ng data na nakapangkat ayon sa pagkakatulad ng istruktura sa set ng pagsasanay) sa loob ng data. Ang quantification ng GNN generalization sa mga natatanging structural subgroup ay tinatawag na structural subgroup generalization [25]. Ang mga naturang pagsasaalang-alang ay mahalaga sa aplikasyon at pag-unlad ng GNN. Halimbawa, sa loob ng mga network ng pakikipag-ugnayan ng protina-protina, ang mga istrukturang subgroup na ito ay maaaring kumatawan sa iba't ibang mga molekular na kumplikado, na nakakaimpluwensya sa katumpakan ng mga hula sa pakikipag-ugnayan. Katulad nito, ang pag-unawa kung paano nakakaimpluwensya ang kaalaman sa topology ng mga GNN sa generalization ay mahalaga kapag gumagawa ng mga diskarte sa sampling para sa pagsasanay. Ang lawak kung saan ang pagganap ng generalization ng mga GNN ay naiimpluwensyahan ng mga partikular na tampok na istruktura ng data ng graph ay kritikal sa pagpapasya sa komposisyon ng mga dataset ng pagsasanay. Sa kabila ng kahalagahan nito, kulang pa rin ang pag-unawa sa ugnayan sa pagitan ng kamalayan ng topology ng mga GNN at ang paglalahat ng istrukturang subgroup nito. Higit pa rito, ang pagkilala sa kamalayan sa topology ng mga GNN ay nagdudulot ng isang hamon, lalo na kung isasaalang-alang na ang iba't ibang mga domain at mga gawain ay maaaring unahin ang mga natatanging aspeto ng istruktura. Samakatuwid, ang isang maraming nalalaman na balangkas ay kinakailangan upang masuri ang kamalayan sa topology ng mga GNN na may kaugnayan sa iba't ibang mga istruktura.

Upang matugunan ang puwang na ito, sa papel na ito, nagmumungkahi kami ng isang nobelang balangkas batay sa tinatayang metric na pag-embed upang pag-aralan ang ugnayan sa pagitan ng structural subgroup generalization at topology na kamalayan ng mga GNN sa konteksto ng semisupervised node classification. Ang iminungkahing balangkas ay nagbibigay-daan para sa pagsisiyasat ng structural subgroup generalization ng mga GNN na may paggalang sa iba't ibang mga structural subgroup. Higit na konkreto, ang mga pangunahing kontribusyon ng gawaing ito ay ibinubuod bilang mga sumusunod.

1. Iminumungkahi namin ang isang nobela, structure-agnostic na framework gamit ang tinatayang metric na pag-embed upang suriin ang interplay sa pagitan ng structural subgroup generalization at topology awareness ng mga GNN. Ang balangkas na ito ay maraming nalalaman, na tinatanggap ang iba't ibang mga hakbang sa istruktura tulad ng pinakamaikling distansya ng landas, at nangangailangan lamang ng kaukulang panukalang istruktura. Ang pagiging simple nito sa pagtatantya ng mga pangunahing salik ay ginagawa itong naaangkop at pangkalahatan sa isang malawak na hanay ng mga senaryo.

2. Sa pamamagitan ng pormal na pagsusuri sa loob ng aming balangkas, nagtatatag kami ng isang malinaw na ugnayan sa pagitan ng kamalayan sa topolohiya ng GNN at ng kanilang pagganap sa pangkalahatan (Theorem 1). Ipinakita rin namin na habang ang pinahusay na kamalayan sa topology ay nagpapalakas ng pagpapahayag ng GNN, maaari itong magresulta sa hindi pantay na pagganap ng generalization, na pinapaboran ang mga subgroup na mas structurally katulad sa set ng pagsasanay (Theorem 2). Ang nasabing istrukturang ari-arian ay maaaring nakakapinsala (nagdudulot ng mga isyu sa hindi patas) o kapaki-pakinabang (nagbibigay-alam sa mga desisyon sa disenyo) depende sa senaryo. Hinahamon nito ang umiiral na paniniwala na ang pagtaas ng kamalayan sa topology sa pangkalahatan ay nakikinabang sa mga GNN [29, 33, 48], na nagbibigay-diin sa kahalagahan ng pagsasaalang-alang sa kaugnayan sa pagitan ng kamalayan sa topology at pagganap ng generalization.

3. Pinapatunayan namin ang aming balangkas sa pamamagitan ng isang case study sa pinakamaikling distansya ng landas, na itinatampok ang pagiging praktikal at kaugnayan nito. Pinatutunayan ng mga resulta ang aming mga teoretikal na natuklasan, na nagpapakita na ang mga GNN na may mas mataas na kamalayan sa mga pinakamaikling distansya ng landas ay mahusay sa pag-uuri ng mga pangkat ng vertex na mas malapit sa set ng pagsasanay. Bukod dito, ipinapakita namin kung paano mailalapat ang aming mga natuklasan upang mapagaan ang malamig na problema sa pagsisimula sa aktibong pag-aaral ng graph [11,15], na itinatampok ang mga praktikal na implikasyon ng aming balangkas at mga resulta.