En Ny Måde at Træne AI på Grafdata Uden Overvågning

```html Forfattere: Zhen Peng Wenbing Huang Minnan Luo Qinghua Zheng Yu Rong Tingyang Xu Junzhou Huang ABSTRAKT Rigdommen i indholdet af forskellige informationsnetværk såsom sociale netværk og kommunikationsnetværk giver et hidtil uset potentiale for at lære udtryksfulde repræsentationer af høj kvalitet uden ekstern supervision. Dette papir undersøger, hvordan man bevarer og udtrækker den rigelige information fra grafstrukturerede data til indlejringsrummet på en usuperviseret måde. Til dette formål foreslår vi et nyt koncept, grafisk gensidig information (GMI), til at måle korrelationen mellem inputgrafer og skjulte repræsentationer på højt niveau. GMI generaliserer ideen om konventionelle gensidige informationsberegninger fra vektorrummet til grafdomænet, hvor måling af gensidig information fra to aspekter af knudepunktsfunktioner og topologisk struktur er uundværlig. GMI udviser flere fordele: For det første er den uændret af den isomorfe transformation af inputgrafer – en uundgåelig begrænsning i mange eksisterende grafrepræsentationslæringsalgoritmer; Desuden kan den effektivt estimeres og maksimeres af nuværende metoder til estimering af gensidig information, såsom MINE; Endelig bekræfter vores teoretiske analyse dens korrekthed og rationalitet. Med hjælp fra GMI udvikler vi en usuperviseret læringsmodel, der trænes ved at maksimere GMI mellem inputtet og outputtet fra en grafisk neural koder. Omfattende eksperimenter med transduktiv såvel som induktiv knudepunktsklassifikation og linkforudsigelse demonstrerer, at vores metode overgår state-of-the-art usuperviserede modstykker, og endda nogle gange overgår præstationen af superviserede. 1 INTRODUKTION For at opnå pålidelig kvantitativ analyse af forskellige informationsnetværk er repræsentationslæring af høj kvalitet for grafstrukturerede data blevet et af de nuværende fascinerende emner. Nylige metoder mod dette mål, almindeligvis kategoriseret som Graph Neural Networks (GNNs), har opnået bemærkelsesværdige fremskridt i et stort antal læringsopgaver, såsom knudepunktsklassifikation [ , , ], linkforudsigelse [ , , ], grafjustering [ , , ], molekylær generering [ , , ], for blot at nævne nogle få. Selvom der er frugtbare fremskridt, kræver træning af GNN'er i eksisterende tilgange normalt en vis form for supervision. Utvivlsomt er mærkningsinformation dyr at anskaffe – manuel annotation eller betaling for tilladelse, og er endda umulig at opnå på grund af privatlivspolitikken. Ikke at nævne, at pålideligheden af givne etiketter undertiden er tvivlsom. Derfor bliver det nødvendigt for mange praktiske tilfælde, hvordan man opnår grafrepræsentation af høj kvalitet uden supervision, hvilket motiverer studiet af dette papir. 35 42 50 26 27 49 12 19 43 4 5 46 Ved omhyggeligt at undersøge vores indsamlede grafstrukturerede data finder vi, at de generelt kommer fra forskellige kilder såsom sociale netværk, citationnetværk og kommunikationsnetværk, hvor der eksisterer en enorm mængde af både indholds- og linkinformation. For eksempel inkluderer data på mange sociale platforme som Twitter, Flickr og Facebook funktioner af brugere, *f.eks.*, grundlæggende personlige oplysninger, tekster, billeder, IP og deres relationer, *f.eks.*, køber den samme vare, er venner. Disse rige datakilder er tilstrækkelige til at understøtte efterfølgende minedriftsopgaver uden yderligere vejledning: hvis to enheder udviser ekstrem lighed i funktioner, er der stor sandsynlighed for et link imellem dem (linkforudsigelse), og de hører sandsynligvis til samme kategori (klassifikation); hvis to enheder begge linker til samme enhed, har de sandsynligvis lignende karakteristika (anbefaling). I denne forstand letter bevaring og udtrækning af så meget information som muligt fra informationsnetværk til indlejringsrummet læring af udtryksfulde repræsentationer af høj kvalitet, der udviser ønskværdig ydeevne i minedriftsopgaver uden nogen form for supervision. Usuperviseret grafrepræsentationslæring er et mere gunstigt valg i mange tilfælde på grund af friheden fra etiketter, især når vi har til hensigt at drage fordel af store mængder umærkede data i naturen. For fuldt ud at arve den rige information i grafer udfører vi i dette papir grafindlejring baseret på gensidig informationsmaksimering (MI), inspireret af den empiriske succes af Deep Info-Max-metoden [ ], som opererer på billeder. For at opdage nyttige repræsentationer træner Deep InfoMax koderen til at maksimere MI mellem dens input (dvs. billederne) og output (dvs. de skjulte vektorer). Når man overvejer Deep InfoMax i grafdomænet, er den første sten, vi skal træde over, hvordan man definerer MI mellem grafer og skjulte vektorer, mens grafens topologi er mere kompliceret end billeder (se Figur En af udfordringerne er at sikre, at MI-funktionen mellem hver knudes skjulte repræsentation og dens naboskabsinputfunktioner adlyder den symmetriske egenskab, eller ækvivalent, er uændret af permutationer af naboskaberne. Som et nyligt arbejde, der overvejer MI, indlejrer Deep Graph Infomax (DGI) [ ] først en inputgraf og en tilsvarende korrupt graf, opsummerer derefter inputgrafen som en vektor via en udlæsningsfunktion, maksimerer endelig MI mellem denne opsummeringsvektor og skjulte repræsentationer ved at diskriminere inputgrafen (positiv prøve) fra den korrupte graf (negativ prøve). Figur giver et let forståeligt overblik over DGI. Maksimering af denne type MI viser sig at være ækvivalent med at maksimere den mellem inputknudens funktioner og skjulte vektorer, men denne ækvivalens gælder under flere forudindstillede betingelser, f.eks. skal udlæsningsfunktionen være injektiv, hvilket endnu ikke synes at være overdrevent begrænset i virkelige tilfælde. Selv vi kan garantere eksistensen af en injektiv udlæsningsfunktion ved et bestemt design, f.eks. den der bruges i DeepSets [ ], påvirkes udlæsningsfunktionens injektive evne også af, hvordan dens parametre trænes. Det vil sige, at en oprindeligt injektiv funktion stadig har risiko for at blive ikke-injektiv, hvis den trænes uden nogen ekstern supervision. Og hvis udlæsningsfunktionen ikke er injektiv, vil inputgrafinformationen i en opsummeringsvektor aftage, efterhånden som grafens størrelse øges. Desuden forbliver DGI i en grov graf/patch-niveau MI-maksimering. Derfor er der ingen garanti for, at koderen kan destillere tilstrækkelig information fra inputdata, da den aldrig omhyggeligt korrelerer skjulte repræsentationer med deres originale input. 20 1). 41 1 47 I dette papir foreslår vi en mere ligetil måde at betragte MI med hensyn til grafiske strukturer uden at bruge nogen udlæsningsfunktion og korruptionsfunktion. Vi udleder direkte MI ved at sammenligne inputtet (dvs. undergrafen bestående af inputnaboskabet) og outputtet (dvs. den skjulte repræsentation af hver knude) af koderen. Og interessant nok demonstrerer vores teoretiske afledninger, at den direkte formulerede MI kan nedbrydes til en vægtet sum af lokale MI'er mellem hver naboskabsfunktion og den skjulte vektor. På denne måde har vi nedbrudt inputfunktionerne og gjort MI-beregningen håndterbar. Desuden kan denne form for MI nemt opfylde den symmetriske egenskab, hvis vi justerer vægtenes værdier. Vi henviser til flere detaljer i § Da ovennævnte MI primært måles på niveauet af knudepunktsfunktioner, betegner vi det som Feature Mutual Information (FMI). 3.1. To resterende problemer vedrørende FMI: kombinationsvægtene er stadig ukendte, og den tager ikke hensyn til topologien (dvs. kantfunktionerne). For yderligere at adressere disse to problemer definerer vi vores måling af grafisk gensidig information (GMI) baseret på FMI. Specifikt anvender GMI en intuitiv værditildeling ved at sætte vægtene i FMI lig med nærheden mellem hver nabo og målnoden i repræsentationsrummet. For at bevare topologiinformationen korrelerer GMI yderligere disse vægte med kantfunktionerne via et yderligere gensidigt informationsterm. Den resulterende GMI er topologisk uændret og også beregnelig med Mutual Information Neural Estimation (MINE) [ ]. Hovedbidragene fra vores arbejde er som følger: 1. 2. 2 • : Vi generaliserer den konventionelle MI-estimering til grafdomænet og foreslår et nyt koncept af grafisk gensidig information (GMI) i overensstemmelse hermed. GMI er fri for den Begreber potentielle risiko forårsaget af udlæsningsfunktionen, da den overvejer MI mellem inputgrafer og indlejringer på højt niveau på en ligetil måde. • : Gennem vores teoretiske analyse giver vi en håndterbar og beregnelig form af GMI, der nedbryder den Algoritmer hele GMI til en vægtet sum af lokale MI'er. Med hjælp fra MINE-metoden kan GMI-maksimering nemt opnås på et knudepunktsniveau. • : Vi verificerer effektiviteten af GMI på flere populære knudepunktsklassifikations- og linkforudsigelsesopgaver, herunder både transduktive og induktive. Eksperimenterne demonstrerer, at vores metode leverer lovende ydeevne på en række benchmarks, og den overgår endda undertiden de superviserede modstykker. Eksperimentelle resultater 2 RELATERET ARBEJDE I overensstemmelse med fokusset i vores arbejde gennemgår vi kort det tidligere arbejde inden for de to følgende områder: estimering af gensidig information og neurale netværk til læring af repræsentation over grafer. 1. 2. . Da InfoMax-princippet [ ] går ind for at maksimere MI mellem input og output af neurale netværk, forsøger mange metoder som ICA-algoritmer [ , ] at anvende ideen om MI i usuperviseret funktionslæring. Ikke desto mindre kan disse metoder ikke let generaliseres til dybe neurale netværk på grund af vanskeligheden ved at beregne MI mellem højdimensionelle kontinuerlige variabler. Heldigvis gør Mutual Information Neural Estimation (MINE) [ ] estimering af MI på dybe neurale netværk mulig ved at træne et statistiknetværk som en klassifikator til at skelne prøver, der kommer fra den fælles distribution og produktet af marginalerne af to tilfældige variabler. Specifikt bruger MINE den eksakte KL-baserede formulering af MI, mens et ikke-KL alternativ, Jensen-Shannon-divergensen (JSD) [ ], kan bruges uden bekymring for den præcise værdi af MI. Estimering af gensidig information 3 1 21 2 30 . Med den hurtige udvikling af grafneurale netværk (GNN'er) er et stort antal grafrepræsentationslæringsalgoritmer baseret på GNN'er blevet foreslået i de seneste år, som udviser stærkere ydeevne end traditionelle random walk-baserede og faktorisationsbaserede indlejringsmetoder [ , , , , ]. Typisk kan disse metoder opdeles i superviserede og usuperviserede kategorier. Blandt dem er der en rig litteratur om superviseret repræsentationslæring over grafer [ , , , , ]. På trods af deres variation i netværksarkitektur opnår de empirisk succes med hjælp fra etiketter, der ofte ikke er tilgængelige i realistiske scenarier. I dette tilfælde har usuperviserede graflæringsmetoder [ , , ] bredere anvendelsespotentiale. Den velkendte metode er GraphSAGE [ ], et induktivt rammeværk til at træne GNN'er med en random walk-baseret målsætning i sin usuperviserede indstilling. Og for nylig anvender DGI [ ] ideen om MI-maksimering i grafdomænet og opnår stærk ydeevne i et usuperviseret mønster. DGI implementerer dog en grov maksimering (dvs. maksimering af MI på graf-/patchniveau), hvilket gør det vanskeligt at bevare den delikate information i inputgrafen. Desuden ser betingelsen på udlæsningsfunktionen, der bruges i DGI, ud til at være overdrevent begrænset i virkelige tilfælde. I modsætning hertil fokuserer vi på at fjerne begrænsningen af udlæsningsfunktionen og opnå grafisk gensidig informationsmaksimering på et knudepunktsniveau ved direkte at maksimere MI mellem input og output af koderen. Repræsentationer afledt af vores metode er mere sofistikerede i at bevare inputgrafinformation, hvilket sikrer dets potentiale for efterfølgende grafmineringsopgaver, f.eks. knudepunktsklassifikation, linkforudsigelse og anbefaling. Neurale netværk til grafrepræsentationslæring 6 15 33 34 39 7 9 25 40 48 11 16 41 16 41 3 GRAFISK GENSIDIG INFORMATION: DEFINITION OG MAKSIMERING Før vi går videre, præsenterer vi først de foreløbige begreber, der bruges i dette papir. Lad G = (V, E) betegne en graf med *N* knudepunkter *vi* ∈ V og kanter *eij* = (*vi* , *vj* ) ∈ E. Knudepunktsfunktionerne, med den antagede empiriske sandsynlighedsfordeling P, er givet ved *X* ∈ R*N* ×*D* = {*x* 1, · · · , *x* N } hvor *xi* ∈ R*D* betegner funktionen for knudepunkt *vi*. Adjacensmatricen *A* ∈ R*N* ×*N* repræsenterer kantforbindelser, hvor *Aij* associeret til kanten *eij* kan være et reelt tal eller en multidimensionel vektor1. Målet med grafrepræsentationslæring er at lære en koder *f* : R*N* ×*D* × R*N* ×*N* → R*N* ×*D*', så de skjulte vektorer *H* = {*h*1, · · · , *hN* } = *f* (*X* , *A*) angiver repræsentationer på højt niveau for alle knudepunkter. Kodningsprocessen kan omskrives i en knudepunkts-vis form. For at vise dette definerer vi *Xi* og *Ai* for knudepunkt *i* som henholdsvis funktionerne af dets naboer og den tilsvarende adjacensmatrix betinget af naboerne. Især består *Xi* af alle k-hop naboer af *vi* med *k* ≤ *l*, når koderen *f* er en *l*-lag GNN, og den indeholder selve knudepunktet *i*, hvis vi yderligere tilføjer selvsløjfer i adjacensmatricen. Her kalder vi undergrafen udvidet af *Xi* og *Ai* for en *supportgraf* for knudepunkt *i*, betegnet med G*i*. Med definitionen af supportgraf bliver kodningen for hver knude *hi* = *f* (G*i* ) = *f* (*Xi* , *Ai* ). I Deep InfoMax [ ] er træningsmålet for koderen at maksimere MI mellem dens input og output. MI estimeres ved at anvende et statistiknetværk som diskriminator til at klassificere prøver, der kommer fra den fælles distribution, og dem, der er trukket fra produktet af marginalerne. Naturligt, når man tilpasser ideen om Deep InfoMax til grafer, bør vi maksimere MI mellem repræsentationen *hi* og supportgrafen G*i* for hver knude. Vi betegner sådan grafisk MI som *I* (*hi* ; G*i* ). Det er dog ikke ligetil at definere I (hi ; Gi ). Vanskelighederne er: Vanskeligheder med at definere grafisk gensidig information. 20 • Den grafiske MI bør være uændret med hensyn til knudepunktsindekset. Med andre ord, vi bør have *I* (*hi* ; G*i* ) = *I* (*hi* ; G′*i* ), hvis G*i* og G′*i* er isomorfe med hinanden. • Hvis vi anvender MINE-metoden til MI-beregning, accepterer diskriminatoren i MINE kun input af en fast størrelse. Dette er endnu ikke muligt for G*i*, da forskellige G*i* normalt inkluderer forskellige antal knudepunkter og derfor har forskellige størrelser. For at komme uden om problemet med at definere grafisk gensidig information, begynder dette afsnit med at introducere begrebet Feature Mutual Information (FMI), der kun er baseret på knudepunktsfunktioner. Baseret på inspirationen fra nedbrydningen af FMI definerer vi derefter Graphical Mutual Information (GMI), som tager højde for både knudepunktsfunktionerne og 3.1 Feature Mutual Information Vi betegner den empiriske sandsynlighedsfordeling af knudepunktsfunktioner *Xi* som *p*(*Xi* ), sandsynligheden for *hi* som *p*(*hi* ), og den fælles fordeling som *p*(*hi* , *Xi* ). Ifølge informationsteorien er MI mellem *hi* og *Xi* defineret som Interessant nok har vi følgende sætning om gensidig informationsnedbrydning til beregning af *I* (*hi* ; *Xi* ). Sætning 1 (Nedbrydning af Gensidig Information). (*hi* |*Xi* ) (*hi* ; *Xi* ) Hvis den betingede sandsynlighed p er multiplikativ (se definitionen af multiplikativ i [ ]), kan den globale gensidige information I 36 defineret i ligning. (1) nedbrydes som en vægtet sum af lokale MI'er, nemlig, ≤ ≤ 1 hvor, xj er den j-te nabo til knudepunkt i, in er antallet af alle elementer i Xi, og vægten wij opfylder 1 wij for hver j. For at bevise ovenstående sætning introducerer vi først to lemmaer og en definition. Lemma 1. For vilkårlige tilfældige variabler X, Y og Z gælder Med nedbrydningen i Sætning kan vi beregne højre side af ligning via MINE, da input til diskriminatoren nu bliver parrene af (*hi* , *xj* ), hvis størrelse altid holdes den samme (dvs. *D*' × *D*). Desuden kan vi justere vægtene for at afspejle den isomorfe transformation af inputgrafer. For eksempel, hvis *Xi* kun indeholder en-hop naboer af knudepunkt *i*, vil det at sætte alle vægte til at være identiske føre til samme MI for inputknudepunkterne i forskellige ordener. 1, (2) På trods af visse fordele ved nedbrydningen er det svært at karakterisere de præcise værdier af vægtene, da de er relateret til værdierne af *I* (*hi* ; *xj* ) og deres underliggende sandsynlighedsfordelinger. En triviel måde er at sætte alle vægte til , derefter maksimerer højre side af ligning ækvivalens med at maksimere den nedre grænse af *I* (*hi* ; *Xi* ), hvorved den sande FMI også maksimeres til en vis grad. Udover denne metode giver vi yderligere en mere forbedret løsning ved at betragte vægtene som trænbare opmærksomheder, hvilket er emnet i næste afsnit. 1 (2) Inspireret af nedbrydningen i Sætning forsøger vi at konstruere trænbare vægte fra den anden side af grafer (dvs. 3.2 Topologi-Aware Mutual Information 1, topologisk synspunkt), så værdierne af *wij* kan være mere fleksible og fange grafens iboende egenskaber. Til sidst udleder vi definitionen af Grafisk Gensidig Information (GMI). Definition 2 (Grafisk Gensidig Information). G = (*X* , *A* ) MI mellem den skjulte vektor h og dens supportgraf defineres som hvor definitionerne af både xj og in er de samme som i Sætning 1, aij er kantvægten/funktionen i adjacensmatricen A, og σ (·) er en sigmoidfunktion. Intuitivt måler vægten wij i den første term af ligning (10) den håndteret i eksperimenter er uvægtede. Formelt beregner vi I (wij ; aij ) = aijloдwij + (1 − aij )loд(1 − wij ). (12) Ved at maksimere I (hi ; Gi ) med summen af ligning (11) og ligning (12) over alle skjulte vektorer H, ankommer vi til vores komplette målsætningsfunktion for bidraget af en lokal MI til den globale. Vi implementerer bidraget af I (hi ; xj ) ved ligheden mellem repræsentationerne hi og hj (dvs. wij = σ (hThj )). Samtidig maksimerer termen I (wij ; aij ) MI mellem wij og kantvægten/funktionen af inputgrafen (dvs. aij ) for at tvinge wij til at overholde topologiske relationer. I denne forstand vil graden af bidraget være i overensstemmelse med nærheden i topologisk struktur, hvilket generelt accepteres som et faktum, at wij kan være større, hvis knudepunkt j er "tættere" på knudepunkt i og mindre ellers. Denne strategi kompenserer for fejlen, at FMI kun fokuserer på knudepunktsfunktioner og får lokale MI'er til at bidrage adaptivt til den globale. For bedre at forstå ideen om opmærksomhed i denne strategi kan du referere til den opmærksomhedsbaserede GCN [40]. Bemærk, at definitionen af ligning (10) er anvendelig for generelle tilfælde. For visse specifikke situationer kan vi let modificere ligning (10) for effektivitet. For eksempel, når vi beskæftiger os med uvægtede grafer (nemlig at kantværdien er 1, hvis forbundet, og 0 ellers), kan vi erstatte den anden MI-term I (wij ; aij ) med et negativt krydsentropitab for at opnå en mere effektiv beregning. Vi henviser til flere detaljer i næste afsnit. Samlet set er der flere fordele ved definitionen af ligning (10). For det første er denne type MI uændret af den isomorfe transformation af inputgrafer. For det andet er den beregningsmæssigt mulig, da hver komponent på højre side kan estimeres af MINE. Endnu vigtigere er GMI mere kraftfuld end DGI til at fange original inputinformation på grund af dens eksplicitte korrelation mellem skjulte vektorer og inputfunktioner af både knudepunkter og kanter på et finkornet knudepunktsniveau. 3.3 Maksimering af GMI Nu maksimerer vi direkte højre side af ligning med hjælp fra MINE. Bemærk, at MINE estimerer en nedre grænse for MI med Donsker-Varadhan (DV) [ ] repræsentationen af KL-divergensen mellem den fælles distribution og produktet af marginalerne. Da vi fokuserer mere på at maksimere MI snarere end at opnå dens specifikke værdi, kan andre ikke-KL alternativer som Jensen-Shannon MI estimator (JSD) [ ] og Noise-Contrastive estimator (infoNCE) [ ] anvendes til at erstatte den. Baseret på de eksperimentelle resultater og analyse i [ ], tyder vi på JSD-estimatoren i dette papir af hensyn til effektivitet og effektivitet, da infoNCE-estimatoren er følsom over for negative samplingstrategier (antallet af negative prøver), og derfor kan blive en flaskehals for store datasæt med et fast tilgængeligt hukommelse. Tværtimod gør JSD-estimatorens ufølsomhed over for negative samplingstrategier og dens anerkendte ydeevne på mange opgaver den mere egnet til vores opgave. Specifikt beregner vi *I* (*hi* ; *xj* ) i den første term af ligning ved (10) 10 30 31 20 (10) hvor D*w* : *D* × *D*' → R er en diskriminator konstrueret af et neuralt netværk med parameter *w*. *x j* er en negativ prøve trukket fra P = P, og *sp*(*x*) = *loд*(1 + *ex*) betegner soft-plus-funktionen. Som nævnt i § maksimerer vi *I* (*wij* ; *aij* ) ved at beregne dens krydsentropi i stedet for at bruge JSD-estimatoren, da de grafer, vi håndterede i eksperimenter, er uvægtede. Formelt beregner vi 3.2, Ved at maksimere I (hi ; Gi ) med summen af ligning (11) og ligning (12) over alle skjulte vektorer H, ankommer vi til vores komplette målsætningsfunktion for GMI-optimering. Desuden kan vi yderligere tilføje afvejningsparametre for at balancere ligning (11) og ligning (12) for større fleksibilitet. 4 EKSPERIMENTER I dette afsnit evaluerer vi empirisk ydeevnen af GMI på to almindelige opgaver: knudepunktsklassifikation (transduktiv og induktiv) og linkforudsigelse. En yderligere relativt fair sammenligning mellem GMI og to andre usuperviserede algoritmer (EP-B og DGI) demonstrerer yderligere dens effektivitet. Vi giver også visualisering af t-SNE-plot og analyserer indflydelsen af modeldybde. 4.1 Datasæt For at vurdere kvaliteten af vores til