Salt la conținut

Aplicații ale rețelelor pe grafuri

IntermediarLectură: 8 min

Pagina despre rețelele neuronale pe grafuri explică felul în care funcționează aceste rețele: fiecare nod își actualizează vectorul pornind de la vectorii vecinilor. Pentru a folosi o astfel de rețea, prima întrebare este ce sunt nodurile și ce sunt muchiile. Odată ce graful este ales, același mecanism poate prezice durata unui drum, vremea de mâine sau efectul unei molecule asupra unei bacterii.

AplicațieNoduriMuchiiCe prezice rețeaua
Google Mapsporțiuni de drumporțiunile care se continuă una pe altadurata drumului
GraphCastpuncte de pe o rețea care acoperă Pământullegături la mai multe distanțevremea peste 6 ore, pas cu pas până la 10 zile
Halicinaatomii unei moleculelegăturile chimicedacă molecula oprește creșterea unei bacterii
GNoMEatomii unui cristalatomii aflați aproape unii de alțiidacă un cristal este stabil
PinSageimagini salvate (pinuri) și colecții (panouri)o imagine salvată într-o colecțiece imagini se potrivesc unei imagini date
Simularea fiziciiparticule de apă, nisip sau alte materialeparticulele aflate aproapemișcarea la pasul următor

O estimare a duratei unui drum trebuie să știe nu doar cât de aglomerată este strada pe care ne aflăm, ci și cum se va schimba traficul în următoarele minute, pe străzile pe care urmează să ajungem. Un ambuteiaj de pe o stradă se întinde, în câteva minute, și pe străzile care duc spre acea stradă.

În 2020, DeepMind și echipa Google Maps au introdus o rețea pe grafuri pentru această problemă. Rețeaua de drumuri este împărțită în supersegmente: șiruri de porțiuni de drum consecutive, care urmează traseele obișnuite ale traficului. Fiecare supersegment este un graf, în care nodurile sunt porțiunile de drum, iar o muchie leagă două porțiuni care se continuă una pe alta. Prin transmiterea mesajelor, fiecare porțiune află ce se întâmplă pe porțiunile vecine, iar rețeaua estimează cât durează parcurgerea întregului supersegment.

Google Maps estima deja corect durata pentru peste 97% dintre drumuri. Rețeaua pe grafuri a redus mult cazurile în care estimarea greșea mult: în Sydney, cu peste 40% față de modelul folosit anterior, iar în celelalte orașe analizate, cu procente cuprinse între 16% (Londra și Copenhaga) și 51% (Taichung, în Taiwan).

Modelele meteorologice clasice rezolvă numeric ecuațiile fizicii atmosferei, pe supercalculatoare. GraphCast, publicat de Google DeepMind în 2023, învață prognoza direct din datele meteorologice ale ultimelor decenii.

Atmosfera este descrisă pe o grilă cu pasul de 0,25 grade, adică aproximativ 28 de kilometri la ecuator, pe 37 de niveluri de altitudine. Rețeaua lucrează în trei etape:

  1. codificarea: valorile de pe grilă sunt mutate pe nodurile unei rețele de puncte care acoperă tot Pământul;
  2. procesarea: 16 straturi de transmitere a mesajelor rulează pe această rețea de puncte;
  3. decodarea: rezultatul este mutat înapoi pe grilă, ca prognoză pentru peste 6 ore.

Prognoza pentru 6 ore devine apoi intrare pentru următorul pas, iar repetarea duce prognoza până la 10 zile.

Rețeaua de puncte este construită dintr-un icosaedru, un poliedru cu 20 de fețe triunghiulare, ale cărui fețe sunt împărțite în triunghiuri tot mai mici, de 6 ori la rând. La final are 40.962 de noduri. Graful păstrează însă muchiile de la toate etapele împărțirii: muchiile scurte, de la ultima etapă, transportă detaliile locale, iar cele lungi, de la primele etape, duc informația peste mii de kilometri într-un singur strat. Este o soluție directă la problema câmpului receptiv: fără muchiile lungi, un sistem meteorologic din Atlantic ar avea nevoie de foarte multe straturi ca să influențeze prognoza pentru Europa.

O prognoză pe 10 zile durează sub un minut pe un singur cip Google Cloud TPU v4. Comparat cu HRES, modelul determinist al Centrului European pentru Prognoze Meteorologice pe Termen Mediu (ECMWF), cel mai precis sistem operațional de acest fel, GraphCast a fost mai precis pentru 90,3% dintre cele 1.380 de mărimi și termene de prognoză verificate.

ECMWF a testat GraphCast în timp real încă din 2023. Din 25 februarie 2025, centrul folosește operațional propriul model antrenat pe date, AIFS, care codifică și decodează datele tot cu o rețea pe grafuri, iar la mijloc folosește un Transformer. Succesorul lui GraphCast, GenCast (2024), este un model de difuzie care produce mai multe prognoze posibile. Rețeaua lui GenCast de eliminare a zgomotului lucrează pe aceeași rețea de puncte, cu un Transformer pe graf, iar prognozele pe 15 zile ale modelului au fost mai bune decât cele ale sistemului de ansamblu al ECMWF pentru 97,2% din 1.320 de ținte.

O moleculă este un graf natural: atomii sunt nodurile, iar legăturile chimice sunt muchiile. Unul dintre primele succese ale transmiterii mesajelor a venit din chimie. În 2017, Justin Gilmer și colegii săi au antrenat o rețea pe setul QM9, cu aproximativ 134.000 de molecule organice mici, și au estimat 11 dintre cele 13 proprietăți ale moleculelor cu precizia cerută de chimiști, fără calculele costisitoare ale chimiei cuantice.

În 2020, Jonathan Stokes și colegii săi, de la MIT, au folosit o rețea pe grafuri numită Chemprop ca să caute antibiotice noi. Au antrenat-o pe 2.335 de molecule, despre care se știa dacă opresc creșterea bacteriei E. coli, apoi au folosit-o ca să evalueze 6.111 molecule din Drug Repurposing Hub, o colecție de medicamente și de molecule studiate deja. Așa au găsit halicina, o moleculă care omora și bacterii rezistente la antibioticele existente, precum Mycobacterium tuberculosis și enterobacteriile rezistente la carbapeneme. La șoareci, halicina a vindecat infecții cu Clostridioides difficile și cu o tulpină de Acinetobacter baumannii rezistentă la toate antibioticele disponibile. Tot atunci, rețeaua a evaluat peste 107 milioane de molecule din baza de date ZINC15. Din cele 23 de molecule alese pentru testare, 8 au avut efect antibacterian.

În 2023, o echipă din care făcea parte și Stokes a repetat procesul pentru Acinetobacter baumannii. Rețeaua a evaluat aproximativ 7.500 de molecule și a găsit abaucina, care acționează doar asupra acestei bacterii și a vindecat infecții ale rănilor la șoareci. Un antibiotic atât de țintit afectează mai puțin celelalte bacterii din organism. Descoperirea unei molecule este însă doar primul pas: până la un medicament aprobat urmează ani de teste, inclusiv pe oameni.

Și un cristal este un graf de atomi. În 2023, Google DeepMind a publicat GNoME, un sistem bazat pe rețele pe grafuri antrenat să estimeze dacă un cristal este stabil, adică dacă are o energie mai mică decât orice combinație de materiale cunoscute în care s-ar putea descompune. GNoME a propus 2,2 milioane de structuri cristaline cu această proprietate față de materialele cunoscute până atunci. După ce au fost adăugate la lista materialelor stabile, 381.000 dintre aceste structuri au rămas stabile și față de celelalte structuri noi, ceea ce a dus lista la 421.000 de cristale stabile. Dintre acestea, 736 fuseseră deja obținute experimental de alte echipe.

Rezultatele au fost primite și cu rezerve. În același număr al revistei Nature, o echipă de la Berkeley a descris A-Lab, un laborator automat care a încercat să sintetizeze materiale propuse de calcule. Articolul inițial anunța 41 de compuși noi obținuți din 58 de încercări. O corectură publicată în ianuarie 2026 a schimbat rezultatul în 36 de compuși din 57 de ținte, obținuți în 17 zile, și a precizat că „noi” însemna noi pentru baza de date de pornire, nu neapărat noi pentru știință. Chimiștii Anthony Cheetham și Ram Seshadri au publicat în 2024 o analiză critică a lucrării despre GNoME, care pune sub semnul întrebării cât de noi și de utile sunt structurile propuse.

Pinterest are un graf natural: imaginile salvate de utilizatori, numite pinuri, și colecțiile în care sunt salvate, numite panouri. Un pin este legat de fiecare panou în care a fost salvat. Două pinuri salvate des în aceleași panouri seamănă, chiar dacă imaginile arată diferit.

În 2018, Pinterest și Universitatea Stanford au descris PinSage, o rețea pe grafuri pornită de la ideile lui GraphSAGE. Graful avea 3 miliarde de noduri (2 miliarde de pinuri și 1 miliard de panouri) și 18 miliarde de muchii, iar rețeaua a fost antrenată pe 7,5 miliarde de exemple. La un asemenea graf, nodurile nu pot aduna mesajele tuturor vecinilor, așa că fiecare nod folosește doar un număr mic de vecini, aleși după cât de des sunt vizitați în plimbări aleatoare prin graf. PinSage a fost folosit pentru pinurile recomandate lângă o imagine și pentru pagina principală a fiecărui utilizator, iar testele A/B au arătat o implicare a utilizatorilor cu 30% până la 100% mai mare.

Idei asemănătoare sunt folosite și în alte rețele sociale. LinkedIn a descris în 2024 LiGNN, o rețea pe grafuri pentru recomandări, care, în testele A/B, a crescut cu 2% rata de clic pe reclame și cu 1% rata la care candidații primesc un răspuns la aplicațiile pentru locuri de muncă.

Un fluid sau un material granular, precum nisipul, poate fi simulat ca un set de particule. În 2020, Alvaro Sanchez-Gonzalez și colegii săi, de la DeepMind, au tratat fiecare particulă ca pe un nod, legat prin muchii de particulele aflate în apropiere. Rețeaua primește pozițiile și vitezele recente și prezice accelerația fiecărei particule la pasul următor, iar repetarea pașilor produce întreaga simulare.

Același model a învățat să simuleze apa, nisipul, un material vâscos și obiecte rigide, inclusiv interacțiunile dintre materiale, cu până la aproximativ 19.000 de particule. Pentru că învață reguli locale, între particule apropiate, rețeaua a funcționat și pe un spațiu mai mare, cu 85.000 de particule, de 34 de ori mai multe decât la antrenare, pe parcursul a 5.000 de pași.