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

Osadzanie sieci — Node2Vec, DeepWalk, LINE

Rok
2014 (DeepWalk); 2016 (Node2Vec)
Typ
Representation learning / unsupervised network method

Ten tekst jest tłumaczeniem maszynowym i nie został jeszcze sprawdzony. Przeczytaj oryginał po angielsku

Rozmiar czcionki

Do czego służy?

Osadzanie sieci (network embedding) to rodzina metod uczenia reprezentacji, które mapują każdy węzeł grafu do gęstego, niskowymiarowego wektora, zachowując przy tym właściwości strukturalne sieci.

Podejście to zostało sformalizowane dla danych z sieci społecznościowych przez Perozzi, Al-Rfou i Skiena w pracy DeepWalk (2014), która zaadaptowała model skip-gram z Word2Vec do losowych spacerów po grafach, a następnie rozszerzone przez Grovera i Leskovca w Node2Vec (2016), który wprowadził ważony losowy spacer równoważący eksplorację wszerz i w głąb. Te osadzenia przekształcają dane relacyjne w wektory cech, które standardowe klasyfikatory uczenia maszynowego i algorytmy klasteryzacji mogą bezpośrednio przetwarzać.

Intuicja stojąca za metodą

Graf składa się z węzłów i krawędzi, ale większość algorytmów uczenia maszynowego oczekuje tabeli liczb. Osadzanie sieci rozwiązuje problem tłumaczenia. Tak jak Word2Vec uczy się znaczeń słów, analizując, które słowa pojawiają się blisko siebie w zdaniach, DeepWalk uczy się znaczeń węzłów, analizując, które węzły pojawiają się blisko siebie w losowych spacerach po grafie. Wynikiem jest współrzędna w przestrzeni wektorowej — węzły, które są strukturalnie podobne lub często odwiedzane razem, znajdują się blisko siebie. Gdy każdy węzeł ma swój wektor, można go przekazać do klasyfikatora, sklastrować za pomocą k-średnich lub zwizualizować za pomocą UMAP, bez pisania żadnego kodu specyficznego dla grafów.

Historia

Pomysł zastosowania Word2Vec do danych o strukturze grafu został wprowadzony przez Perozzi, Al-Rfou i Skiena w DeepWalk (KDD 2014), który pokazał, że losowe spacery po grafie społecznym mogą zastąpić ręcznie tworzone cechy do klasyfikacji węzłów. Grover i Leskovec rozszerzyli to w Node2Vec (KDD 2016), wprowadzając drugorzędowy ważony losowy spacer parametryzowany przez p i q, zapewniając wyraźną kontrolę nad kompromisem między eksploracją sąsiedztwa opartą na homofilii a równoważnością strukturalną. Około tego samego okresu Tang i in. zaproponowali LINE (WWW 2015), który uczy osadzeń poprzez bezpośrednie optymalizowanie celów bliskości pierwszego i drugiego rzędu, zamiast poprzez losowe spacery, co czyni go odpowiednim dla bardzo dużych grafów. Te trzy metody wspólnie ustanowiły dziedzinę uczenia reprezentacji grafów i zainspirowały kolejne architektury grafowych sieci neuronowych.

Kiedy stosować

Osadzanie sieci jest odpowiednie, gdy dysponujesz grafem o co najmniej 50 węzłach i potrzebujesz ciągłych cech wektorowych do zadań niższego poziomu, takich jak klasyfikacja węzłów, predykcja krawędzi lub klastrowanie węzłów. Metoda nadaje się zarówno do grafów nieważonych, jak i ważonych, oraz obsługuje struktury skierowane lub nieskierowane. Wybierz DeepWalk, gdy wystarczy prosty, jednolity punkt odniesienia oparty na losowych spacerach. Wybierz Node2Vec, gdy chcesz dostroić równowagę między homofilią a równoważnością strukturalną za pomocą parametrów p i q. Jeśli potrzebujesz osadzić nowe, wcześniej niewidziane węzły w czasie wnioskowania bez ponownego treningu, preferuj metodę indukcyjną, taką jak GraphSAGE; osadzanie sieci w standardowej formie jest transdukcyjne. Metoda nie wymaga atrybutów węzłów o rozkładzie normalnym.

Ograniczenia i uwagi

  • Transdukcyjne: model nie może osadzać węzłów, które nie były obecne podczas treningu, bez pełnego ponownego treningu.
  • Wrażliwość na hiperparametry: wymiar osadzenia, długość spaceru, liczba spacerów, rozmiar okna, p i q — wszystkie wpływają na jakość osadzenia i wymagają dostrojenia.
  • Losowe spacery nie wychwytują struktury grafu wyższego rzędu (np. hiperkrawędzi lub krawędzi wielokrotnych relacji) bez rozszerzeń.
  • Wydajność spada na bardzo małych grafach (poniżej 50 węzłów), gdzie korpus spacerów jest zbyt rzadki, aby nauczyć się wiarygodnych statystyk.

Warunki podane w źródle nie zastępują niezależnego przeglądu naukowego ani walidacji przez silnik analityczny.

Mocne strony

  • Konwertuje relacyjne dane grafowe na wektory o stałej długości, kompatybilne z każdym standardowym potokiem uczenia maszynowego.
  • Parametry p i q w Node2Vec pozwalają analitykowi dostroić równowagę między osadzeniami wrażliwymi na społeczność a osadzeniami wrażliwymi na rolę.
  • Wagi krawędzi mogą być włączone do prawdopodobieństw spaceru, wychwytując siłę relacji bez dodatkowych kroków modelowania.
  • Skaluje się do dużych grafów dzięki wydajnemu próbkowaniu losowych spacerów i procedurze treningowej skip-gram.

Zastosowania

  • Klasyfikacja węzłów w sieciach cytowań, platformach społecznościowych lub grafach interakcji biologicznych.
  • Predykcja krawędzi — identyfikacja brakujących lub przyszłych krawędzi poprzez porównanie podobieństwa osadzeń węzłów.
  • Detekcja społeczności poprzez klastrowanie wektorów węzłów za pomocą metod k-średnich lub hierarchicznych.
  • Detekcja anomalii — węzły, których osadzenia są wartościami odstającymi w przestrzeni wektorowej, mogą reprezentować nietypowe role strukturalne.
  • Systemy rekomendacyjne, w których użytkownicy i przedmioty są węzłami w dwudzielnym lub wielowarstwowym grafie interakcji.

Jak to działa

Jak to działa

1

Proces rozpoczyna się od grafu G, w którym węzły są bytami, a krawędzie reprezentują relacje. Krawędzie mogą być skierowane lub nieskierowane i mogą przenosić wagi, które później wpłyną na prawdopodobieństwo przejścia. Jeśli wagi krawędzi są obecne, są uwzględniane w prawdopodobieństwach spaceru; jeśli ich nie ma, wszystkie krawędzie otrzymują równe wagi. Na tym etapie analityk wybiera również wariant algorytmu — DeepWalk dla jednolitych losowych spacerów, Node2Vec dla ważonych spacerów kontrolowanych przez parametry p (powrót) i q (wewnątrz-zewnątrz), lub LINE, gdy bliskość pierwszego i drugiego rzędu ma być uczona oddzielnie. Wybór między reżimami parametrów Node2Vec jest kierowany oczekiwaną właściwością sieci: homofilią (podobne węzły łączą się, preferowana jest eksploracja wszerz, q < 1) lub równoważnością strukturalną (węzły o podobnych rolach mogą być odległe, preferowana jest eksploracja w głąb, p < 1).

2

Zaczynając od każdego węzła, algorytm symuluje serię losowych spacerów o ustalonej długości (zazwyczaj 30 kroków) i powtarza je wielokrotnie (zazwyczaj 200 spacerów na węzeł). Każdy spacer generuje sekwencję identyfikatorów węzłów analogiczną do zdania słów. W DeepWalk następny węzeł jest wybierany jednostajnie spośród sąsiadów. W Node2Vec następny węzeł jest wybierany zgodnie z prawdopodobieństwami przejścia ważonymi przez p i q: powrót do poprzedniego węzła jest penalizowany przez 1/p, pozostanie na tej samej odległości jest utrzymywane na 1, a oddalanie się jest kontrolowane przez 1/q. Zbiór wszystkich spacerów tworzy korpus sekwencji węzłów, który koduje topologię grafu.

3

Korpus sekwencji węzłów jest podawany do modelu skip-gram (tej samej architektury co Word2Vec). Dla każdego węzła w spacerze model przewiduje otaczające węzły kontekstowe w określonym oknie (zazwyczaj 10 kroków). Za pomocą stochastycznego spadku gradientu model uczy się gęstej reprezentacji wektorowej o ustalonej wymiarowości — zazwyczaj 64 lub 128 — dla każdego węzła, tak aby węzły współwystępujące w spacerach miały podobne wektory. Wymiarowość jest hiperparametrem: większe wymiary wychwytują więcej struktury, ale zwiększają obliczenia i ryzyko przeuczenia na małych grafach.

4

Po wytrenowaniu model dostarcza jeden wektor osadzenia na węzeł. Wektory te są używane jako cechy do klasyfikacji węzłów (podawane do klasyfikatora regresji logistycznej lub neuronowego), predykcji krawędzi (porównując wektory par kandydatów na węzły) lub detekcji społeczności (klastrując wektory). Osadzenia są transdukcyjne: są ustalone dla węzłów widzianych podczas treningu. Jeśli nowe węzły muszą być osadzone po treningu, należy zamiast tego użyć metody indukcyjnej, takiej jak GraphSAGE, ponieważ standardowy model Node2Vec lub DeepWalk nie może generalizować na niewidziane węzły bez ponownego treningu.

Częste pułapki

  • Zastosowanie modelu Node2Vec do nowych węzłów, które nie były w grafie treningowym — model nie będzie miał dla nich wektora; użyj metody indukcyjnej (np. GraphSAGE), gdy osadzanie transdukcyjne jest nieakceptowalne.
  • Używanie domyślnych p=1, q=1 (równoważne DeepWalk) bez analizy, czy sieć podąża za wzorcem homofilii, czy równoważności strukturalnej — dostrojenie p i q do oczekiwanego wzorca może znacznie poprawić wydajność zadania niższego poziomu.
  • Traktowanie wymiaru osadzenia jako stałej: na małych grafach wymiar 64 lub 128 może prowadzić do przeuczenia; zacznij od niższej wartości i waliduj na zadaniu niższego poziomu.
  • Ignorowanie minimalnego wymogu próbkowania: grafy z mniej niż 50 węzłami generują korpusy spacerów zbyt cienkie, aby wytrenować wiarygodne osadzenia.

Najczęściej zadawane pytania

Jaka jest różnica między DeepWalk, Node2Vec i LINE?

DeepWalk wykorzystuje jednorodne losowe spacery i model skip-gram Word2Vec — jest to najprostszy punkt odniesienia. Node2Vec dodaje ważone losowe spacery kontrolowane przez p i q, pozwalając analitykowi dostroić, czy spacer eksploruje jak przeszukiwanie wszerz (homofilia), czy w głąb (równoważność strukturalna). LINE w ogóle nie używa losowych spacerów; optymalizuje cele bliskości pierwszego i drugiego rzędu bezpośrednio na liście krawędzi, co jest bardziej skalowalne dla bardzo dużych grafów, ale poświęca sygnał sąsiedztwa oparty na spacerach.

Jak wybrać parametry p i q w Node2Vec?

p kontroluje prawdopodobieństwo powrotu do poprzedniego węzła (niskie p = mniej cofania), a q kontroluje promień eksploracji (q < 1 faworyzuje eksplorację na zewnątrz, q > 1 utrzymuje spacer blisko źródła). Jeśli oczekujesz, że węzły w tej samej społeczności będą podobne (homofilia), ustaw q < 1, aby spacer mógł się rozprzestrzeniać na zewnątrz. Jeśli oczekujesz, że węzły o tej samej roli strukturalnej będą podobne, nawet jeśli są odległe, ustaw p < 1, aby zachęcić do eksploracji w głąb. Waliduj oba reżimy na zadaniu niższego poziomu.

Czy mogę osadzać nowe węzły po treningu bez ponownego trenowania całego modelu?

Standardowe Node2Vec i DeepWalk są transdukcyjne: macierz osadzeń obejmuje tylko węzły widziane podczas treningu. Dla indukcyjnej generalizacji na nowe, wcześniej niewidziane węzły, użyj indukcyjnej metody grafowych sieci neuronowych, takiej jak GraphSAGE, która uczy funkcję agregacji na sąsiedztwach węzłów, którą można zastosować do dowolnego węzła w czasie wnioskowania.

Ile wymiarów powinienem użyć do osadzenia?

Najczęstsze wybory to 64 i 128, i działają one dobrze dla średnich i dużych grafów. Dla małych grafów (50–200 węzłów) zacznij od niższej wymiarowości (16 lub 32), aby uniknąć przeuczenia, i oceniaj jakość osadzenia, mierząc wydajność zadania niższego poziomu (np. dokładność klasyfikacji węzłów), a nie tylko błąd rekonstrukcji.

Pokrewne metody

Źródła

  1. Grover, A. & Leskovec, J. (2016). Node2Vec: Scalable Feature Learning for Networks. Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), 855-864.

    Otwórz odnośnik DOI
    Skopiowano.
  2. Perozzi, B., Al-Rfou, R., & Skiena, S. (2014). DeepWalk: Online Learning of Social Representations. Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), 701-710.

    Otwórz odnośnik DOI
    Skopiowano.