Grafowa sieć neuronowa

Graficzna sieć neuronowa ( GNN ) to klasa sztucznych sieci neuronowych do przetwarzania danych, które można przedstawić w postaci wykresów .

Podstawowe elementy budulcowe sieci neuronowej Graph (GNN). ${\ Displaystyle (1)}$ Równoważna warstwa permutacji. ${\ Displaystyle (2)}$ Lokalna warstwa puli. ${\ Displaystyle (3)}$ Globalna pula (lub odczyt) warstwa. Kolory wskazują cechy .

W bardziej ogólnym temacie „ Głębokie uczenie geometryczne ” niektóre istniejące architektury sieci neuronowych można interpretować jako sieci GNN działające na odpowiednio zdefiniowanych grafach. Konwolucyjne sieci neuronowe , w kontekście widzenia komputerowego , mogą być postrzegane jako GNN zastosowane do grafów ustrukturyzowanych jako siatki pikseli . Transformatory , w kontekście przetwarzania języka naturalnego , mogą być postrzegane jako GNN zastosowane do pełnych grafów , których węzłami są słowa w zdaniu .

Kluczowym elementem projektu GNN jest wykorzystanie przekazywania komunikatów parami , tak że węzły grafu iteracyjnie aktualizują swoje reprezentacje, wymieniając informacje z sąsiadami. Od ich powstania zaproponowano kilka różnych architektur GNN, które implementują różne smaki przekazywania wiadomości, zapoczątkowane przez rekurencyjne lub konwolucyjne podejścia konstruktywne. Od 2022 r. Otwartą kwestią badawczą jest to, czy możliwe jest zdefiniowanie architektur GNN „wykraczających poza” przekazywanie komunikatów, czy też każdy GNN można zbudować na przekazywaniu komunikatów przez odpowiednio zdefiniowane grafy.

Odpowiednie domeny zastosowań GNN obejmują sieci społecznościowe , sieci cytowań , biologię molekularną , chemię, fizykę i NP-trudne problemy optymalizacji kombinatorycznej .

kilka bibliotek open source implementujących grafowe sieci neuronowe, takich jak PyTorch Geometric ( PyTorch ), TensorFlow GNN ( TensorFlow ) i jraph ( Google JAX ).

Architektura

Architektura ogólnego GNN obejmuje następujące podstawowe warstwy :

1. Równoważnik permutacji : warstwa równoważnika permutacji odwzorowuje reprezentację wykresu na zaktualizowaną reprezentację tego samego wykresu. W literaturze warstwy ekwiwalentne permutacji są realizowane poprzez przekazywanie komunikatów parami między węzłami grafu. Intuicyjnie , w warstwie przekazywania komunikatów węzły aktualizują swoje reprezentacje poprzez agregację komunikatów otrzymanych od ich bezpośrednich sąsiadów. W związku z tym każda warstwa przekazywania wiadomości zwiększa pole odbiorcze GNN o jeden przeskok.
2. Lokalne łączenie : lokalna warstwa łączenia zgrubia wykres poprzez próbkowanie w dół . Lokalne łączenie jest wykorzystywane do zwiększania pola receptywnego GNN, w podobny sposób jak łączenie warstw w konwolucyjnych sieciach neuronowych . Przykłady obejmują łączenie k-najbliższych sąsiadów , łączenie k-najlepszych i łączenie samouważności.
3. Łączenie globalne : warstwa łączenia globalnego, znana również jako warstwa odczytu , zapewnia reprezentację całego wykresu o stałym rozmiarze. Warstwa globalnej puli musi być niezmienna permutacyjnie, tak aby permutacje w kolejności węzłów i krawędzi grafu nie zmieniały ostatecznego wyniku. Przykłady obejmują elementarną sumę, średnią lub maksimum.

Wykazano, że GNN nie mogą być bardziej wyraziste niż test izomorfizmu wykresu Weisfeilera-Lehmana. W praktyce oznacza to, że istnieją różne struktury grafów (np. cząsteczki o tych samych atomach , ale różnych wiązaniach ), których nie można rozróżnić za pomocą GNN. Można zaprojektować potężniejsze sieci GNN działające na geometriach o wyższych wymiarach, takich jak uproszczone kompleksy . Od 2022 r. Otwartą kwestią badawczą jest to, czy przyszłe architektury przezwyciężą prymitywne przekazywanie wiadomości.

nieizomorficzne , których nie można rozróżnić za pomocą GNN ze względu na ograniczenia testu izomorfizmu grafów Weisfeilera-Lehmana. Kolory wskazują cechy węzłów .

Warstwy przekazywania wiadomości

Aktualizacja reprezentacji węzłów w warstwie sieci neuronowej przekazującej wiadomości (MPNN). Węzeł odbiera wiadomości wysyłane przez wszystkich jego bezpośrednich sąsiadów $} _ {1}}$$x$ do ${\ Displaystyle \ mathbf {x} _{4}}$ . Wiadomości są obliczane za pomocą funkcji wiadomości $uwzględnia$ cechy zarówno nadawców, jak i odbiorców

Warstwy przekazujące komunikaty to warstwy równoważne permutacji, odwzorowujące wykres na zaktualizowaną reprezentację tego samego grafu. Formalnie można je wyrazić jako sieci neuronowe przekazujące wiadomości (MPNN).

Niech $wykresem$ , gdzie $węzłów$ _ _ $_$ _ Niech ${\ displaystyle N_ {u}}$ będzie sąsiedztwem jakiegoś węzła ${\ displaystyle u \ in V}$ . Dodatkowo $_$ cechami _ węzła ${\ Displaystyle u \ in V}$ i ${\ Displaystyle \ mathbf {e} _ {uv}}$ być cechami krawędzi ${\ Displaystyle (u, v )\w E}$ . Warstwę MPNN można wyrazić w następujący sposób:

${\ Displaystyle \ mathbf {h} _ {u} = \ phi \ lewo (\ mathbf {x} _ {u},\bigoplus _{v\in N_{u}}\psi (\mathbf {x} _{u},\mathbf {x} _{v},\mathbf {e} _{uv})\ Prawidłowy)}$

gdzie i są funkcjami różniczkowalnymi (np. $)$$phi$ neuronowe , a jest niezmiennym permutacyjnym operatorem agregacji, który może przyjąć dowolną liczbę danych wejściowych ( $}$ np. elementarna suma, średnia lub maksimum). W szczególności ${\ displaystyle \ phi}$ i są określane jako aktualizacja i wiadomość ${\ displaystyle \ phi}$ odpowiednio funkcje. Intuicyjnie , w bloku obliczeniowym MPNN, węzły grafów aktualizują swoje reprezentacje poprzez agregację komunikatów otrzymanych od swoich sąsiadów.

Wyjścia jednej lub więcej warstw MPNN $na$$.$ dla wykresie Reprezentacje węzłów mogą być wykorzystywane do dowolnych dalszych zadań, takich jak klasyfikacja węzłów/grafów lub przewidywanie krawędzi.

Węzły grafu w sieci MPNN aktualizują swoją reprezentację, agregując informacje od swoich bezpośrednich sąsiadów. $,$ związku z tym układanie $w stos oznacza$ że ​​jeden węzeł będzie mógł komunikować się z węzłami, które są co najwyżej „przeskokami”. W zasadzie, aby każdy węzeł otrzymywał informacje z każdego innego węzła, należałoby ułożyć w stos liczbę warstw MPNN równą średnicy grafu . Jednak układanie wielu warstw MPNN może powodować problemy, takie jak nadmierne wygładzanie i nadmierne zgniatanie. Oversmoothing odnosi się do problemu nieodróżnialności reprezentacji węzłów. Oversquashing odnosi się do wąskiego gardła, które jest tworzone przez ściskanie zależności dalekiego zasięgu w reprezentacjach o stałym rozmiarze. Środki zaradcze, takie jak pomijanie połączeń (jak w szczątkowych sieciach neuronowych ), reguły bramkowanej aktualizacji i wiedza o skokach, mogą złagodzić nadmierne wygładzanie. Modyfikowanie ostatniej warstwy tak, aby była w pełni przylegającą warstwą, tj. poprzez traktowanie wykresu jako pełnego wykresu , może złagodzić nadmierne zgniecenie w problemach, w których wymagane są zależności dalekiego zasięgu.

W literaturze opracowano inne „smaki” MPNN, takie jak grafowe sieci splotowe i grafowe sieci uwagi, których definicje można wyrazić w kategoriach formalizmu MPNN.

Grafowa sieć splotowa

Grafowa sieć splotowa (GCN) została po raz pierwszy wprowadzona przez Thomasa Kipfa i Maxa Wellinga w 2017 roku.

Warstwa GCN definiuje przybliżenie pierwszego rzędu zlokalizowanego filtra widmowego na wykresach. Sieci GCN można rozumieć jako uogólnienie konwolucyjnych sieci neuronowych na dane o strukturze grafowej.

Formalne wyrażenie warstwy GCN brzmi następująco:

${\ Displaystyle \ mathbf {H} = \ sigma \ lewo ({\ tylda {\ mathbf {D}}} ^ {- {\ Frac {1}{2}}}{\tylda {\mathbf {A}}}{\tylda {\mathbf {D}}}^{-{\frac {1}{2}}}\mathbf {X} \ mathbf {\Theta} \right)}$

gdzie ${\ Displaystyle \ mathbf {H}}$ jest macierzą reprezentacji węzłów ${\ Displaystyle \ mathbf {h} _ {u}}$ , ${\ Displaystyle \ mathbf {X}}$ jest macierzą cech węzłów ${\ Displaystyle \ mathbf {x} _ {u}}$ , ${\ Displaystyle \ sigma (\ cdot)}$ jest funkcją aktywacji (np. ReLU ), ${\ Displaystyle {\ tylda {\ mathbf {A} }}}$ to wykres macierz sąsiedztwa z dodatkiem pętli własnych, $} }$ macierzą stopnia wykresu z dodatkiem pętli własnych, a $D}}}}$$\ mathbf {$ to macierz możliwych do nauczenia parametrów.

W szczególności niech będzie macierzą sąsiedztwa $wykresu$ : wtedy można zdefiniować ${\ Displaystyle {\ tylda {\ mathbf {A}}} = \ mathbf {$ i ${\ Displaystyle {\ tylda {\ mathbf {D}}} _ {ii} = \ suma _ {j \ w V} {\ tylda {A}} _ {ij}}$ , gdzie ${\ Displaystyle \ mathbf {I}}$ oznacza macierz tożsamości . Ta normalizacja zapewnia, że ​​wartości własne re ${\ mathbf {D}}} ^ {- {\ Frac {1} {2}}} {\ tylda {\ mathbf {A}}} {\ tylda {\ mathbf {D}}} ^ {- {\ Frac {1} {2}}}} są$ ograniczone w zakresie ${\ Displaystyle [0,1 ]}$ , unikając numerycznych niestabilności i eksplodujących/znikających gradientów .

Ograniczeniem GCN jest to, że nie pozwalają one na wielowymiarowe funkcje krawędzi mi $\ displaystyle \ mathbf {e} _ {uv}}$ . $jednak$ powiązanie wag każdą $każdej$ tj niezerowy wpis w macierzy sąsiedztwa równy wadze odpowiedniej krawędzi.

Wykres sieci uwagi

Grafowa sieć uwagi (GAT) została wprowadzona przez Petara Veličkovicia i in. w 2018 roku

Grafowa sieć uwagi jest połączeniem grafowej sieci neuronowej i warstwy uwagi. Implementacja warstwy uwagi w graficznych sieciach neuronowych pomaga zwrócić uwagę lub skupić się na ważnych informacjach z danych, zamiast skupiać się na całości danych.

Wielogłowicową warstwę GAT można wyrazić w następujący sposób:

${\ Displaystyle \ mathbf {h} _ {u} = {\ overset {K} {\ underset {k = 1} {\Big \Vert }}}\sigma \left(\sum _{v\in N_{u}}\alpha _{uv}\mathbf {W} ^{k}\mathbf {x} _{v}\ Prawidłowy)}$

gdzie $_$ liczbą głów uwagi $,$ oznacza $jest$ , funkcją ( _ _ ReLU ), $\ alpha _ {ij}}$$to$ to współczynniki uwagi, a możliwych do wyszkolenia parametrów dla ${\ displaystyle k}$ -ta głowa uwagi.

W przypadku ostatniej warstwy GAT wyjścia z każdej głowicy uwagi są uśredniane przed zastosowaniem funkcji aktywacji. Formalnie ostateczną warstwę GAT można zapisać jako:

${\ Displaystyle \ mathbf {h} _ {u} = \ sigma \ lewo ({\ Frac {1} K}}\sum _{k=1}^{K}\sum _{v\in N_{u}}\alpha _{uv}\mathbf {W} ^{k}\mathbf {x} _{v }\Prawidłowy)}$

Uwaga w uczeniu maszynowym to technika, która naśladuje uwagę poznawczą . $\ w V}$ kontekście uczenia się na wykresach współczynnik uwagi $ważny$ jak jest węzeł dla węzła $v$ .

Znormalizowane współczynniki uwagi oblicza się w następujący sposób:

${\ Displaystyle \ alfa _ {uv} = {\ Frac {\ exp ({\ tekst {LeakyReLU}} \ lewo (\ mathbf {a} ^ {T} [\ mathbf {W} \ mathbf {h} _ { u}\Vert \mathbf {W} \mathbf {h} _{v}\Vert \mathbf {e} _{uv}]\right)}}{\sum _{z\in N_{u}}\exp ({\text{LeakyReLU}}\left(\mathbf {a} ^{T}[\mathbf {W} \mathbf {h} _{u}\Vert \mathbf {W} \mathbf {h} _{z }\Vert \mathbf {e} _{uz}]\right))}}}$

gdzie $oznacza$ wektorem możliwych do nauczenia wag, transpozycję , a ${\ tekst {LeakyReLU}}}$${\ Displaystyle$ jest zmodyfikowanym ReLU za {\ Displaystyle \ mathbf { funkcja aktywacji. Współczynniki uwagi są znormalizowane, aby można je było łatwo porównać w różnych węzłach.

GCN można postrzegać jako szczególny przypadek GAT, w którym współczynników uwagi nie można się nauczyć, ale są ustalone i równe wagom krawędzi. ${\ displaystyle w_ {uv}}$ .

Bramkowana sieć neuronowa sekwencji grafów

Bramkowana sieć neuronowa sekwencji grafów (GGS-NN) została wprowadzona przez Yujię Li i in. w 2015 r. GGS-NN rozszerza sformułowanie GNN autorstwa Scarselli i in. do sekwencji wyjściowych. Struktura przekazywania komunikatów jest implementowana jako reguła aktualizacji do bramkowanej jednostki rekurencyjnej ).

GGS-NN można wyrazić w następujący sposób:

${\ Displaystyle \ mathbf {h} _ {u} ^ {(0)} = \ mathbf {x} _ {u} \, \ Vert \, \ mathbf {0}}$

${\ Displaystyle \ mathbf {m} _ {u} ^ {(l + 1)} = \ suma _ {v \ w N_ {u}} \ mathbf { \Theta } \mathbf {h} _{v}}$

${\ Displaystyle \ mathbf {h} _ {u} ^ {(l + 1)} = {\ tekst {GRU}} (\ mathbf {m} _ {u} ^ { (l+1)},\mathbf {h} _{u}^{(l)})}$

gdzie ${\ Displaystyle \ Vert}$$Displaystyle$ konkatenację wektorów , {\ $\ mathbf {0}}$ jest wektorem zer, jest macierzą możliwych do nauczenia parametrów, ${\ Displaystyle { \text{GRU}}}$ to komórka GRU, a $.$ indeks sekwencji W GGS-NN reprezentacje węzłów są uważane za ukryte stany komórki GRU. Początkowy węzeł zawiera ${\ displaystyle \ mathbf {x} _ {u} ^ {(0)}}$ są wypełnione zerami aż do wymiaru stanu ukrytego komórki GRU. Ta sama komórka GRU jest używana do aktualizacji reprezentacji dla każdego węzła.

Lokalne warstwy puli

Lokalne warstwy łączenia zgrubiają wykres poprzez próbkowanie w dół. Przedstawiamy tutaj kilka możliwych do nauczenia się lokalnych strategii łączenia, które zostały zaproponowane. $wykres$ reprezentowany przez macierz $cech węzłów$ i macierz sąsiedztwa . Dane $cech$ to nowa macierz $węzłów$ i nowa macierz

Łączenie najlepszych k

Najpierw ustawiliśmy

${\ Displaystyle \ mathbf {y} = {\ Frac {\ mathbf {X} \ mathbf {p}} {\ Vert \ mathbf {p} \ Vert}}}$

gdzie jest $którego można się nauczyć$ projekcji, . $oblicza$ projekcji skalarną wartość projekcji dla każdego węzła wykresu.

Warstwę puli górnych k można następnie sformalizować w następujący sposób:

${\ Displaystyle \ mathbf {X} '= (\ mathbf {X} \ dot {\ tekst {sigmoid}} (\ mathbf {y}}) _ {\ mathbf { ja} }}$

${\ Displaystyle \ mathbf {A} '= \ mathbf {A} _ {\ mathbf {i} \ mathbf {i}}}$

gdzie ${\ Displaystyle \ mathbf {i} = {\ tekst {góra}} _ {k} (\ mathbf {y})}$ to podzbiór węzłów z k najwyższymi wynikami projekcji, ${\ Displaystyle \ dot} oznacza$ mnożenie macierzy po elementach , a ${\ Displaystyle {\ tekst {sigmoid}} (\ cdot)}$ jest funkcją sigmoidalną . Innymi słowy, węzły z najwyższymi k najwyższymi wynikami projekcji są zachowywane w nowej macierzy sąsiedztwa ${\ Displaystyle \ mathbf {A} '}$ . Operacja sigmoidy $, że$ projekcji $trenować$ przez wsteczną , w przeciwnym razie dawałaby dyskretne wyniki

Łączenie samouwagi

Najpierw ustawiliśmy

${\ Displaystyle \ mathbf {y} = {\ tekst {GNN}} (\ mathbf {X}, \ mathbf {A})}$

gdzie $jest$ równowariantną warstwą GNN ogólnej permutacji (np. GCN, GAT, MPNN).

Warstwa łączenia samouwagi może zostać sformalizowana w następujący sposób:

${\ Displaystyle \ mathbf {X} '= (\ mathbf {X} \ odot \ mathbf {y}) _ {\ mathbf {i}}}$

${ \ Displaystyle \ mathbf {A} '= \ mathbf {A} _ {\ mathbf {i} \ mathbf {i}}}$

gdzie ${\ Displaystyle \ mathbf {i} = {\ tekst {góra}} _ {k} (\ mathbf {y})}$ to podzbiór węzłów z k najwyższymi wynikami projekcji, ${\ Displaystyle \ dot} oznacza$ mnożenie macierzy po elementach .

Warstwa puli samouwagi może być postrzegana jako rozszerzenie warstwy puli górnych k. W odróżnieniu od łączenia najlepszych k, wyniki samouwagi obliczone w łączeniu samouwagi uwzględniają zarówno cechy grafu, jak i topologię grafu.

Aplikacje

Fałdowanie białek

Zobacz też: AlphaFold

Grafowe sieci neuronowe są jednym z głównych elementów składowych AlphaFold , programu sztucznej inteligencji opracowanego przez firmę Google DeepMind w celu rozwiązania problemu fałdowania białek w biologii . AlphaFold zajął pierwsze miejsce w kilku CASP .

Portale społecznościowe

Zobacz też: System rekomendacji

Sieci społecznościowe są główną domeną zastosowań sieci GNN ze względu na ich naturalną reprezentację w postaci wykresów społecznościowych . GNN są wykorzystywane do opracowywania systemów rekomendacji opartych zarówno na relacjach społecznych , jak i relacjach pozycji.

Optymalizacja kombinatoryczna

Zobacz też: Optymalizacja kombinatoryczna

Sieci GNN są wykorzystywane jako podstawowe elementy składowe kilku algorytmów optymalizacji kombinatorycznej. Przykłady obejmują obliczanie najkrótszych ścieżek lub obwodów Eulera dla danego grafu, wyznaczanie rozmieszczenia układów scalonych lepszych lub konkurencyjnych w stosunku do rozwiązań stworzonych przez człowieka oraz ulepszanie reguł rozgałęzień zaprojektowanych przez ekspertów w gałęziach i wiązaniach .

Bezpieczeństwo cybernetyczne

Zobacz też: System wykrywania włamań

Sieć komputerów widziana jako wykres może być analizowana za pomocą GNN w celu wykrycia anomalii. Anomalie na wykresach pochodzenia często korelują ze złośliwą aktywnością w sieci. GNN zostały wykorzystane do identyfikacji tych anomalii w poszczególnych węzłach i na ścieżkach w celu wykrycia złośliwych procesów lub na poziomie krawędzi w celu wykrycia ruchu bocznego .

link zewnętrzny

https://distill.pub/2021/gnn-intro/