Una Nova Manera d'Entrenar IA en Dades de Grafs sense Supervisió

Autors: Zhen Peng Wenbing Huang Minnan Luo Qinghua Zheng Yu Rong Tingyang Xu Junzhou Huang RESUM La riquesa en el contingut de diverses xarxes d'informació com ara xarxes socials i xarxes de comunicació proporciona un potencial sense precedents per aprendre representacions expressives d'alta qualitat sense supervisió externa. Aquest article investiga com preservar i extreure la informació abundant de dades estructurades en grafs en un espai d'incrustació de manera no supervisada. Per a això, proposem un concepte nou, Informació Gràfica Mútua (GMI), per mesurar la correlació entre els grafs d'entrada i les representacions latents d'alt nivell. GMI generalitza la idea dels càlculs convencionals d'informació mútua de l'espai vectorial al domini dels grafs, on la mesura de la informació mútua des de dos aspectes de les característiques dels nodes i l'estructura topològica és indispensable. GMI presenta diversos avantatges: Primer, és invariant a la transformació isomòrfica dels grafs d'entrada, una restricció inevitable en molts algorismes d'aprenentatge de representació de grafs existents; A més, es pot estimar i maximitzar eficientment amb mètodes d'estimació d'informació mútua actuals com MINE; Finalment, la nostra anàlisi teòrica confirma la seva correcció i racionalitat. Amb l'ajuda de GMI, desenvolupem un model d'aprenentatge no supervisat entrenat maximitzant GMI entre l'entrada i la sortida d'un codificador neuronal de grafs. Experiments considerables en classificació de nodes transductiva i inductiva, així com en predicció d'enllaços, demostren que el nostre mètode supera als seus homòlegs no supervisats de darrer mode, i fins i tot de vegades supera el rendiment dels supervisats. 1 INTRODUCCIÓ Per aconseguir un anàlisi quantitatiu fiable per a diverses xarxes d'informació, l'aprenentatge de representació d'alta qualitat per a dades estructurades en grafs s'ha convertit en un dels temes més fascinants actualment. Els mètodes recents orientats a aquest objectiu, comunament categoritzats com a Xarxes Neuronals de Grafs (GNNs), han fet avenços remarcables en moltes tasques d'aprenentatge, com ara la classificació de nodes [ , , ], la predicció d'enllaços [ , , ], l'alineació de grafs [ , , ], la generació molecular [ , , ], per esmentar-ne alguns. Tot i el progrés fructífer, l'entrenament de GNNs en els enfocaments existents sol requerir alguna forma de supervisió. Indubtablement, la informació de les etiquetes és cara d'adquirir (anotació manual o pagament de permís), i fins i tot impossible d'obtenir a causa de la política de privadesa. Sense oblidar que la fiabilitat de les etiquetes donades és de vegades qüestionable. Per tant, com aconseguir una representació de grafs d'alta qualitat sense supervisió esdevé necessari per a molts casos pràctics, la qual cosa motiva l'estudi d'aquest article. 35 42 50 26 27 49 12 19 43 4 5 46 Després d'examinar acuradament les nostres dades estructurades en grafs recollides, trobem que generalment provenen de diverses fonts com ara xarxes socials, xarxes de citacions i xarxes de comunicació on existeix una gran quantitat d'informació de contingut i enllaç. Per exemple, les dades de moltes plataformes socials com Twitter, Flickr i Facebook inclouen característiques dels usuaris, *per exemple*, detalls personals bàsics, textos, imatges, IP, i les seves relacions, *per exemple*, comprar el mateix article, ser amics. Aquestes dades riques de contingut són suficients per donar suport a tasques de mineria posteriors sense cap guia addicional: si dues entitats mostren una similitud extrema en les característiques, hi ha una alta probabilitat d'un enllaç entre elles (predicció d'enllaços), i és probable que pertanyin a la mateixa categoria (classificació); si dues entitats s'enllacen a la mateixa entitat, probablement tenen característiques similars (recomanació). En aquest sentit, preservar i extreure tanta informació com sigui possible de les xarxes d'informació en un espai d'incrustació facilita l'aprenentatge de representacions expressives d'alta qualitat que exhibeixen un rendiment desitjable en tasques de mineria sense cap forma de supervisió. L'aprenentatge no supervisat de grafs és una opció més favorable en molts casos a causa de la llibertat d'etiquetes, especialment quan pretenem beneficiar-nos de dades no etiquetades a gran escala del món real. Per heretar completament la informació rica en grafs, en aquest article, executem l'incrustació de grafs basada en la maximització de la Informació Mútua (MI), inspirats per l'èxit empíric del mètode Deep Info-Max [ ] que opera sobre imatges. Per descobrir representacions útils, Deep InfoMax entrena l'codificador per maximitzar la MI entre les seves entrades (és a dir, les imatges) i les sortides (és a dir, els vectors latents). Quan considerem Deep InfoMax en el domini dels grafs, la primera pedra que hem de superar és com definir la MI entre grafs i vectors latents, ja que la topologia dels grafs és més complexa que les imatges (veure Figura Un dels reptes és garantir que la funció MI entre la representació latent de cada node i les seves característiques d'entrada del veïnatge obeeixi la propietat simètrica, o equivalentment, sigui invariant a les permutacions dels veïnats. Com un treball recent que considera la MI, Deep Graph Infomax (DGI) [ ] primer incrusta un graf d'entrada i un graf corromput corresponent, després resumeix el graf d'entrada com un vector mitjançant una funció de lectura, finalment maximitza la MI entre aquest vector resum i les representacions latents discriminant el graf d'entrada (mostra positiva) del graf corromput (mostra negativa). La Figura ofereix una visió general fàcilment comprensible de DGI. Es demostra que maximitzar aquest tipus de MI és equivalent a maximitzar la dels vectors de nodes d'entrada i els vectors latents, però aquesta equivalència es manté sota diverses condicions preestablertes, *per exemple*, la funció de lectura ha de ser injectiva, cosa que sembla ser massa restrictiva en casos reals. Fins i tot si podem garantir l'existència d'una funció de lectura injectiva mitjançant un disseny determinat, *per exemple*, la utilitzada en DeepSets [ ], la capacitat injectiva de la funció de lectura també es veu afectada per com s'entrenen els seus paràmetres. És a dir, una funció originalment injectiva encara té el risc de tornar-se no injectiva si s'entrena sense cap supervisió externa. I si la funció de lectura no és injectiva, la informació del graf d'entrada continguda en un vector resum disminuirà a mesura que augmenti la mida del graf. A més, DGI roman en una maximització de MI a nivell de graf/parche gruixut. Per tant, en DGI, no hi ha garantia que l'codificador pugui destil·lar suficient informació de les dades d'entrada, ja que mai correlaciona elaboradament les representacions latents amb les seves entrades originals. 20 1). 41 1 47 En aquest article, presentem una manera més senzilla de considerar la MI en termes d'estructures gràfiques sense utilitzar cap funció de lectura ni funció de corrupció. Derivem directament la MI comparant l'entrada (és a dir, el subgraf que comprèn el veïnatge d'entrada) i la sortida (és a dir, la representació latent de cada node) de l'codificador. I interessantment, les nostres derivacions teòriques demostren que la MI formulada directament es pot descompondre en una suma ponderada de MI locals entre cada característica del veïnatge i el vector latent. D'aquesta manera, hem descompost les característiques d'entrada i hem fet que el càlcul de la MI sigui tractable. A més, aquesta forma de MI pot satisfer fàcilment la propietat simètrica si ajustem els valors dels pesos. Demanarem més detalls a la Secció Com que la MI es mesura principalment a nivell de característiques de nodes, l'anomenem Informació Mútua de Característiques (FMI). 3.1. Queden dues qüestions pendents sobre FMI: els pesos combinats encara són desconeguts i no té en compte la topologia (és a dir, les característiques dels enllaços). Per abordar encara més aquestes dues qüestions, definim la nostra mesura d'Informació Gràfica Mútua (GMI) basada en FMI. En particular, GMI aplica una assignació de valors intuïtiva establint els pesos en FMI iguals a la proximitat entre cada veí i el node objectiu en l'espai de representació. Per conservar la informació topològica, GMI correlaciona encara més aquests pesos amb les característiques dels enllaços d'entrada mitjançant un terme addicional d'informació mútua. El GMI resultant és topològicament invariant i també calculable amb Estimació Neuronal d'Informació Mútua (MINE) [ ]. Les principals contribucions del nostre treball són les següents: 1. 2. 2 • : Generalitzem l'estimació convencional de MI al domini dels grafs i proposem un nou concepte d'Informació Gràfica Mútua (GMI) en conseqüència. GMI està lliure del Concepte risc potencial causat per la funció de lectura, ja que considera la MI entre els grafs d'entrada i les incrustacions d'alt nivell d'una manera senzilla. • : A través de la nostra anàlisi teòrica, oferim una forma tractable i calculable de GMI que descompon Algorismes el GMI total en una suma ponderada de MI locals. Amb l'ajuda del mètode MINE, la maximització de GMI es pot aconseguir fàcilment a nivell de node. • : Verifiquem l'efectivitat de GMI en diverses tasques populars de classificació de nodes i predicció d'enllaços, incloent-hi tant transductives com inductives. Els experiments demostren que el nostre mètode ofereix un rendiment prometedor en una varietat de benchmarks i fins i tot supera de vegades els seus homòlegs supervisats. Resultats Experimentals 2 TREBALL RELACIONAT En línia amb el focus del nostre treball, revisem breument el treball previ en les dues àrees següents: estimació d'informació mútua, i xarxes neuronals per aprendre representacions sobre grafs. 1. 2. . Com el principi InfoMax [ ] defensa la maximització de la MI entre les entrades i sortides de les xarxes neuronals, molts mètodes com els algorismes ICA [ , ] intenten emprar la idea de la MI en l'aprenentatge de característiques no supervisat. No obstant això, aquests mètodes no es poden generalitzar fàcilment a xarxes neuronals profundes a causa de la dificultat de calcular la MI entre variables contínues d'alta dimensionalitat. Afortunadament, l'Estimació Neuronal d'Informació Mútua (MINE) [ ] fa factible l'estimació de la MI en xarxes neuronals profundes mitjançant l'entrenament d'una xarxa d'estadístiques com a classificador per distingir mostres provinents de la distribució conjunta i del producte de les marginals de dues variables aleatòries. Específicament, MINE utilitza la formulació KL exacta de la MI, mentre que una alternativa no-KL, la divergència de Jensen-Shannon (JSD) [ ], es pot utilitzar sense la preocupació pel valor precís de la MI. Estimació d'informació mútua 3 1 21 2 30 . Amb el ràpid desenvolupament de les xarxes neuronals de grafs (GNNs), s'han proposat un gran nombre d'algorismes d'aprenentatge de representació de grafs basats en GNNs en els últims anys, que mostren un rendiment més fort que els enfocaments tradicionals basats en passeigs aleatoris i factorització [ , , , , ]. Típicament, aquests mètodes es poden dividir en categories supervisades i no supervisades. Entre ells, hi ha una rica literatura sobre aprenentatge de representació supervisat sobre grafs [ , , , , ]. Malgrat la seva variància en l'arquitectura de xarxa, aconsegueixen èxit empíric amb l'ajuda d'etiquetes que sovint no són accessibles en escenaris realistes. En aquest cas, els mètodes d'aprenentatge de grafs no supervisats [ , , ] tenen un potencial d'aplicació més ampli. El mètode conegut és GraphSAGE [ ], un marc inductiu per entrenar GNNs mitjançant un objectiu basat en passeigs aleatoris en la seva configuració no supervisada. I recentment, DGI [ ] aplica la idea de maximització de MI al domini dels grafs i obté un fort rendiment de manera no supervisada. No obstant això, DGI implementa una maximització de gran abast (és a dir, maximitzar la MI a nivell de graf/parche) que fa que sigui difícil preservar la informació delicada del graf d'entrada. A més, la condició imposada a la funció de lectura utilitzada en DGI sembla ser massa restrictiva en casos reals. En contrast, ens centrem en eliminar la restricció de la funció de lectura i arribar a la maximització de la informació mútua gràfica a nivell de node maximitzant directament la MI entre les entrades i les sortides de l'codificador. Les representacions derivades pel nostre mètode són més sofisticades a l'hora de mantenir la informació del graf d'entrada, cosa que garanteix el seu potencial per a tasques de mineria de grafs posteriors, *per exemple*, classificació de nodes, predicció d'enllaços i recomanació. Xarxes neuronals per a l'aprenentatge de representació de grafs 6 15 33 34 39 7 9 25 40 48 11 16 41 16 41 3 INFORMACIÓ GRÀFICA MÚTUA: DEFINICIÓ I MAXIMITZACIÓ Abans d'anar més enllà, primer proporcionem els conceptes preliminars utilitzats en aquest article. Sigui G = (V, E) un graf amb *N* nodes *vi* ∈ V i enllaços *eij* = (*vi* , *vj* ) ∈ E. Les característiques dels nodes, amb una distribució de probabilitat empírica assumida P, es donen per *X* ∈ R × = {*x* 1, · · · , *x N* } on *xi* ∈ R denota la característica per al node *vi* . La matriu d'adjacència *A* ∈ R ×*N* representa les connexions d'enllaç, on *Aij* associat a l'enllaç *eij* podria ser un número real o un vector multidimensional1. N D D N L'objectiu de l'aprenentatge de representació de grafs és aprendre un codificador *f* : R ×*D* × R ×*N* → R ×*D*′, de manera que els vectors latents *H* = {*h*1, · · · , *hN* } = *f* (*X* , *A*) indiquin representacions d'alt nivell per a tots els nodes. El procés de codificació es pot reescriure en forma de node. N N N Per mostrar això, definim *Xi* i *Ai* per al node *i* com respectivament les característiques dels seus veïns i la matriu d'adjacència corresponent condicionada als veïns. Particularment, *Xi* comprèn tots els veïns de k-hop de *vi* amb *k* ≤ *l* quan l'codificador *f* és un GNN de *l* capes, i conté el propi node *i* si afegim bucles a la matriu d'adjacència. Aquí, anomenem el subgraf expandit per *Xi* i *Ai* un *graf de suport* per al node *i*, denotat per G*i*. Amb la definició del graf de suport, la codificació per a cada node esdevé *hi* = *f* (G*i*) = *f* (*Xi* , *Ai* ). A Deep InfoMax [ ], l'objectiu d'entrenament de l'codificador és maximitzar la MI entre les seves entrades i sortides. La MI s'estima utilitzant una xarxa d'estadístiques com a discriminant per classificar mostres que provenen de la distribució conjunta i les que provenen del producte de les marginals. Naturalment, quan adaptem la idea de Deep InfoMax als grafs, hauríem de maximitzar la MI entre la representació *hi* i el graf de suport G*i* per a cada node. Denotem aquesta MI gràfica com *I* (*hi* ; G*i*). Tanmateix, no és senzill definir I (*hi* ; Gi*). Les dificultats són: Dificultats en la definició de la informació mútua gràfica. 20 • La MI gràfica ha de ser invariant respecte a l'índex del node. En altres paraules, hauríem de tenir *I* (*hi* ; G*i*) = *I* (*hi* ; G′*i*), si G*i* i G′*i* són איזomorfs entre si. • Si adoptem el mètode MINE per al càlcul de la MI, el discriminant en MINE només accepta entrades de mida fixa. Això encara és infeasible per a G*i* ja que diferents G*i* solen incloure un nombre diferent de nodes i, per tant, són de mides diferents. Per superar el problema de definir la informació mútua gràfica, aquesta secció comença introduint el concepte d'Informació Mútua de Característiques (FMI) que només depèn de les característiques dels nodes. Inspirats per la descomposició de FMI, definim llavors Informació Gràfica Mútua (GMI), que té en compte tant les característiques dels nodes com 3.1 INFORMACIÓ MÚTUA DE CARACTERÍSTIQUES Denotem la distribució de probabilitat empírica de les característiques dels nodes *Xi* com *p*(*Xi* ), la probabilitat de *hi* com *p*(*hi* ), i la distribució conjunta per *p*(*hi* , *Xi* ). Segons la teoria de la informació, la MI entre *hi* i *Xi* es defineix com Interessantment, tenim el següent teorema de descomposició d'informació mútua per calcular *I* (*hi* ; *Xi* ). Teorema 1 (Descomposició d'Informació Mútua). (*hi* |*Xi* ) (*hi* ; *Xi* ) Si la probabilitat condicional p és multiplicativa (veure la definició de multiplicatiu a [ ]), la informació mútua global I 36 definida a l'Eq. (1) es pot descompondre com una suma ponderada de MI locals, és a dir, ≤ ≤ 1 on, xj és el j-è veí del node i, in és el nombre de tots els elements a Xi, i el pes wij satisfà 1 wij per a cada j. Per provar l'anterior teorema, introduïm primer dues lemes i una definició. Lemma 1. Per a qualsevol variable aleatòria X, Y, i Z, tenim Amb la descomposició del Teorema podem calcular el costat dret de l'Eq. mitjançant MINE, ja que les entrades del discriminant ara esdevenen els parells (*hi*, *xj*) les mides dels quals es mantenen sempre iguals (és a dir, *D*′ × *D*). A més, podem ajustar els pesos per reflectir la transformació isomòrfica dels grafs d'entrada. Per exemple, si *Xi* conté només veïns d'un salt del node *i*, establir tots els pesos de manera idèntica conduirà a la mateixa MI per als nodes d'entrada en ordres diferents. 1, (2) Malgrat alguns avantatges de la descomposició, és difícil caracteritzar els valors exactes dels pesos ja que estan relacionats amb els valors de *I* (*hi* ; *xj*) i les seves distribucions de probabilitat subjacents. Una manera trivial és establir tots els pesos a , llavors maximitzar el costat dret de l'Eq. equival a maximitzar el límit inferior de *I* (*hi* ; *Xi* ), per la qual cosa la veritable FMI també es maximitza fins a cert punt. A més d'aquest mètode, proporcionem addicionalment una solució més millorada considerant els pesos com a atencions entrenables, que és el tema de la propera subsecció. 1 (2) Inspirats per la descomposició del Teorema intentem construir pesos entrenables des de l'altre aspecte dels grafs (és a dir, 3.2 INFORMACIÓ MÚTUA CONSCIENT DE LA TOPOLOGIA 1, vista topològica) de manera que els valors de *wij* puguin ser més flexibles i capturar la propietat inherent dels grafs. Finalment, derivem la definició d'Informació Gràfica Mútua (GMI). Definició 2 (Informació Gràfica Mútua). G = (*X* , *A* ) La MI entre el vector latent h i el seu graf de suport es defineix com on les definicions de *xj* i *in* són les mateixes que al Teorema 1, *aij* és el pes/característica de l'enllaç a la matriu d'adjacència *A*, i σ(·) és una funció sigmoide. Intuitivament, el pes *wij* en el primer terme de l'Eq. (10) mesura la tractat en experiments no ponderats. Formalment, calculem *I* (*wij* ; *aij*) = *aij*log(*wij*) + (1 - *aij* )log(1 - *wij* ). (12) Maximitzant *I* (*hi* ; G*i*) amb la suma de l'Eq. (11) i l'Eq. (12) sobre tots els vectors latents *H*, arribem a la nostra funció objectiu completa per la contribució d'una MI local a la global. Implementem la contribució de *I* (*hi* ; *xj*) per la similitud entre les representacions *hi* i *hj* (és a dir, *wij* = σ (*hThj* )). Mentrestant, el terme *I* (*wij* ; *aij*) maximitza la MI entre *wij* i el pes/característica de l'enllaç del graf d'entrada (és a dir, *aij*) per imposar que *wij* s'ajusti a les relacions topològiques. En aquest sentit, el grau de contribució seria coherent amb la proximitat en l'estructura topològica, cosa que s'accepta comunament com un fet que *wij* podria ser més gran si el node *j* està "més a prop" del node *i* i més petit en cas contrari. Aquesta estratègia compensa el defecte que FMI només es centra en les característiques dels nodes i fa que les MI locals contribueixin al global de manera adaptativa. Per comprendre millor la idea d'atenció en aquesta estratègia, podeu consultar el GCN basat en atenció. Tingueu en compte que la definició de l'Eq. (10) és aplicable a casos generals. Per a situacions específiques, podem modificar lleugerament l'Eq. (10) per a eficiència. Per exemple, quan tractem amb grafs no ponderats (és a dir, el valor de l'enllaç és 1 si està connectat i 0 en cas contrari), podríem substituir el segon terme de MI *I* (*wij* ; *aij*) per una pèrdua d'entropia creuada negativa. Minimitzar l'entropia creuada també contribueix a la maximització de MI, i proporciona un càlcul més eficient. Demanarem més detalls a la propera secció. En general, hi ha diversos avantatges amb la definició de l'Eq. (10). En primer lloc, aquest tipus de MI és invariant a la transformació isomòrfica dels grafs d'entrada. En segon lloc, és computacionalment factible ja que cada component del costat dret es pot estimar per MINE. Més important encara, GMI és més potent que DGI per capturar la informació d'entrada original degut a la seva correlació explícita entre els vectors latents i les característiques d'entrada tant de nodes com d'enllaços a nivell de node detallat. 3.3 MAXIMITZACIÓ DE GMI Ara maximitzem directament el costat dret de l'Eq. amb l'ajuda de MINE. Tingueu en compte que MINE estima un límit inferior de la MI amb la representació Donsker-Varadhan (DV) [ ] de la divergència KL entre la distribució conjunta i el producte de les marginals. Com que ens centrem més en maximitzar la MI en lloc d'obtenir el seu valor específic, es poden utilitzar alternatives no-KL com l'estimador d'informació de Jensen-Shannon (JSD) [ ] i l'estimador de contrastació de soroll (infoNCE) [ ] per reemplaçar-lo. Basant-nos en els resultats experimentals i l'anàlisi a [ ], ens basem en l'estimador JSD en aquest article per raons d'efectivitat i eficiència, ja que l'estimador infoNCE és sensible a les estratègies de mostreig negatiu (el nombre de mostres negatives) i, per tant, pot convertir-se en un coll d'ampolla per a conjunts de dades a gran escala amb memòria disponible fixa. En contrast, la insensibilitat de l'estimador JSD a les estratègies de mostreig negatiu i el seu rendiment respectable en moltes tasques el fan més adequat per a la nostra tasca. En particular, calculem *I* (*hi* ; *xj*) en el primer terme de l'Eq. per (10) 10 30 31 20 (10) on D : × ′ → R és un discriminant construït per una xarxa neuronal amb paràmetre *w*. *xj* és una mostra negativa de P = P, i *sp*(x) = log(1 + ex ) denota la funció soft-plus. w D D Com s'ha