Novi način za obuku AI na grafičkim podacima bez nadzora

```html Autori: Zhen Peng Wenbing Huang Minnan Luo Qinghua Zheng Yu Rong Tingyang Xu Junzhou Huang APSTRAKTNO Bogatstvo sadržaja raznih informacionih mreža kao što su društvene mreže i komunikacione mreže pruža neviđen potencijal za učenje izrazitih reprezentacija visokog kvaliteta bez eksternog nadzora. Ovaj rad istražuje kako očuvati i ekstrahovati obilje informacija iz podataka strukturiranih u grafove u prostor ugrađenih reprezentacija na nadziran način. U tu svrhu, predlažemo nov koncept, Grafičku uzajamnu informaciju (GMI), za merenje korelacije između ulaznih grafova i skrivenih reprezentacija visokog nivoa. GMI generalizuje ideju konvencionalnih proračuna uzajamne informacije iz vektorskog prostora u domen grafa gde je merenje uzajamne informacije iz dva aspekta karakteristika čvorova i topološke strukture neophodno. GMI pokazuje nekoliko prednosti: Prvo, nepromenljiv je na izomorfnu transformaciju ulaznih grafova—neizbežno ograničenje u mnogim postojećim algoritmima za učenje reprezentacija grafova; Osim toga, može se efikasno proceniti i maksimizirati trenutnim metodama procene uzajamne informacije kao što je MINE; Konačno, naša teorijska analiza potvrđuje njegovu ispravnost i racionalnost. Uz pomoć GMI, razvijamo model nadziranog učenja obučen maksimiziranjem GMI između ulaza i izlaza neuronskog grafičkog enkodera. Obimni eksperimenti na transduktivnoj, kao i na induktivnoj klasifikaciji čvorova i predviđanju veza, pokazuju da naša metoda nadmašuje savremene nadzirane parnjake, a ponekad čak i nadmašuje performanse nadziranih metoda. 1 UVOD Radi postizanja pouzdane kvantitativne analize za različite informacione mreže, učenje reprezentacija visokog kvaliteta za podatke strukturirane u grafove postalo je jedna od trenutno fascinantnih tema. Nedavne metode ka ovom cilju, koje se obično kategorizuju kao Grafičke Neuronske Mreže (GNNs), postigle su značajan napredak u velikom broju zadataka učenja, kao što su klasifikacija čvorova [ , , ], predviđanje veza [ , , ], poravnavanje grafova [ , , ], generisanje molekula [ , , ], da navedemo samo neke. Uprkos plodnom napretku, treniranje GNNs u postojećim pristupima obično zahteva određeni oblik nadzora. Nesumnjivo, informacije o etiketama su skupe za sticanje—ručna anotacija ili plaćanje dozvole, i čak je nemoguće postići zbog politike privatnosti. Da ne spominjemo da je pouzdanost datih etiketa ponekad upitna. Stoga, kako postići visokokvalitetnu grafičku reprezentaciju bez nadzora postaje neophodno za veliki broj praktičnih slučajeva, što motiviše proučavanje ovog rada. 35 42 50 26 27 49 12 19 43 4 5 46 Pažljivim ispitivanjem naših prikupljenih podataka strukturiranih u grafove, otkrivamo da oni generalno potiču iz različitih izvora kao što su društvene mreže, mreže citata i komunikacione mreže gde postoji ogromna količina informacija o sadržaju i vezama. Na primer, podaci na mnogim društvenim platformama kao što su Twitter, Flickr i Facebook uključuju karakteristike korisnika, , osnovne lične detalje, tekstove, slike, IP, i njihove odnose, , kupovina istog predmeta, prijateljstvo. Ovi bogati podaci o sadržaju su dovoljni za naknadne zadatke rudarenja bez dodatnog vođenja: ako dva entiteta pokazuju ekstremnu sličnost u karakteristikama, postoji velika verovatnoća veze između njih (predviđanje veze), i verovatno pripadaju istoj kategoriji (klasifikacija); ako dva entiteta povezuju isti entitet, verovatno imaju slične karakteristike (preporuka). U tom smislu, očuvanje i izdvajanje što je moguće više informacija iz informacionih mreža u prostor ugrađivanja olakšava učenje izrazitih reprezentacija visokog kvaliteta koje pokazuju željene performanse u zadacima rudarenja bez ikakvog oblika nadzora. Nadzirano učenje grafova je povoljniji izbor u mnogim slučajevima zbog slobode od etiketa, posebno kada nameravamo da iskoristimo velike količine neoznačenih podataka u divljini. npr. npr. Da bismo u potpunosti nasledili bogate informacije u grafovima, u ovom radu, izvodimo grafičko ugrađivanje zasnovano na maksimizaciji uzajamne informacije (MI), inspirisani empirijskim uspehom metode Deep Info-Max [ ] koja radi na slikama. Da bismo otkrili korisne reprezentacije, Deep InfoMax trenira enkoder da maksimizira MI između svojih ulaza ( , slike) i izlaza ( , skriveni vektori). Kada razmatramo Deep InfoMax u domenu grafova, prvi kamen koji moramo preći je kako definisati MI između grafova i skrivenih vektora, dok je topologija grafova komplikovanija od slika (videti sliku Jedan od izazova je osigurati da funkcija MI između skrivenih reprezentacija svakog čvora i karakteristika ulaznih suseda zadovolji simetrijsku osobinu, ili ekvivalentno, da bude nepromenljiva na permutacije suseda. Kao jedan nedavni rad koji razmatra MI, Deep Graph Infomax (DGI) [ ] prvo ugrađuje ulazni graf i odgovarajući modifikovan graf, zatim sumira ulazni graf kao vektor putem funkcije čitanja, na kraju maksimizira MI između ovog sumarnog vektora i skrivenih reprezentacija diskriminišući ulazni graf (pozitivni uzorak) od modifikovanog grafa (negativni uzorak). Slika daje lako razumljiv pregled DGI-ja. Maksimizacija ove vrste MI se pokazala ekvivalentnom maksimizaciji MI između karakteristika ulaznih čvorova i skrivenih vektora, ali ova ekvivalencija važi pod nekoliko unapred postavljenih uslova, , funkcija čitanja treba da bude injektivna, što se čini previše ograničenim u stvarnim slučajevima. Čak i ako možemo garantovati postojanje injektivne funkcije čitanja određenim dizajnom, , onaj korišćen u DeepSets [ ], injektivna sposobnost funkcije čitanja takođe utiče na to kako se njeni parametri treniraju. To znači da originalno-injektivna funkcija još uvek ima rizik da postane ne-injektivna ako se trenira bez ikakvog eksternog nadzora. A ako funkcija čitanja nije injektivna, informacija ulaznog grafa sadržana u sumarnom vektoru će se smanjiti kako se veličina grafa povećava. Štaviše, DGI ostaje na gruboj maksimizaciji MI na nivou grafa/patch-a. Stoga u DGI-ju nema garancije da enkoder može destilirati dovoljno informacija iz ulaznih podataka jer nikada ne korelira pažljivo skrivene reprezentacije sa svojim originalnim ulazima. 20 tj. tj. 1). 41 1 npr. npr. 47 U ovom radu, predlažemo jednostavniji način razmatranja MI u smislu grafičkih struktura bez korišćenja bilo kakve funkcije čitanja ili funkcije modifikacije. Direktno izvodimo MI upoređujući ulaz ( , podgraf koji se sastoji od ulaznih suseda) i izlaz ( , skrivena reprezentacija svakog čvora) enkodera. I zanimljivo, naše teorijske derivacije pokazuju da se direktno formulisani MI može razložiti na ponderisani zbir lokalnih MI između svake karakteristike suseda i skrivenog vektora. Na ovaj način, razložili smo ulazne karakteristike i učinili proračun MI izvodljivim. Štaviše, ova forma MI lako može zadovoljiti simetrijsku osobinu ako prilagodimo vrednosti težina. Više detalja potražite u § Kako se gore navedeni MI uglavnom meri na nivou karakteristika čvorova, nazivamo ga MI karaktera (FMI). tj. tj. 3.1. Dva preostala problema sa FMI: kombinovane težine su još uvek nepoznate i ne uzima u obzir topologiju ( , karakteristike veza). Da bismo dalje rešili ova dva problema, definišemo naše merenje Grafičke Uzajamne Informacije (GMI) zasnovano na FMI. Konkretno, GMI primenjuje intuitivnu dodelu vrednosti postavljanjem težina u FMI jednakim blizini svakog suseda ciljnom čvoru u prostoru reprezentacije. Što se tiče zadržavanja informacije o topologiji, GMI dodatno koreliše ove težine sa karakterističnim vezama ulaza putem dodatnog člana uzajamne informacije. Rezultujući GMI je topološki nepromenljiv i takođe izračunljiv pomoću metoda procene neuronske uzajamne informacije (MINE) Glavni doprinosi našeg rada su sledeći: 1. 2. tj. [2]. • : Generalizujemo konvencionalnu procenu MI u domen grafova i u skladu s tim predlažemo novi koncept Grafičke Uzajamne Informacije (GMI). GMI je slobodan od Koncepti potencijalnog rizika uzrokovanog funkcijom čitanja jer razmatra MI između ulaznih grafova i ugrađivanja visokog nivoa na direktan način. • : Kroz našu teorijsku analizu, dajemo izvodljiv i izračunljiv oblik GMI koji razlaže Algoritmi celokupni GMI na ponderisani zbir lokalnih MI. Uz pomoć MINE metode, maksimizacija GMI se lako postiže na nivou čvora. • : Verifikujemo efikasnost GMI na nekoliko popularnih zadataka klasifikacije čvorova i predviđanja veza Eksperimentalni nalaz uključujući transdiktivne i induktivne. Eksperimenti pokazuju da naš metod pruža obećavajuće performanse na raznim merilima i ponekad čak nadmašuje nadzirane parnjake. 2 POVEZANI RADOVI U skladu sa fokusom našeg rada, kratko pregledamo prethodne radove u dve sledeće oblasti: procena uzajamne informacije, i neuronske mreže za učenje reprezentacija nad grafovima. 1. 2. . Kao što InfoMax princip [ ] zagovara maksimizaciju MI između ulaza i izlaza neuronskih mreža, mnoge metode kao što su ICA algoritmi [ , ] pokušavaju da primene ideju MI u nadziranom učenju karakteristika. Ipak, ove metode se ne mogu lako generalizovati na duboke neuronske mreže zbog poteškoća u izračunavanju MI između visoko-dimenzionalnih kontinuiranih promenljivih. Srećom, Procena Neuronske Uzajamne Informacije (MINE) [ ] čini procenu MI na dubokim neuronskim mrežama izvodljivom treniranjem statističke mreže kao klasifikatora za razlikovanje uzoraka koji potiču iz zajedničke distribucije i proizvoda marginalnih distribucija dve slučajne promenljive. Konkretno, MINE koristi eksplicitnu KL-baziranu formulaciju MI, dok se ne-KL alternativa, Jensen-Shannon divergencija (JSD) [ ], može koristiti bez brige o preciznoj vrednosti MI. Procena uzajamne informacije 3 1 21 2 30 . Sa brzim razvojem grafičkih neuronskih mreža (GNNs), veliki broj algoritama za učenje reprezentacija grafova zasnovanih na GNNs predložen je poslednjih godina, koji pokazuju jače performanse od tradicionalnih pristupa zasnovanih na slučajnim hodanjima i faktorizaciji [ , , , , ]. Tipično, ove metode se mogu podeliti na nadzirane i nenadzirane kategorije. Među njima, postoji bogata literatura o nadziranom učenju reprezentacija nad grafovima [ , , , , ]. Uprkos njihovoj raznolikosti u mrežnoj arhitekturi, postižu empirijski uspeh uz pomoć etiketa koje često nisu dostupne u realističnim scenarijima. U ovom slučaju, nenadzirane metode učenja grafova [ , , ] imaju širi potencijal primene. Dobro poznata metoda je GraphSAGE [ ], induktivni okvir za treniranje GNNs putem cilja zasnovanog na slučajnom hodanju u svom nenadziranom okruženju. A nedavno, DGI [ ] primenjuje ideju maksimizacije MI u domen grafova i postiže jake performanse na nenadziran način. Međutim, DGI implementira maksimizaciju grube granularnosti ( , maksimizaciju MI na nivou grafa/patch-a) što otežava očuvanje delikatnih informacija u ulaznom grafu. Osim toga, uslov postavljen na funkciju čitanja korišćenu u DGI-ju čini se previše ograničenim u stvarnim slučajevima. Nasuprot tome, fokusiramo se na uklanjanje ograničenja funkcije čitanja i postizanje maksimizacije grafičke uzajamne informacije na nivou čvora direktnim maksimiziranjem MI između ulaza i izlaza enkodera. Reprezentacije izvedene našom metodom su sofisticiranije u zadržavanju informacija ulaznog grafa, što osigurava njegov potencijal za naknadne zadatke rudarenja grafova, , klasifikaciju čvorova, predviđanje veza i preporuke. Neuronske mreže za učenje reprezentacija grafova 6 15 33 34 39 7 9 25 40 48 11 16 41 16 41 tj. npr. 3 GRAFIČKA UZAJAMNA INFORMACIJA: DEFINICIJA I MAKSIMIZACIJA Pre nego što nastavimo, prvo pružamo preliminarni koncept koji se koristi u ovom radu. Neka G = (V, E) označava graf sa čvorova ∈ V i veza = ( , ) ∈ E. Karakteristike čvorova, sa pretpostavljenom empirijskom raspodelom verovatnoće P, date su sa ∈ N vi eij vi vj X R × = { 1, · · · , } gde ∈ R označava karakteristiku za čvor . Adjacencijska matrica ∈ R × predstavlja veze veza, gde povezan sa vezom može biti realan broj ili višedimenzionalni vektor1. N D x x N xi D vi A N N Aij eij Cilj učenja reprezentacija grafova je naučiti enkoder : R × × R × → R × ′ , tako da skriveni vektori = { 1, · · · , } = ( , ) ukazuju na reprezentacije visokog nivoa za sve čvorove. Proces kodiranja se može ponovo napisati u obliku po čvoru. f N D N N N D H h hN f X A Da bismo ovo pokazali, definišemo i za čvor kao respektivno karakteristike njegovih suseda i odgovarajuću adjacencijsku matricu Xi Ai i pod uslovom suseda. Konkretno, sadrži sve k-hop susede od sa ≤ kada je enkoder -slojni GNN, i sadrži sam čvor ako dalje dodamo samopovezivanja u adjacencijsku matricu. Ovde, nazivamo podgraf proširen sa i kao za čvor , označen sa G . Sa definicijom podržavajućeg grafa, kodiranje za svaki čvor postaje = (G ) = ( , ). Xi vi k l f l i Xi Ai podržavajući graf i i hi f i f Xi Ai U Deep InfoMax [ ], cilj treniranja enkodera je maksimizirati MI između njegovih ulaza i izlaza. MI se procenjuje korišćenjem statističke mreže kao diskriminatora za klasifikaciju uzoraka koji potiču iz zajedničke distribucije i onih izvučenih iz proizvoda marginalnih distribucija. Naravno, kada se ideja Deep InfoMax prilagodi grafovima, trebalo bi da maksimiziramo MI između reprezentacije i podržavajućeg grafa G za svaki čvor. Obeležavamo takvu grafičku MI kao ( ; G ). Međutim, nije jednostavno definisati I (hi ; Gi ). Poteškoće su: Poteškoće u definisanju grafičke uzajamne informacije. 20 hi i I hi i • Grafička MI treba da bude nepromenljiva u odnosu na indeks čvora. Drugim rečima, trebalo bi da imamo ( ; G ) = ( ; G′ ), ako su G i G′ izomorfni jedan drugom. I hi i I hi i i i • Ako usvojimo MINE metodu za izračunavanje MI, diskriminator u MINE prihvata samo ulaze fiksne veličine. Ovo je još uvek neizvodljivo za G jer različiti G obično uključuju različit broj čvorova i stoga su različitih veličina. i i Da bismo prevazišli problem definisanja grafičke uzajamne informacije, ovaj odeljak počinje uvođenjem koncepta MI karaktera (FMI) koji se oslanja samo na karakteristike čvorova. Na osnovu inspiracije iz dekompozicije FMI, zatim definišemo Grafičku Uzajamnu Informaciju (GMI), koja uzima u obzir kako karakteristike čvorova, tako i 3.1 Karakteristična Uzajamna Informacija Obeležavamo empirijsku raspodelu verovatnoće karakteristika čvorova kao ( ), verovatnoću kao ( ), i zajedničku distribuciju kao ( , ). Prema teoriji informacija, MI između i definiše se kao Xi p Xi hi p hi p hi Xi hi Xi Zanimljivo je da imamo sledeću teoremu dekompozicije uzajamne informacije za izračunavanje ( ; ). I hi Xi Teorema 1 (Dekompozicija Uzajamne Informacije). ( | ) ( ; ) Ako je uslovna verovatnoća p hi Xi multiplikativna (videti definiciju multiplikativnosti u [ ]), globalna uzajamna informacija I 36 hi Xi definisana u Eq. (1) može se razložiti kao ponderisani zbir lokalnih MI, naime, ≤ ≤ 1 gde je xj j-ti sused čvora i, in je broj svih elemenata u Xi , a ponder wi j zadovoljava 1 wi j za svako j. Da bismo dokazali gornju teoremu, prvo uvodimo dve leme i jednu definiciju. Lema 1. Za bilo koje slučajne promenljive X, Y , i Z, imamo Sa dekompozicijom u Teoremi možemo izračunati desnu stranu Eq. putem MINE kao ulaze diskriminatora, koji sada postaju parovi ( , ) čija veličina uvek ostaje ista ( , ′-po- ). Osim toga, možemo prilagoditi težine da odražavaju izomorfnu transformaciju ulaznih grafova. Na primer, ako sadrži samo jednokorakne susede čvora , postavljanje svih težina da budu identične dovešće do iste MI za ulazne čvorove u različitim redosledima. 1, (2) hi xj tj. D D Xi i Uprkos nekim prednostima dekompozicije, teško je okarakterisati tačne vrednosti težina jer su povezane sa vrednostima ( ; ) i njihovim osnovnim raspodelama verovatnoće. I hi xj Trivijalan način je postavljanje svih težina na , zatim maksimiziranje desne strane Eq. ekvivalentno maksimiziranju donje granice ( ; ), čime se stvarni FMI takođe maksimizira do nekog stepena. Osim ove metode, dodatno pružamo poboljšano rešenje razmatranjem težina kao treniranih pažnji, što je tema sledećeg pododeljka. 1 (2) I hi Xi Inspirisani dekompozicijom u Teoremi pokušavamo da konstruišemo trenirane težine iz drugog aspekta grafova ( , 3.2 Uzajamna Informacija Svesna Topologije 1, tj. topološkog pogleda) tako da vrednosti mogu biti fleksibilnije i uhvatiti inherentna svojstva grafova. Konačno izvodimo definiciju Grafičke Uzajamne Informacije (GMI). wi j Definicija 2 (Grafička Uzajamna Informacija). G = ( , ) MI između skrivenog vektora h i njegovog podržavajućeg grafa X A definiše se kao gde su definicije i xj i in iste kao u Teoremi 1, aij je težina/karakteristika veze u adjacencijskoj matrici A, i σ (·) je sigmoidalna funkcija. Intuitivno, težina wi j u prvom termu Eq. (10) meri obrađeno u eksperimentima je neponderisano. Formalno, izračunavamo I (wi j ; aij ) = aijloдwi j + (1 − aij )loд(1 − wi j ). (12) Maksimiziranjem I (hi ; Gi ) sa sumom Eq. (11) i Eq. (12) nad svim skrivenim vektorima H , dolazimo do naše kompletne ciljne funkcije za doprinos lokalnog MI globalnom. Implementiramo doprinos I (hi ; xj ) sličnošću između reprezentacija hi i hj (tj. wi j = σ (hThj )). Istovremeno, termin I (wi j ; aij ) maksimizira MI između wi j i težine/karakteristike veze ulaznog grafa (tj. aij ) da bi prisilili wi j da se pridržava topoloških odnosa. U ovom smislu, stepen doprinosa biće konzistentan sa blizinom u topološkoj strukturi, što se obično prihvata kao činjenica da wi j može biti veći ako je čvor j “bliži” čvoru i i manji inače. Ova strategija kompenzuje nedostatak što se FMI fokusira samo na karakteristike čvorova i čini da lokalni MI doprinose globalnom adaptivno. Da bismo bolje razumeli ideju pažnje u ovoj strategiji, možete pogledati GCN zasnovan na pažnji [40]. Napomena da je definicija Eq. (10) primenljiva za opšte slučajeve. Za određene specifične situacije, možemo malo modifikovati Eq. (10) radi efikasnosti. Na primer, kada se radi sa neponderisanim grafovima (tj. vrednost veze je 1 ako je povezano i 0 inače), možemo zameniti drugi MI termin I (wi j ; aij ) negativnim gubitkom unakrsne entropije. Minimizacija unakrsne entropije takođe doprinosi maksimizaciji MI, i pruža efikasniji proračun. Više detalja potražite u sledećem odeljku. Sve u svemu, postoji nekoliko prednosti po definiciji Eq. (10). Prvo, ova vrsta MI je nepromenljiva na izomorfnu transformaciju ulaznih grafova. Drugo, to je računarski izvodljivo jer svaka komponenta na desnoj strani može biti procenjena od strane MINE. Što je najvažnije, GMI je moćniji od DGI-ja u hvatanju originalnih informacija ulaza zbog eksplicitne korelacije između skrivenih vektora i karakteristika ulaza kako čvorova tako i veza na finom nivou čvora. 3.3 Maksimizacija GMI Sada direktno maksimiziramo desnu stranu Eq. uz pomoć MINE. Napomena da MINE procenjuje donju granicu MI sa Donsker-Varadhan (DV) reprezentacijom KL-divergencije između zajedničke distribucije i proizvoda marginalnih distribucija. Pošto se više fokusiramo na maksimiziranje MI umesto na dobijanje njegove specifične vrednosti, druge ne-KL alternative kao što su Jensen-Shannon MI estimator (JSD) [ ] i Noise-Contrastive estimator (infoNCE) [ ] mogu se koristiti da ga zamene. Na osnovu eksperimentalnih nalaza i analize u [ ], koristimo JSD estimator u ovom radu radi efikasnosti i delotvornosti, jer je infoNCE estimator osetljiv na strategije negativnog uzorkovanja (broj negativnih uzoraka) te stoga može postati prepreka za velike skupove podataka sa fiksnom dostupnom memorijom. Nasuprot tome, neosetljivost JSD estimatora na strategije negativnog uzorkovanja i njegov respektabilan učinak na mnogim zadacima čine ga pogodnijim za naš zadatak. Konkretno, izračunavamo ( ; ) u prvom termu Eq. pomoću (10) [10] 30 31 20 I hi xj (10) gde D : × ′ → R predstavlja diskriminator konstruisan neuronskom mrežom sa parametrom . je negativno uzorkovan iz P = P, i ( ) = (1 + ) označava meku-plus funkciju. w D D w x j sp x loд ex Kao što je pomenuto u § maksimiziramo ( ; ) izračunavanjem njegove unakrsne entropije umesto korišćenja JSD estimatora jer su grafovi sa kojima smo se bavili u eksperimentima neponderisani. Formalno, izračunavamo 3.2, I wi j aij

Novi način za obuku AI na grafičkim podacima bez nadzora

About Author

KOMENTARI

HANG TAGS

OVAJ ČLANAK JE PREDSTAVLJEN U

Related Stories

Light-Mode

Classic

Newspaper

Minty

Dark-Mode

Neon Noir

Minty

HN StartUps