Was ist Grafikeinbettung?

12

Ich bin kürzlich auf das Einbetten von Graphen wie DeepWalk und LINE gestoßen. Ich habe jedoch immer noch keine klare Vorstellung davon, was unter Grafikeinbettungen zu verstehen ist und wann sie zu verwenden sind (Anwendungen). Anregungen sind willkommen!

Volka
quelle
1
Eine Grafikeinbettung ist eine Einbettung für Grafiken! Es wird also ein Diagramm erstellt und Einbettungen für das Diagramm, die Kanten oder Scheitelpunkte zurückgegeben. Einbettungen ermöglichen die Ähnlichkeitssuche und erleichtern im Allgemeinen das maschinelle Lernen, indem sie Darstellungen bereitstellen .
Emre
@Emre was bedeutet das einbetten? :)
Volka
1
Im Sinne der Einbettung geht es darum, Dinge auf etwas zu fixieren. Das Einbetten von Graphen ähnelt dem Fixieren von Scheitelpunkten auf einer Oberfläche und dem Zeichnen von Kanten, um beispielsweise ein Netzwerk darzustellen. So kann zum Beispiel ein planarer Graph auf einer Oberfläche eingebettet werden, ohne dass sich Kanten kreuzen. Kanten und entsprechenden Kantenlängen können Gewichte zugeordnet werden. hilft uns zu verstehen / schätzen, wie @Emre Ähnlichkeitssuche usw. erwähnt2D
Kiritee Gak
@KiriteeGak Danke :) Was sind ihre realen Anwendungen? Sie sagen, dass sie für die Empfehlung und alle verwendet werden können? aber wie?
Volka
1
Die Youtube-Videoempfehlung kann als Modell dargestellt werden, bei dem das gerade betrachtete Video der Knoten ist, auf dem Sie sich befinden, und die nächsten Videos, die in Ihrer Empfehlung enthalten sind, sind Ihnen am ähnlichsten, je nachdem, was ähnliche Nutzer als Nächstes und viele andere gesehen haben Weitere Faktoren sind natürlich ein riesiges Netzwerk, das es zu durchqueren gilt. Dieses Papier ist eine einfache gute Lektüre zum Verständnis der Anwendung.
Kiritee Gak

Antworten:

18

Durch das Einbetten von Diagrammen wird eine Zuordnung von einem Netzwerk zu einem Vektorraum unter Beibehaltung der relevanten Netzwerkeigenschaften erlernt.

Vektorräume sind für die Datenwissenschaft zugänglicher als Diagramme. Diagramme enthalten Kanten und Knoten. In diesen Netzwerkbeziehungen kann nur eine bestimmte Teilmenge von Mathematik, Statistik und maschinellem Lernen verwendet werden. Vektorräume verfügen über ein umfangreicheres Toolset aus diesen Domänen. Darüber hinaus sind Vektoroperationen oft einfacher und schneller als die entsprechenden Graphoperationen.

Ein Beispiel ist die Suche nach nächsten Nachbarn. Sie können in einem Diagramm "Sprünge" von einem Knoten zu einem anderen Knoten ausführen. In vielen realen Diagrammen gibt es nach ein paar Sprüngen wenig aussagekräftige Informationen (z. B. Empfehlungen von Freunden von Freunden von Freunden). In Vektorräumen können Sie jedoch Abstandsmetriken verwenden, um quantitative Ergebnisse zu erhalten (z. B. Euklidianabstand oder Kosinusähnlichkeit). Wenn Sie quantitative Abstandsmetriken in einem aussagekräftigen Vektorraum haben, ist es einfach, die nächsten Nachbarn zu finden.

" Graph Embedding-Techniken, -Anwendungen und -Leistung: Eine Umfrage " ist ein Übersichtsartikel, der ausführlicher behandelt wird.

Brian Spiering
quelle
24

Was sind Grafik-Einbettungen? "Graph Embeddings" ist heute ein heißer Bereich im maschinellen Lernen. Es bedeutet im Grunde, eine "latente Vektordarstellung" von Graphen zu finden, die die Topologie (im einfachsten Sinne) des Graphen erfasst. Wir können diese "Vektordarstellung" bereichern, indem wir auch die Vertex-Vertex-Beziehungen, Kanteninformationen usw. berücksichtigen. Das Diagramm enthält ungefähr zwei Einbettungsebenen (natürlich können wir jederzeit weitere Ebenen definieren, indem wir das gesamte Diagramm logisch aufteilen Subgraphen verschiedener Größen):

  • Vertex-Einbettungen - Hier finden Sie eine latente Vektordarstellung für jeden Vertex in der angegebenen Grafik. Sie können dann die verschiedenen Scheitelpunkte vergleichen, indem Sie diese Vektoren im Raum zeichnen. Interessanterweise werden "ähnliche" Scheitelpunkte näher aneinander gelegt als diejenigen, die unähnlich oder weniger verwandt sind. Dies ist die gleiche Arbeit, die in "DeepWalk" von Perozzi ausgeführt wird.
  • Grafikeinbettungen - Hier finden Sie die latente Vektordarstellung der gesamten Grafik. Sie haben beispielsweise eine Gruppe chemischer Verbindungen, für die Sie überprüfen möchten, welche Verbindungen einander ähnlich sind, wie viele Arten von Verbindungen sich in der Gruppe befinden (Cluster) usw. Sie können diese Vektoren verwenden und sie im Raum und aufzeichnen Hier finden Sie alle oben genannten Informationen. Dies ist die Arbeit, die Yanardag in "Deep Graph Kernels" leistet.

Anwendungen - Bei genauer Betrachtung handelt es sich bei Einbettungen um "latente" Darstellungen, dh wenn ein Graph ein | V | hat * | V | Adjazenzmatrix wobei | V | = 1M, es ist schwierig, 1M * 1M-Zahlen in einem Algorithmus zu verwenden oder zu verarbeiten. Eine latente Einbettung der Dimension 'd' mit d << | V | würde also die Adjazenzmatrix | V | ergeben * d und relativ einfach zu bedienen. Eine andere Anwendung könnte sein: - Stellen Sie sich ein einfaches Szenario vor, in dem wir den Personen, die ähnliche Interessen an einem sozialen Netzwerk haben, Produkte empfehlen möchten. Durch das Abrufen von Vertex-Einbettungen (hier bedeutet dies die Vektordarstellung jeder Person) können wir ähnliche finden, indem wir diese Vektoren zeichnen. Dies erleichtert die Empfehlung. Dies sind einige Anwendungen und es gibt andere. Sie können sich auf ein schönes Umfragepapier beziehen - Graph Embedding Techniques, eine Umfrage .

Woher kam das alles? Es gab viele Arbeiten in diesem Bereich und fast alle stammen aus der bahnbrechenden Forschung auf dem Gebiet der Verarbeitung natürlicher Sprache - "Word2Vec" von Mikolov. Wenn Sie mit der Untersuchung von Grafikeinbettungen beginnen möchten, empfehle ich, zunächst zu verstehen, wie Word2Vec funktioniert. Hier finden Sie nette Erklärungen - das Erlernen von Word2Vec-Parametern und Stanford Lecture . Dann können Sie zu den Papieren springen, die Sie aufgelistet haben. Diese Werke können kategorisiert werden als:

flyingDope
quelle
2
Wowww !! Dies ist absolut eine perfekte Antwort. Vielen Dank :) Sehr gut gemacht :)
Volka
Hallo Mausam Jain. Können Sie mir bitte mitteilen, ob ich mithilfe von Diagrammeinbettungen wichtige Knoten im Netzwerk identifizieren kann?
Volka
Hallo Volka. Um diese Frage zu beantworten, muss ich wissen, an welcher Art von Grafik Sie arbeiten. Ist es Twitter, Facebook, Reddit oder etwas anderes?
flyingDope
Danke für Ihre Antwort. Ich arbeite derzeit in einem sozialen Netzwerk, in dem ich die sozialsten Personen identifizieren möchte :)
Volka
0

In dem Aufsatz Ein zentraler Grenzwertsatz für eine Omnibus-Einbettung zufälliger Punktproduktgraphen von Levin et al. Papier, definiert eine bestimmte Art der Graph-Einbettung (die Omnibus-Einbettung) die Graph-Einbettung als eine Methode, "bei der die Eckpunkte eines Graphen Vektoren in einem niedrigdimensionalen euklidischen Raum zugeordnet werden". Überprüfen Sie den Link für weitere Informationen.

goatboy3million
quelle
Willkommen im Forum. Wenn Sie eine Arbeit erwähnen möchten, notieren Sie sich bitte auch deren Namen als Teil des Textes (da Links beschädigt werden können).
Mark.F