Graph Neural Networks (GNNs) för representation inlärning av grafer följer i stort sett ett område aggregering ram, där representation vektorn för en nod beräknas av rekursivt aggregering och transformera vektorer för sina angränsande noder. Många GNN-varianter har föreslagits och har uppnått toppmoderna resultat på både nod- och grafklassificeringsuppgifter. Trots GNN:s revolutionerande grafrepresentationsinlärning finns det dock begränsad förståelse för deras representationsegenskaper och begränsningar. Här presenterar vi en teoretisk ram för att analysera GNN:s uttryckskraft i att fånga olika grafstrukturer. Våra resultat kännetecknar den diskriminerande kraften hos populära GNN-varianter, såsom Graph Convolutional Networks och GraphSAGE, och visar att de inte kan lära sig att skilja på vissa enkla grafstrukturer. Vi utvecklar sedan en enkel arkitektur som är bevisligen den mest uttrycksfulla bland klassen av GNNs och är lika kraftfull som Weisfeiler-Lehman grafen isomorfism test. Vi validerar empiriskt våra teoretiska resultat på ett antal grafklassificeringsriktmärken och visar att vår modell uppnår toppmoderna resultat. Publicerad som konferensartikel på ICLR 2019 Här presenterar vi ett teoretiskt ramverk för att analysera GNN:s representationskraft. Vi karakteriserar formellt hur uttrycksfulla olika GNN-varianter är i att lära sig att representera och skilja mellan olika grafstrukturer. Vårt ramverk är inspirerat av den nära kopplingen mellan GNNs och Weisfeiler-Lehman (WL) grafen isomorfism test (Weisfeiler & Lehman, 1968), en kraftfull test känd för att skilja en bred klass av grafer (Babai & Kucera, 1979). Likt GNNs, WL testar iterativt uppdaterar en given nod funktion vektor genom att aggregera funktioner vektorer för sina nätverksgrannar. Vad som gör WL-testet så kraftfullt är dess injitiva aggregeringsuppdatering som kartlägger olika nodkvarter till olika funktionsvektorer. Vår nyckelinsikt är att en GNN kan ha lika stor diskriminativ effekt som WL-testet om GNN:s aggregeringssystem är mycket uttrycksfullt och kan modellera injicerande funktioner. För att matematiskt formalisera ovanstående insikt, vårt ramverk först abstracts funktionen vektorer av en nod grannar som en multiset, d.v.s. en uppsättning med möjligen upprepande element. Sedan kan grannen aggregering i GNNs abstrakteras som en funktion över multisetet. Vi studerar noggrant olika varianter av multisetfunktioner och karakteriserar teoretiskt deras diskriminativa kraft, d.v.s. hur väl olika aggregeringsfunktioner kan särskilja olika multiset. Ju mer diskriminerande multiset-funktionen är, desto kraftfullare är representationskraften hos den underliggande GNN. Våra huvudresultat sammanfattas enligt följande: 1) Vi visar att GNN är som mest lika kraftfulla som WL-testet när det gäller att särskilja grafstrukturer. 2) Vi etablerar villkor på grannen aggregering och graf pooling funktioner under vilka den resulterande GNN är lika kraftfull som WL testet. 3) Vi identifierar grafstrukturer som inte kan särskiljas genom populära GNN varianter, såsom GCN (Kipf & Welling, 2017) och GraphSAGE (Hamilton et al., 2017a), och vi exakt karakteriserar de typer av grafstrukturer som GNN-baserade modeller kan fånga. 4) Vi utvecklar en enkel neural arkitektur, Graph Isomorphism Network (GIN), och visar att dess discriminativa/representativa kraft är lika med kraften i WL testet. Vi validerar vår teori genom experiment på grafklassificeringsdata, där GNN:s uttryckskraft är avgörande för att fånga grafstrukturer. I synnerhet jämför vi GNN:s prestanda med olika aggregeringsfunktioner. Våra resultat bekräftar att den mest kraftfulla GNN (our Graph Isomorphism Network (GIN)) har hög representationskraft eftersom den nästan perfekt passar träningsdata, medan de mindre kraftfulla GNN-varianterna ofta kraftigt underutnyttjar träningsdata. Dessutom överträffar de representativa mer kraftfulla GNN de övriga genom att testa noggrannhet och uppnå toppmoderna prestanda på många grafklassificeringsriktmärken.
Grafen Isomorphism Network (GIN) REF kan särskilja samma strukturer som 1-dim WL-testet av grafen isomorphism, och dess arkitektur är ganska enkel och effektiv.
How Powerful are Graph Neural Networks?
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}