Przejdź do treści
Wróć do wyników wyszukiwania

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

Rozmiar czcionki

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

1

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.

2

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.

3

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.

4

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ą.

5

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

  1. Kipf, T.N. & Welling, M. (2017). Semi-Supervised Classification with Graph Convolutional Networks. International Conference on Learning Representations (ICLR).

    Otwórz odnośnik DOI
    Skopiowano.
  2. 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 DOI
    Skopiowano.
  3. Hamilton, W.L. (2020). Graph Representation Learning. Morgan & Claypool.

    Otwórz odnośnik DOI
    Skopiowano.