Ett nytt sätt att träna AI på grafdata utan övervakning

Författare: Zhen Peng Wenbing Huang Minnan Luo Qinghua Zheng Yu Rong Tingyang Xu Junzhou Huang SAMMANFATTNING Rikligheten i innehållet i olika informationsnätverk som sociala nätverk och kommunikationsnätverk ger en oöverträffad potential för att lära sig högkvalitativa uttrycksfulla representationer utan extern övervakning. Denna artikel undersöker hur man bevarar och extraherar den rikliga informationen från grafstrukturerad data till inbäddningsutrymme på ett oövervakat sätt. För detta ändamål föreslår vi ett nytt koncept, Graphical Mutual Information (GMI), för att mäta korrelationen mellan indatagrafar och hög-nivå dolda representationer. GMI generaliserar idén om konventionella ömsesidiga informationsberäkningar från vektorrum till grafdomänen där mätning av ömsesidig information från två aspekter av nodegenskaper och topologisk struktur är oumbärlig. GMI uppvisar flera fördelar: För det första är den invariant mot den isomorfa transformationen av indatagrafar – en oundviklig begränsning i många befintliga algoritmer för grafrepresentationinlärning; Dessutom kan den effektivt uppskattas och maximeras med nuvarande metoder för ömsesidig informationsuppskattning såsom MINE; Slutligen bekräftar vår teoretiska analys dess korrekthet och rationalitet. Med hjälp av GMI utvecklar vi en oövervakad inlärningsmodell som tränas genom att maximera GMI mellan in- och utdata från en grafisk neural kodare. Betydande experiment på transdutiva såväl som induktiva nodklassificering och länkanpassning visar att vår metod överträffar de bästa oövervakade motsvarigheterna och ibland till och med överträffar prestandan hos de övervakade. 1 INTRODUKTION För att uppnå tillförlitlig kvantitativ analys för olika informationsnätverk har högkvalitativ representationsinlärning för grafstrukturerad data blivit ett av de mest fascinerande ämnena. Nya metoder för att uppnå detta mål, vanligtvis kategoriserade som Graph Neural Networks (GNNs), har gjort anmärkningsvärda framsteg inom ett stort antal inlärningsuppgifter, såsom nodklassificering [ , , ], länkanpassning [ , , ], grafinriktning [ , , ], molekylär generering [ , , ], för att nämna några. Trots fruktbara framsteg kräver träning av GNNs i befintliga metoder vanligtvis någon form av övervakning. Utan tvekan är märkningsinformationen dyr att förvärva – manuell annotering eller betalning för tillstånd, och är till och med omöjlig att uppnå på grund av sekretesspolicyn. För att inte tala om att tillförlitligheten hos givna etiketter ibland är tveksam. Hur man uppnår högkvalitativ grafrepresentation utan övervakning blir därför nödvändigt för ett stort antal praktiska fall, vilket motiverar studien i denna artikel. 35 42 50 26 27 49 12 19 43 4 5 46 Genom att noggrant granska vår insamlade grafstrukturerade data finner vi att den generellt kommer från olika källor som sociala nätverk, citatnätverk och kommunikationsnätverk där en enorm mängd både innehåll och länk information finns. Till exempel inkluderar data på många sociala plattformar som Twitter, Flickr och Facebook funktioner för användare, *t.ex.*, grundläggande personliga detaljer, texter, bilder, IP, och deras relationer, *t.ex.*, köpa samma vara, vara vänner. Dessa rika innehållsdata är tillräckliga för efterföljande gruvuppgifter utan ytterligare vägledning: om två entiteter uppvisar extrem likhet i egenskaper finns det en hög sannolikhet för en koppling mellan dem (länkanpassning), och de tillhör troligen samma kategori (klassificering); om två entiteter båda länkar till samma entitet har de troligen liknande egenskaper (rekommendation). I denna mening underlättar bevarandet och extraheringen av så mycket information som möjligt från informationsnätverk till inbäddningsutrymme inlärning av högkvalitativa uttrycksfulla representationer som uppvisar önskvärd prestanda i gruvuppgifter utan någon form av övervakning. Oövervakad grafrepresentationinlärning är ett mer gynnsamt val i många fall på grund av friheten från etiketter, särskilt när vi avser att dra nytta av en stor mängd omärkt data i det vilda. För att fullt ut ärva den rika informationen i grafer, genomför vi i denna artikel grafinbäddning baserad på Maximering av Ömsesidig Information (MI), inspirerad av den empiriska framgången med Deep Info-Max-metoden [ ] som verkar på bilder. För att upptäcka användbara representationer tränar Deep InfoMax kodaren att maximera MI mellan dess indata ( *dvs.*, bilderna) och utdata ( *dvs.*, de dolda vektorerna). När man överväger Deep InfoMax i grafdomänen är den första stenen vi behöver kliva över hur man definierar MI mellan grafer och dolda vektorer, medan grafens topologi är mer komplicerad än bilder (se Figur En av utmaningarna är att säkerställa att MI-funktionen mellan varje nods dolda representation och dess grannskapsinmatningsegenskaper följer den symmetriska egenskapen, eller ekvivalent, är invariant mot permutationer av grannskap. Som ett nyligen genomfört arbete som överväger MI, bäddar Deep Graph Infomax (DGI) [ ] först in en indatagraf och en motsvarande korrupt graf, summerar sedan indatagrafen som en vektor via en avläsningsfunktion, och maximerar slutligen MI mellan denna summeringsvektor och dolda representationer genom att diskriminera indatagrafen (positivt prov) från den korrupta grafen (negativt prov). Figur ger en lättförståelig översikt av DGI. Maximering av denna typ av MI bevisas vara ekvivalent med att maximera den mellan indatanodegenskaperna och dolda vektorer, men denna ekvivalens gäller under flera förinställda villkor, *t.ex.*, avläsningsfunktionen bör vara injektiv, vilket ändå verkar vara överbegränsat i verkliga fall. Även om vi kan garantera existensen av en injektiv avläsningsfunktion genom viss design, *t.ex.*, den som används i DeepSets [ ], påverkas avläsningsfunktionens injektiva förmåga också av hur dess parametrar tränas. Det vill säga att en ursprungligen injektiv funktion fortfarande har risken att bli icke-injektiv om den tränas utan någon extern övervakning. Och om avläsningsfunktionen inte är injektiv, minskar informationen från indatagrafen som finns i en summeringsvektor när grafens storlek ökar. Dessutom befinner sig DGI i en grovkornig graf-/patch-nivå MI-maximering. Därför finns det ingen garanti för att kodaren kan destillera tillräcklig information från indata eftersom den inte noggrant korrelerar dolda representationer med sina ursprungliga indata. 20 1). 41 1 47 I denna artikel föreslår vi ett enklare sätt att överväga MI med avseende på grafstrukturer utan att använda någon avläsningsfunktion och korruptionsfunktion. Vi härleder direkt MI genom att jämföra indata ( *dvs.*, delgrafen som består av indatas grannskap) och utdata ( *dvs.*, den dolda representationen av varje nod) från kodaren. Och intressant nog visar våra teoretiska härledningar att den direkt formulerade MI kan dekomponeras i en viktad summa av lokala MI mellan varje grannskapsdrag och den dolda vektorn. På så sätt har vi dekomponerat indataegenskaperna och gjort MI-beräkningen hanterbar. Dessutom kan denna form av MI enkelt uppfylla den symmetriska egenskapen om vi justerar vikternas värden. Mer detaljer hittar du i § Eftersom ovanstående MI huvudsakligen mäts på nivån av nodegenskaper, kallar vi det Feature Mutual Information (FMI). 3.1. Två återstående frågor om FMI: **1.** kombinationsvikterna är fortfarande okända och **2.** den tar inte hänsyn till topologin ( *dvs.*, kantens egenskaper). För att ytterligare adressera dessa två frågor definierar vi vår Graphical Mutual Information (GMI) mätning baserat på FMI. Specifikt tillämpar GMI en intuitiv värdetilldelning genom att sätta vikterna i FMI lika med närheten mellan varje granne och målknuten i representationsutrymmet. För att behålla topologiinformationen korrelerar GMI ytterligare dessa vikter med kantens inmatningsegenskaper via en ytterligare ömsesidig informationsterm. Den resulterande GMI är topologiskt invariant och även beräkningsbar med Mutual Information Neural Estimation (MINE) [ ]. Huvudbidragen i vårt arbete är som följer: 2 • * *: Vi generaliserar den konventionella MI-uppskattningen till grafdomänen och föreslår ett nytt koncept av Graphical Mutual Information (GMI) därefter. GMI är fri från Koncept potentiell risk orsakad av avläsningsfunktionen eftersom den överväger MI mellan indatagrafar och hög-nivå inbäddningar på ett enkelt sätt. • * *: Genom vår teoretiska analys ger vi en hanterbar och beräkningsbar form av GMI som dekomponerar Algoritmer hela GMI till en viktad summa av lokala MI. Med hjälp av MINE-metoden kan GMI-maximering enkelt uppnås på nodnivå. • * *: Vi verifierar effektiviteten av GMI på flera populära nodklassificerings- och länkanpassningsuppgifter, inklusive både transdutiva och induktiva. Experimenten visar att vår metod levererar lovande prestanda på en rad riktmärken och den överträffar ibland till och med de övervakade motsvarigheterna. Experimentella Fynd 2 RELATERAT ARBETE I linje med vårt fokus granskar vi kortfattat tidigare arbete inom följande två områden: **1.** ömsesidig informationsuppskattning och **2.** neurala nätverk för representationsinlärning över grafer. **Ömsesidig informationsuppskattning**. Som InfoMax-principen [ ] förespråkar maximering av MI mellan indata och utdata från neurala nätverk, försöker många metoder som ICA-algoritmer [ , ] att använda idén om MI i oövervakad egenskapsinlärning. Ändå kan dessa metoder inte enkelt generaliseras till djupa neurala nätverk på grund av svårigheten att beräkna MI mellan högdimensionella kontinuerliga variabler. Lyckligtvis gör Mutual Information Neural Estimation (MINE) [ ] uppskattningen av MI på djupa neurala nätverk möjlig genom att träna ett statistiknätverk som en klassificerare för att skilja prover som kommer från den gemensamma fördelningen och produkten av marginalerna av två slumpmässiga variabler. Specifikt använder MINE den exakta KL-baserade formuleringen av MI, medan ett icke-KL-alternativ, Jensen-Shannon-divergensen (JSD) [ ], kan användas utan oro för det exakta värdet av MI. 3 1 21 2 30 **Neurala nätverk för grafrepresentationinlärning**. Med den snabba utvecklingen av grafiska neurala nätverk (GNNs) har ett stort antal algoritmer för grafrepresentationinlärning baserade på GNNs föreslagits under de senaste åren, vilka uppvisar starkare prestanda än traditionella random walk-baserade och faktorisering-baserade inbäddningsmetoder [ , , , , ]. Typiskt kan dessa metoder delas in i övervakade och oövervakade kategorier. Bland dem finns en rik litteratur om övervakad representationinlärning över grafer [ , , , , ]. Trots deras variation i nätverksarkitektur uppnår de empirisk framgång med hjälp av etiketter som ofta inte är tillgängliga i realistiska scenarier. I detta fall har oövervakade grafinlärningsmetoder [ , , ] bredare tillämpningspotential. Den välkända metoden är GraphSAGE [ ], ett induktivt ramverk för att träna GNNs med ett random walk-baserat mål i dess oövervakade inställning. Och nyligen tillämpar DGI [ ] idén om MI-maximering på grafdomänen och uppnår stark prestanda i ett oövervakat mönster. DGI implementerar dock en grovkornig maximering (*dvs.*, maximering av MI på graf-/patchnivå) vilket gör det svårt att bevara den känsliga informationen i indatagrafen. Dessutom verkar villkoret som ställs på avläsningsfunktionen som används i DGI vara överbegränsat i verkliga fall. Däremot fokuserar vi på att ta bort begränsningen av avläsningsfunktionen och uppnå grafisk ömsesidig informationsmaximering på nodnivå genom att direkt maximera MI mellan indata och utdata från kodaren. Representationer som härleds av vår metod är mer sofistikerade när det gäller att behålla indatagrafsinformation, vilket säkerställer dess potential för efterföljande grafgruvuppgifter, *t.ex.*, nodklassificering, länkanpassning och rekommendation. 6 15 33 34 39 7 9 25 40 48 11 16 41 16 41 3 GRAFISK ÖMSESIDIG INFORMATION: DEFINITION OCH MAXIMERING Innan vi går vidare ger vi först de preliminära begrepp som används i denna artikel. Låt G = (V, E) beteckna en graf med *N* noder *vi* ∈ V och kanter *eij* = (*vi* , *vj* ) ∈ E. Nodegenskaperna, med antagen empirisk sannolikhetsfördelning P, ges av *X* ∈ R ×*D* = {*x* 1, · · · , *x* N } där *xi* ∈ R*D* betecknar egenskapen för nod *vi* . Adjacensmatrisen *A* ∈ R ×*N* representerar kantkopplingar, där *Aij* associerad med kanten *eij* kan vara ett reellt tal eller en multidimensionell vektor1. N N Målet med grafrepresentationinlärning är att lära sig en kodare *f* : R ×*D* × R ×*N* → R ×*D*′ , så att de dolda vektorerna *H* = {*h*1, · · · , *hN* } = *f* (*X* , *A*) indikerar hög-nivå representationer för alla noder. Kodningsprocessen kan skrivas om i en nod-vis form. N N N För att visa detta definierar vi *Xi* och *Ai* för nod *i* som respektive egenskaperna för dess grannar och motsvarande adjacensmatris villkorligt på grannarna. Särskilt består *Xi* av alla k-hop-grannar till *vi* med *k* ≤ *l* när kodaren *f* är en *l*-lagers GNN, och den innehåller noden *i* själv om vi ytterligare lägger till självloopar i adjacensmatrisen. Här kallar vi delgrafen som expanderas av *Xi* och *Ai* för en *stöddiagraf* för nod *i*, betecknad med G*i*. Med definitionen av stöddiagrafen blir kodningen för varje nod *hi* = *f* (G*i*) = *f* (*Xi* , *Ai*). **Svårigheter att definiera grafisk ömsesidig information**. I Deep InfoMax [ ] är träningsmålet för kodaren att maximera MI mellan dess indata och utdata. MI uppskattas genom att använda ett statistiknätverk som en diskriminator för att klassificera prover som kommer från den gemensamma fördelningen och de som dras från produkten av marginalerna. Naturligtvis, när vi anpassar idén om Deep InfoMax till grafer, bör vi maximera MI mellan representationen *hi* och stöddiagrafen G*i* för varje nod. Vi betecknar sådan grafisk MI som *I* (*hi* ; G*i*). Det är dock inte enkelt att definiera I (*hi* ; Gi ). Svårigheterna är: 20 • Den grafiska MI bör vara invariant med avseende på nodindexet. Med andra ord, vi bör ha *I* (*hi* ; G*i*) = *I* (*hi* ; G′*i*), om G*i* och G′*i* är isomorfa med varandra. • Om vi antar MINE-metoden för MI-beräkning, accepterar diskriminatorn i MINE endast indata av en fast storlek. Detta är ännu inte genomförbart för G*i* eftersom olika G*i* vanligtvis inkluderar olika antal noder och därmed har distinkta storlekar. För att komma runt problemet med att definiera grafisk ömsesidig information, börjar detta avsnitt med att introducera konceptet Feature Mutual Information (FMI) som endast förlitar sig på nodegenskaper. Baserat på inspiration från dekomponeringen av FMI, definierar vi sedan Graphical Mutual Information (GMI), som tar hänsyn till både nodegenskaper och 3.1 Egenskapsömsesidig Information Vi betecknar den empiriska sannolikhetsfördelningen av nodegenskaper *Xi* som *p*(*Xi* ), sannolikheten för *hi* som *p*(*hi* ), och den gemensamma fördelningen med *p*(*hi* , *Xi* ). Enligt informationsteorin definieras MI mellan *hi* och *Xi* som Intressant nog har vi följande teorem för ömsesidig informationsdekomponering för att beräkna *I* (*hi* ; *Xi* ). Teorem 1 (Ömsesidig informationsdekomponering). *Om den betingade sannolikheten p*(*hi* |*Xi* ) *är multiplikativ (se definitionen av multiplikativ i [ ]), kan den globala ömsesidiga informationen I* (*hi* ; *Xi* ) *definierad i Ekv. dekomponeras som en viktad summa av lokala MI, nämligen,* 36 (1) *där, xj är den j-te grannen till nod i, in är antalet alla element i Xi , och vikten wij uppfyller* ≤ *wij* ≤ 1 *för varje j.* 1 För att bevisa ovanstående teorem introducerar vi först två lemma och en definition. Lemma 1. *För alla slumpmässiga variabler X, Y och Z har vi* Med dekomponeringen i Teorem kan vi beräkna höger sida av Ekv. via MINE eftersom indata till diskriminatorn nu blir paren av (*hi* , *xj*) vars storlek alltid hålls densamma (*dvs.*, *D*′ -med -*D*). Dessutom kan vi justera vikterna för att återspegla den isomorfa transformationen av indatagrafar. Till exempel, om *Xi* endast innehåller en-hop grannar till nod *i*, kommer inställning av alla vikter att vara identiska att leda till samma MI för indatanoderna i olika ordningar. 1, (2) Trots vissa fördelar med dekomponeringen är det svårt att karakterisera de exakta värdena på vikterna eftersom de är relaterade till värdena av *I* (*hi* ; *xj*) och deras underliggande sannolikhetsfördelningar. Ett trivialt sätt är att sätta alla vikter till , sedan maximering av höger sida av Ekv. motsvarar att maximera den undre gränsen för *I* (*hi* ; *Xi* ), varigenom den sanna FMI också maximeras till viss del. Utöver denna metod ger vi dessutom en mer förbättrad lösning genom att betrakta vikterna som träningsbara uppmärksamheter, vilket är ämnet i nästa delavsnitt. 1 (2) Inspirerad av dekomponeringen i Teorem försöker vi konstruera träningsbara vikter från den andra aspekten av grafer (*dvs.*, 3.2 Topologi-medveten ömsesidig information 1, topologiskt perspektiv) så att värdena på *wij* kan vara mer flexibla och fånga den inneboende egenskapen hos grafer. Slutligen härleder vi definitionen av Graphical Mutual Information (GMI). Definition 2 (Grafisk ömsesidig information). *MI mellan den dolda vektorn h och dess stöddiagraf* G = (*X* , *A*) *definieras som* där definitionerna av både xj och in är desamma som i Teorem 1, aij är kantvikten/egenskapen i adjacensmatrisen A, och σ(·) är en sigmoidfunktion. Intuitivt mäter vikten wij i den första termen av Ekv. (10) den hanterades i experimenten är oviktade. Formellt beräknar vi I (wij ; aij ) = aijloдwij + (1 − aij )loд(1 − wij ). (12) Genom att maximera I (hi ; Gi ) med summan av Ekv. (11) och Ekv. (12) över alla dolda vektorer H, kommer vi till vår fullständiga objektivfunktion för bidraget från en lokal MI till den globala. Vi implementerar bidraget från I (hi ; xj ) genom likheten mellan representationerna hi och hj (dvs., wij = σ (hThj )). Samtidigt maximerar termen I (wij ; aij ) MI mellan wij och kantvikten/egenskapen för indatagrafen (dvs., aij ) för att tvinga wij att följa topologiska relationer. I denna mening kommer bidragets grad att vara konsekvent med närheten i topologisk struktur, vilket allmänt accepteras som ett faktum att wij kan vara större om nod j är ”närmare” nod i och mindre annars. Denna strategi kompenserar för bristen att FMI endast fokuserar på nodegenskaper och gör att lokala MI bidrar till den globala adaptivt. För att bättre förstå idén om uppmärksamhet i denna strategi, kan du referera till den uppmärksamhetsbaserade GCN. Notera att definitionen av Ekv. (10) är tillämplig för allmänna fall. För vissa specifika situationer kan vi modifiera Ekv. (10) något för effektivitet. Till exempel, vid hantering av oviktade grafer (dvs. kantvärdet är 1 om ansluten och 0 annars), kan vi ersätta den andra MI-termen I (wij ; aij ) med en negativ korsentropiförlust. Minimering av korsentropin bidrar också till MI-maximering, och den ger en mer effektiv beräkning. Mer detaljer hittar du i nästa avsnitt. Sammantaget finns det flera fördelar med definitionen av Ekv. (10). För det första är denna typ av MI invariant mot den isomorfa transformationen av indatagrafar. För det andra är den beräkningsmässigt genomförbar eftersom varje komponent på höger sida kan uppskattas av MINE. Ännu viktigare är att GMI är kraftfullare än DGI när det gäller att fånga ursprunglig indatainformation på grund av dess explicita korrelation mellan dolda vektorer och indataegenskaper för både noder och kanter på en finkornig nodnivå. 3.3 Maximering av GMI Nu maximerar vi direkt höger sida av Ekv. med hjälp av MINE. Notera att MINE uppskattar en nedre gräns för MI med Donsker-Varadhan (DV) [ ] representationen av KL-divergensen mellan den gemensamma fördelningen och produkten av marginalerna. Eftersom vi fokuserar mer på att maximera MI snarare än att få dess specifika värde, kan andra icke-KL-alternativ som Jensen-Shannon MI-estimator (JSD) [ ] och Noise-Contrastive-estimator (infoNCE) [ ] användas för att ersätta den. Baserat på de experimentella fynden och analysen i [ ], använder vi JSD-estimatorn i denna artikel för effektivitet och prestanda, eftersom infoNCE-estimatorn är känslig för strategier för negativ sampling (antalet negativa prover) och därmed kan bli en flaskhals för stora datamängder med ett fast tillgängligt minne. Tvärtom, JSD-estimatorns okänslighet för strategier för negativ sampling och dess respektabla prestanda på många uppgifter gör den mer lämplig för vår uppgift. Specifikt beräknar vi *I* (*hi* ; *xj*) i den första termen av Ekv. med (10) 10 30 31 20 (10) där D : *D* × *D*′ → R är en diskriminator konstruerad av ett neuralt nätverk med parameter *w*. *xj* är ett negativt prov taget från P = P, och *sp*(*x*) = *loд*(1 + *ex*) betecknar mjuk-plus-funktionen. w Som nämnts i § maximerar vi *I* (*wij* ; *aij*) genom att beräkna dess korsentropi istället för att använda JSD-estimatorn eftersom graferna vi hanterade i experimenten är oviktade. Formellt beräknar vi 3.2, Genom att maximera I (hi ; Gi ) med summan av Ekv. (11) och Ekv. (12) över alla dolda vektorer H, kommer vi till vår fullständiga objektivfunktion för GMI-optimering. Dessutom kan vi ytterligare lägga till avvägningsparametrar för att balansera Ekv. (11) och (12) för större flexibilitet. 4 EXPERIMENT I detta avsnitt utvärderar vi empiriskt prestandan hos GMI på två vanliga uppgifter: nodklassificering (transdktiv och induktiv) och länkanpassning. En ytterligare relativt rättvis jämförelse mellan GMI och två andra oövervakade algoritmer (EP-B och DGI) visar ytterligare dess effektivitet. Vi tillhandahåller också visualisering av t-SNE-diagram och analyserar inflytandet av modellens djup. 4.1 Datamängder För att bedöma kvaliteten på vårt tillvägagångssätt i varje uppgift använder vi 4 eller 5 vanliga riktmärkesdatamängder från tidigare arbete [ , , ]. Detaljerad statistik ges i Tabell 16 25 41 1. I klassificeringsuppgiften är Cora, Citeseer och PubMed [ ]2& 38