Grafovska neuronska mreža

Grafovske neuronske mreže ( GNN, Graph Neural Network ) su specijalizirane veštačke neuronske mreže dizajnirane za zadatke čiji su ulazni podaci grafovi.

Jedan istaknuti primjer je molekularni dizajn lijekova. Svaki ulazni uzorak je grafički prikaz molekule, gdje atomi formiraju čvorove, a hemijske veze između atoma formiraju grane.Osim grafičkog prikaza, ulazni podaci sadrže i poznata hemijska svojstva svakog atoma.. Uzorci iz skupa podataka stoga se mogu razlikovati po dužini, što odražava različite brojeve atoma u molekulama i različiti broj veza između njih. Zadatak je predvidjeti efikasnost date molekule za određenu medicinsku primjenu, poput eliminacije bakterije E. coli .

Ključni element dizajna GNN-ova je korištenje parnog prenošenja poruka, tako da čvorovi grafa iterativno ažuriraju svoje reprezentacije razmjenjujući informacije sa svojim susjedima. Predloženo je nekoliko GNN arhitektura, koje implementiraju različite vrste prenošenja poruka, počevši od rekurzivnih ili konvolucijskih pristupa. Prema podacima iz 2022. godine ostaje nejasno da li je moguće definisati GNN arhitekture koje idu "izvan" prenošenja poruka, ili se, pak, svaka GNN može izgraditi na osnovu prenošenja poruka putem adekvatno definisanih grafova.

Osnovni komponente grafovske neuronske mreže (GNM). $(1)$ Permutacijsko ekvivarijantni sloj. $(2)$ Lokalni sloj združivanja. $(3)$ Sloj globalnog združivanja (ili očitavanja). Boje označavaju karakteristike .

U širem kontekstu "geometrijskog dubokog učenja", određene postojeće arhitekture neuronskih mreža mogu se interpretirati kao GNN-ovi koji rade na odgovarajuće definiranim grafovima. Sloj konvolucijske neuronske mreže, u kontekstu kompjuterskog vida, može se smatrati GNN-om primijenjenim na grafove čiji su čvorovi pikseli, a samo susjedni pikseli su povezani granama u grafu. Transformatorski sloj, u obradi prirodnog jezika, može se smatrati GNN-om primijenjenim na potpune grafove čiji su čvorovi riječi ili tokeni u odlomku teksta prirodnog jezika .

Relevantni domeni primjene za GNN uključuju obradu prirodnog jezika, društvene mreže, citatne mreže, molekularnu biologiju, hemiju, fiziku i NP-teške probleme kombinatorne optimizacije.

Biblioteke otvorenog koda koje implementiraju GNN-ove uključuju PyTorch Geometric ( PyTorch ), TensorFlow GNN ( TensorFlow ), Deep Graph Library (nezavisna od okvira), jraph ( Google JAX ) i GraphNeuralNetworks.jl /GeometricFlux.jl ( Julia, Flux ).

Arhitektura

Arhitektura generičkog GNN-a implementira sljedeće osnovne slojeve :

1. Permutacijsko ekvivarijantni sloj : permutacijsko ekvivarijantni sloj preslikava reprezentaciju grafa u ažuriranu reprezentaciju istog grafa. U literaturi, permutacijski ekvivarijantni slojevi se implementiraju putem parnog prijenosa poruka između čvorova grafa. Intuitivno, u sloju prijenosa poruka, čvorovi ažuriraju svoje reprezentacije agregiranjem poruka primljenih od svojih neposrednih susjeda. Kao takav, svaki sloj prijenosa poruka povećava receptivno polje GNN-a za jedan skok.
2. Lokalno združivanje : sloj lokalnog združivanja ugrubljuje graf putem smanjenja uzorkovanja . Lokalno grupiranje se koristi za povećanje receptivnog polja GNN-a, na sličan način kao grupiranje slojeva u konvolucijskim neuronskim mrežama. Primjeri uključuju grupiranje k najbližih susjeda, grupiranje top-k i grupiranje samo-pažnje.
3. Globalno grupiranje: sloj globalnog grupiranja, također poznat kao sloj za očitavanje, pruža reprezentaciju cijelog grafa fiksne veličine. Sloj globalnog grupiranja mora biti invarijantan u odnosu na permutacije, tako da permutacije u redoslijedu čvorova i grana grafa ne mijenjaju konačni izlaz. Primjeri uključuju zbir po elementima, srednju vrijednost ili maksimum.

Dokazano je da GNN-ovi ne mogu biti izražajniji od Weisfeiler-Lemanovog testa izomorfizma grafova. U praksi, to znači da postoje različite strukture grafova (npr. molekule s istim atomima, ali različitim vezama ) koje GNN-ovi ne mogu razlikovati. Mogu se dizajnirati moćniji GNN-ovi koji djeluju na geometrijama viših dimenzija, kao što su simplicijalni kompleksi. Prema podacima iz 2022, da li će buduće arhitekture prevazići primitivnost prenosa poruka, ostaje nejasno.

Neizomorfni grafovi koje GNN ne može razlikovati zbog ograničenja Weisfeiler-Lehmanovog testa izomorfizma grafova. Boje označavaju karakteristike čvorova.

Slojevi za prenos poruka

Ažuriranje reprezentacije čvora u sloju neuronske mreže za prenos poruka (MPNN). Čvor $\mathbf {x} _{0}$ prima poruke poslane od svih njegovih neposrednih susjeda $\mathbf {x} _{1}$ do $\mathbf {x} _{4}$ Poruke se računaju putem funkcije za poruke. $\psi$, što uzima u obzir karakteristike i pošiljaoca i primaoca.

Slojevi za prenos poruka su permutacijsko ekvivarijantni slojevi koji preslikavaju graf u ažuriranu reprezentaciju istog grafa. Formalno, mogu se izraziti kao neuronske mreže za prenos poruka (MPNN).

Neka je $G=(V,E)$ graf, gdje $V$ je skup čvorova i $E$ je skup grana. Neka je $N_{u}$ susjedstvo nekog čvora $u\in V$ Osim toga, neka su $\mathbf {x} _{u}$ karakteristike čvora $u\in V$ i $\mathbf {e} _{uv}$ su karakteristike grana $(u,v)\in E$. MPNN sloj se može izraziti na sljedeći način:

$\mathbf {h} _{u}=\phi \left(\mathbf {x} _{u},\bigoplus _{v\in N_{u}}\psi (\mathbf {x} _{u},\mathbf {x} _{v},\mathbf {e} _{uv})\right)$

Gdje su $\phi$ i $\psi$ diferencijabilne funkcije (npr. veštačke neuronske mreže), a $\bigoplus$ je operator permutaciono-invariantne agregacije koji može prihvatiti proizvoljan broj ulaza (npr. zbir po elementima, srednja vrijednost ili maksimum). Konkretno, $\phi$ i $\psi$ se nazivaju funkcije ažuriranja odnosno poruke. Intuitivno, u računarskom bloku MPNN-a, čvorovi grafa ažuriraju svoje reprezentacije agregirajući poruke primljene od svojih susjeda.

Izlazi jednog ili više MPNN slojeva su reprezentacije čvorova $\mathbf {h} _{u}$ za svaki čvor $u\in V$ u grafu. Reprezentacije čvorova mogu se koristiti za bilo koji nizvodni zadatak, kao što je klasifikacija čvorova/grafa ili predviđanje grana.

Čvorovi grafa u MPNN-u ažuriraju svoju reprezentaciju agregiranjem informacija od svojih neposrednih susjeda. Kao takvo, slaganje $n$ MPNN slojeva znači da će jedan čvor moći komunicirati s čvorovima koji su najviše $n$ "skoka" dalje. U principu, da bi se osiguralo da svaki čvor prima informacije od svakog drugog čvora, bilo bi potrebno složiti određeni broj MPNN slojeva jednak prečniku grafa. Međutim, slaganje mnogih MPNN slojeva može uzrokovati probleme poput prekomjernog zaglađivanja i prekomjernog zgnječenja. Prekomjerno zaglađivanje se odnosi na problem nerazlučivosti reprezentacija čvorova. Prekomjerno zgnječenje se odnosi na problem koji nastaje stiskanjem dugodometnih zavisnosti u reprezentacije fiksne veličine. Protivmjere poput preskakanja veza (kao u rezidualnim neuronskim mrežama ), pravila ažuriranja sa zatvaračima i preskakanje znanja mogu ublažiti prekomjerno zaglađivanje. Modificiranje konačnog sloja da bude potpuno susjedni sloj, tj. razmatranjem grafa kao kompletni graf, može ublažiti prekomjerno zgnječenje u problemima gdje su potrebne dugodometne zavisnosti.

U literaturi su razvijene i druge "varijante" MPNN-a, kao što su konvolucijske mreže grafova i mreže pažnje grafova, čije se definicije mogu izraziti u terminima formalizma MPNN-a.

Konvolucijska mreža grafova

Konvolucijsku mrežu grafova (GCN, Graph Convolutional Network) prvi put su predstavili Thomas Kipf i Max Welling 2017. godine.

GCN sloj definira aproksimaciju prvog reda lokaliziranog spektralnog filtera na grafovima. GCN-ovi se mogu shvatiti kao generalizacija konvolucijskih neuronskih mreža na podatke strukturirane grafovima.

Formalni izraz GCN sloja glasi:

$\mathbf {H} =\sigma \left({\tilde {\mathbf {D} }}^{-{\frac {1}{2}}}{\tilde {\mathbf {A} }}{\tilde {\mathbf {D} }}^{-{\frac {1}{2}}}\mathbf {X} \mathbf {\Theta } \right)$

gdje $\mathbf {H}$ je matrica reprezentacija čvorova $\mathbf {h} _{u}$, $\mathbf {X}$ je matrica karakteristika čvorova $\mathbf {x} _{u}$, $\sigma (\cdot )$ je aktivacijska funkcija (npr. ReLU ), ${\tilde {\mathbf {A} }}$ je matrica susjednosti grafa s dodatkom vlastitih petlji, ${\tilde {\mathbf {D} }}$ je matrica stepena grafa sa dodatkom samopetlji, i $\mathbf {\Theta }$ je matrica parametara koje je moguće trenirati.

Posebno, neka je $\mathbf {A}$ matrica susjednosti grafa: tada se može definirati ${\tilde {\mathbf {A} }}=\mathbf {A} +\mathbf {I}$ i ${\tilde {\mathbf {D} }}_{ii}=\sum _{j\in V}{\tilde {A}}_{ij}$, gdje $\mathbf {I}$ označava jediničnu matricu . Ova normalizacija osigurava da svojstvene vrijednosti od ${\tilde {\mathbf {D} }}^{-{\frac {1}{2}}}{\tilde {\mathbf {A} }}{\tilde {\mathbf {D} }}^{-{\frac {1}{2}}}$ su ograničeni u rasponu $[0,1]$, izbjegavajući numeričke nestabilnosti i eksplodirajuće/nestajuće gradijente .

Ograničenje GCN-ova je to što ne dozvoljavaju višedimenzionalne karakteristike grane $\mathbf {e} _{uv}$. Međutim, moguće je povezati skalarne težine $w_{uv}$ na svaku granu nametanjem $A_{uv}=w_{uv}$, tj. postavljanjem svakog unosa različitog od nule u matrici susjednosti na jednakoj težini sa odgovarajućom granom.

Graf mreže pažnje

Graf mreže pažnje (GAT, Graph Attention Network) predstavili su Petar Veličković i saradnici 2018. godine.

Grafička mreže pažnje je kombinacija GNN-a i sloja pažnje. Implementacija sloja pažnje u grafičkim neuronskim mrežama pomaže u usmjeravanju pažnje ili fokusa na važne informacije od podataka umjesto fokusiranja na cijelokupnim podacima.

Višeglavni GAT sloj može se izraziti na sljedeći način:

$\mathbf {h} _{u}={\overset {K}{\underset {k=1}{\Big \Vert }}}\sigma \left(\sum _{v\in N_{u}}\alpha _{uv}\mathbf {W} ^{k}\mathbf {x} _{v}\right)$

gdje $K$ je broj glava za pažnju, ${\Big \Vert }$ označava spajanje vektora, $\sigma (\cdot )$ je aktivacijska funkcija (npr. ReLU ), $\alpha _{ij}$ su koeficijenti pažnje, i $W^{k}$ je matrica parametara za obuku $k$-te glave za pažnju.

Za završni GAT sloj, uzima se srednja vrednost svih glava za pažnju prije primjene aktivacijske funkcije. Formalno, završni GAT sloj se može napisati kao:

$\mathbf {h} _{u}=\sigma \left({\frac {1}{K}}\sum _{k=1}^{K}\sum _{v\in N_{u}}\alpha _{uv}\mathbf {W} ^{k}\mathbf {x} _{v}\right)$

Pažnja u mašinskom učenju je tehnika koja oponaša kognitivnu pažnju. U kontekstu učenja na grafovima, koeficijent pažnje $\alpha _{uv}$ mjeri koliko je važan čvor $u\in V$ čvoru $v\in V$ .

Normalizirani koeficijenti pažnje izračunavaju se na sljedeći način:

$\alpha _{uv}={\frac {\exp({\text{LeakyReLU}}\left(\mathbf {a} ^{T}[\mathbf {W} \mathbf {x} _{u}\Vert \mathbf {W} \mathbf {x} _{v}\Vert \mathbf {e} _{uv}]\right))}{\sum _{z\in N_{u}}\exp({\text{LeakyReLU}}\left(\mathbf {a} ^{T}[\mathbf {W} \mathbf {x} _{u}\Vert \mathbf {W} \mathbf {x} _{z}\Vert \mathbf {e} _{uz}]\right))}}$

gdje $\mathbf {a}$ je vektor naučivih težina, $\cdot ^{T}$ označava transpoziciju, $\mathbf {e} _{uv}$ su karakteristike grane (ako su prisutne), i ${\text{LeakyReLU}}$ je modificirana ReLU aktivacijska funkcija. Koeficijenti pažnje su normalizirani kako bi se mogli lako upoređivati između različitih čvorova.

GCN može se posmatrati kao poseban slučaj GAT-a gdje koeficijenti pažnje nisu naučivi, već su fiksni i jednaki težinama grana $w_{uv}$.

Neuronska mreža sa zatvorenom sekvencom grafova

Neuronsku mrežu sa zatvorenom sekvencom grafova (GGS-NN Gated Graph Sequence Neural Network) predstavili su Yujia Li i saradnici 2015. godine. GGS-NN proširuje formulaciju GNN-a koju su dali Scarselli i saradnici na izlazne sekvence. Okvir za prenos poruka implementiran je kao pravilo ažuriranja za ćeliju sa zatvorenom rekurentnom jedinicom (GRU Gated Recurrent Unit).

GGS-NN se može izraziti na sljedeći način:

$\mathbf {h} _{u}^{(0)}=\mathbf {x} _{u}\,\Vert \,\mathbf {0}$

$\mathbf {m} _{u}^{(l+1)}=\sum _{v\in N_{u}}\mathbf {\Theta } \mathbf {h} _{v}$

$\mathbf {h} _{u}^{(l+1)}={\text{GRU}}(\mathbf {m} _{u}^{(l+1)},\mathbf {h} _{u}^{(l)})$

gdje $\Vert$ označava konkatenacija vektora, $\mathbf {0}$ je vektor nula, $\mathbf {\Theta }$ je matrica naučivih parametara, ${\text{GRU}}$ je ćelija GRU-a, i $l$ označava indeks sekvence. U GGS-NN, reprezentacije čvorova se smatraju skrivenim stanjima GRU ćelije. Početne karakteristike čvora $\mathbf {x} _{u}^{(0)}$ se dopunjuju nulama do dimenzije skrivenog stanja GRU ćelije. Ista GRU ćelija se koristi za ažuriranje reprezentacija za svaki čvor.

Lokalni slojevi za grupiranje

Lokalni slojevi združivanja pogrubljuju graf putem smanjivanja uzorkovanja. Nakon toga, predstavljeno je nekoliko predloženih naučivih strategija lokalnog udruživanja. Za svaki slučaj, ulaz je početni graf predstavljen matricom karakteristika čvorova $\mathbf {X}$ i matricom susjedstva grafa $\mathbf {A}$. Izlaz je nova matrica karakteristika čvorova $\mathbf {X} '$ i nova matrica susjedstva grafa $\mathbf {A} '$.

Top-k združivanje

Prvo postavljamo:

$\mathbf {y} ={\frac {\mathbf {X} \mathbf {p} }{\Vert \mathbf {p} \Vert }}$

gdje $\mathbf {p}$ je projekcijski naučivi vektor. Projekcijski vektor $\mathbf {p}$ izračunava skalarnu projekcijsku vrijednost za svaki čvor grafa.

Gornji loj objedinjavanja top-k se tada može formalizirati na sljedeći način:

$\mathbf {X} '=(\mathbf {X} \odot {\text{sigmoid}}(\mathbf {y} ))_{\mathbf {i} }$

$\mathbf {A} '=\mathbf {A} _{\mathbf {i} ,\mathbf {i} }$

gdje $\mathbf {i} ={\text{top}}_{k}(\mathbf {y} )$ je podskup čvorova sa najvišim rezultatima projekcije od top-k, $\odot$ označava množenje matrica po elementima, i ${\text{sigmoid}}(\cdot )$ je sigmoidna funkcija . Drugim riječima, čvorovi sa najvišim rezultatima projekcije top-k zadržavaju se u novoj matrici susjednosti. $\mathbf {A} '$ . ${\text{sigmoid}}(\cdot )$ funkcija pravi vektor projekcije $\mathbf {p}$ obučljivo povratnim širenjem, što bi inače proizvodilo diskretne rezultate.

Združivanje samopažnje

Prvo smo postavili

$\mathbf {y} ={\text{GNN}}(\mathbf {X} ,\mathbf {A} )$

gdje ${\text{GNN}}$ je generički permutacijsko ekvivarijantni GNN sloj (npr. GCN, GAT, MPNN).

Sloj združivanja samo-pažnje se tada može formalizirati na sljedeći način:

$\mathbf {X} '=(\mathbf {X} \odot \mathbf {y} )_{\mathbf {i} }$

$\mathbf {A} '=\mathbf {A} _{\mathbf {i} ,\mathbf {i} }$

gdje $\mathbf {i} ={\text{top}}_{k}(\mathbf {y} )$ je podskup čvorova sa najvišim rezultatima projekcije od top-k, i $\odot$ označava množenje matrica po elementima .

Sloj združivanja samopažnje može se posmatrati kao proširenje sloja združivanja top-k. Za razliku od objedinjavanja top-k, rezultati samopažnje izračunati u združivanju samopažnje uzimaju u obzir i karakteristike grafa i topologiju grafa.

Heterofilno učenje grafova

Princip homofilije, tj. čvorovi s istim oznakama ili sličnim atributima imaju veću vjerovatnoću da budu povezani, uobičajeno se smatra glavnim razlogom superiornosti grafovskih neuronskih mreža (GNN) u odnosu na tradicionalne neuronske mreže (NN, Neural Network) na podacima strukturiranim grafovima, posebno na zadacima na nivou čvorova. Međutim, nedavni rad je identificirao netrivijalni skup skupova podataka gdje performanse GNN-a u poređenju s NN-ovima nisu zadovoljavajuće. Heterofilija, tj. niska homofilija, smatra se glavnim uzrokom ovog empirijskog zapažanja. Ljudi su počeli preispitivati i ponovo procjenjivati većinu postojećih modela grafova u scenariju heterofilije na različitim vrstama grafova, npr. heterogenim grafovima, vremenskim grafovima i hipergrafovima . Štaviše, utvrđeno je da su brojne primjene vezane za grafove usko povezane s problemom heterofilije, npr. otkrivanje prevare/anomalija na grafovima, napadi i robusnost na grafovima, privatnost, federirano učenje i segmentacija oblaka tačaka, klasterovanje grafova, sistemi preporuka, generativni modeli, predviđanje veza, klasifikacija i bojenje grafova itd. U posljednjih nekoliko godina, značajan napor je uložen u proučavanje i rješavanje problema heterofilije u učenju grafova.

Primjene

Savijanje proteina

Grafovske neuronske mreže su jedan od glavnih gradivnih blokova AlphaFolda, programa veštačke inteligencije koji je razvio Google-ov DeepMind za rješavanje problema savijanja proteina u biologiji . AlphaFold je osvojio prvo mjesto na nekoliko CASP takmičenja.

Društvene mreže

Društvene mreže su glavna domena primjene GNN-ova zbog njihove prirodne reprezentacije kao društveni grafovai. GNN-ovi se koriste za razvoj sistema preporuka zasnovanih i na društvenim odnosima i na odnosima među elementima.

Kombinatorna optimizacija

GNN-ovi se koriste kao osnovni gradivni blokovi za nekoliko kombinatornih optimizacijskih algoritama. Primjeri uključuju izračunavanje najkraćih puteva ili Eulerovih kola za dati graf, izvođenje rasporeda čipova superiornijih ili konkurentnijih u odnosu na ručno izrađena ljudska rješenja, i poboljšanje pravila grananja koje su dizajnirali stručnjaci u metodi grananja i ograničavanja.

Kibernetička sigurnost

Kada se posmatra kao graf, mreža računara može se analizirati pomoću GNN-ova radi otkrivanja anomalija. Anomalije unutar grafova porijekla često su u korelaciji sa zlonamjernim aktivnostima unutar mreže. GNN-ovi su korišteni za identifikaciju ovih anomalija na pojedinačnim čvorovima i unutar putanja radi otkrivanja zlonamjernih procesa ili na nivou grane radi otkrivanja lateralnog kretanja .

Mreže za distribuciju vode

Sistemi distribucije vode mogu se modelirati kao grafovi, što je onda jednostavna primjena GNN-a. Ova vrsta algoritma primijenjena je za predviđanje potražnje za vodom, međusobno povezujući područja okružnog mjerenja (DMA, District Metered Areas) radi poboljšanja kapaciteta predviđanja. Druga primjena ovog algoritma na modeliranje distribucije vode je razvoj metamodela.

Računarski vid

Da bi se slika predstavila kao graf, slika se prvo dijeli na više dijelova, od kojih se svaki tretira kao čvor u grafu. Grane se zatim formiraju povezivanjem svakog čvora sa njegovim najbližim susjedima na osnovu prostorne sličnosti ili sličnosti karakteristika. Ova reprezentacija zasnovana na grafu omogućava primjenu modela učenja grafova na vizualne zadatke. Relaciona struktura pomaže u poboljšanju ekstrakcije karakteristika i poboljšanju performansi razumijevanja slike.

Tekst i NLP

Grafovski prikaz teksta pomaže u hvatanju dubljih semantičkih odnosa između riječi. Mnoge studije su koristile grafovske mreže za poboljšanje performansi u raznim zadacima obrade teksta kao što su klasifikacija teksta, odgovaranje na pitanja, prevođenje neuronskih mašina (NMT), izdvajanje događaja, provjera činjenica itd.

Reference

• Kratak uvod u grafovske neuronske mreže