Kaj so GNN (grafovske nevronske mreže)?

Pogosto podatkov nimamo v urejeni obliki kot je mreža (slike) ali pa zaporedje (tekst). Reprezentacijo vozlišč se priučimo z iterativno agragacijo okolice, pri čemer vsako vozlišče posodobi svoj embedding glede na trenutni embedding & embeddinge vozlišč v neki okolici. To, da pri izračunu uporabimo samo okolico vozlišča pomeni, da so GNN invariantne za permutacije vozlišč ter nam omogoča delo z variabilnimi velikostmi jat. To lahko zašišemo v matrični formuli z dvema "trainable" linearnima transformacijama $W^{(l)}$ in $B^{(l)}$: $$\mathbf{h}_v^{(0)} = x_v$$ $$\mathbf{h}_v^{(l+1)} = \sigma \left( \mathbf{W}^{(l)} \sum_{u \in \text{sosedi}(v)} \frac{\mathbf{h}_u^{(l)}}{|\text{sosedi}(v)|} + \mathbf{B}^{(l)}\mathbf{h}^{(l)}_v \right), \quad \forall k \in \{0, \dots , K-1 \}$$ $$\mathbf{z}_v = \mathbf{h}_v^{(K)}$$

Osnovne GNN obravnavajo vse sosede enako, toda v jatah rib so bolj pomembne tiste, ki so tik zraven nas. Vpliv sosedov je torej odvisen od oddaljenosti, orientacije in hitrosti ribe. GAT (Graph Attention Network) reši ta problem, saj se za vhodna sporočila iz ostalih vozlišč priuči pomembnost uteži (attention coeficient). Mi ga izračunamo med pari vozlišč (rib) iz njihovih pozicij in hitrosti, ter ga normaliziramo po sosedih z uporabo softmaxa. S tem dosežemo, da ribe blizu skupaj in tiste, ki plavajo v podobno smer, bolj vplivajo druga na drugo. Formula kako posodobimo embedding $\mathbf{h}_v^{(l)}$ ribe $v$ na layerju $l$ znotraj GATa: $$\textbf{h}_v^{(l)}=\sigma \left( \sum_{u\in \text{sosedi}(v)} \alpha_{vu}\textbf{W}^{(l)}\textbf{h}_u^{(l-1)}\right)$$ Attention coefficient med vozliščema (ribama) $A$ in $B$ izračunamo kot $$e_{AB} = a\left( \textbf{W}^{(l)}\textbf{h}_A^{(l-1)}, \ \textbf{W}^{(l)}\textbf{h}_B^{(l-1)}\right)$$, kjer je $a$ neka točkovalna funkcija (ki se jo naučimo znotraj tega attention mehanizma).

BONUS: Drugi del našega modela je transformer. Podobno kot transformerji gledajo npr zaporedje besed v povedi in poskušajo uganiti naslednjo, mi modeliramo odnose z zaporedjem. Pri tem uporabljamo self-attention mehanizem, pri čemer vsak element v zaporedju pogleda vse ostale in se nauči, kako pomembni so zanj (podobno kot se pri stavku nauči, na katero besedo se npr nanaša nek zaimek ali pridevnik). Temporal (časovni) transformer obravnava zaporedne time frame (časovne korake) kot zaporedje, kar omogoča našemu modelu da se nauči, kako prejšnja stanja jate rib vplivajo na prihodnje obnašanje.

Napovedovanje premikanja jate rib z uporabo grafovskih nevronskih mrež

Jate ptic in rib, roji žuželk, velike gruče ljudi - vse tvorijo čudovito skupinsko obnašanje, kjer se obnašajo kot celota. Simulacija in napovedovanje takšnega obnašanja nam omogoča, da lahko napovemo obnašanje množic v prostoru z določenimi potmi (npr štadion). Problema se lotimo z grafovskimi nevronskimi mrežamo (angl. GNN - graph neural networks). Ideja je, da je obnašanje posameznika odvisno od ostalih članov jate, še posebej od tistih, ki so v neposredni bližini, in od gibanja posameznika v kratkem intervalu prej.

Posamezno ribo predstavimo z vozliščem, ki ima kot atribute pozicijo v 2D prostoru in vektor hitrosti, povezave v grafu pa predstavljajo potencialne interakcije med ribami. Napovedati želimo atribute vozlišč ob naslednjem času - problem je očitno odvisen tako od časovnih in prostorskih interakcij, zato smo sestavili spatiotemporal GNN-Transformer. Z GATom smo zajeli prostorske interakcije na vsakem frameu (gibanje ribe je odvisno od hitrosti in poravnanosti njenih sosedov), ki nam za vsako ribo da njen embedding. Za zajem časovne komponente smo uporabili transformer, ki nam pove, kako se embedding vsake ribe spreminja v zadnjih $T$ framih. Na koncu majhen prediction head vrne napoved za $(x,y)$ premik vsake ribe.

Model smo testirali na 3 različnih konstrukcijah grafov.

• kNN - vsaka riba je povezana s $k$ najbližjimi sosedi
• kNN + mostovi - kNN grafi lahko včasih razpadejo na nepovezane komponente (nastaneta 2 ločeni jati rib). V tem primeru ne moremo prenesti informacije med komponentami (message passing odpove). Komponente zato povežemo z mostovi med centroidi (označeni krogi na sliki), in takšne povezave posebej označimo.
• poln graf - vsaka riba je povezana z vsako. To sicer zajame globalne interakcije, ampak je drago ($\mathcal{O}(n)$ povezav) in lahko povzroči povprečenje obnašanja (over-smoothing).

Ključen problem v napovedovanju poti je t.i. "exposure bias" - če treniramo zgolj za 1 korak vnaprej, se morda v tistem koraku zmotimo za malo, a se ta napaka akumulira skozi naslednje korake, in po 5 korakih napovemo povsem napačen premik, kljub temu, da smo korak za korakom napovedovali "precej OK". Da se temu izognemo, treniramo z nekim drseči oknom.

Objavljeno: 30. 1. 2026