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 to osadzanie wykresów! Więc bierze wykres i zwraca osadzenia dla wykresu, krawędzi lub wierzchołków. Osadzenia umożliwiają wyszukiwanie podobieństwa i ogólnie ułatwiają uczenie maszynowe, zapewniając reprezentacje .
Emre,
@Emre, co to znaczy osadzanie? :)
Volka
1
Zgodnie z znaczeniem osadzania, naprawianie rzeczy na czymś. Osadzanie wykresów przypomina trochę mocowanie wierzchołków na powierzchni i rysowanie krawędzi, które reprezentują powiedzmy sieć. Przykład może być taki, że płaski wykres można osadzić na powierzchni bez przekraczania krawędzi. Ciężary mogą być przypisane do krawędzi i odpowiedniej długości krawędzi, a mianowicie. pomaga nam zrozumieć / oszacować, jak @Emre wspomniał o wyszukiwaniu podobieństw itp.2 D.
Kiritee Gak
@KiriteeGak Dzięki :) Jakie są ich aplikacje w prawdziwym świecie? Mówią, że można ich użyć do rekomendacji i tak dalej? ale jak?
Volka
1
Rekomendacje wideo w YouTube można przedstawić jako model, w którym aktualnie oglądany film to węzeł, na którym się znajdujesz, a następne filmy, które są w Twojej rekomendacji, są najbardziej podobne do ciebie na podstawie tego, co podobni użytkownicy obejrzeli w następnej kolejności i wielu więcej czynników, które jest ogromną siecią do przemierzania. Ten artykuł jest prostym, dobrym tekstem na temat zrozumienia zastosowania.
Kiritee Gak
Odpowiedzi:
19
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.
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:
Odpowiedzi:
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.
źródło
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):
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 .
źródło
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.
źródło