'n Nuwe Manier om KI op Grafiekdata Sonder Toesig op te Lei'

Outeurs: Zhen Peng Wenbing Huang Minnan Luo Qinghua Zheng Yu Rong Tingyang Xu Junzhou Huang OPSOMMING Die rykdom in die inhoud van verskeie inligtingsnetwerke soos sosiale netwerke en kommunikasienetwerke bied die ongekende potensiaal vir die leer van hoë-gehalte uitdrukkingsvolle verteenwoordigings sonder eksterne toesig. Hierdie artikel ondersoek hoe om die oorvloedige inligting van graaf-gestruktureerde data in inbeddingruimte op 'n onbewaakte wyse te bewaar en te onttrek. Vir hierdie doel stel ons 'n nuwe konsep voor, Grafiese Onderlinge Inligting (GMI), om die korrelasie tussen invoergrawe en hoëvlak verborge verteenwoordigings te meet. GMI veralgemeen die idee van konvensionele onderlinge inligtingberekeninge van vektorruimte na die graafdomein waar die meet van onderlinge inligting uit twee aspekte van noduskenmerke en topologiese struktuur onontbeerlik is. GMI vertoon verskeie voordele: Eerstens, dit is onveranderlik tot die isomorfiese transformasie van invoergrawe - 'n onvermydelike beperking in baie bestaande graafverteenwoordigingsleeralgoritmes; Daarbenewens kan dit doeltreffend geskat en gemaksimeer word deur huidige onderlinge inligting-skattingsmetodes soos MINE; Laastens, ons teoretiese ontleding bevestig die korrektheid en rasionaliteit daarvan. Met die hulp van GMI ontwikkel ons 'n onbewaakte leermodel wat opgelei word deur GMI tussen die invoer en uitvoer van 'n graafneuraalenkoder te maksimeer. Besonderse eksperimente op transduktiewe sowel as induktiewe nodusklassifikasie en skakelvoorspelling demonstreer dat ons metode beter presteer as die staat van die kuns onbewaakte eweknieë, en soms selfs die prestasie van toesighouende oortref. 1 INLEIDING Om betroubare kwantitatiewe ontleding vir diverse inligtingsnetwerke te bereik, het hoë-gehalte verteenwoordigingsleer vir graaf-gestruktureerde data een van die huidige fassinerende onderwerpe geword. Onlangse metodes wat op hierdie doelwit gemik is, algemeen gekategoriseer as Graaf Neurale Netwerke (GNNs), het merkwaardige vooruitgang gemaak in 'n groot aantal leertake, soos nodusklassifikasie [ , , ], skakelvoorspelling [ , , ], graafbelyning [ , , ], molekulêre generasie [ , , ], om maar 'n paar te noem. Alhoewel daar vrugbare vordering is, vereis die opleiding van GNNs in bestaande benaderings gewoonlik 'n sekere vorm van toesig. Ongetwyfeld is die etiketinligting duur om te verkry - handmatige annotasie of betaling vir toestemming, en is selfs onmoontlik om te verkry as gevolg van privaatheidsbeleid. Om nie eens te praat van die betroubaarheid van gegewe etikette wat soms twyfelagtig is nie. Daarom word hoe om hoë-gehalte graafverteenwoordiging sonder toesig te verkry, noodsaaklik vir 'n groot aantal praktiese gevalle, wat die studie van hierdie artikel motiveer. 35 42 50 26 27 49 12 19 43 4 5 46 Deur noukeurig ons versamelde graaf-gestruktureerde data te ondersoek, vind ons dat dit oor die algemeen van verskillende bronne kom, soos sosiale netwerke, aanhalingnetwerke en kommunikasienetwerke waar 'n geweldige hoeveelheid inhoud en skakel inligting bestaan. Byvoorbeeld, data op baie sosiale platforms soos Twitter, Flickr en Facebook sluit kenmerke van gebruikers in, byvoorbeeld, basiese persoonlike besonderhede, tekste, beelde, IP, en hul verhoudings, byvoorbeeld, dieselfde item koop, vriende wees. Hierdie ryk inhouddata is voldoende om daaropvolgende myn-take sonder bykomende leiding te ondersteun: as twee entiteite uiterste ooreenkoms in kenmerke vertoon, is daar 'n hoë waarskynlikheid van 'n skakel tussen hulle (skakelvoorspelling), en hulle behoort waarskynlik tot dieselfde kategorie (klassifikasie); as twee entiteite albei na dieselfde entiteit skakel, het hulle waarskynlik soortgelyke eienskappe (aanbeveling). In hierdie sin fasiliteer die bewaring en onttrekking van soveel inligting as moontlik uit inligtingsnetwerke in inbeddingruimte die leer van hoë-gehalte uitdrukkingsvolle verteenwoordigings wat wenslike prestasie vertoon in myn-take sonder enige vorm van toesig. Onbewaakte graafverteenwoordigingsleer is in baie gevalle 'n gunstiger keuse as gevolg van die vryheid van etikette, veral wanneer ons voordeel wil trek uit 'n groot hoeveelheid ongemerkte data in die natuur. Om die ryk inligting in grawe ten volle te erf, voer ons in hierdie artikel graafinbedding uit gebaseer op Onderlinge Inligting (MI) maksimeer, geïnspireer deur die empiriese sukses van die Deep Info-Max metode [ ] wat op beelde werk. Om nuttige verteenwoordigings te ontdek, lei Deep InfoMax die enkoder op om MI tussen sy insette (d.w.s., die beelde) en uitsette (d.w.s., die verborge vektore) te maksimeer. Wanneer Deep InfoMax in die graafdomein oorweeg word, is die eerste klip wat ons moet omstap hoe om MI tussen grawe en verborge vektore te definieer, terwyl die topologie van grawe meer kompleks is as beelde (sien Figuur Een van die uitdagings is om te verseker dat die MI-funksie tussen elke nodus se verborge verteenwoordiging en sy buur-invoerkenmerke die simmetriese eienskap gehoorsaam, of ekwivalent, onveranderlik is tot permutasi van die buurte. Soos een onlangse werk wat MI oorweeg, plaas Deep Graph Infomax (DGI) [ ] eers 'n invoergraaf en 'n ooreenstemmende beskadigde graaf inbed, som dan die invoergraaf op as 'n vektor via 'n uitleesfunksie, maksimeer uiteindelik MI tussen hierdie opsommingsvektor en verborge verteenwoordigings deur die invoergraaf (positiewe monster) van die beskadigde graaf (negatiewe monster) te onderskei. Figuur gee 'n maklik verstaanbare oorsig van DGI. Maksimeer hierdie tipe MI is bewys as ekwivalent aan die maksimeer van die een tussen die invoernoduskenmerke en verborge vektore, maar hierdie ekwivalensie geld onder verskeie voorafbepaalde voorwaardes, byvoorbeeld, die uitleesfunksie moet inspuitend wees, wat nog steeds te beperkend blyk te wees in werklike gevalle. Selfs as ons die bestaan van inspuitende uitleesfunksie kan waarborg deur sekere ontwerp, byvoorbeeld, die een wat in DeepSets [ ] gebruik word, word die inspuitingsvermoë van die uitleesfunksie ook beïnvloed deur hoe sy parameters opgelei word. Dit wil sê dat 'n oorspronklik-inspuitende funksie steeds die risiko het om nie-inspuitend te word as dit sonder enige eksterne toesig opgelei word. En as die uitleesfunksie nie inspuitend is nie, sal die invoergraafinligting wat in 'n opsommingsvektor vervat is, afneem namate die grootte van die graaf toeneem. Boonop bly DGI in 'n growwe graaf/pleister-vlak MI maksimeer. Daarom is daar geen waarborg dat die enkoder voldoende inligting uit invoerdata kan onttrek nie, aangesien dit nooit verborge verteenwoordigings deeglik met hul oorspronklike invoere korreleer nie. 20 1). 41 1 47 In hierdie artikel stel ons 'n eenvoudiger manier voor om MI in terme van grafiese strukture te oorweeg sonder om enige uitleesfunksie en korrupsiefunksie te gebruik. Ons lei MI direk af deur die invoer (d.w.s., die sub-graaf wat die invoerbuurt bestaan) en die uitvoer (d.w.s., die verborge verteenwoordiging van elke nodus) van die enkoder te vergelyk. En interessant genoeg toon ons teoretiese afleidings dat die direk-geformuleerde MI opgedeel kan word in 'n geweegde som van plaaslike MIS tussen elke buurkenmerk en die verborge vektor. Op hierdie manier het ons die invoerkenmerke opgedeel en die MI-berekening hanteerbaar gemaak. Boonop kan hierdie vorm van MI maklik die simmetriese eienskap bevredig as ons die waardes van gewigte aanpas. Ons stel meer besonderhede uit na § Aangesien hierdie MI hoofsaaklik op die vlak van noduskenmerke gemeet word, noem ons dit Kenmerk Onderlinge Inligting (FMI). 3.1. Twee oorblywende kwessies oor FMI: die kombinerende gewigte is nog onbekend en dit hou nie rekening met die topologie nie (d.w.s., die randkenmerke). Om hierdie twee kwessies verder aan te spreek, definieer ons ons Grafiese Onderlinge Inligting (GMI) meting gebaseer op FMI. In die besonder pas GMI 'n intuïtiewe waardetoekenning toe deur die gewigte in FMI gelyk aan die nabyheid tussen elke buurman en die teiken nodus in die verteenwoordigingsruimte te stel. Wat die topologie-inligting behou, korreleer GMI verder hierdie gewigte met die invoerrandkenmerke via 'n bykomende onderlinge inligting term. Die resulterende GMI is topologies onveranderlik en ook berekenbaar met Onderlinge Inligting Neurale Skatting (MINE) Die hoofbydraes van ons werk is soos volg: 1. 2. . • : Ons veralgemeen die konvensionele MI-skatting na die graafdomein en stel gevolglik 'n nuwe konsep van Grafiese Onderlinge Inligting (GMI) voor. GMI is vry van die Konsepte potensiële risiko veroorsaak deur die uitleesfunksie aangesien dit MI tussen invoergrawe en hoëvlak inbeddings op 'n eenvoudige patroon oorweeg. • : Deur ons teoretiese ontleding gee ons 'n hanteerbare en berekenbare vorm van GMI wat die Algoritmes hele GMI in 'n geweegde som van plaaslike MIS ontbind. Met die hulp van die MINE-metode kan GMI-maksimeer maklik op 'n nodus-vlak bereik word. • : Ons verifieer die effektiwiteit van GMI op verskeie gewilde nodusklassifikasie en skakelvoorspelling Eksperimentele Bevindinge take, insluitend transduktiewe en induktiewe. Die eksperimente demonstreer dat ons metode belowende prestasie lewer op 'n verskeidenheid van maatstawwe en dit soms selfs die toesighouende eweknieë oortref. 2 VERWANTE WERK In lyn met die fokus van ons werk, bespreek ons kortliks die vorige werk in die volgende twee gebiede: onderlinge inligting skatting, en neurale netwerke vir die leer van verteenwoordiging oor grawe. 1. 2. . Soos die InfoMax beginsel [ ] die maksimeer van MI tussen die insette en uitsette van neurale netwerke voorstaan, probeer baie metodes soos ICA-algoritmes [ , ] om die idee van MI in onbewaakte kenmerkleer toe te pas. Nietemin kan hierdie metodes nie maklik na diep neurale netwerke veralgemeen word nie as gevolg van die probleme om MI tussen hoë-dimensionele deurlopende veranderlikes te bereken. Gelukkig maak Onderlinge Inligting Neurale Skatting (MINE) [ ] die skatting van MI op diep neurale netwerke moontlik deur 'n statistiekenetwerk op te lei as 'n klassifiseerder om monsters wat van die gesamentlike verspreiding en die produk van marginale van twee ewekansige veranderlikes afkomstig is, te onderskei. Spesifiek gebruik MINE die presiese KL-gebaseerde formulering van MI, terwyl 'n nie-KL alternatief, die Jensen-Shannon divergensie (JSD) [ ], gebruik kan word sonder die bekommernis oor die presiese waarde van MI. Onderlinge inligting skatting 3 1 21 2 30 . Met die vinnige ontwikkeling van graafneurale netwerke (GNNs), is 'n groot aantal graafverteenwoordigingsleeralgoritmes gebaseer op GNNs in die afgelope jare voorgestel, wat sterker prestasie toon as tradisionele ewekansige-loop-gebaseerde en faktoriseringsgebaseerde inbeddingsbenaderings [ , , , , ]. Tipies kan hierdie metodes in toesighouende en onbewaakte kategorieë verdeel word. Onder hulle is daar 'n ryk literatuur oor toesighouende verteenwoordigingsleer oor grawe [ , , , , ]. Ten spyte van hul variasie in netwerkargitektuur, behaal hulle empiriese sukses met die hulp van etikette wat dikwels nie in realistiese scenario's toeganklik is nie. In hierdie geval het onbewaakte grafleermetodes [ , , ] 'n breër toepassingspotensiaal. Die bekende metode is GraphSAGE [ ], 'n induktiewe raamwerk om GNNs op te lei deur 'n ewekansige-loop-gebaseerde doelwit in sy onbewaakte instelling. En onlangs pas DGI [ ] die idee van MI-maksimeer na die graafdomein toe en verkry sterk prestasie op 'n onbewaakte patroon. DGI implementeer egter 'n growwe-vlak maksimeer (d.w.s., maksimeer MI op graaf/pleister-vlak) wat dit moeilik maak om die delikate inligting in die invoergraaf te bewaar. Daarbenewens blyk die voorwaarde op die uitleesfunksie wat in DGI gebruik word, te beperkend te wees in werklike gevalle. Daarteenoor fokus ons op die verwydering van die beperking van die uitleesfunksie en die bereiking van grafiese onderlinge inligting maksimeer op 'n nodus-vlak deur MI direk tussen insette en uitsette van die enkoder te maksimeer. Verteenwoordigings wat deur ons metode verkry word, is meer gesofistikeerd in die behou van invoergraafinligting, wat sy potensiaal vir daaropvolgende graafmyn-take verseker, byvoorbeeld, nodusklassifikasie, skakelvoorspelling en aanbeveling. Neurale netwerke vir graafverteenwoordigingsleer 6 15 33 34 39 7 9 25 40 48 11 16 41 16 41 3 GRAFIESE ONDERLINGE INLIGTING: DEFINISIE EN MAKSIMEER Voordat ons verder gaan, verskaf ons eers die voorlopige konsepte wat in hierdie artikel gebruik word. Laat G = (V, E) 'n graaf met nodusse ∈ V en rande = ( , ) ∈ E voorstel. Die noduskenmerke, met aangetoonde empiriese waarskynlikheidsverspreiding P, word gegee deur ∈ N vi eij vi vj X R × = { 1, · · · , } waar ∈ R die kenmerk vir nodus verteenwoordig. Die aangrensingsmatriks ∈ R × verteenwoordig randverbindinge, waar wat aan rand assosieer is, 'n reële getal of meerdimensionale vektor1 kan wees. N D x x N xi D vi A N N Aij eij Die doel van graafverteenwoordigingsleer is om 'n enkoder : R × × R × → R × ′ , te leer, sodat die verborge vektore = { 1, · · · , } = ( , ) hoëvlak verteenwoordigings vir alle nodusse aandui. Die kodering proses kan in 'n nodus-wyse vorm herskryf word. f N D N N N D H h hN f X A Om dit te wys, definieer ons en vir nodus as onderskeidelik die kenmerke van sy buurmanne en die ooreenstemmende aangrensingsmatriks Xi Ai i voorwaardelik op die buurmanne. Besonderlik bestaan uit al die k-hop buurmanne van met ≤ wanneer die enkoder 'n -laag GNN is, en dit bevat die nodus self as ons self-lusse verder by die aangrensingsmatriks voeg. Hier noem ons die sub-graaf wat deur en uitgebrei word 'n vir nodus , aangedui as G . Met die definisie van ondersteuningsgraaf word die kodering vir elke nodus = (G ) = ( , ) vervat. Xi vi k l f l i Xi Ai ondersteuningsgraaf i i hi f i f Xi Ai In Deep InfoMax [ ], is die opleiding doelwit van die enkoder om MI tussen sy insette en uitsette te maksimeer. Die MI word geskat deur 'n statistiekenetwerk as 'n onderskeider te gebruik om monsters te klassifiseer wat van die gesamentlike verspreiding kom en die wat van die produk van marginale getrek word. Van nature, wanneer ons die idee van Deep InfoMax aan grawe aanpas, moet ons MI tussen die verteenwoordiging en die ondersteuningsgraaf G vir elke nodus maksimeer. Ons noem sulke grafiese MI as ( ; G ). Dit is egter nie eenvoudig om I (hi ; Gi ) te definieer nie. Die probleme is: Probleme in die definieer van grafiese onderlinge inligting. 20 hi i I hi i • Die grafiese MI moet onveranderlik wees ten opsigte van die nodusindeks. Met ander woorde, ons moet hê ( ; G ) = ( ; G′ ), as G en G′ isomorfies aan mekaar is. I hi i I hi i i i • As ons die MINE-metode vir MI-berekening aanvaar, aanvaar die onderskeider in MINE slegs insette van 'n vaste grootte. Dit is nog steeds onuitvoerbaar vir G aangesien verskillende G gewoonlik verskillende getalle nodusse insluit en dus van verskillende groottes is. i i Om die probleem van die definieer van grafiese onderlinge inligting te omseil, begin hierdie afdeling met die bekendstelling van die konsep van Kenmerk Onderlinge Inligting (FMI) wat slegs op noduskenmerke steun. Na inspirasie van die ontbinding van FMI, definieer ons dan Grafiese Onderlinge Inligting (GMI), wat beide die noduskenmerke en 3.1 Kenmerk Onderlinge Inligting Ons dui die empiriese waarskynlikheidsverspreiding van noduskenmerke aan as ( ), die waarskynlikheid van as ( ), en die gesamentlike verspreiding deur ( , ). Volgens inligtingsteorie word die MI tussen en gedefinieer as Xi p Xi hi p hi p hi Xi hi Xi Interessant genoeg het ons die volgende onderlinge inligting ontbindingsteorema vir die berekening van ( ; ). I hi Xi Teorema 1 (Onderlinge Inligting Ontbinding). ( | ) ( ; ) As die voorwaardelike waarskynlikheid p hi Xi multiplikatief is (sien die definisie van multiplikatief in [ ]), kan die globale onderlinge inligting I 36 hi Xi gedefinieer in Eq. (1) ontbind word as 'n geweegde som van plaaslike MIS, naamlik, ≤ ≤ 1 waar xj die j-de buurman van nodus i is, in is die getal van alle elemente in Xi , en die gewig wij voldoen aan 1 wij vir elke j. Om die bogenoemde teorema te bewys, stel ons eers twee lemmas en 'n definisie bekend. Lemma 1. Vir enige ewekansige veranderlikes X, Y , en Z, het ons Met die ontbinding in Teorema kan ons die regterkant van Eq. bereken via MINE, aangesien die insette vir die onderskeider nou die pare van ( , ) is waarvan die grootte altyd dieselfde bly (d.w.s., ′-by- ). Boonop kan ons die gewigte aanpas om die isomorfiese transformasie van invoergrawe te weerspieël. Byvoorbeeld, as slegs een-hop buurmanne van nodus bevat, sal die instelling van alle gewigte identies lei tot dieselfde MI vir die invoernodusse in verskillende volgorde. 1, (2) hi xj D D Xi i Ten spyte van sekere voordele van die ontbinding, is dit moeilik om die presiese waardes van die gewigte te karakteriseer aangesien dit verwant is aan die waardes van ( ; ) en hul onderliggende waarskynlikheidsverspreidings. I hi xj 'n Triviale manier is om alle gewigte as te stel, dan maksimeer die regterkant van Eq. ekwivalent aan die maksimeer van die onderste limiet van ( ; ), waardeur die ware FMI ook tot 'n sekere mate gemaksimeer word. Behalwe hierdie metode, bied ons ook 'n meer verbeterde oplossing deur die gewigte as opleibare aandag te beskou, wat die onderwerp in die volgende subafdeling is. 1 (2) I hi Xi Geïnspireer deur die ontbinding in Teorema probeer ons om opleibare gewigte uit die ander aspek van grawe te konstrueer (d.w.s., 3.2 Topologie-Bewuste Onderlinge Inligting 1, topologiese oogpunt) sodat die waardes van meer buigsaam kan wees en die inherente eienskap van grawe kan vasvang. Uiteindelik lei ons die definisie van Grafiese Onderlinge Inligting (GMI) af. wij Definisie 2 (Grafiese Onderlinge Inligting). G = ( , ) Die MI tussen die verborge vektor h en sy ondersteuningsgraaf X A word gedefinieer as waar die definisies van beide xj en in dieselfde is as Teorema 1, aij is die randgewig/kenmerk in die aangrensingsmatriks A, en σ (·) is 'n sigmoidfunksie. Intuïtief meet die gewig wij in die eerste term van Eq. (10) die hanteer in eksperimente is ongeweeg. Formeel bereken ons I (wij ; aij ) = aijloдwij + (1 − aij )loд(1 − wij ). (12) Deur I (hi ; Gi ) te maksimeer met die som van Eq. (11) en Eq. (12) oor alle verborge vektore H , kom ons by ons volledige doelwitfunksie vir bydrae van 'n plaaslike MI tot die globale een. Ons implementeer die bydrae van I (hi ; xj ) deur die ooreenkoms tussen verteenwoordigings hi en hj (d.w.s., wij = σ (hThj )). Intussen maksimeer die term I (wij ; aij ) MI tussen wij en die randgewig/kenmerk van die invoergraaf (d.w.s., aij ) om wij te dwing om aan topologiese verwantskappe te voldoen. In hierdie sin sal die graad van die bydrae ooreenstem met die nabyheid in topologiese struktuur, wat algemeen aanvaar word as 'n feit dat wij groter kan wees as nodus j "nader" aan nodus i is en kleiner andersins. Hierdie strategie kompenseer vir die fout dat FMI slegs op noduskenmerke fokus en laat plaaslike MIS adaptief tot die globale een bydra. Om die idee van aandag in hierdie strategie beter te verstaan, kan jy verwys na die aandag-gebaseerde GCN. Let wel dat die definisie van Eq. (10) van toepassing is vir algemene gevalle. Vir sekere spesifieke situasies kan ons Eq. (10) effens aanpas vir doeltreffendheid. Byvoorbeeld, wanneer ons met ongeweegde grawe te doen het (naamlik, die randwaarde is 1 indien verbind en 0 andersins), kan ons die tweede MI-term I (wij ; aij ) vervang met 'n negatiewe kruis-entropie verlies. Die minimering van die kruis-entropie dra ook by tot MI-maksimeer, en dit lewer 'n meer doeltreffende berekening. Ons stel meer besonderhede uit in die volgende afdeling. Oor die algemeen is daar verskeie voordele deur die definisie van Eq. (10). Eerstens, hierdie soort MI is onveranderlik tot die isomorfiese transformasie van invoergrawe. Tweedens, dit is berekenbaar omdat elke komponent aan die regterkant deur MINE geskat kan word. Belangriker nog, GMI is kragtiger as DGI in die vaslegging van oorspronklike invoerinligting as gevolg van sy eksplisiete korrelasie tussen verborge vektore en invoerkenmerke van beide nodusse en rande op 'n fyn-vlak nodus-vlak. 3.3 Maksimeer van GMI Nou maksimeer ons direk die regterkant van Eq. met die hulp van MINE. Let wel dat MINE 'n onderste limiet van MI skat met die Donsker-Varadhan (DV) -voorstelling van die KL-divergensie tussen die gesamentlike verspreiding en die produk van marginale. Aangesien ons meer fokus op die maksimeer van MI eerder as om die spesifieke waarde daarvan te verkry, kan ander nie-KL alternatiewe soos Jensen-Shannon MI-skatter (JSD) [ ] en Noise-Contrastive estimator (infoNCE) [ ] gebruik (10) 30 31