Co to jest osadzanie wykresów?

Ostatnio natknąłem się na osadzanie wykresów, takie jak DeepWalk i LINE. Jednak nadal nie mam jasnego pojęcia, co oznacza osadzanie wykresów i kiedy go używać (aplikacje)? Wszelkie sugestie są mile widziane!

Osadzanie wykresów uczy się mapowania z sieci do przestrzeni wektorowej, zachowując przy tym odpowiednie właściwości sieci.

Przestrzenie wektorowe są bardziej podatne na analizę danych niż wykresy. Wykresy zawierają krawędzie i węzły, te relacje sieciowe mogą wykorzystywać tylko określony podzbiór matematyki, statystyki i uczenia maszynowego. Przestrzenie wektorowe mają bogatszy zestaw narzędzi z tych domen. Ponadto operacje wektorowe są często prostsze i szybsze niż równoważne operacje graficzne.

Jednym z przykładów jest znalezienie najbliższych sąsiadów. Możesz wykonać „przeskok” z węzła do innego węzła na wykresie. Na wielu rzeczywistych wykresach po kilku przeskokach niewiele jest istotnych informacji (np. Rekomendacje znajomych znajomych). Jednak w przestrzeniach wektorowych można użyć wskaźników odległości, aby uzyskać wyniki ilościowe (np. Odległość euklidesowa lub podobieństwo kosinusu). Jeśli masz ilościowe miary odległości w znaczącej przestrzeni wektorowej, znalezienie najbliższych sąsiadów jest proste.

„ Techniki osadzania wykresów, aplikacje i wydajność: ankieta ” to artykuł przeglądowy, który jest bardziej szczegółowy.

Co to są osadzenia wykresów? „Osadzanie wykresów” to dziś gorący obszar w uczeniu maszynowym. Zasadniczo oznacza to znalezienie „utajonej reprezentacji wektorowej” wykresów, która uchwyci topologię (w bardzo podstawowym znaczeniu) wykresu. Możemy wzbogacić tę „reprezentację wektorową”, biorąc również pod uwagę relacje wierzchołek-wierzchołek, informacje o krawędziach itp. Istnieją mniej więcej dwa poziomy osadzania na wykresie (oczywiście możemy w dowolnym momencie zdefiniować więcej poziomów, logicznie dzieląc cały wykres na podgrupy o różnych rozmiarach):

• Osadzanie wierzchołków - tutaj znajdziesz utajoną reprezentację wektorową każdego wierzchołka na danym wykresie. Następnie możesz porównać różne wierzchołki, wykreślając te wektory w przestrzeni, a co ciekawe „podobne” wierzchołki są narysowane bliżej siebie niż te, które są odmienne lub mniej powiązane. To ta sama praca, którą wykonuje Perozzi w „DeepWalk”.
• Osadzanie wykresów - tutaj znajdziesz utajoną reprezentację wektora całego wykresu. Na przykład masz grupę związków chemicznych, dla których chcesz sprawdzić, które związki są do siebie podobne, ile rodzajów związków jest w grupie (klastry) itp. Możesz użyć tych wektorów i narysować je w przestrzeni i znajdź wszystkie powyższe informacje. To jest praca, którą wykonuje Yanardag w „Deep Graph Kernels”.

Aplikacje - Przyglądając się uważnie, osadzanie to „utajone” przedstawienie, co oznacza, że ​​wykres ma | V | * | V | macierz przylegania gdzie | V | = 1 mln, trudno jest użyć lub przetworzyć 1 mln * 1 mln liczb w algorytmie. Zatem utajone osadzenie wymiaru „d”, gdzie d << | V |, utworzyłoby macierz przyległości | V | * d i stosunkowo łatwiejszy w użyciu. Inna aplikacja może być - Rozważmy prosty scenariusz, w którym chcemy polecać produkty osobom o podobnych zainteresowaniach w sieci społecznościowej. Pobierając osadzenia wierzchołków (tutaj oznacza reprezentację wektorową każdej osoby), możemy znaleźć podobne, wykreślając te wektory, co ułatwia rekomendację. To są niektóre aplikacje i są inne. Możesz odnieść się do ładnego artykułu z ankiety - Graph Embedding Techniques, ankieta .

Skąd to wszystko się wzięło? Było wiele prac w tej dziedzinie i prawie wszystkie pochodzą z przełomowych badań w dziedzinie przetwarzania języka naturalnego - „Word2Vec” autorstwa Mikołaja. Jeśli chcesz rozpocząć badania nad osadzaniem grafów, polecam najpierw zrozumieć, jak działa Word2Vec. Można znaleźć ładne wyjaśnienia - wyjaśnienie uczenia się parametrów Word2Vec i wykład Stanforda . Następnie możesz przejść do wymienionych dokumentów. Prace te można podzielić na następujące kategorie:

• Działa w oparciu o „Osadzanie wierzchołków”: - DeepWalk , Node2Vec , LINE .

• Działa w oparciu o „Graph Embeddings”: - Deep Graph Kernels , Subgraph2Vec .

W artykule Centralne twierdzenie graniczne na omnibus osadzanie wykresów iloczynu losowego przez Levina i in. papier, określony typ osadzania wykresów (osadzanie Omnibus) definiuje osadzanie wykresów jako metodologię „, w której wierzchołki wykresu są odwzorowywane na wektory w mało wymiarowej przestrzeni euklidesowej”. Sprawdź link, aby uzyskać więcej informacji.