Salt la conținut

Rețele neuronale pe grafuri

IntermediarLectură: 12 min

O imagine este o grilă de pixeli, iar un text este un șir de tokenuri. Multe date nu arată însă nici ca o grilă, nici ca un șir. O moleculă este formată din atomi uniți prin legături chimice, o rețea socială din oameni legați prin prietenii, iar o rețea de drumuri din intersecții legate prin străzi. În aceste date, legăturile contează la fel de mult ca elementele pe care le leagă.

O rețea neuronală pe grafuri (graph neural network, GNN) lucrează direct pe astfel de structuri. Fiecare element învață din elementele cu care este legat, iar după câțiva pași fiecare „știe” ceva despre propria vecinătate. Rețele de acest fel estimează durata drumurilor în Google Maps, prognozează vremea în modelul GraphCast și au ajutat la descoperirea unui antibiotic nou, halicina. Pagina despre aplicațiile rețelelor pe grafuri descrie aceste exemple.

Un graf (graph) este format din noduri (nodes) și muchii (edges), adică legături între perechi de noduri. Fiecare nod are un vector de caracteristici: pentru un atom, de exemplu, elementul chimic și sarcina electrică, iar pentru un utilizator, vârsta și interesele. Și muchiile pot avea caracteristici, precum tipul legăturii chimice (simplă, dublă sau triplă), și pot avea un sens, ca citările dintre articolele științifice. Numărul de vecini ai unui nod se numește grad (degree).

Calculatorul păstrează legăturile într-o matrice de adiacență (adjacency matrix), notată AA, cu câte un rând și o coloană pentru fiecare nod. Valoarea de pe rândul ii și coloana jj este 1 dacă nodurile ii și jj sunt legate și 0 dacă nu sunt.

O rețea pe grafuri poate răspunde la trei tipuri de întrebări.

  • Despre noduri: ce subiect are un articol științific dintr-o rețea de citări sau dacă un cont dintr-o rețea socială este fals.
  • Despre muchii: dacă între două noduri ar trebui să existe o legătură, de exemplu ce produs l-ar putea interesa pe un client.
  • Despre întregul graf: o proprietate a întregii molecule, de exemplu dacă poate opri creșterea unei bacterii.

Forma completă a modelului a fost descrisă în 2009 de Franco Scarselli, Marco Gori și colegii lor, de la Universitatea din Siena. Rețelele pe grafuri au devenit larg folosite după 2017, odată cu rețelele convoluționale pe grafuri, descrise mai jos.

O rețea neuronală obișnuită primește la intrare un vector de lungime fixă, cu valorile mereu în aceeași ordine. Am putea transforma matricea de adiacență într-un vector și am putea da rețelei acest vector, dar apar trei probleme.

  • Mărimea: o moleculă poate avea 5 atomi sau 500, iar o rețea socială, miliarde de utilizatori.
  • Ordinea: nodurile nu au o ordine naturală. Dacă numerotăm altfel aceleași noduri, matricea de adiacență se schimbă, deși graful a rămas același. Un graf cu 10 noduri poate fi numerotat în 10!10! feluri, adică 3.628.800, iar rețeaua ar trebui să dea același răspuns pentru fiecare. Proprietatea se numește invarianță la permutări (permutation invariance).
  • Vecinătatea: într-o imagine, fiecare pixel are opt vecini, așezați mereu la fel, iar o rețea neuronală convoluțională (convolutional neural network, CNN) se bazează pe această regularitate. Într-un graf, un nod poate avea un singur vecin, iar altul o mie.

Privite așa, și imaginile, și textele sunt grafuri: o imagine este o grilă în care fiecare pixel este legat de pixelii vecini, iar un text este un lanț de tokenuri. Rețelele pe grafuri tratează cazul general, în care legăturile pot avea orice formă.

Aproape toate rețelele pe grafuri folosesc transmiterea mesajelor (message passing). Fiecare nod are un vector, la început chiar vectorul de caracteristici al nodului. La fiecare strat al rețelei, fiecare nod face trei lucruri:

  1. primește de la fiecare vecin câte un mesaj, de obicei vectorul vecinului, eventual transformat;
  2. adună mesajele printr-o agregare (aggregation) care nu depinde de ordinea vecinilor, de exemplu o sumă, o medie sau un maxim;
  3. își actualizează (update) vectorul, combinând rezultatul agregării cu vectorul pe care îl avea înainte, printr-o rețea mică.
Un strat de transmitere a mesajelorNodul v are patru vecini, a, b, c și d. Fiecare vecin îi trimite propriul vector, ca mesaj. Nodul v adună mesajele printr-o agregare care nu depinde de ordinea vecinilor, de exemplu o sumă, o medie sau o medie ponderată prin atenție. Apoi actualizarea, o rețea mică ale cărei ponderi sunt aceleași pentru toate nodurile, combină rezultatul cu vectorul vechi al lui v și produce vectorul nou al lui v.abcdvVecinii lui v îi trimit vectorii.Agregaresumă, medie, atențieActualizareponderi comuneVectorul noual lui vAcelași calcul, pentru fiecare nod
Un strat al rețelei. Toate nodurile fac același calcul în paralel, cu aceleași ponderi, deci rețeaua funcționează pe grafuri de orice mărime.

Toate nodurile folosesc aceleași ponderi, la fel cum o rețea convoluțională folosește același filtru în toate pozițiile unei imagini. Numărul de parametri nu depinde deci de mărimea grafului, iar aceeași rețea poate primi o moleculă mică sau una mare. Pentru că suma, media și maximul nu țin cont de ordine, nici rezultatul nu depinde de felul în care au fost numerotate nodurile. Cadrul general a fost formulat în 2017 de Justin Gilmer și colegii săi, de la Google, care au arătat că multe modele propuse până atunci sunt cazuri particulare ale acestui cadru.

Pentru curioșiFormula unui strat de transmitere a mesajelor
hv(k+1)=ϕ(hv(k), ⨁u∈N(v)ψ(hv(k),hu(k),euv))h_v^{(k+1)} = \phi\left(h_v^{(k)},\ \bigoplus_{u \in \mathcal{N}(v)} \psi\left(h_v^{(k)}, h_u^{(k)}, e_{uv}\right)\right)

hv(k)h_v^{(k)} este vectorul nodului vv după kk straturi, N(v)\mathcal{N}(v) este mulțimea vecinilor lui vv, iar euve_{uv} sunt caracteristicile muchiei dintre uu și vv. Funcția ψ\psi calculează mesajul trimis de uu, ⨁\bigoplus este agregarea (sumă, medie sau maxim), iar ϕ\phi este actualizarea. ψ\psi și ϕ\phi sunt rețele mici, cu aceleași ponderi pentru toate nodurile.

După un strat, fiecare nod știe ceva despre vecinii direcți. După două straturi știe ceva și despre vecinii vecinilor, pentru că aceștia și-au trimis informația mai departe încă de la primul strat. După kk straturi, vectorul unui nod depinde de toate nodurile aflate la cel mult kk muchii distanță. Această zonă se numește câmp receptiv (receptive field).

Pentru o întrebare despre întregul graf, vectorii tuturor nodurilor sunt adunați la final într-un singur vector, de exemplu prin sumă sau medie, iar acest vector trece printr-un clasificator obișnuit. Pasul se numește agregare la nivelul grafului (readout).

Cea mai cunoscută variantă este rețeaua convoluțională pe grafuri (graph convolutional network, GCN), propusă în 2017 de Thomas Kipf și Max Welling, de la Universitatea din Amsterdam. Într-un strat GCN, fiecare nod face o medie ponderată între propriul vector și vectorii vecinilor, înmulțește rezultatul cu o matrice de ponderi comună tuturor nodurilor și aplică o funcție de activare, de exemplu ReLU.

Ponderile mediei țin cont de grade. Fără această corecție, un nod cu o mie de vecini ar aduna valori de sute de ori mai mari decât un nod cu doi vecini. GCN împarte mesajul de pe fiecare muchie la rădăcina pătrată a produsului dintre gradele celor două noduri, așa că un vecin cu foarte multe legături contează mai puțin pentru fiecare dintre nodurile cu care este legat.

Pentru curioșiFormula unui strat GCN
H(k+1)=σ(D~−1/2A~D~−1/2H(k)W(k)),A~=A+IH^{(k+1)} = \sigma\left(\tilde D^{-1/2} \tilde A \tilde D^{-1/2} H^{(k)} W^{(k)}\right), \qquad \tilde A = A + I

Matricea H(k)H^{(k)} are câte un rând pentru fiecare nod, cu vectorul nodului după kk straturi. A~\tilde A este matricea de adiacență la care se adaugă matricea identitate II, adică o legătură a fiecărui nod cu sine, ca nodul să-și păstreze și propria valoare. D~\tilde D este matricea diagonală cu gradele din A~\tilde A, W(k)W^{(k)} este matricea de ponderi a stratului, aceeași pentru toate nodurile, iar σ\sigma este funcția de activare. Pentru o muchie între nodurile ii și jj, produsul D~−1/2A~D~−1/2\tilde D^{-1/2} \tilde A \tilde D^{-1/2} dă ponderea 1/d~id~j1/\sqrt{\tilde d_i \tilde d_j}, unde d~i\tilde d_i este gradul nodului ii.

Kipf și Welling au testat GCN pe rețele de citări între articole științifice. Pe setul Cora, cu 2.708 articole și 5.429 de citări, rețeaua a primit subiectul a doar 5,2% dintre articole, iar pe articolele de test l-a ghicit corect în 81,5% din cazuri. O problemă în care doar câteva noduri au etichete, iar rețeaua le deduce pe ale celorlalte, se numește clasificare semi-supervizată (semi-supervised classification).

  • GraphSAGE (Universitatea Stanford, 2017) a fost gândit pentru grafuri foarte mari. În loc să adune mesajele tuturor vecinilor, fiecare nod alege la întâmplare un număr fix de vecini, de exemplu 25, așa că un strat costă la fel indiferent dacă nodul are 25 de vecini sau un milion. Rețeaua învață o regulă de calcul, nu câte un vector pentru fiecare nod, deci poate fi folosită și pentru noduri noi, care nu existau la antrenare.
  • Rețelele cu atenție pe grafuri (graph attention networks, GAT), propuse în 2018 de Petar Veličković și colegii săi, nu tratează toți vecinii la fel. Pentru fiecare muchie, rețeaua calculează o pondere de atenție din vectorii celor două noduri, iar agregarea devine o medie cu aceste ponderi. Un nod poate învăța astfel să țină cont mai mult de unii vecini decât de alții.

Transmiterea mesajelor are o limită. Să luăm două grafuri cu câte șase noduri: un hexagon și două triunghiuri separate. În ambele, fiecare nod are exact doi vecini. Dacă toate nodurile pornesc cu același vector, fiecare nod primește la fiecare strat exact aceleași mesaje în ambele grafuri, așa că rețeaua nu le poate deosebi, oricât de multe straturi ar avea.

În 2019, Keyulu Xu și colegii săi au arătat că rețelele bazate pe transmiterea mesajelor nu pot deosebi mai multe grafuri decât un algoritm clasic de comparare a grafurilor, numit testul Weisfeiler-Lehman. Tot ei au arătat că felul agregării contează. Media nu deosebește un nod cu un singur vecin de un nod cu trei vecini identici, pentru că media unui vector este aceeași cu media a trei copii ale vectorului. Suma îi deosebește. Rețeaua propusă de ei, GIN (graph isomorphism network), folosește suma și ajunge la aceeași putere ca testul Weisfeiler-Lehman.

Graful de mai jos are zece persoane, în două grupuri de prieteni. Singura legătură dintre grupuri este prietenia dintre Elena și Florin.

Graful din exemplu și distanța fiecărui nod până la AnaZece persoane în două grupuri de prieteni. În primul grup sunt Ana, Bogdan, Carmen, Dan și Elena, iar în al doilea Florin, Gabriela, Horia, Ioana și Laura. Singura legătură dintre grupuri este prietenia dintre Elena și Florin. Informația pornită de la Ana ajunge după un strat la Bogdan și Carmen, după două straturi la Dan și Elena, după trei la Florin, după patru la Gabriela și Horia și după cinci la Ioana și Laura.0Ana1Bogdan1Carmen2Dan2Elena3Florin4Gabriela4Horia5Ioana5Laurasingura legătură
Numărul din fiecare nod este stratul la care ajunge acolo, pentru prima dată, informația pornită de la Ana.

Primul exemplu pornește de la o informație pe care o are doar Ana: nodul ei are valoarea 1, iar toate celelalte au 0. La fiecare strat, fiecare nod face media dintre propria valoare și valorile vecinilor. Exemplul nu folosește ponderi învățate, ca să se vadă doar transmiterea mesajelor. Codul afișează valorile după primele cinci straturi și după 200 de straturi, iar · înseamnă că informația nu a ajuns încă la acel nod.

import numpy as np
# Zece persoane în două grupuri de prieteni, legate printr-o singură prietenie (Elena și Florin)
names = ["Ana", "Bogdan", "Carmen", "Dan", "Elena", "Florin", "Gabriela", "Horia", "Ioana", "Laura"]
edges = [(0, 1), (0, 2), (1, 2), (1, 3), (2, 3), (2, 4), (3, 4), (4, 5),
(5, 6), (5, 7), (6, 7), (6, 8), (7, 8), (7, 9), (8, 9)]
n = len(names)
A = np.zeros((n, n)) # matricea de adiacență: A[i, j] = 1 dacă i și j sunt prieteni
for i, j in edges:
A[i, j] = A[j, i] = 1
# Un strat de transmitere a mesajelor, fără ponderi învățate:
# fiecare nod face media dintre valoarea lui și valorile vecinilor
A_self = A + np.eye(n) # fiecare nod este legat și de el însuși
mean_neighbors = A_self / A_self.sum(axis=1, keepdims=True)
def show(label, values):
cells = ("·" if v == 0 else "<0.001" if v < 0.0005 else f"{v:.3f}" for v in values)
print(f"{label:<11}" + "".join(f"{c:>9}" for c in cells))
print(" " * 11 + "".join(f"{name:>9}" for name in names))
x = np.zeros(n)
x[0] = 1.0 # doar Ana are informația
show("început", x)
for layer in range(1, 201):
x = mean_neighbors @ x
if layer <= 5 or layer == 200:
show(f"strat {layer}", x)

Codul poate fi modificat și rulat direct în browser (Ctrl + Enter).

Informația înaintează câte o muchie la fiecare strat, exact ca în diagramă. Florin primește ceva abia la al treilea strat, iar Ioana și Laura abia la al cincilea. După 200 de straturi, toate nodurile au aceeași valoare și nu se mai poate spune de unde a pornit informația. Acest fenomen limitează numărul de straturi, așa cum arată secțiunea despre limite.

Al doilea exemplu este o clasificare semi-supervizată, ca în articolul despre GCN. Știm doar că Ana face parte din grupul 0 și că Laura face parte din grupul 1, iar rețeaua trebuie să găsească grupul tuturor celorlalți. Fiecare nod pornește doar cu propria identitate, un vector one-hot, iar două straturi de agregare GCN îi aduc informație din vecinătatea de doi pași. Peste vectorii obținuți, codul antrenează un clasificator liniar, doar pe cele două noduri cu etichetă. Varianta fără funcții de activare între straturi se numește SGC (simplified graph convolution) și a fost propusă în 2019 de Felix Wu și colegii săi, care au arătat că, pe multe seturi de date, se descurcă aproape la fel de bine ca GCN și se antrenează mult mai repede.

# Graful (names, edges, n și A) este cel din exemplul de mai sus.
# Normalizarea din GCN: muchia dintre i și j primește ponderea 1 / sqrt(grad(i) * grad(j))
A_self = A + np.eye(n)
degree = A_self.sum(axis=1)
S = A_self / np.sqrt(np.outer(degree, degree))
# La început, fiecare nod știe doar cine este (un vector one-hot).
# Două straturi de agregare îi aduc informație de la nodurile aflate la cel mult doi pași.
X = np.eye(n)
H = S @ S @ X
# Știm grupul a doar două persoane: Ana este în grupul 0, iar Laura în grupul 1
labeled = [0, 9]
Y = np.array([[1.0, 0.0], [0.0, 1.0]])
# Un clasificator liniar (softmax), antrenat prin coborâre pe gradient doar pe cele două noduri
def softmax(z):
e = np.exp(z - z.max(axis=1, keepdims=True))
return e / e.sum(axis=1, keepdims=True)
rng = np.random.default_rng(seed=0)
W = rng.normal(scale=0.1, size=(n, 2))
for step in range(500):
P = softmax(H[labeled] @ W)
W -= H[labeled].T @ (P - Y) / len(labeled)
P = softmax(H @ W)
for i, name in enumerate(names):
note = " (etichetă dată)" if i in labeled else ""
print(f"{name:<9} grupul {P[i].argmax()} probabilitatea grupului 1: {P[i, 1]:.2f}{note}")

Codul poate fi modificat și rulat direct în browser (Ctrl + Enter).

Cu doar două etichete, rețeaua pune toate cele zece persoane în grupul corect. Fiecare nod ajunge să semene cu nodul etichetat de care este mai aproape în graf. Elena și Florin, legați între ei peste granița dintre grupuri, au probabilitățile cele mai puțin sigure: 0,12 și 0,89.

  • Netezirea excesivă (over-smoothing): după multe straturi, vectorii tuturor nodurilor ajung să semene unii cu alții, ca în primul exemplu. Qimai Li și colegii săi au descris fenomenul în 2018, pornind chiar de la GCN. De aceea, rețelele pe grafuri au adesea doar două sau trei straturi, în timp ce rețelele pentru imagini sau text au zeci.
  • Comprimarea excesivă (over-squashing): informația de la nodurile îndepărtate trebuie să treacă prin puține muchii. În exemplu, tot ce află grupul lui Florin despre grupul Anei trece prin muchia dintre Elena și Florin. Când câmpul receptiv crește foarte repede de la un strat la altul, tot mai multă informație trebuie strânsă într-un vector de aceeași mărime. Uri Alon și Eran Yahav au arătat în 2021 că acest blocaj explică de ce rețelele pe grafuri se descurcă greu când rezultatul depinde de noduri aflate departe unele de altele.
  • Mărimea: un graf cu miliarde de noduri nu încape în memoria unei plăci grafice. Antrenarea se face pe bucăți: se alege un lot de noduri și se iau doar vecinătățile acestor noduri, eventual eșantionate, ca la GraphSAGE.

Un Transformer poate fi privit ca o rețea pe un graf în care fiecare token este un nod legat de toate celelalte. Mecanismul de atenție este o agregare a mesajelor de la toți vecinii, cu ponderi calculate din vectorii nodurilor, ca la GAT. Într-un text nu există muchii care să spună ce cuvinte sunt legate, așa că Transformerul se uită la toate perechile și învață singur care contează. Ordinea cuvintelor, pe care un graf complet nu o reține, vine din codificarea pozițională. Chaitanya Joshi a descris această legătură în 2020, în eseul „Transformers are Graph Neural Networks”.

Legătura funcționează și în sens invers. Transformerele pe grafuri (graph transformers) aplică atenția peste toate perechile de noduri ale unui graf, deci informația nu mai trebuie să treacă prin muchiile care fac blocaj, și adaugă structura grafului ca informație suplimentară. Graphormer (Microsoft Research, 2021), de exemplu, adaugă la scorul de atenție dintre două noduri un termen care depinde de distanța dintre noduri în graf, măsurată în muchii.