Co to jest osadzanie wykresów?

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

Przestrzenie wektorowe są bardziej podatne na naukę o 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 dziedzin. Ponadto operacje na wektorach są często prostsze i szybsze niż równoważne operacje na wykresach.

Jednym z przykładów jest znajdowanie najbliższych sąsiadów. Na wykresie można wykonywać „przeskoki” z węzła do innego węzła. Na wielu rzeczywistych wykresach po kilku przeskokach jest niewiele znaczących informacji (np. Rekomendacje od znajomych lub znajomych znajomych). Jednak w przestrzeniach wektorowych można użyć metryk odległości, aby uzyskać wyniki ilościowe (np. Odległość euklidesowa lub podobieństwo cosinusowe). Jeśli masz ilościowe metryki 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 zawiera bardziej szczegółowe informacje.

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

• Osadzenia wierzchołków – tutaj znajdziesz utajoną reprezentację wektorową każdy wierzchołek na danym wykresie. Następnie możesz porównać różne wierzchołki, wykreślając te wektory w przestrzeni i, co ciekawe, „podobne” wierzchołki są wykreślane bliżej siebie niż te, które są odmienne lub mniej powiązane. To jest ta sama praca, którą wykonuje Perozzi w „DeepWalk”.
• Osadzenia wykresów – Tutaj znajdziesz utajoną reprezentację wektorową 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 typów związków jest w grupie (klastry) itp. Możesz użyć tych wektorów i wykreślić je w przestrzeni i znajdź wszystkie powyższe informacje. To jest praca wykonana w „Deep Graph Kernels” przez Yanardag.

Aplikacje – Patrząc uważnie, osadzenia są „utajonymi” reprezentacjami, co oznacza, że wykres ma | V | * | V | macierz sąsiedztwa, gdzie | V | = 1M, trudno jest użyć lub przetworzyć 1M * 1M liczb w algorytmie. Zatem ukryte osadzenie wymiaru „d”, gdzie d < < | V |, utworzy macierz sąsiedztwa | V | * di stosunkowo łatwiejsze w użyciu. Inną aplikacją może być – Rozważmy prosty scenariusz, w którym chcemy polecać produkty osobom, które mają podobne zainteresowania w sieci społecznościowej.Uzyskując osadzenia wierzchołków (tutaj oznacza to reprezentację wektorową każdej osoby), możemy znaleźć podobne, wykreślając te wektory, co ułatwia rekomendacje. Oto niektóre aplikacje i są inne. Możesz odnieść się do fajnej ankiety – Techniki osadzania wykresów, ankieta .

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

• Prace oparte na „Vertex Embeddings”: – DeepWalk , Node2Vec , LINE .

• Działa w oparciu o „Osadzenia wykresów”: – Jądra głębokiego grafu , Subgraph2Vec .

Komentarze

• Wowww !! To absolutnie doskonała odpowiedź. Wielkie dzięki 🙂 Bardzo dobrze zrobione 🙂
• Cześć Mausam Jain. Czy możesz mi dać znać, czy mogę użyć osadzania wykresów do identyfikacji ważnych węzłów w sieci?
• Cześć, Volka. Aby odpowiedzieć na to pytanie, muszę wiedzieć, nad jakim typem wykresu pracujesz; czy to twitter, facebook, reddit czy coś innego?
• Dziękuję za odpowiedź. Aktualnie pracuję w sieci społecznościowej, w której chcę zidentyfikować najbardziej towarzyskie osoby 🙂
• Tutaj ' jest bardziej rozbudowaną wersją tej odpowiedzi. directiondatascience.com/…

W artykule Centralne twierdzenie graniczne dla omnibusowego osadzania losowych wykresów iloczynu skalarnego autorstwa Levina i in. artykuł, szczególny typ osadzania wykresów (osadzanie Omnibus) definiuje osadzanie wykresów jako metodologię, „w której wierzchołki grafu są odwzorowywane na wektory w niskowymiarowej przestrzeni euklidesowej”. Sprawdź link, aby uzyskać więcej informacji.

Komentarze

• witamy na forum. Jeśli chcesz wspomnieć o pracy, zapisz jej nazwę również jako część tekstu (ponieważ linki mogą być uszkodzone).