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. mini|Osnovni komponente grafovske neuronske mreže (GNM). Permutacijsko ekvivarijantni sloj. Lokalni sloj združivanja. 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 :

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. 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. 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. mini|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 mini|Ažuriranje reprezentacije čvora u sloju neuronske mreže za prenos poruka (MPNN). Čvor prima poruke poslane od svih njegovih neposrednih susjeda do Poruke se računaju putem funkcije za poruke. , š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 graf, gdje je skup čvorova i je skup grana. Neka je susjedstvo nekog čvora Osim toga, neka su karakteristike čvora i su karakteristike grana . MPNN sloj se može izraziti na sljedeći način:

Gdje su i diferencijabilne funkcije (npr. veštačke neuronske mreže), a je operator permutaciono-invariantne agregacije koji može prihvatiti proizvoljan broj ulaza (npr. zbir po elementima, srednja vrijednost ili maksimum). Konkretno, i 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 za svaki čvor 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 MPNN slojeva znači da će jedan čvor moći komunicirati s čvorovima koji su najviše "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:

gdje je matrica reprezentacija čvorova , je matrica karakteristika čvorova , je aktivacijska funkcija (npr. ReLU ), je matrica susjednosti grafa s dodatkom vlastitih petlji, je matrica stepena grafa sa dodatkom samopetlji, i je matrica parametara koje je moguće trenirati.

Posebno, neka je matrica susjednosti grafa: tada se može definirati i , gdje označava jediničnu matricu . Ova normalizacija osigurava da svojstvene vrijednosti od su ograničeni u rasponu , izbjegavajući numeričke nestabilnosti i eksplodirajuće/nestajuće gradijente .

Ograničenje GCN-ova je to što ne dozvoljavaju višedimenzionalne karakteristike grane . Međutim, moguće je povezati skalarne težine na svaku granu nametanjem , 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:

gdje je broj glava za pažnju, označava spajanje vektora, je aktivacijska funkcija (npr. ReLU ), su koeficijenti pažnje, i je matrica parametara za obuku -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:

Pažnja u mašinskom učenju je tehnika koja oponaša kognitivnu pažnju. U kontekstu učenja na grafovima, koeficijent pažnje mjeri koliko je važan čvor čvoru .

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

gdje je vektor naučivih težina, označava transpoziciju, su karakteristike grane (ako su prisutne), i 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 .

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:

gdje označava konkatenacija vektora, je vektor nula, je matrica naučivih parametara, je ćelija GRU-a, i označava indeks sekvence. U GGS-NN, reprezentacije čvorova se smatraju skrivenim stanjima GRU ćelije. Početne karakteristike čvora 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 i matricom susjedstva grafa . Izlaz je nova matrica karakteristika čvorova i nova matrica susjedstva grafa .

Top-k združivanje Prvo postavljamo:

gdje je projekcijski naučivi vektor. Projekcijski vektor izračunava skalarnu projekcijsku vrijednost za svaki čvor grafa.

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

gdje je podskup čvorova sa najvišim rezultatima projekcije od top-k, označava množenje matrica po elementima, i je sigmoidna funkcija . Drugim riječima, čvorovi sa najvišim rezultatima projekcije top-k zadržavaju se u novoj matrici susjednosti. . funkcija pravi vektor projekcije obučljivo povratnim širenjem, što bi inače proizvodilo diskretne rezultate.

Združivanje samopažnje Prvo smo postavili

gdje 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:

gdje je podskup čvorova sa najvišim rezultatima projekcije od top-k, i 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