Was ist die Einbettung von Graphen?

Das Einbetten von Graphen lernt eine Zuordnung von einem Netzwerk zu einem Vektorraum unter Beibehaltung der relevanten Netzwerkeigenschaften.

Vektorräume sind für die Datenwissenschaft zugänglicher als Diagramme. Diagramme enthalten Kanten und Knoten. Diese Netzwerkbeziehungen können nur eine bestimmte Teilmenge von Mathematik, Statistik und maschinellem Lernen verwenden. Vektorräume verfügen über ein umfangreicheres Toolset aus diesen Domänen. Darüber hinaus sind Vektoroperationen häufig einfacher und schneller als die entsprechenden Diagrammoperationen.

Ein Beispiel ist das Finden der nächsten Nachbarn. Sie können „Sprünge“ von Knoten zu einem anderen Knoten in einem Diagramm 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. euklidische Entfernung oder Kosinusähnlichkeit). Wenn Sie quantitative Entfernungsmetriken in einem aussagekräftigen Vektorraum haben, ist es einfach, die nächsten Nachbarn zu finden.

„ Techniken, Anwendungen und Leistung zum Einbetten von Graphen: Eine Umfrage „ist ein Übersichtsartikel, der ausführlicher behandelt wird.

Was sind Graph Embeddings? „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 sehr einfachen Sinne) des Graphen erfasst. Wir können diese „Vektordarstellung“ reich machen, indem wir auch die Vertex-Vertex-Beziehungen, Kanteninformationen usw. berücksichtigen. Es gibt ungefähr zwei Ebenen von Einbettungen im Diagramm (natürlich können wir jederzeit weitere Ebenen definieren, indem wir das gesamte Diagramm logisch unterteilen Untergraphen verschiedener Größen):

• Vertex-Einbettungen – Hier finden Sie eine latente Vektordarstellung von jeder Scheitelpunkt in der gegebenen Grafik. Sie können dann die verschiedenen Scheitelpunkte vergleichen, indem Sie diese Vektoren im Raum zeichnen. Interessanterweise werden „ähnliche“ Scheitelpunkte näher beieinander gezeichnet als diejenigen, die unähnlich oder weniger verwandt sind. Dies ist die gleiche Arbeit, die Perozzi in „DeepWalk“ ausgeführt hat.
• Graph Embeddings – Hier Sie finden die latente Vektordarstellung des gesamten Graphen. 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 in der Gruppe vorhanden sind (Cluster) usw. Sie können diese Vektoren verwenden und sie im Raum und zeichnen Hier finden Sie alle oben genannten Informationen. Dies ist die Arbeit, die Yanardag in „Deep Graph Kernels“ erledigt.

Anwendungen – Bei genauerer Betrachtung sind Einbettungen „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“, wobei d < < | V | die Adjazenzmatrix | V | ergeben würde * d und relativ einfach zu bedienen. Eine andere Anwendung könnte sein: Stellen Sie sich ein einfaches Szenario vor, in dem wir Produkte für Personen empfehlen möchten, die ähnliche Interessen an einem sozialen Netzwerk haben.Indem wir Scheitelpunkt-Einbettungen erhalten (hier bedeutet dies die Vektordarstellung jeder Person), können wir die ähnlichen finden, indem wir diese Vektoren zeichnen, und 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? In diesem Bereich wurden viele Arbeiten durchgeführt, und fast alle stammen aus der bahnbrechenden Forschung im Bereich der Verarbeitung natürlicher Sprache – „Word2Vec“ von Mikolov. Wenn Sie mit der Erforschung von Diagrammeinbettungen beginnen möchten, würde ich empfehlen, zunächst zu verstehen, wie Word2Vec funktioniert. Sie finden nette Erklärungen – Lernen von Word2Vec-Parametern erklärt und Stanford Lecture . Dann können Sie zu den Papieren springen, die Sie aufgelistet haben. Diese Werke können wie folgt kategorisiert werden:

• Werke, die auf „Vertex Embeddings“ basieren: – DeepWalk , Node2Vec , LINE .

• Funktioniert basierend auf „Graph Embeddings“: – Deep Graph Kernels , Subgraph2Vec .

Kommentare

• Wowww !! Dies ist absolut eine perfekte Antwort. Vielen Dank 🙂 Sehr gut gemacht 🙂
• Hallo Mausam Jain. Können Sie mir bitte mitteilen, ob ich mithilfe von Grafikeinbettungen wichtige Knoten im Netzwerk identifizieren kann?
• 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?
• Vielen Dank für Ihre Antwort. Ich arbeite tatsächlich in einem sozialen Netzwerk, in dem ich die sozialsten Personen identifizieren möchte 🙂
• Hier ‚ ist eine ausführlichere Version dieser Antwort. Richtung Datascience.com/…

In der Arbeit Ein zentraler Grenzwertsatz für eine Omnibus-Einbettung von zufälligen Punktproduktgraphen von Levin et al. Papier, eine bestimmte Art der Grapheinbettung (die Omnibus-Einbettung) definiert die Grapheinbettung als eine Methode, „bei der die Eckpunkte eines Graphen auf Vektoren in einem niedrigdimensionalen euklidischen Raum abgebildet werden“. Überprüfen Sie den Link für weitere Informationen.

Kommentare

• Willkommen im Forum. Wenn Sie ein Papier erwähnen möchten, schreiben Sie bitte auch seinen Namen als Teil des Textes auf (da Links unterbrochen werden können).