Nový spôsob tréningu AI na grafových dátach bez dohľadu

```html Autori: Zhen Peng Wenbing Huang Minnan Luo Qinghua Zheng Yu Rong Tingyang Xu Junzhou Huang ABSTRAKT Bohatosť obsahu rôznych informačných sietí, ako sú sociálne siete a komunikačné siete, poskytuje bezprecedentný potenciál na učenie vysokokvalitných expresívnych reprezentácií bez externého dohľadu. Tento článok skúma, ako zachovať a extrahovať bohaté informácie z dát štruktúrovaných do grafov do priestoru vkladania bez dohľadu. Na tento účel navrhujeme nový koncept, grafické vzájomné informácie (GMI), na meranie korelácie medzi vstupnými grafmi a skrytými reprezentáciami na vysokej úrovni. GMI zovšeobecňuje myšlienku konvenčných výpočtov vzájomných informácií z vektorového priestoru do domény grafov, kde je meranie vzájomných informácií z dvoch aspektov vlastností uzlov a topologickej štruktúry nevyhnutné. GMI vykazuje niekoľko výhod: Po prvé, je invariantný voči izomorfnej transformácii vstupných grafov – nevyhnutná obmedzenie mnohých existujúcich algoritmov na učenie reprezentácií grafov; Okrem toho môže byť efektívne odhadnutý a maximalizovaný súčasnými metódami odhadu vzájomných informácií, ako je MINE; Nakoniec, naša teoretická analýza potvrdzuje jeho správnosť a racionalitu. S pomocou GMI vyvíjame model učenia bez dohľadu trénovaný maximalizáciou GMI medzi vstupom a výstupom grafového neurónového kodéra. Rozsiahle experimenty na transdukčnej aj indukčnej klasifikácii uzlov a predikcii väzieb preukazujú, že naša metóda prekonáva najmodernejšie bez dohľadu, a niekedy dokonca prekračuje výkonnosť metód s dohľadom. 1 ÚVOD Na dosiahnutie spoľahlivej kvantitatívnej analýzy pre rôzne informačné siete sa učenie vysokokvalitných reprezentácií pre dáta štruktúrované do grafov stalo jednou z aktuálnych fascinujúcich tém. Najnovšie metódy smerujúce k tomuto cieľu, bežne kategorizované ako grafové neurónové siete (GNN), dosiahli pozoruhodné pokroky v mnohých učiacich úlohách, ako je klasifikácia uzlov [ , , ], predikcia väzieb [ , , ], zarovnávanie grafov [ , , ], generovanie molekúl [ , , ], a iné. Napriek plodnému pokroku, tréning GNN v existujúcich prístupoch zvyčajne vyžaduje určitú formu dohľadu. Nepochybne, informácie o označení sú drahé na získanie – manuálna anotácia alebo platenie za povolenie, a dokonca nemožné na získanie kvôli pravidlám ochrany súkromia. Nehovoriac o tom, že spoľahlivosť poskytnutých označení je niekedy otázna. Preto, ako dosiahnuť vysokokvalitnú reprezentáciu grafov bez dohľadu, sa stalo nevyhnutnosťou pre veľa praktických prípadov, čo motivuje štúdiu tohto článku. 35 42 50 26 27 49 12 19 43 4 5 46 Po dôkladnom preskúmaní našich nazbieraných dát štruktúrovaných do grafov sme zistili, že všeobecne pochádzajú z rôznych zdrojov, ako sú sociálne siete, citačné siete a komunikačné siete, kde existuje obrovské množstvo obsahu aj odkazových informácií. Napríklad dáta na mnohých sociálnych platformách ako Twitter, Flickr a Facebook zahŕňajú vlastnosti používateľov, *napr.*, základné osobné údaje, texty, obrázky, IP, a ich vzťahy, *napr.*, nákup rovnakého tovaru, priateľstvo. Tieto bohaté obsahové dáta sú dostatočné na podporu následných ťažobných úloh bez dodatočného usmernenia: ak dve entity vykazujú extrémnu podobnosť vo vlastnostiach, existuje vysoká pravdepodobnosť väzby medzi nimi (predikcia väzby) a je pravdepodobné, že patria do rovnakej kategórie (klasifikácia); ak sa dve entity navzájom odkazujú na rovnakú entitu, pravdepodobne majú podobné charakteristiky (odporúčanie). V tomto zmysle, zachovanie a extrakcia čo najväčšieho množstva informácií z informačných sietí do priestoru vkladania uľahčuje učenie vysokokvalitných expresívnych reprezentácií, ktoré vykazujú žiadaný výkon v ťažobných úlohách bez akejkoľvek formy dohľadu. Učenie reprezentácií grafov bez dohľadu je v mnohých prípadoch priaznivejšou voľbou kvôli slobode od označení, najmä keď máme v úmysle využiť rozsiahle neoznačené dáta v divočine. Aby sme plne zdedili bohaté informácie v grafoch, v tomto článku vykonávame vkladanie grafov založené na maximalizácii vzájomných informácií (MI), inšpirované empirickým úspechom metódy Deep Info-Max [ ], ktorá funguje na obrázkoch. Na objavenie užitočných reprezentácií trénuje Deep InfoMax kodér na maximalizáciu MI medzi jeho vstupmi ( *t. j.*, obrázky) a výstupmi ( *t. j.*, skryté vektory). Pri zvažovaní Deep InfoMax v doméne grafov, prvým kameňom, cez ktorý musíme prekročiť, je ako definovať MI medzi grafmi a skrytými vektormi, zatiaľ čo topológia grafov je zložitejšia ako obrázky (pozri Obrázok Jednou z výziev je zabezpečiť, aby funkcia MI medzi skrytou reprezentáciou každého uzla a jeho susednými vstupnými vlastnosťami dodržiavala symetrickú vlastnosť, alebo ekvivalentne, aby bola invariantná voči permutáciám susedstiev. Ako jedna nedávna práca zaoberajúca sa MI, Deep Graph Infomax (DGI) [ ] najprv vkladá vstupný graf a zodpovedajúci poškodený graf, potom zhrnie vstupný graf do vektora pomocou funkcie čítania (readout function), nakoniec maximalizuje MI medzi týmto súhrnným vektorom a skrytými reprezentáciami diskriminovaním vstupného grafu (pozitívna vzorka) od poškodeného grafu (negatívna vzorka). Obrázok poskytuje ľahko pochopiteľný prehľad DGI. Maximalizácia tohto druhu MI je dokázaná ako ekvivalentná maximalizácii medzi vstupnými vlastnosťami uzlov a skrytými vektormi, ale táto ekvivalencia platí za niekoľkých prednastavených podmienok, *napr.*, funkcia čítania by mala byť injektívna, čo sa v reálnych prípadoch zdá byť príliš obmedzené. Aj keď môžeme zaručiť existenciu injektívnej funkcie čítania určitým dizajnom, *napr.*, ten použitý v DeepSets [ ], injektívna schopnosť funkcie čítania je tiež ovplyvnená tým, ako sú jej parametre trénované. To znamená, že pôvodne injektívna funkcia stále riskuje stať sa ne-injektívnou, ak je trénovaná bez akéhokoľvek externého dohľadu. A ak funkcia čítania nie je injektívna, informácie zo vstupného grafu obsiahnuté v súhrnných vektoroch sa zmenšia so zväčšujúcou sa veľkosťou grafu. Okrem toho DGI zostáva v hrubom maximalizovaní MI na úrovni grafu/záplaty. Preto v DGI nie je zaručené, že kodér dokáže získať dostatočné informácie zo vstupných dát, pretože nikdy starostlivo nesúvisí skryté reprezentácie s ich pôvodnými vstupmi. 20 1). 41 1 47 V tomto článku navrhujeme priamočiarejší spôsob zvažovania MI z hľadiska grafových štruktúr bez použitia akejkoľvek funkcie čítania alebo poškodzovania. Priamo odvodzujeme MI porovnaním vstupu ( *t. j.*, podgraf zložený zo vstupného susedstva) a výstupu ( *t. j.*, skrytej reprezentácie každého uzla) kodéra. A zaujímavo, naše teoretické odvodenia ukazujú, že priamo formulovaná MI môže byť dekomponovaná na vážený súčet lokálnych MI medzi každými susednými vlastnosťami a skrytým vektorom. Týmto spôsobom sme dekomponovali vstupnú funkciu a urobili výpočet MI zvládnuteľným. Okrem toho táto forma MI môže ľahko splniť symetrickú vlastnosť, ak upravíme hodnoty váh. Viac detailov odložíme do § Keďže vyššie uvedená MI sa meria hlavne na úrovni vlastností uzlov, nazývame ju Feature Mutual Information (FMI). 3.1. Dva zostávajúce problémy s FMI: **1.** kombinačné váhy sú stále neznáme a **2.** nezohľadňuje topológiu ( *t. j.*, vlastnosti hrán). Aby sme tieto dva problémy ďalej riešili, definujeme naše meranie Grafových vzájomných informácií (GMI) založené na FMI. Konkrétne, GMI aplikuje intuitívne priradenie hodnôt nastavením váh vo FMI rovných blízkosti medzi každým susedom a cieľovým uzlom v priestore reprezentácie. Aby sme zachovali topologické informácie, GMI ďalej koreluje tieto váhy s vlastnosťami vstupných hrán prostredníctvom dodatočného člena vzájomných informácií. Výsledná GMI je topologicky invariantná a tiež vypočítateľná pomocou metód na odhad vzájomných informácií neurónovou sieťou (Mutual Information Neural Estimation - MINE) [ ]. Hlavné prínosy našej práce sú nasledovné: 2 • * *: Zovšeobecňujeme konvenčný odhad MI do domény grafov a podľa toho navrhujeme nový koncept Grafových vzájomných informácií (GMI). GMI je bez rizika spôsobeného funkciou čítania, pretože zvažuje MI medzi vstupnými grafmi a skrytými vkladaniami na vysokej úrovni priamočiarym spôsobom. Koncepty • * *: Prostredníctvom našej teoretickej analýzy poskytujeme zvládnuteľnú a vypočítateľnú formu GMI, ktorá dekomponuje celkovú GMI na vážený súčet lokálnych MI. S pomocou metódy MINE možno maximalizáciu GMI ľahko dosiahnuť na úrovni uzlov. Algoritmy • * *: Overujeme účinnosť GMI na niekoľkých populárnych úlohách klasifikácie uzlov a predikcie väzieb vrátane transdukčných aj indukčných. Experimenty ukazujú, že naša metóda poskytuje sľubný výkon na rôznych benchmarkoch a dokonca niekedy prekonáva aj supervízované náprotivky. Experimentálne zistenia 2 SÚVISIACE PRÁCE V súlade so zameraním našej práce stručne prehodnocujeme predchádzajúce práce v dvoch nasledujúcich oblastiach: **1.** odhad vzájomných informácií a **2.** neurónové siete na učenie reprezentácií nad grafmi. . Ako princíp InfoMax [ ] obhajuje maximalizáciu MI medzi vstupmi a výstupmi neurónových sietí, mnohé metódy ako ICA algoritmy [ , ] sa pokúšajú použiť myšlienku MI v učení vlastností bez dohľadu. Napriek tomu sa tieto metódy nedajú ľahko zovšeobecniť na hlboké neurónové siete kvôli obtiažnosti výpočtu MI medzi vysokodimenzionálnymi spojitými premennými. Našťastie, Mutual Information Neural Estimation (MINE) [ ] umožňuje odhad MI na hlbokých neurónových sieťach prostredníctvom tréningu štatistickej siete ako klasifikátora na rozlíšenie vzoriek pochádzajúcich zo spoločného rozdelenia a súčinu marginálnych rozdelení dvoch náhodných premenných. Konkrétne MINE používa presné KL-založené formulácie MI, zatiaľ čo ne-KL alternatíva, Jensen-Shannonova divergencia (JSD) [ ], sa môže použiť bez obáv o presnú hodnotu MI. Odhad vzájomných informácií 3 1 21 2 30 . S rýchlym vývojom grafových neurónových sietí (GNN) bolo v posledných rokoch navrhnutých veľké množstvo algoritmov na učenie reprezentácií grafov založených na GNN, ktoré vykazujú silnejší výkon ako tradičné prístupy založené na náhodných prechádzkach a faktorizácii [ , , , , ]. Typicky sa tieto metódy dajú rozdeliť na kategórie s dohľadom a bez dohľadu. Medzi nimi existuje bohatá literatúra o učení reprezentácií s dohľadom nad grafmi [ , , , , ]. Napriek ich variáciám v sieťovej architektúre dosahujú empirický úspech s pomocou označení, ktoré sú v realistických scenároch často nedostupné. V tomto prípade majú metódy učenia grafov bez dohľadu [ , , ] širší aplikačný potenciál. Známou metódou je GraphSAGE [ ], indukčný rámec na trénovanie GNN pomocou cieľa založeného na náhodných prechádzkach v jeho nastavení bez dohľadu. A nedávno DGI [ ] aplikuje myšlienku maximalizácie MI do domény grafov a dosahuje silný výkon v režime bez dohľadu. DGI však implementuje maximalizáciu hrubého zrna ( *t. j.*, maximalizáciu MI na úrovni grafu/záplaty), čo sťažuje zachovanie jemných informácií vo vstupnom grafe. Okrem toho podmienka na funkciu čítania použitú v DGI sa zdá byť v reálnych prípadoch príliš obmedzujúca. Na rozdiel od toho sa zameriavame na odstránenie obmedzenia funkcie čítania a dosiahnutie maximalizácie grafových vzájomných informácií na úrovni uzlov priamou maximalizáciou MI medzi vstupmi a výstupmi kodéra. Reprezentácie odvodené našou metódou sú sofistikovanejšie v zachovaní informácií zo vstupného grafu, čo zaisťuje jej potenciál pre následné ťažobné úlohy grafov, *napr.*, klasifikáciu uzlov, predikciu väzieb a odporúčanie. Neurónové siete pre učenie reprezentácií grafov 6 15 33 34 39 7 9 25 40 48 11 16 41 16 41 3 GRAFOVÉ VZÁJOMNÉ INFORMÁCIE: DEFINÍCIA A MAXIMALIZÁCIA Predtým, ako pôjdeme ďalej, najprv poskytneme predbežné koncepty použité v tomto článku. Nech G = (V, E) označuje graf s *N* uzlami *vi* ∈ V a hranami *eij* = (*vi*, *vj*) ∈ E. Vlastnosti uzlov, s predpokladaným empirickým rozdelením pravdepodobnosti P, sú dané ako *X* ∈ R*N* ×*D* = {*x* 1, · · · , *x N*} kde *xi* ∈ R*D* označuje vlastnosť uzla *vi*. Matica susednosti *A* ∈ R*N* ×*N* reprezentuje pripojenia hrán, kde *Aij* priradená hrane *eij* môže byť reálne číslo alebo viacrozmerný vektor1. Cieľom učenia reprezentácií grafov je naučiť kodér *f* : R*N* ×*D* × R*N* ×*N* → R*N* ×*D*', tak aby skryté vektory *H* = {*h*1, · · · , *hN*} = *f* (*X*, *A*) indikovali reprezentácie na vysokej úrovni pre všetky uzly. Proces kódovania možno prepísať v tvare pre jednotlivé uzly. Aby sme to ukázali, definujeme *Xi* a *Ai* pre uzol *i* ako zodpovedajúce vlastnosti jeho susedov a zodpovedajúcu maticu susednosti podmienenú susedmi. Konkrétne, *Xi* pozostáva zo všetkých k-hop susedov *vi* s *k* ≤ *l*, ak je kodér *f* l-vrstvová GNN, a obsahuje samotný uzol *i*, ak ďalej pridáme samoprípoje (self-loops) v matici susednosti. Tu nazveme podgraf rozšírený pomocou *Xi* a *Ai* ako *podporný graf* pre uzol *i*, označený ako G*i*. S definíciou podporného grafu sa kódovanie pre každý uzol stáva *hi* = *f* (G*i*) = *f* (*Xi*, *Ai*). V Deep InfoMax [ ] je cieľom tréningu kodéra maximalizovať MI medzi jeho vstupmi a výstupmi. MI sa odhaduje použitím diskriminačnej siete na klasifikáciu vzoriek pochádzajúcich zo spoločného rozdelenia a vzoriek odvodených zo súčinu marginálnych rozdelení. Prirodzene, pri adaptácii myšlienky Deep InfoMax na grafy, by sme mali maximalizovať MI medzi reprezentáciou *hi* a podporným grafom G*i* pre každý uzol. Takéto grafové MI označujeme ako *I* (*hi*; G*i*). Je však nejednoznačné definovať I (*hi*; Gi). Obtiažnosti sú: Obtiažnosť definovania grafových vzájomných informácií. 20 • Grafové MI by malo byť invariantné vzhľadom na index uzla. Inými slovami, mali by sme mať *I* (*hi*; G*i*) = *I* (*hi*; G′*i*), ak sú G*i* a G′*i* navzájom izomorfné. • Ak použijeme metódu MINE na výpočet MI, diskriminátor v MINE akceptuje iba vstupy pevnej veľkosti. To je však neuskutočniteľné pre G*i*, pretože rôzne G*i* zvyčajne zahŕňajú rôzny počet uzlov a teda majú rôzne veľkosti. Aby sme sa vyhli problému definovania grafových vzájomných informácií, táto sekcia začína zavedením konceptu Feature Mutual Information (FMI), ktorý sa spolieha iba na vlastnosti uzlov. Na základe inšpirácie z dekompozície FMI potom definujeme Graphical Mutual Information (GMI), ktorá zohľadňuje vlastnosti uzlov a 3.1 Vlastné vzájomné informácie Označujeme empirické rozdelenie pravdepodobnosti vlastností uzlov *Xi* ako *p*(*Xi*), pravdepodobnosť *hi* ako *p*(*hi*) a spoločné rozdelenie ako *p*(*hi*, *Xi*). Podľa teórie informácií je MI medzi *hi* a *Xi* definovaná ako Zaujímavé je, že máme nasledujúcu tému dekompozície vzájomných informácií na výpočet *I* (*hi*; *Xi*). Teorém 1 (Dekompozícia vzájomných informácií). *Ak je podmienená pravdepodobnosť p*(*hi*|*Xi*) *multiplikatívna (pozri definíciu multiplikatívnosti v [ ]), globálna vzájomná informácia I* (*hi*; *Xi*) *definovaná v rov. * *môže byť dekomponovaná na vážený súčet lokálnych MI, konkrétne,* 36 (1) *kde, xj* *je j-tý sused uzla i, in* *je počet všetkých prvkov v Xi*, *a váha wij spĺňa* ≤ *wij* ≤ 1 *pre každé j.* 1 Na dôkaz vyššie uvedeného teorému najprv uvedieme dve lemy a definíciu. Lema 1. *Pre ľubovoľné náhodné premenné X, Y a Z platí* S dekompozíciou v Teoréme môžeme vypočítať pravú stranu rov. pomocou MINE, pretože vstupy diskriminátora sú teraz páry (*hi*, *xj*), ktorých veľkosť sa vždy zachováva rovnaká ( *t. j.*, *D*′×*D*). Okrem toho môžeme upraviť váhy tak, aby odrážali izomorfnú transformáciu vstupných grafov. Napríklad, ak *Xi* obsahuje iba jednohopových susedov uzla *i*, nastavenie všetkých váh na rovnaké hodnoty povedie k rovnakej MI pre vstupné uzly v rôznych poradiach. 1, (2) Napriek niektorým výhodám dekompozície je ťažké charakterizovať presné hodnoty váh, pretože súvisia s hodnotami *I* (*hi*; *xj*) a ich základnými rozdeleniami pravdepodobnosti. Triviálnym spôsobom je nastaviť všetky váhy na , potom maximalizácia pravej strany rov. je ekvivalentná maximalizácii dolnej hranice *I* (*hi*; *Xi*), čím sa do istej miery maximalizuje aj skutočná FMI. Okrem tejto metódy navyše poskytujeme vylepšené riešenie zvážením váh ako trénovateľných pozorností, čo je téma v nasledujúcej podsekcii. 1 (2) Inšpirovaní dekompozíciou v Teoréme sa snažíme skonštruovať trénovateľné váhy z iného aspektu grafov ( *t. j.*, 3.2 Vzájomné informácie citlivé na topológiu 1, topologického pohľadu), aby hodnoty *wij* mohli byť flexibilnejšie a zachytávali inherentné vlastnosti grafov. Nakoniec odvodíme definíciu Grafových vzájomných informácií (GMI). Definícia 2 (Grafové vzájomné informácie). *MI medzi skrytým vektorom h a jeho podporným grafom* G = (*X*, *A*) *je definovaná ako* kde definície *xj* a *in* sú rovnaké ako v Teoréme 1, *aij* je váha/vlastnosť hrany v matici susednosti A a σ(·) je sigmoídna funkcia. Intuitívne, váha *wij* v prvej časti rov. (10) meria zvládnuté v experimentoch sú nevážené. Formálne, vypočítame I (*wij*; *aij*) = *aij*log*wij* + (1 − *aij* )log(1 − *wij*). (12) Maximalizáciou I (*hi*; *Gi*) so súčtom rov. (11) a rov. (12) cez všetky skryté vektory H, dosahujeme našu kompletnú cieľovú funkciu pre príspevok lokálnej MI ku globálnej. Implementujeme príspevok I (*hi*; *xj*) podobnosťou medzi reprezentáciami *hi* a *hj* (*t. j.*, *wij* = σ (*hThj*)). Medzitým člen I (*wij*; *aij*) maximalizuje MI medzi *wij* a váhou/vlastnosťou hrany vstupného grafu ( *t. j.*, *aij*), aby sa vynútilo, že *wij* zodpovedá topologickým vzťahom. V tomto zmysle by stupeň príspevku mal byť konzistentný s blízkosťou v topologickej štruktúre, čo je bežne prijatý fakt, že *wij* môže byť väčšie, ak je uzol *j* "bližšie" k uzlu *i* a menšie inak. Táto stratégia kompenzuje chybu, že FMI sa zameriava iba na vlastnosti uzlov a umožňuje lokálnym MI prispievať ku globálnej adaptívne. Pre lepšie pochopenie myšlienky pozornosti v tejto stratégii sa môžete obrátiť na GCN založené na pozornosti [40]. Všimnite si, že definícia rov. (10) je aplikovateľná pre všeobecné prípady. Pre určité špecifické situácie môžeme rov. (10) mierne upraviť pre efektivitu. Napríklad, pri práci s neváženými grafmi (tj. hodnota hrany je 1, ak je spojená, a 0 inak), môžeme nahradiť druhý člen MI I (*wij*; *aij*) negatívnou krížovou entropiou. Minimalizácia krížovej entropie tiež prispieva k maximalizácii MI a poskytuje efektívnejší výpočet. Viac detailov odložíme do nasledujúcej sekcie. Celkovo existuje niekoľko výhod vďaka definícii rov. (10). Po prvé, tento druh MI je invariantný voči izomorfnej transformácii vstupných grafov. Po druhé, je výpočtovo uskutočniteľný, pretože každá zložka na pravej strane môže byť odhadnutá pomocou MINE. Dôležitejšie je, že GMI je výkonnejšia ako DGI pri zachytávaní pôvodných vstupných informácií kvôli jej explicitnej korelácia medzi skrytými vektormi a vstupnými vlastnosťami uzlov a hrán vo jemne zrnnom uzlovom meradle. 3.3 Maximalizácia GMI Teraz priamo maximalizujeme pravú stranu rov. s pomocou MINE. Všimnite si, že MINE odhaduje dolnú hranicu MI pomocou Donsker-Varadhanovej (DV) [ ] reprezentácie KL-divergencie medzi spoločným rozdelením a súčinom marginálnych rozdelení. Keďže sa viac zameriavame na maximalizáciu MI namiesto získania jej špecifickej hodnoty, možno použiť iné ne-KL alternatívy, ako je Jensen-Shannon MI estimator (JSD) [ ] a Noise-Contrastive estimator (infoNCE) [ ], na jej nahradenie. Na základe experimentálnych zistení a analýzy v [ ] sa v tomto článku z dôvodu účinnosti a efektívnosti uchýlime k JSD odhadovaču, pretože infoNCE odhadovač je citlivý na stratégie negatívneho vzorkovania (počet negatívnych vzoriek), a preto sa môže stať prekážkou pre rozsiahle dátové sady s obmedzenou dostupnou pamäťou. Naopak, necitlivosť JSD odhadovača na stratégie negatívneho vzorkovania a jeho rešpektovateľný výkon pri mnohých úlohách ho robia vhodnejším pre našu úlohu. Konkrétne, *I* (*hi*; *xj*) v prvej časti rov. vypočítame pomocou (10) 10 30 31 20 (10) kde D*w*: *D* × *D*′ → R je diskriminátor skonštruovaný neurónovou sieťou s parametrom *w*. *x j* je negatívna vzorka odobraná z P = P a *sp*(*x*) = log