En ny måde at træne AI på grafdata uden opsyn

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 overflodige information fra grafstrukturerede data til indlejringsrummet på en usuperviseret måde. Til dette formål foreslår vi et nyt koncept, Graphical Mutual Information (GMI), til at måle korrelationen mellem inputgrafer og skjulte repræsentationer på højt niveau. GMI generaliserer ideen om konventionelle gensidige informationberegninger fra vektorrummet til grafdomænet, hvor måling af gensidig information fra to aspekter af nodetræk og topologisk struktur er uundværlig. GMI udviser flere fordele: For det første er den invariant over for 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 trænet ved at maksimere GMI mellem input og output af en grafisk neural encoder. Omfattende eksperimenter med transdiktive såvel som induktive nodeklassifikation og link-forudsigelse demonstrerer, at vores metode overgår state-of-the-art usuperviserede modparter, og endda nogle gange overstiger ydeevnen af superviserede. 1 INTRODUKTION For at opnå pålidelig kvantitativ analyse for forskellige informationsnetværk er læring af repræsentationer 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 mange læringsopgaver, såsom nodeklassifikation [ , , ], link-forudsigelse [ , , ], grafjustering [ , , ], molekylær generering [ , , ], for blot at nævne nogle få. Selvom de gør 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 annotering eller betaling for tilladelse, og er endda umulig at opnå på grund af fortrolighedspolitikken. Ikke at nævne, at pålideligheden af givne etiketter undertiden er tvivlsom. Derfor bliver det nødvendigt at opnå grafrepræsentation af høj kvalitet uden supervision for mange praktiske tilfælde, 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 en enorm mængde af både indholds- og koblingsinformation eksisterer. For eksempel inkluderer data på mange sociale platforme som Twitter, Flickr og Facebook brugerfunktioner, *f.eks.*, grundlæggende personlige detaljer, tekster, billeder, IP, og deres relationer, *f.eks.*, at købe den samme vare, at være venner. Disse rige indholdsdata er tilstrækkelige til at understøtte efterfølgende minedriftsopgaver uden yderligere vejledning: hvis to enheder udviser ekstrem lighed i funktioner, er der en høj sandsynlighed for et link mellem dem (link-forudsigelse), og de tilhører sandsynligvis den samme kategori (klassifikation); hvis to enheder begge linker til den 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 ønskelig ydeevne i minedriftsopgaver uden nogen form for supervision. Usynlig 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 en stor mængde umærket 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 encoderen 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 nodes skjulte repræsentation og dens nabofunktioner adlyder den symmetriske egenskab, eller ækvivalent, at være invariant over for permutationer af nabolagene. 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 aflæsningsfunktion, og maksimerer til sidst MI mellem denne summervektor og skjulte repræsentationer ved at diskriminere inputgrafen (positiv prøve) fra den korrupte graf (negativ prøve). Figur giver et letforståeligt overblik over DGI. Maksimering af denne form for MI er bevist at være ækvivalent med at maksimere den mellem inputnods træk og skjulte vektorer, men denne ækvivalens holder under flere forudindstillede betingelser, *f.eks.*, at aflæsningsfunktionen skal være injektiv, hvilket endnu synes at være overbegrænset i virkelige tilfælde. Selv hvis vi kan garantere eksistensen af en injektiv aflæsningsfunktion ved visse designs, *f.eks.*, den der bruges i DeepSets [ ], påvirkes aflæ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 ekstern supervision. Og hvis aflæsningsfunktionen ikke er injektiv, vil inputgrafinformationen i en summervektor 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 encoderen 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 aflæsningsfunktion eller korruptionsfunktion. Vi udleder direkte MI ved at sammenligne input ( *dvs.*, subgrafen bestående af inputnabolaget) og output ( *dvs.*, den skjulte repræsentation af hver node) af encoderen. Og interessant nok viser vores teoretiske afledninger, at den direkte formulerede MI kan nedbrydes til en vægtet sum af lokale MI'er mellem hver nabofunktion og den skjulte vektor. På denne måde har vi nedbrudt inputfunktionerne og gjort MI-beregningen håndterbar. Desuden kan denne form for MI let tilfredsstille den symmetriske egenskab, hvis vi justerer vægtenes værdier. Vi henviser flere detaljer til § Da den ovennævnte MI hovedsageligt måles på niveauet af nodetræk, betegner vi den som Feature Mutual Information (FMI). 3.1. To resterende problemer om FMI: **1.** kombinationsvægtene er stadig ukendte, og **2.** den tager ikke topologien ( *dvs.*, kantfunktionerne) i betragtning. For yderligere at adressere disse to problemer definerer vi vores Graphical Mutual Information (GMI) måling 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ålknuden i repræsentationsrummet. For at bevare topologiinformationen korrelerer GMI yderligere disse vægte med inputkantfunktionerne via en yderligere gensidig informationsterm. Den resulterende GMI er topologisk invariant og også beregnelig med Mutual Information Neural Estimation (MINE) [ ]. Hovedbidragene fra vores arbejde er som følger: 2 • ***Koncepter***: Vi generaliserer den konventionelle MI-estimering til grafdomænet og foreslår et nyt koncept af Graphical Mutual Information (GMI) tilsvarende. GMI er fri for den potentielle risiko forårsaget af aflæsningsfunktionen, da den betragter MI mellem inputgrafer og indlejringer på højt niveau på en ligetil måde. • ***Algoritmer***: Gennem vores teoretiske analyse giver vi en håndterbar og beregnelig form af GMI, der nedbryder den hele GMI til en vægtet sum af lokale MI'er. Med hjælp fra MINE-metoden kan GMI-maksimering let opnås på nodeniveau. • ***Eksperimentelle fund***: Vi verificerer effektiviteten af GMI på flere populære nodeklassifikations- og link-forudsigelsesopgaver, herunder både transdiktive og induktive. Eksperimenterne viser, at vores metode leverer lovende ydeevne på en række benchmarks, og den overgår endda nogle gange de superviserede modparter. 2 RELATERET ARBEJDE I overensstemmelse med fokusset i vores arbejde gennemgår vi kort tidligere arbejde inden for de to følgende områder: **1.** estimering af gensidig information og **2.** neurale netværk til læring af repræsentation over grafer. . Som InfoMax-princippet [ ] går ind for at maksimere MI mellem input og output af neurale netværk, forsøger mange metoder såsom ICA-algoritmer [ , ] at anvende ideen om MI i usuperviseret træk-læ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) [ ] estimeringen 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 fordeling 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 om den præcise værdi af MI. Estimering af gensidig information 3 1 21 2 30 . Med den hurtige udvikling af grafneurale netværk (GNNs) er et stort antal grafrepræsentationslæringsalgoritmer baseret på GNNs blevet foreslået i de seneste år, som udviser stærkere ydeevne end traditionelle random walk-baserede og faktorisering-baserede indlejringsmetoder [ , , , , ]. Typisk kan disse metoder opdeles i superviserede og usuperviserede kategorier. Blandt dem er der en rig litteratur om superviseret repræsentationslæring på grafer [ , , , , ]. På trods af deres variationer 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 grafiske læringsmetoder [ , , ] et bredere anvendelsespotentiale. Den velkendte metode er GraphSAGE [ ], et induktivt framework til at træne GNN'er via en random walk-baseret målsætning i dens usuperviserede indstilling. Og for nylig anvender DGI [ ] ideen om MI-maksimering til 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/patch-niveau), hvilket gør det vanskeligt at bevare den sarte information i inputgrafen. Desuden synes betingelsen på aflæsningsfunktionen, der bruges i DGI, at være overbegrænset i virkelige tilfælde. I modsætning hertil fokuserer vi på at fjerne begrænsningen af aflæsningsfunktionen og opnå grafisk gensidig informationsmaksimering på nodeniveau ved direkte at maksimere MI mellem input og output af encoderen. Repræsentationer afledt af vores metode er mere sofistikerede i at bevare inputgrafinformation, hvilket sikrer dens potentiale for efterfølgende graf-minedriftsopgaver, *f.eks.*, nodeklassifikation, link-forudsigelse 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, giver vi først de foreløbige begreber, der bruges i dette papir. Lad G = (V, E) betegne en graf med *N* knuder *vi* ∈ V og kanter *eij* = (*vi* , *vj*) ∈ E. Nodens træk, med antaget empirisk sandsynlighedsfordeling P, er givet ved *X* ∈ R*N* ×*D* = {*x* 1, · · · , *x* N } hvor *xi* ∈ R*D* betegner trækket for knude *vi* . Adjacensmatricen *A* ∈ R*N* ×*N* repræsenterer kantforbindelser, hvor *Aij* tilknyttet kant *eij* kan være et reelt tal eller en flerdimensionel vektor1. Målet med grafrepræsentationslæring er at lære en encoder *f* : R*N* ×*D* × R*N* ×*N* → R*N* ×*D*′, således at de skjulte vektorer *H* = {*h*1, · · · , *hN*} = *f* (*X* , *A*) indikerer repræsentationer på højt niveau for alle knuder. Kodningsprocessen kan omskrives i en knude-wise form. For at vise dette definerer vi *Xi* og *Ai* for knude *i* som henholdsvis træk af dens 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 encoderen *f* er en *l*-lags GNN, og den indeholder knude *i* selv, hvis vi yderligere tilføjer selv-loops i adjacensmatricen. Her kalder vi subgrafen udvidet af *Xi* og *Ai* som en *supportgraf* for knude *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 encoderen at maksimere MI mellem dens input og output. MI estimeres ved at anvende et statistiknetværk som en diskriminator til at klassificere prøver, der kommer fra den fælles fordeling, 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 ). Svårhederne er: Sværheder ved at definere grafisk gensidig information. 20 • Den grafiske MI bør være invariant med hensyn til knudeindekset. Med andre ord bør vi have *I* (*hi* ; G*i*) = *I* (*hi* ; G′*i*), hvis G*i* og G′*i* er isomorfe til hinanden. • Hvis vi adopterer 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 knuder og derfor har forskellige størrelser. For at komme uden om problemet med at definere grafisk gensidig information, begynder dette afsnit med at introducere konceptet Feature Mutual Information (FMI), der kun er afhængig af nodetræk. Baseret på dekompositionen af FMI definerer vi derefter Graphical Mutual Information (GMI), som tager både nodetræk og 3.1 GENSIDIG INFORMATION OM TRÆK Vi betegner den empiriske sandsynlighedsfordeling af nodetræk *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 dekomposition af gensidig information til beregning af *I* (*hi* ; *Xi*). Sætning 1 (Dekompsoition af Gensidig Information). *Hvis den betingede sandsynlighed p*(*hi* |*Xi*) *er multiplikativ (se definitionen af multiplikativ i [* ]), kan den globale gensidige information I* (*hi* ; *Xi*) *defineret i ligning.* *dekomponeres som en vægtet sum af lokale MI'er, nemlig,* 36 (1) *hvor, xj* *er den j-te nabo af knude i, in* *er antallet af alle elementer i Xi*, og vægten wij opfylder ≤ *wij* ≤ 1 *for hver j.* 1 For at bevise ovenstående sætning introducerer vi først to lemmaer og en definition. Lemma 1. *For enhver tilfældig variabel X, Y og Z, har vi* Med dekompositionen 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 holder sig den samme (*dvs.*, *D*′ -med- *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 knude *i*, vil indstilling af alle vægte til at være identiske føre til den samme MI for inputknuder i forskellig rækkefølge. 1, (2) På trods af visse fordele ved dekompositionen 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 ækvivalerer maksimering af højre side af ligning til at maksimere den nedre grænse af *I* (*hi* ; *Xi*), hvorved den sande FMI også maksimeres til en vis grad. Ud over 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 underafsnit. 1 (2) Inspireret af dekompositionen i Sætning forsøger vi at konstruere trænbare vægte fra den anden side af grafer ( *dvs.*, 3.2 Topologi-bevidst gensidig information 1, topologisk synspunkt), så værdierne af *wij* kan være mere fleksible og fange grafens iboende egenskaber. Ultimativt udleder vi definitionen af Graphical Mutual Information (GMI). Definition 2 (Grafisk Gensidig Information). *MI mellem den skjulte vektor h og dens supportgraf* G = (*X* , *A*) *er defineret som* hvor definitionerne af både xj og in er som samme som 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) bidraget fra en lokal MI til den globale. Vi implementerer bidraget fra I (hi ; xj ) ved ligheden mellem repræsentationer 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 håndhæve wij til at overholde topologiske relationer. I denne forstand vil graden af bidraget være konsistent med nærheden i topologisk struktur, hvilket almindeligvis accepteres som et faktum, at wij kan være større, hvis knude j er "tættere" på knude i og mindre ellers. Denne strategi kompenserer for fejlen, at FMI kun fokuserer på nodetræk og gør det muligt for lokale MI'er 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. 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 håndterer uvægtede grafer (nemlig kantværdien er 1, hvis forbundet, og 0 ellers), kan vi erstatte den anden MI-term I (wij ; aij ) med et negativt krydsentropi-tab. Minimering af krydsentropien bidrager også til MI-maksimering, og den leverer en mere effektiv beregning. Vi henviser flere detaljer i næste afsnit. Samlet set er der flere fordele ved definitionen af ligning (10). For det første er denne form for MI invariant over for 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 kraftigere end DGI i at fange original inputinformation på grund af dens eksplicitte korrelation mellem skjulte vektorer og inputtræk af både knuder og kanter på en fin-kornet nodeniveau. 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 af MI med Donsker-Varadhan (DV) [ ] repræsentationen af KL-divergensen mellem den fælles fordeling og produktet af marginalerne. Da vi fokuserer mere på at maksimere MI i stedet for at opnå dens specifikke værdi, kan andre ikke-KL alternativer som Jensen-Shannon MI estimator (JSD) [ ] og Noise-Contrastive estimator (infoNCE) [ ] bruges til at erstatte den. Baseret på de eksperimentelle fund og analyse i [ ], tyr vi til JSD-estimatoren i dette papir af hensyn til effektivitet og effektivitet, da infoNCE-estimatoren er følsom over for negative stikprøve-strategier (antallet af negative stikprøver), og dermed 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 stikprøve-strategier og dens respektable ydeevne på mange opgaver den mere velegnet 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 stikprø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 graferne, vi behandlede i eksperimenterne, 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 (12) for større fleksibilitet. 4 EKSPERIMENTER I dette afsnit evaluerer vi empirisk ydeevnen af GMI på to almindelige opgaver: nodeklassifikation (transdiktiv og induktiv) og link-forudsigelse. En yderligere relativt fair sammenligning mellem GMI og to andre usuperviserede algoritmer (EP-B og DGI) udstiller yderligere dens effektivitet. Vi giver også visualisering af t-SNE-plots og analyserer indflydelsen af modeldybde. 4.1 Datasæt For at vurdere kvaliteten af vores tilgang i hver opgave anvender vi 4 eller 5 almindeligt anvendte benchmarkdatasæt fra tidligere arbejde [ , , Detaljerede statistikker er givet i Tabel 16 25 41]. 1. I klassifikationsopgaven er Cora, Citeseer og PubMed [ ]2 citationnetværk, hvor knuder svarer til dokumenter og kanter repræsenterer citationer. Hvert dokument er forbundet med en bag-of-words repræsentationsvektor og tilhører en af de foruddefinerede klasser. I overensstemmelse med den transdiktive opsætning i [ , ], udføres træning på alle knuder, og 1000 testknuder bruges til evaluering. Reddit3 er et stort socialt netværk bestående af talrige indbyrdes forbundne Reddit-opslag oprettet i september 2014 [ ]. Opslag behandles som knuder, og kanter betyder, at den samme bruger kommenterer. 38 25 41 16 ![ Tabel 1: Statistik over datasættene brugt i eksperimenter. ](https://cdn.hackernoon.com/images/InxBRjRIs6M1kdhuWcyNHiiUrxm1-eph3eec.jpeg) Klasseetiketten er fællesskabet, og vores mål er at forudsige, hvilket fællesskab forskellige opslag tilhører. PPI3 er et protein-protein interaktionsdatasæt, der inkluderer flere grafer relateret til forskellige humane væv [ ]. Positionsgen sæt, motivgen sæt og immunologiske signaturer betragtes som nodetræk, og hver knude har i alt 121 etiketter givet af genontologisæt. Klassifikation af proteinfunktioner, der kan tilhøre flere genrer på tværs af forskellige PPI-grafer, er vores mål. I overensstemmelse med den induktive opsætning i [ ], på Reddit, føder vi opslag lavet i de første 20 dage ind i modellen til træning, mens resten bruges til test (med 30% brugt til validering); på PPI er der 20 grafer til træning, 2 til validering og 2 til test. Det skal understreges, at for Reddit og PPI udføres test på usete (utrænede) knuder og grafer, mens de tre første datasæt bruges til transdiktiv læring. 52 16 I link-forudsigelsesopgaven er BlogCatalog4 et socialt blog-websted, hvor bloggere følger hinanden og registrerer deres blogs under foruddefinerede 6 kategorier. Bloggernes tags bruges som nodetræk. Flickr4 er et billeddelingswebsted, hvor brugere interagerer med andre og danner et socialt netværk. Brugere uploader billeder med 9 foruddefinerede klasser og vælger tilknyttede tags for at afspejle deres interesser, hvilket giver attributinformation. Beskrivelsen af Cora og PPI udelades af pladshensyn. I overensstemmelse med de eksperimentelle indstillinger og evalueringsmetrikker i, givet en graf med visse dele af fjernede kanter, sigter vi mod at forudsige disse manglende links. For Cora, BlogCatalog og Flickr sletter vi tilfældigt 20%, 50% og 70% af kanterne, mens vi sikrer, at resten af netværket opnået efter kantfjernelsen er forbundet, og bruger det beskadigede netværk til træning. Omkring PPI behandler vi direkte en del af kanterne, der ikke er set under træningen, som forudsigelsesmål i stedet for manuel kantfjernelse. 4.2 Eksperimentelle indstillinger Vi tyrer til en standard Graph Convolutional Network (GCN) model med følgende lagvise propagationsregel som encoder for både klassifikations- og link-forudsigelsesopgaver: Encoder-design. Hvor Aˆ = D -1/2AD - 1/2A = A + In, Dii = Aij, H (1) og H (I + 1) er input- og outputmatricerne for den *l*-te lag, *W* (*l*) er en lag-specifik træbar vægtmatrix. Her er den ikke-lineære transformation *σ*, vi anvendte, PReLU-funktionen (parametrisk ReLU) [ ]. Det skal anerkendes, at for knude *i* indeholder nabolaget *Xi* i dens supportgraf Gi knude *i* selv, da selv-loops indsættes gennem A¯ . 17 For at være mere specifik, er encoderen vi brugte på Citeseer og PubMed en et-lags GCN med outputdimensionen D' = 512. Og på Cora, Reddit, BlogCatalog, Flickr og PPI anvender vi en to-lags GCN som vores encoder. Her har vi skjulte dimensioner som D' = 512 i hvert GCN-lag. Bemærk, at brugen af en lignende GCN-encoder til både transdiktive og induktive klassifikationsopgaver gør vores foreslåede metode lettere at følge og skalere til store netværk end DGI, da DGI skal designe varierende encodere til at tilpasse sig forskellige læringsopgaver, især encoderne brugt i induktive opgaver er for komplicerede og indviklede, hvilket ikke er venligt for praktiske anvendelser. Diskriminatoren i ligning scorer input-output funktionsparrene gennem en simpel bilineær funktion, hvilket ligner diskriminatoren brugt i Diskriminator-design. (11) : hvor Θ repræsenterer en træbar scoringsmatrix, og aktiveringsfunktionen *σ*, vi anvendte, er sigmoid med det formål at konvertere scorer til sandsynligheder for (*h*, *x*) som et positivt eksempel. Faktisk, for vægten *wij* af den første term i ligning , har vi to måder at få dens værdi i eksperimenter. Den første er at beholde *wij* = *σ* (*h*T*hj*), hvilket får lokale MI'er til at bidrage adaptivt til den globale, og vi betegner denne variant GMI-adaptiv. Implementeringsdetaljer. (10) Den anden er at lade *wij* = , *dvs.*, venstre endepunkt af intervallet, hvor *wi* *j* tilhører (se Sætning hvilket betyder, at bidraget fra hver lokal MI er lig med, og vi betegner denne variant GMI-gennemsnit. Her er både GMI-gennemsnit og GMI-adaptiv inkluderet i omfanget af sammenligning med baselines. 1/in 1), Alle eksperimenter er implementeret i PyTorch med Glorot-initialisering og udført på en enkelt Tesla P40 GPU. I forbehandling udfører vi række-normalisering på Cora, Citeseer, PubMed, BlogCatalog og Flickr i overensstemmelse med, og anvender behandlingsstrategien i på Reddit og PPI. Under træning bruger vi Adam Optimizer med en indledende træning på 0,001 på alle syv datasæt. Foreslået af anvender vi en tidlig stopstrategi med et vinduesstørrelse på 20 på Cora, Citeseer og PubMed, mens modellen trænes i et fast antal epoker på de induktive datasæt (20 på Reddit, 50 på PPI). Antallet af negative prøver er sat til 5. På grund af den store skala af Reddit og PPI, er vi nødt til at bruge subsampling-færdigheden introduceret i [ ] for at få dem til at passe ind i GPU-hukommelsen. Mere specifikt vælges en minibatch af 256 knuder først, og derefter sampler vi for hver valgte knude uniformt 8 og 5 naboer på dens første og anden niveau nabolag, henholdsvis. Vi anvender en-hop nabolaget til at konstruere supportgrafen i eksperimenter og udnytter *XW*(0) (*dvs.*, en komprimeret inputfunktion) til at beregne FMI, da brugen af den oprindelige inputfunktion *X* forårsager GPU-hukommelsesoverløb. Afvejningsparametrene justeres i intervallet for at balancere ligning og ligning . Batch Normalization-strategien [ ] anvendes til at træne vores model på Reddit og PPI. 16 (11) (12) 22 Til klassifikationsopgaven giver vi de lærte indlejringer på tværs af træningssættet til en logistisk regressionsklassifikator og giver resultaterne på testknuderne [ , ]. Specifikt, i transdiktiv læring, anvender vi den gennemsnitlige klassifikationsnøjagtighed efter 50 kørsler til at evaluere ydeevnen, mens den mikro-gennemsnitlige F1-score gennemsnitliggjort efter 50 kørsler bruges i induktiv læring. Og for PPI, foreslået af [ ], standardiserer vi de lærte indlejringer, før vi fører dem ind i den logistiske regressionsklassifikator. Til link-forudsigelsesopgaven er kriteriet, vi anvendte, AUC, som er arealet under ROC-kurven. De negative prøver involveret i beregningen af AUC genereres ved tilfældigt at vælge et lige antal knudepar uden forbindelser i den originale graf. Jo tættere AUC-scoren nærmer sig 1, jo bedre er algoritmens ydeevne. Ligeledes rapporterer vi AUC-scoren gennemsnitliggjort efter 10 kørsler. Evalueringsmetrikker. 16 25 41 4.3 Klassifikation Tabel rapporterer den gennemsnitlige klassifikationsnøjagtighed af vores metode og andre baselines på transdiktive opgaver. Her tages resultater for EP-B [ ], DGI [ ], Planetoid-T [ ], GAT [ ] samt GWNN [ ] fra deres originale papirer, og resultater for DeepWalk [ ], LP (Label Propagation) [ ] og GCN [ ] kopieres fra Kipf & Welling [ ]. Som for rå træk, fodrer vi dem ind i en logistisk regressionsklassifikator til træning og giver resultaterne på testtrækkene5. Selvom vi giver eksperimentelle resultater af både superviserede og usuperviserede metoder, fokuserer vi i dette papir mere på at sammenligne med usuperviserede, hvilket er i overensstemmelse med vores opsætning. Transdiktiv læring. 2 11 41 45 40 44 33 51 25 25 Som det kan observeres, opnår vores foreslåede GMI-gennemsnit og GMI-adaptiv, sammenlignet med andre usuperviserede metoder, den bedste klassifikationsnøjagtighed på tværs af alle tre datasæt. Vi anser denne stærke ydeevne for at drage fordel af ideen om at forsøge direkte at maksimere grafisk MI mellem input- og outputpar af encoderen E på en fin-kornet nodeniveau. Derfor bevarer den kodede repræsentation maksimalt informationen om nodetræk og topologi i G, hvilket bidrager til klassifikation. I modsætning hertil ignorerer EP-B den underliggende information mellem inputdata og lærte repræsentationer, og DGI forbliver i en graf/patch-niveau MI-maksimering, hvilket begrænser deres evne til at bevare og udtrække den originale inputinformation til indlejringsrummet. Dermed lidt svag ydeevne på klassifikationsopgaver. Desuden, uden vejledning fra etiketter, udviser vores metode sammenlignelige resultater med nogle superviserede modeller som GCN og GAT, endda bedre resultater end dem på Citeseer og PubMed. Vi mener, at repræsentationer lært via GMI-maksimering mellem input og output arver den rige information i graf G, som er nok til klassifikation. Mere bemærkelsesværdigt er, at mange tilgængelige etiketter også gives baseret på informationen i G. Så at bevare så meget information som muligt fra input kan kompensere for informationen givet af etiketten til en vis grad, hvilket understøtter GMI's ydeevne i efterfølgende graf-minedriftsopgaver. Det kan hævdes, at læring fra originale input uden etiketter lover potentialet for højere kvalitetsrepræsentationer end det superviserede mønster, da den ekstreme sparsitet af træningsetiketter kan lide under truslen om overfitting, eller korrektheden af givne etiketter måske ikke er pålidelig. Tabel opsummerer også de mikro-gennemsnitlige F1-scorer for GMI og andre baselines på Reddit og PPI. Vi citerer resultaterne af DGI, GAT, FastGCN [ ] og GaAN [ ] i deres originale papirer, mens resultaterne for de resterende syv sammenlignede metoder er udtrækket fra Hamilton et al. [ ] (her genbruger vi de usuperviserede GraphSAGE-resultater for at matche vores opsætning). Ligeledes er sammenligningen med usuperviserede algoritmer fokus for vores arbejde. Induktiv læring. 2 7 48 16 GMI-gennemsnit og GMI-adaptiv overgår succesfuldt alle andre konkurrerende usuperviserede algoritmer på Reddit og PPI, hvilket bekræfter effektiviteten af GMI-maksimering inden for induktiv klassifikation (generalisering til usete knuder). Interessant nok er resultatet af vores metode på Reddit konkurrencedygtigt med nogle avancerede superviserede modeller, men situationen på PPI er ret anderledes. Efter at have udført yderligere analyse bemærker vi, at 42% af knuderne har nul træk-værdier i PPI, hvilket betyder, at trækmatricen X er meget sparsom [ ]. I dette tilfælde begrænser direkte og udelukkende afhængighed af inputgrafen G = (*X* , *A*) ydeevnen af usuperviserede tilgange, herunder DGI og vores metode, mens læring på en superviseret måde udviser meget bedre ydeevne på grund af den supplerende information bragt af yderligere etiketter. 16 Ifølge Tabel opnår de to varianter af GMI (GMI-gennemsnit og GMI-adaptiv), som bruger forskellige strategier til at måle bidraget fra hver lokal MI (detaljer i § konkurrencedygtige resultater med hinanden, men GMI-adaptiv udviser lidt svagere ydeevne end GMI-gennemsnit. Gennem yderligere analyse antager vi, at det kan skyldes træningsvanskeligheder forårsaget af adaptiv læring. Måske kan ydeevnen af GMI-adaptiv forbedres med hjælp fra en avanceret træningsstrategi. I denne forstand er GMI-gennemsnit mere praktisk og anvendelig, og kan derfor betragtes som en repræsentant i praksis. Evaluering af to varianter af GMI. 2 4.2), 4.4 Effektivitet af Målsætningsfunktion For yderligere at klarlægge effektiviteten af at maksimere grafisk MI i usuperviseret grafrepræsentationslæring og give en relativt fair sammenligning med DGI og EP-B (to usuperviserede algoritmer), erstatter vi vores målsætningsfunktion med deres tabsfuktioner, henholdsvis, mens vi holder andre eksperimentelle indstillinger uændrede. Tabel viser resultaterne under den transdiktive og induktive opsætning. Som det kan observeres, opnår GMI (GMI-gennemsnit og GMI-adaptiv) stærkere ydeevne på tværs af alle fem datasæt, hvilket afspejler, at DGI og EP-B mangler visse overvejelser i grafrepræsentationslæringsopgaven. Specifikt pålægger EP-B tab kun begrænsninger på hver knude og dens naboer på outputniveau (indlejringsrummet), det ignorerer interaktionen mellem input- og outputpar af encoderen, hvilket resulterer i dens dårlige evne til at bevare den gyldige information i G. For DGI, selvom den korrelerer skjulte repræsentationer med deres originale inputtræk implicit, diskuterer den MI på graf/patch-niveau, hvilket er noget groft. 3 Interessant nok opnår vores FMI (uden topologiinformation) mere signifikante forbedringer med stigningen i grafstørrelse sammenlignet med DGI. Vi tilskriver denne opdagelse, at ydeevnedegraderingen af aflæsningsfunktionen får DGI til at miste visse nyttige oplysninger til nodeklassifikationsopgaver med stigningen i grafstørrelse, selvom den udviser god ydeevne på små grafer som Cora og Citeseer. Når inputgrafens topologi reflekteres, overgår vores GMI alle andre typer tab på alle datasæt. Desuden bemærk, at hele træningsprocessen for GMI ligner træningen af diskriminatorer i generative modeller, og GMI udviser empirisk en sammenlignelig træningshastighed med EP-B og DGI på det største datasæt Reddit, hvilket demonstrerer dens gode skalerbarhed. 4.5 Link-forudsigelse Baseret på ovenstående eksperimentelle resultater finder vi, at DGI er en stærk konkurrent til GMI inden for usuperviserede algoritmer. Derfor har vi i dette afsnit til hensigt yderligere at undersøge ydeevnen af DGI og GMI i en anden minedriftsopgave – link-forudsigelse. Her vælger vi FMI og GMI-gennemsnit til at sammenligne med DGI. Tabel rapporterer deres AUC-scorer på fire forskellige datasæt. Under forskellige kanterfjernelsesrater overgår både GMI og FMI DGI bemærkelsesværdigt (undtagen FMI i 70,0% BlogCatalog), hvilket viser, at måling af grafisk MI mellem inputgraf og outputrepræsentationer i et fint mønster er i stand til at fange rig information i input og levere god generaliseringsevne. Om DGI, for det første, dens graf/patch-niveau MI-maksimering, som er relativt grov, begrænser dens ydeevne i en så fin link-forudsigelsesopgave; for det andet, upassende for korruptionsfunktionen svækker DGI's evne til at lære præcise repræsentationer til at forudsige manglende links. Husk, at den negative prøve for diskriminatoren i DGI genereres ved at korrumpere den originale inputgraf, og en veldesignet korruptionsfunktion er uundværlig, hvilket kræver nogle dygtige strategier [ ]. I denne opgave anvender vi stadig funktionsblanding som korruptionsfunktion, der viser de bedste resultater i klassifikationsopgaven til at bygge negative prøver. Men i tilfælde, hvor en inputgraf er ufuldstændig med hensyn til topologiske links, bliver vejledningen fra denne korrupte graf som en negativ etiket i diskriminatoren upålidelig på grund af unøjagtigheden af inputgrafen, hvilket fører til dårlig ydeevne. Derfor er nødvendigheden af en opgaveorienteret korruptionsfunktion en svaghed ved DGI. I modsætning hertil er vores GMI fri for dette problem ved at eliminere korruptionsfunktionen og direkte maksimere grafisk MI mellem input og output af encoderen. Desuden kan det observeres, at FMI er konkurrencedygtig med GMI i de fleste tilfælde, endda på Flickr er FMI overlegen i forhold til GMI. Vi antager, at det skyldes fordelene bragt af den direkte og detaljerede funktionsgensidige informationsmaksimering på nodeniveau. Baseret på homofili-hypotesen [ ] (*dvs.*, enheder i netværket med lignende træk har sandsynlighed for at forbinde sig), gør input funktionsinformationen bevaret i lærte indlejringer FMI til at eje den gode evne til at udlede manglende links. 4 41 29 4.6 Visualisering For en intuitiv illustration viser Tabel t-SNE [ ] plots af de lærte indlejringer på Cora og Citeseer. Fra et kvalitativt perspektiv synes fordelingen af plots lært af FMI og DGI at være ens, og indlejringerne genereret af GMI har tydeligere klynger end rå træk, FMI og DGI. 5 28 Især på Cora er klyngernes kompakthed og adskillelse ekstremt tydelig, hvilket repræsenterer de syv emnekategorier. Som for kvantitativ analyse forsøger vi at måle klyngekvaliteten ved at beregne Silhouette Coefficient-scoren [ ]. Specifikt anvender vi *silhouette_score* funktionen fra scikit-learn Python-pakken [ ] med alle standardindstillinger og følger brugervejledningen til udførelse af evalueringen. Klyngen af indlejringer lært via GMI opnår en Silhouette Coefficient-score på 0,425 på Cora, 0,402 på Citeseer og 0,385 på PubMed, mens DGI får 0,417, 0,391, 0,373 og EP-B opnår 0,384, 0,385, 0,379 på de tre datasæt, henholdsvis. Både kvalitativt og kvantitativt demonstrerer det GMI's store ydeevne, hvilket illustrerer rationaliteten og effektiviteten af grafisk gensidig informationsmaksimering i usuperviseret grafrepræsentationslæring. 37 32 4.7 Indflydelse af Model Dybe I denne del justerer vi antallet af konvolutionelle lag i encoderen for at undersøge indflydelsen af modeldybde på klassifikationsnøjagtigheden. Med hensyn til den potentielle vanskelighed ved at træne dybe neurale netværk, foreslået af [ ], eksperimenterer vi også med en modsvarende residual version af standard GMI-modellen, som tilføjer identitetsskovleforbindelser mellem hvert to skjulte lag for at forbedre træningen af dybe netværk. Her fortsætter vi med D' = 512 træk for hvert skjult lag og starter med at anvende identitetsskovleforbindelser fra det andet lag, da input og output af det første lag ikke har samme dimension. 18 Desuden, sammenlignet med standard GMI-modellen, der opnår GMI-maksimering mellem den endelige repræsentation og den originale inputgraf, overvejer vi en anden variant kaldet tæt GMI, som maksimerer GMI mellem hvert skjult lag og inputgrafen. Figur giver en detaljeret arkitektonisk illustration. De involverede hyperparametre forbliver uændrede, bortset fra at vi træner i faste epoker (600 på Cora og Citeseer) uden tidlig stop. Resultaterne er plottet i Figur 2 3. For det første udvider stigningen i modeldybde markant præstationsgabet mellem modeller med og uden skovleforbindelser. Det bedste resultat for Cora opnås med en to-lags GCN-encoder, mens det bedste resultat for Citeseer opnås med en et-lags GCN-encoder. Ud over det faktum, at stigningen i modeldybde gør træning uden anvendelse af skovleforbindelser vanskelig, antager vi også, at den fjernere naboinformation bragt af flere konvolutionelle lag kan være støj for selv-repræsentationslæring. Specifikt betyder den forskellige nærhed mellem naboer forskellige grader af lighed; hvis to vilkårlige knuder er en vis afstand fra hinanden, er de sandsynligvis helt forskellige. Derfor kan informationen aggregeret fra det fjernere nabolag i standard GMI-modellen indeholde meget støj, der er uens med knudens eget karakteristika, hvilket nedbryder kvaliteten af de lærte indlejringer og efterfølgende klassifikationsydeevne. I modsætning hertil muliggør yderligere identitetsskovleforbindelser, at modellen kan videreføre informationen fra det foregående lags input, hvilket kan betragtes som en komplementær proces til lignende naboinformation fra grundere lag til dybere lag, derfor er residualversionen relativt mindre sårbar over for modeldybde. For det andet observerer vi, at den tætte GMI-variant også kan afhjælpe præstationsforringelsen til en vis grad, selvom MI har tendens til at forfalde med dybde ved data process inequality [ ]. Dette skyldes maksimering af grafisk MI mellem outputtet af hvert lag og inputgrafen, hvilket pålægger en direkte begrænsning på hvert skjult lag for at bevare inputinformationen så intakt som muligt. Baseret på denne observation kan det at håndhæve begrænsningen af at maksimere MI på skjulte lag for at reducere informations tabet ved træning af dybe neurale netværk være en god praksis. 8 5 KONKLUSION For at overvinde dilemmaet med mangel på tilgængelig supervision og undgå den potentielle risiko forårsaget af upålidelige etiketter, introducerer vi et nyt koncept af grafisk gensidig information (GMI) til at udføre grafrepræsentationslæring på en usuperviseret måde. Dens kerne ligger i direkte at maksimere den gensidige information mellem input og output af en grafisk neural encoder med hensyn til nodetræk og topologisk struktur. Gennem vores teoretiske analyse giver vi en definition af GMI og nedbryder den til en form for vægtet sum, der let kan beregnes af den nuværende metode til estimering af gensidig information, MINE. Tilsvarende udvikler vi en usuperviseret model og udfører to almindelige graf-minedriftsopgaver. Resultaterne viser, at GMI overgår state-of-the-art usuperviserede baselines på tværs af både klassifikationsopgaver (transdiktive og induktive) og link-forudsigelsesopgaver, og nogle gange endda er konkurrencedygtig med superviserede algoritmer. Fremtidigt arbejde vil koncentrere sig om opgaveorienteret repræsentationslæring eller tilpasning af ideen om GMI-maksimering til andre typer grafer såsom heterogene grafer og hypergrafer. TAK Dette arbejde blev støttet af National Key Research and Development Program of China (nr. 2018AAA0101400), National Nature Science Foundation of China (nr. 61872287 og nr. 61532015), Innovative Research Group of the National Natural Science Foundation of China (nr. 61721002), Innovation Research Team of Ministry of Education (IRT_17R86) og Project of China Knowledge Center for Engineering Science and Technology. Desuden blev denne forskning finansieret af National Science and Technology Major Project of the Ministry of Science and Technology of China (nr. 2018AAA0102900). REFERENCER Luís B Almeida. 2003. MISEP–Linear and Nonlinear ICA Based on Mutual Information. 4, Dec (2003), 1297–1318. Journal of machine learning research Mohamed Ishmael Belghazi, Aristide Baratin, Sai Rajeswar, Sherjil Ozair, Yoshua Bengio, Aaron Courville, and R Devon Hjelm. 2018. Mine: mutual information neural estimation. In . ICML Anthony J Bell and Terrence J Sejnowski. 1995. An information-maximization approach to blind separation and blind deconvolution. 7, 6 (1995), 1129–1159. Neural computation Esben Jannik Bjerrum and Richard Threlfall. 2017. Molecular generation with recurrent neural networks (RNNs). (2017). arXiv preprint arXiv:1705.04612 Xavier Bresson and Thomas Laurent. 2019. A Two-Step Graph Convolution