Sieć neuronowa grafowa — GCN / GAT / GraphSAGE
- Rok
- 2017–2018 (major variants)
- Typ
- Deep learning on graph-structured data
Ten tekst jest tłumaczeniem maszynowym i nie został jeszcze sprawdzony. Przeczytaj oryginał po angielsku
Do czego służy?
Sieć neuronowa grafowa (GNN) to architektura głębokiego uczenia, która działa bezpośrednio na danych o strukturze grafu, łącząc cechy węzłów z informacjami strukturalnymi poprzez iteracyjne przekazywanie komunikatów między sąsiadami.
Trzy kanoniczne warianty — sieć konwolucyjna grafowa (GCN) wprowadzona przez Kipfa i Wellinga w 2017 r., sieć uwagowa grafowa (GAT) wprowadzona przez Veličkovića i wsp. w 2018 r. oraz GraphSAGE — różnią się sposobem agregacji informacji od sąsiadów: GCN stosuje splot spektralny na pełnej macierzy sąsiedztwa, GAT przypisuje wagi sąsiadom na podstawie nauczonych współczynników uwagi, a GraphSAGE próbkuje i agreguje lokalne sąsiedztwa indukcyjnie, umożliwiając generalizację na nieznane węzły.
Intuicja stojąca za metodą
Wyobraź sobie każdy węzeł w grafie jako osobę w sieci społecznościowej. Ta osoba ma swój własny profil (cechy), ale to, kogo zna, również wiele o niej mówi. GNN pozwala każdemu węzłowi wielokrotnie zbierać komunikaty od swoich sąsiadów, mieszać te komunikaty z własnymi informacjami i aktualizować swoją reprezentację — warstwa po warstwie. Po kilku rundach tej wymiany w stylu plotek, osadzenie każdego węzła odzwierciedla nie tylko jego samego, ale także lokalny podgraf wokół niego. GCN robi to za pomocą ustalonej symetrycznej średniej sąsiadów; GAT decyduje, którym sąsiadom bardziej ufać, ucząc się wag uwagi; GraphSAGE pobiera próbkę ustalonego podzbioru sąsiadów i uczy się funkcji agregacji, którą można zastosować do węzłów, których nigdy wcześniej nie widział.
Historia
Podstawy zastosowania sieci neuronowych do grafów zostały położone przez Scarselli i wsp. (2009), ale współczesna era GNN rozpoczęła się od sieci konwolucyjnej grafowej (2017) Kipfa i Wellinga, która uprościła spektralny splot grafowy do wydajnej aproksymacji pierwszego rzędu przy użyciu mnożenia przez symetryczną znormalizowaną macierz sąsiedztwa. Rok później Veličković i wsp. (2018) wprowadzili sieci uwagowe grafowe, zastępując stałe uśrednianie GCN uczonymi współczynnikami uwagi na każdej krawędzi — pozwalając modelowi selektywnie ważyć sąsiadów. Równocześnie Hamilton i wsp. (2017) zaproponowali GraphSAGE, indukcyjny framework, który pobiera próbki sąsiedztwa o ustalonej wielkości i uczy funkcje agregacji przenoszalne na nieznane węzły, czyniąc GNN praktycznymi dla dużych i dynamicznych grafów. Te trzy prace ustanowiły paradygmat przekazywania komunikatów, który obecnie stanowi podstawę większości badań nad GNN.
Kiedy stosować
Użyj GNN, gdy Twoje dane mają naturalnie strukturę grafu — sieci społecznościowe, sieci cytowań, grafy molekularne, grafy wiedzy lub każde ustawienie, w którym relacje między encjami niosą sygnał predykcyjny. Potrzebujesz macierzy cech węzłów i listy krawędzi. Do znaczącego treningu wymagane jest minimum około 50 węzłów. GNN mają zastosowanie do klasyfikacji węzłów (przewidywania etykiety dla każdego węzła), predykcji krawędzi (wnioskowania o brakujących krawędziach) i klasyfikacji grafów (przypisywania etykiety całemu grafowi). Założenie homofilowości — połączone węzły mają tendencję do dzielenia tej samej etykiety — jest niejawnie wykorzystywane przez GCN i standardowe GAT; jeśli Twój graf jest heterofilowy, rozważ architektury zaprojektowane dla tego ustawienia. W przypadku dużych grafów trening w pełnej partii jest niemożliwy ze względu na pamięć i potrzebne jest próbkowanie sąsiedztwa w mini-partiach (w stylu GraphSAGE). Jeśli Twój graf ma mniej niż 20 węzłów, tradycyjne metryki centralności są bardziej odpowiednim wyborem.
Ograniczenia i uwagi
- Nadmierne wygładzanie: stosowanie wielu warstw GNN powoduje, że wszystkie osadzenia węzłów zbiegają się do wspólnej wartości, ograniczając efektywną głębokość do około 2–4 warstw w praktyce.
- Skalowalność: pełne przetwarzanie GCN i GAT wymaga przechowywania całej macierzy sąsiedztwa i macierzy cech w pamięci, co jest niewykonalne dla bardzo dużych grafów bez próbkowania lub partycjonowania.
- Założenie homofilowości wpisane w standardową agregację pogarsza wydajność na grafach heterofilowych, gdzie sąsiedzi mają tendencję do posiadania różnych etykiet.
- Minimalny rozmiar próbki wynoszący ~50 węzłów jest wymagany; mniejsza liczba węzłów pozostawia modelowi niewystarczający sygnał do nauczenia się znaczących reprezentacji.
Warunki podane w źródle nie zastępują niezależnego przeglądu naukowego ani walidacji przez silnik analityczny.
Mocne strony
- Wspólne wykorzystanie zarówno cech węzłów, jak i topologii grafu, przewyższając metody wykorzystujące tylko jedną z nich.
- Mechanizm uwagi GAT zapewnia indywidualne wyniki ważności dla każdej krawędzi, dodając interpretowalność do agregacji.
- GraphSAGE jest indukcyjny i może generalizować na węzły i grafy nieznane podczas treningu, umożliwiając wdrożenie w rosnących sieciach.
- Ujednolicony framework przekazywania komunikatów obejmuje klasyfikację węzłów, predykcję krawędzi i klasyfikację grafów z tym samym szkieletem architektonicznym.
Zastosowania
- Klasyfikacja węzłów w sieciach cytowań — przewidywanie tematu artykułu na podstawie jego treści i linków cytowań.
- Odkrywanie leków — przewidywanie właściwości molekularnych poprzez traktowanie atomów jako węzłów, a wiązań chemicznych jako krawędzi.
- Systemy rekomendacyjne — modelowanie użytkowników i przedmiotów jako grafu dwudzielnego i przewidywanie interakcji użytkownik-przedmiot poprzez predykcję krawędzi.
- Wykrywanie oszustw w sieciach transakcji finansowych — identyfikacja anomalnych węzłów na podstawie ich cech i struktury sąsiedztwa.
- Uzupełnianie grafu wiedzy — wnioskowanie o brakujących relacjach między encjami w bazach wiedzy na dużą skalę.
Jak to działa
Jak to działa
Graf jest zdefiniowany przez macierz cech węzłów X (jeden wiersz na węzeł, jedna kolumna na atrybut) i listę krawędzi (lub macierz sąsiedztwa) A. Niekierowane krawędzie są standardem dla GCN i GAT; GraphSAGE obsługuje również grafy skierowane. Pętle własne są zazwyczaj dodawane do A, aby każdy węzeł był uwzględniony we własnej agregacji.
Surowe atrybuty węzłów są normalizowane i, jeśli to konieczne, osadzane w ciągłej przestrzeni wektorowej. Atrybuty krawędzi, jeśli są obecne, mogą być uwzględnione jako dodatkowe sygnały. Wynikiem jest gęsta macierz cech, którą będzie transformować każda warstwa GNN.
Każda warstwa GNN oblicza nową reprezentację węzła poprzez agregację cech sąsiadów węzła i łączenie ich z własnymi cechami węzła za pomocą uczonej macierzy wag i nieliniowej funkcji aktywacji. GCN stosuje mnożenie przez znormalizowaną macierz sąsiedztwa (splot spektralny); GAT oblicza współczynniki uwagi softmax dla każdej krawędzi, dzięki czemu wpływowi sąsiedzi wnoszą większy wkład; GraphSAGE losowo pobiera próbkę sąsiedztwa o ustalonej wielkości i stosuje różniczkowalny agregator (średnia, LSTM lub pooling). Stosowanie L warstw pozwala informacjom przepływać na odległość L przeskoków, ale stosowanie zbyt wielu warstw powoduje nadmierne wygładzanie, gdzie wszystkie osadzenia węzłów zbiegają się do tej samej wartości.
Końcowe osadzenia węzłów są przekazywane do głowicy specyficznej dla zadania. W przypadku klasyfikacji węzłów warstwa softmax przypisuje prawdopodobieństwa klas każdemu węzłowi. W przypadku predykcji krawędzi iloczyn skalarny lub MLP ocenia prawdopodobieństwo krawędzi między dwoma osadzeniami węzłów. W przypadku klasyfikacji grafów globalny pooling (suma, średnia lub hierarchiczny) agreguje wszystkie osadzenia węzłów w jeden wektor na poziomie grafu przed warstwą klasyfikacyjną.
Wydajność modelu jest mierzona na wydzielonym zbiorze testowym przy użyciu metryk odpowiednich dla zadania: dokładność lub F1 dla klasyfikacji węzłów i grafów, AUC-ROC dla predykcji krawędzi. Ponieważ zbiory danych grafowych często mają ograniczony rozmiar, ocena transdukcyjna (maski treningowe/walidacyjne/testowe na tym samym grafie) lub podziały indukcyjne (rozłączne podgrafy) powinny odpowiadać scenariuszowi wdrożenia.
Częste pułapki
- Dodanie zbyt wielu warstw GNN powoduje nadmierne wygładzanie: wszystkie osadzenia węzłów zbiegają się, a model traci moc dyskryminacyjną. Zachowaj liczbę warstw na poziomie 2–4 i monitoruj wariancję osadzeń.
- Trening na pełnym grafie bez mini-partii jest niemożliwy ze względu na pamięć dla dużych sieci; użyj próbkowania sąsiedztwa w stylu GraphSAGE lub partycjonowania grafu dla grafów z więcej niż kilkoma tysiącami węzłów.
- Bezpośrednie zastosowanie GCN wytrenowanego transdukcyjnie do nowych, nieznanych węzłów w czasie wnioskowania jest nieprawidłowe; użyj metody indukcyjnej, takiej jak GraphSAGE, jeśli Twoje wdrożenie wymaga generalizacji na nowe węzły.
- Ignorowanie założenia homofilowości na grafach heterofilowych daje słabe wyniki; sprawdź współczynnik asortatywności grafu przed wyborem standardowego wariantu GNN.
- Przy mniej niż 20 węzłach trening GNN daje zawodne reprezentacje; preferuj konwencjonalną analizę centralności sieci w tym reżimie.
Najczęściej zadawane pytania
Który wariant GNN powinienem zacząć — GCN, GAT, czy GraphSAGE?
GCN jest najprostszym punktem odniesienia i dobrze działa na małych i średnich grafach homofilowych, gdzie wszystkie węzły są znane w czasie treningu. GAT jest preferowany, gdy ważność sąsiadów się różni i chcesz mieć interpretowalne wagi uwagi. GraphSAGE jest właściwym wyborem, gdy potrzebujesz generalizacji na węzły nieznane podczas treningu lub gdy graf jest zbyt duży do przetwarzania w pełnej partii.
Czym jest nadmierne wygładzanie i jak go uniknąć?
Nadmierne wygładzanie występuje, gdy wiele warstw GNN powoduje zbieganie się wszystkich osadzeń węzłów do tej samej wartości, eliminując informacje dyskryminacyjne. W praktyce 2–4 warstwy są zazwyczaj optymalne. Techniki takie jak połączenia rezydualne, sieci typu „jumping knowledge” i DropEdge mogą pomóc, jeśli potrzebne są głębsze architektury.
Czy GNN wymagają oznakowanych danych dla wszystkich węzłów?
Nie. GCN i GAT są powszechnie stosowane w ustawieniach półnadzorowanych, gdzie tylko niewielka część węzłów posiada etykiety; struktura grafu propaguje informacje od oznakowanych do nieoznakowanych węzłów. GraphSAGE może być również trenowany w sposób w pełni nadzorowany lub nienadzorowany, w zależności od zadania.
Jak duży musi być graf?
Do znaczącego treningu GNN potrzebne jest minimum około 50 węzłów. Przy mniej niż 20 węzłach model nie może nauczyć się wiarygodnych reprezentacji, a bardziej odpowiednia jest tradycyjna analiza oparta na centralności. W przypadku grafów z milionami węzłów wymagane jest próbkowanie sąsiedztwa w mini-partiach (jak w GraphSAGE) lub metody partycjonowania grafu, aby utrzymać użycie pamięci w ryzach.
Pokrewne metody
Źródła
Kipf, T.N. & Welling, M. (2017). Semi-Supervised Classification with Graph Convolutional Networks. International Conference on Learning Representations (ICLR).
Otwórz odnośnik DOISkopiowano.Veličković, P., Cucurull, G., Casanova, A., Romero, A., Liò, P., & Bengio, Y. (2018). Graph Attention Networks. International Conference on Learning Representations (ICLR).
Otwórz odnośnik DOISkopiowano.Hamilton, W.L. (2020). Graph Representation Learning. Morgan & Claypool.
Otwórz odnośnik DOISkopiowano.