Xarxa neuronal gràfica

Gràfics no isomorfs que no es poden distingir per una GNN a causa de les limitacions del Test d'isomorfisme de gràfics de Weisfeiler-Lehman. Els colors indiquen les característiques dels nodes.

Una xarxa neuronal gràfica (GNN) és una classe de xarxes neuronals artificials per processar dades que es poden representar com a gràfics. En el tema més general de "aprenentatge profund geomètric", certes arquitectures de xarxes neuronals existents es poden interpretar com a GNN que operen en gràfics adequadament definits. Les xarxes neuronals convolucionals, en el context de la visió per ordinador, es poden veure com una GNN aplicada a gràfics estructurats com a quadrícules de píxels. Els transformadors, en el context del processament del llenguatge natural, es poden veure com a GNN aplicats a gràfics complets els nodes dels quals són paraules en una frase.

Actualització de la representació del node en una capa de xarxa neuronal de pas de missatges (MPNN). Node $\mathbf {x} _{0}$ rep missatges enviats per tots els seus veïns immediats $\mathbf {x} _{1}$ a $\mathbf {x} _{4}$ . Els missatges s'estan calculant mitjançant la funció de missatge $\phi$, que té en compte les característiques tant dels remitents com del receptor.

L'element clau del disseny de les GNN és l'ús del pas de missatges per parells, de manera que els nodes de gràfic actualitzen iterativament les seves representacions intercanviant informació amb els seus veïns. Des dels seus inicis, s'han proposat diverses arquitectures GNN diferents, que implementen diferents sabors de pas de missatges, començat per recursius o convolucionals constructius enfocaments. A 2022, si és possible definir arquitectures GNN que "anen més enllà" del pas de missatges, o si cada GNN es pot construir a partir de missatges que passen sobre gràfics adequadament definits, és una qüestió de recerca oberta.

Els dominis d'aplicació rellevants per a les GNN inclouen Processament del llenguatge natural, xarxes socials, xarxes de citacions, biologia molecular, química, física i problemes d'optimització combinatòria NP-hard.Hi ha disponibles diverses biblioteques de codi obert que implementen xarxes neuronals de gràfics, com ara PyTorch Geometric (PyTorch), TensorFlow GNN (TensorFlow) i jraph (Google JAX).

Arquitectura

L'arquitectura d'una GNN genèrica implementa les següents capes fonamentals:

1. Equivariant de permutació: una capa d'equivariant de permutació mapeja una representació d'un gràfic en una representació actualitzada del mateix gràfic. A la literatura, les capes equivariants de permutació s'implementen mitjançant missatges per parells que passen entre nodes de gràfics. Intuïtivament, en una capa de transmissió de missatges, els nodes actualitzen les seves representacions agregant els missatges rebuts dels seus veïns immediats. Com a tal, cada capa de pas de missatge augmenta el camp receptiu de la GNN en un salt.
2. Agrupació local: una capa d'agrupació local aproxima el gràfic mitjançant un mostreig inferior. L'agrupació local s'utilitza per augmentar el camp receptiu d'una GNN, de manera similar a l'agrupació de capes en xarxes neuronals convolucionals. Els exemples inclouen l'agrupació de k-veïns més propers, l'agrupació de k superior, i l'agrupació d'autoatenció.
3. Agrupació global: una capa d'agrupació global, també coneguda com a capa de lectura, proporciona una representació de mida fixa de tot el gràfic. La capa d'agrupació global ha de ser invariant de la permutació, de manera que les permutacions en l'ordenació dels nodes i les vores del gràfic no alterin la sortida final. Els exemples inclouen la suma per elements, la mitjana o el màxim.

S'ha demostrat que les GNN no poden ser més expressives que la prova d'isomorfisme del gràfic de Weisfeiler-Lehman. A la pràctica, això vol dir que existeixen diferents estructures de gràfics (per exemple, molècules amb els mateixos àtoms però enllaços diferents) que no es poden distingir per les GNN. Es poden dissenyar GNN més potents que operen en geometries de dimensió superior, com ara complexos senzills. A 2022, si les arquitectures futures superaran o no el missatge que passa primitiu és una qüestió de recerca oberta.

Aplicacions

Plegament de proteïnes

Les xarxes neuronals de gràfics són un dels components principals d'AlphaFold, un programa d'intel·ligència artificial desenvolupat per DeepMind de Google per resoldre el problema del plegament de proteïnes en biologia. AlphaFold va aconseguir el primer lloc en diverses competicions CASP.

Xarxes socials

Les xarxes socials són un domini d'aplicació important per a les GNN a causa de la seva representació natural com a gràfics socials. Els GNN s'utilitzen per desenvolupar sistemes de recomanació basats tant en relacions socials com en relacions d'elements.

Optimització combinatòria

Els GNN s'utilitzen com a blocs de construcció fonamentals per a diversos algorismes d'optimització combinatòria. Els exemples inclouen calcular els camins més curts o els circuits eulerians per a un gràfic donat, derivar ubicacions de xips superiors o competitives a solucions humanes fetes a mà, i millorar les regles de ramificació dissenyades per experts en branch and bound.

Seguretat cibernètica

Quan es veu com un gràfic, una xarxa d'ordinadors es pot analitzar amb GNN per a la detecció d'anomalies. Les anomalies dins dels gràfics de procedència sovint es correlacionen amb l'activitat maliciosa dins de la xarxa. Les GNN s'han utilitzat per identificar aquestes anomalies en nodes individuals i dins de camins per detectar processos maliciosos, o a nivell de vora per detectar moviment lateral.