Odnoszę wrażenie, że każdy, kto w toku swojej edukacji zetknął się z zagadnieniami matematyki dyskretnej, miał do czynienia z grafami. W liceum, technikum lub na studiach niejednokrotnie omawiane są pojęcia takie jak cykle Hamiltona, ścieżki czy stopnie wierzchołków.

Z własnego doświadczenia wiem jednak, że tego rodzaju informacje dość szybko ulatują z głowy, a ich praktyczna przydatność jest, oględnie mówiąc, ograniczona. Z wyjątkiem zawodowych matematyków lub osób specjalizujących się w takich dziedzinach jak logistyka, optymalizacja ruchu w sieci czy odkrywanie leków i białek - klasyczne grafy i ich teoria pozostają ciekawostką i przypisem na marginesie naszych edukacyjnych podróży.

 

Tymczasem, jeśli wytężymy swoją wyobraźnię i odpowiednio ją ukierunkujemy - uda nam się dostrzec grafy w naszym najbliższym otoczeniu, także cyfrowym. Są nimi sieci społecznościowe, gdzie poszczególne osoby nawiązują kontakty i wymieniają wiadomości; są nimi portale do poszukiwania pracy przeplatające kompetencje kandydatów, wymagania na stanowiska i oferty firm; jest nią sama sieć z routerami, pakietami, odbiorcami i nadawcami.

 

Co jednak jeszcze ciekawsze - także teksty mogą być grafem, gdy wydobędziemy z nich pojęcia, abstrakcje, osoby i ich relacje. Semantyczny rozkład artykułów czy wypowiedzi może nam dostarczyć wartościowej wiedzy dotyczącej powiązań między tematami, wątkami i bohaterami.

 

Żadna z tych koncepcji nie jest nowa. Teoria grafów stanowi część matematyki już od około XVIII wieku, a lingwiści doskonale znają rozbiory gramatyczne. Zaskakujące jest jednak, jak rzadko myślimy w kategoriach grafów, gdy przychodzi do rozwiązywania problemów biznesowych lub technicznych.

 

Architektura MPNN

 

Rozwiązania techniczne służące do przetwarzania grafów także nie są niczym nowym. Jedna z najbardziej znanych grafowych baz danych - Neo4j - miała swoją premierę w 2007 r. i od tamtej pory powstały liczne, zbliżone rozwiązania. Naukowe oprogramowanie jak Matlab od lat posiada funkcje pozwalające na prowadzenie analiz grafowych.

 

Tymczasem w świecie sieci neuronowych sytuacja ma się nieco inaczej. Przytłaczająca większość modeli tego typu zakłada istnienie pewnej stałej, uporządkowanej struktury. Wielowarstwowe perceptrony (ang. multilayer perceptrons - MLP) przyjmują jako wejście macierze o stałej liczbie kolumn. Sieci rekurencyjne (ang. recurrent neural networks - RNN) i ich odmiany jak LSTM przyjmują następstwo czasu obserwacji następujących jedna po drugiej. Sieci splotowe (ang. convolutional neural networks - CNN) przyjmują obrazki o zadanej wielkości i posługują się kernelami/filtrami w formie kwadratu. Od każdej takiej reguły istnieją oczywiście wyjątki, a jednak w przeważającej większości przypadków regularność i struktura są podstawą tego rodzaju architektur.

 

W przypadku grafów sprawa ma się jednak zupełnie inaczej. Wierzchołki mogą posiadać różne sąsiedztwo, a czasem nie posiadać go w ogóle! Mogą formować cykle, pętle do samego siebie i inne struktury. Na przestrzeni lat podejmowano różne próby szkolenia sieci neuronowych na potrzeby grafów, wykorzystując rozmaite elementy aparatu matematycznego (Z. Wu i in., 2021) - od analizy spektralnej (ang. spectral graph convolution), przez rekurencję grafową, aż po specjalne warianty splotu.

 

Pewna architektura okazała się jednak wyjątkowo uniwersalna i elastyczna - łatwa do implementacji, rozszerzania, modyfikowania i eksperymentowania. Mowa o paradygmacie przekazywania wiadomości (ang. message passing neural network - MPNN) zaprezentowanym w 2017 r. (Gilmer i in., 2017). Jego założenia są zwodniczo proste. Cały proces szkolenia sieci MPNN sprowadza się bowiem do kilku faz:

 

  • Dla każdego wierzchołka v, opisanego za pomocą wektora atrybutów hu∈ Rd w grafie:
    • Znajdź wszystkich jego sąsiadów u∈ N(v) połączonych krawędzią euv;
    • Dla każdego takiego sąsiada i krawędzi::

■ Skonstruuj “wiadomość” przekształcając w dowolny sposób wektor atrybutów sąsiada i krawędzi:
mu=MSG(hv, hu, euv).

    • Agreguj wszystkie wiadomości w dowolny sposób: hN(v)=AGG({mu| ∀u ∈N(v) }).
    • Dokonaj aktualizacji wierzchołka v w dowolny sposób, biorąc pod uwagę jego dotychczasową reprezentację oraz sąsiedztwo:
      hv= UPD(hv, hN(v)).

 

Rys. 1: Uproszczony schemat działania modelu przekazywania wiadomości w architekturze MPNN.

 

Kroki te można powtarzać wielokrotnie, stopniowo zmieniając reprezentację wierzchołków. Jak widać w powyższym uproszczonym opisie, dokładna implementacja funkcji MSG, AGG i UPD nie została podana, umożliwiając niemal dowolne ich kształtowanie. Od chwili opublikowania pierwszej wersji architektury MPNN powstały setki jej rozszerzeń i modyfikacji obejmujących m.in. stosowanie wielokrotnych agregacji, kalkulację współczynników uwagi czy wyspecjalizowanych podsieci neuronowych.

 

Równolegle rozwijane są inne podejścia, w tym architektury hybrydowe, łączące MPNN z analizą spektralną lub klasyczną teorią grafów.

 

Zastosowania sieci grafowych

 

No dobrze, ale można sobie w tym punkcie zadać pytanie - jak można tego rodzaju sieci wykorzystać praktycznie i w jakich zadaniach sprawdzają się najlepiej?

 

Można wskazać trzy główne poziomy, na których funkcjonują sieci grafowe (GNN):

1. Działania na poziomie wierzchołków - obejmują wszelkie predykcje dokonywane na wierzchołkach grafów, a więc klasyfikację, regresję lub poszukiwanie podobieństwa na podstawie wektorów cech. 

Jako przykłady można podać przyporządkowywanie kont lub użytkowników sieci społecznościowych do kategorii (bot/rzeczywista osoba) bądź rozpoznawanie i unifikację encji znalezionych w tekście (np. Donald Trump, Prezydent Trump i Trump to ta sama postać).

Rys. 2: Przykład klasyfikacji użytkowników w sieci społecznościowej.

 

2. Działania na poziomie krawędzi - mają na celu klasyfikację/regresję już istniejących połączeń lub sugerowanie dodania kolejnych.

Jednymi z najbardziej oczywistych zastosowań mogą być systemy rekomendacyjne, w których połączenie oznacza zakup produktu i jego ewentualną ocenę. Inne przypadki to wykrywanie oszustw w transakcjach finansowych lub interakcji leków.

 

Rys. 3: Analiza krawędzi w grafie przepływów finansowych między osobami a instytucjami.

 

3. Działania na poziomie całych grafów - w takim przypadku sieć GNN bierze pod uwagę cechy wszystkich wierzchołków i/lub krawędzi i generuje podsumowanie numeryczne (osadzenie - ang. embedding) dla całego grafu. Następnie można dokonać jego klasyfikacji, prognozowania wartości numerycznej lub oceniać podobieństwo do innych struktur.

 

Rys. 4: Przykład cząsteczek, które można klasyfikować na podstawie ich własności.

 

Tego typu operacje spotyka się m.in. w chemii lub biologii przy analizie cząsteczek, a także podczas oceny struktur organizacyjnych podmiotów gospodarczych lub sieci społecznościowych.

 

Wraz z ogromnym wzrostem popularności systemów agentowych opartych na modelach LLM coraz częściej spotyka się wzorzec generowania treści wspomaganych wyszukiwaniem w bazach grafowych (ang. GraphRAG) lub analizę semantyczną z prowadzonym przez agenta rozkładem na podmiot-relację-przedmiot. Sieci GNN mogą wydatnie pomóc w konstruowaniu tego rodzaju struktur oraz ich późniejszym przetwarzaniu (Knollmeyer i in., 2025) - np. poprzez unifikację znalezionych encji lub sugerowanie zależności.

 

Podsumowanie

 

Obecnie grafy to coś więcej niż temat, którym zamęcza się studentów podczas zajęć z "Matematyki dyskretnej". Możemy je odnaleźć na każdym kroku - są w naszej rzeczywistości biznesowej (gdzie funkcjonują jako taksonomie pojęć lub ontologie), sieciowej (poprzez relacje na platformach i jako przesył danych), a nawet w zwyczajnych tekstach, gdzie tworzą trójki podmiot-relacja-przedmiot.

 

Zaprojektowano specjalne architektury sieci neuronowych - GNN - aby móc poradzić sobie z nieregularnymi i zmiennymi strukturami grafowymi. GNN potrafią przetwarzać pojedyncze wierzchołki, relacje lub całe grupy obiektów, realizując zadania z różnych dziedzin uczenia maszynowego - klasyfikację, regresję, grupowanie, wyszukiwanie podobieństw.

 

W połączeniu z grafowymi bazami danych oraz systemami agentowymi opartymi na LLM-ach uzyskujemy zestaw zaawansowanych narzędzi, pozwalających znajdować porządek w pozornie chaotycznym świecie grafów.

 

Bibliografia

Gilmer, J., Schoenholz, S. S., Riley, P. F., Vinyals, O., & Dahl, G. E. (2017, July). Neural message passing for quantum chemistry. In International conference on machine learning (pp. 1263-1272). PMLR.

Han, Haoyu, Yu Wang, Harry Shomer, Kai Guo, Jiayuan Ding, Yongjia Lei, Mahantesh Halappanavar et al. "Retrieval-augmented generation with graphs (GraphRAG)." arXiv preprint arXiv:2501.00309 (2024).

Knollmeyer S, Caymazer O, Grossmann D. Document GraphRAG: Knowledge Graph Enhanced Retrieval Augmented Generation for Document Question Answering Within the Manufacturing Domain. Electronics. 2025; 14(11):2102. https://doi.org/10.3390/electronics14112102

Wu, Z., Pan, S., Chen, F., Long, G., Zhang, C., & Yu, P. S. (2021). A Comprehensive Survey on Graph Neural Networks. IEEE Transactions on Neural Networks and Learning Systems, 32(1), 4–24. https://doi.org/10.1109/TNNLS.2020.2978386