Network Embedding — Node2Vec, DeepWalk, LINE
- Jahr
- 2014 (DeepWalk); 2016 (Node2Vec)
- Typ
- Representation learning / unsupervised network method
Dieser Text ist eine maschinelle Übersetzung und wurde noch nicht geprüft. Original auf Englisch lesen
Was leistet sie?
Network Embedding ist eine Familie von Methoden des repräsentationsbasierten Lernens, die jeden Knoten eines Graphen in einen dichten, niedrigdimensionalen Vektor abbilden und dabei die strukturellen Eigenschaften des Netzwerks erhalten.
Der Ansatz wurde für Daten sozialer Netzwerke von Perozzi, Al-Rfou und Skiena mit DeepWalk (2014) formalisiert, welche das Word2Vec Skip-Gram-Modell auf Zufallswanderungen auf Graphen adaptierten, und von Grover und Leskovec mit Node2Vec (2016) erweitert, welche eine gewichtete Zufallswanderung einführten, die die Exploration mittels Breitensuche und Tiefensuche ausbalanciert. Diese Embeddings wandeln relationale Daten in Merkmalsvektoren um, die von Standard-Klassifikatoren und Clustering-Algorithmen des maschinellen Lernens direkt verarbeitet werden können.
Die Intuition hinter der Methode
Ein Graph besteht aus Knoten und Kanten, aber die meisten Algorithmen des maschinellen Lernens erwarten eine Tabelle mit Zahlen. Network Embedding löst das Übersetzungsproblem. So wie Word2Vec Wortbedeutungen lernt, indem es betrachtet, welche Wörter in Sätzen nahe beieinander vorkommen, lernt DeepWalk Knotenbedeutungen, indem es betrachtet, welche Knoten in Zufallswanderungen über den Graphen hinweg nahe beieinander vorkommen. Das Ergebnis ist eine Koordinate in einem Vektorraum – Knoten, die strukturell ähnlich oder häufig gemeinsam besucht werden, landen nahe beieinander. Sobald jeder Knoten einen Vektor hat, können diese Vektoren in einen Klassifikator eingespeist, mit k-means geclustert oder mit UMAP visualisiert werden, ohne spezifischen Code für den Graphen schreiben zu müssen.
Geschichte
Die Idee, Word2Vec auf graphstrukturierte Daten anzuwenden, wurde von Perozzi, Al-Rfou und Skiena in DeepWalk (KDD 2014) eingeführt, die zeigten, dass Zufallswanderungen auf einem sozialen Graphen handentworfene Merkmale für die Knotenklassifizierung ersetzen können. Grover und Leskovec erweiterten dies in Node2Vec (KDD 2016) durch die Einführung einer Zufallswanderung zweiter Ordnung, die durch p und q parametrisiert ist und eine explizite Kontrolle über den Kompromiss zwischen homophiliebasierter und strukturell-äquivalenzbasierter Nachbarschaftsexploration ermöglicht. Ungefähr zur gleichen Zeit schlugen Tang et al. LINE (WWW 2015) vor, das Einbettungen lernt, indem es Ziele der ersten und zweiten Ordnung direkt optimiert und nicht durch Zufallswanderungen, was es für sehr große Graphen geeignet macht. Zusammen etablierten diese drei Methoden das Feld des Network Representation Learning und inspirierten nachfolgende Graph Neural Network-Architekturen.
Wann wird sie eingesetzt?
Network Embedding ist geeignet, wenn Sie einen Graphen mit mindestens 50 Knoten haben und kontinuierliche Vektor-Merkmale für nachgelagerte Aufgaben wie Knotenklassifizierung, Link-Vorhersage oder Knoten-Clustering benötigen. Die Methode eignet sich sowohl für ungewichtete als auch für gewichtete Graphen und verarbeitet gerichtete oder ungerichtete Strukturen. Wählen Sie DeepWalk, wenn eine einfache, uniforme Zufallswanderungs-Baseline ausreicht. Wählen Sie Node2Vec, wenn Sie die Balance zwischen Homophilie und struktureller Äquivalenz über die Parameter p und q abstimmen möchten. Wenn Sie neue, bisher ungesehene Knoten zur Inferenzzeit einbetten müssen, ohne neu zu trainieren, bevorzugen Sie eine induktive Methode wie GraphSAGE; Network Embedding in seiner Standardform ist transduktiv. Die Methode erfordert keine normalverteilten Knotenattribute.
Grenzen und Hinweise
- Transduktiv: Das Modell kann keine Knoten einbetten, die während des Trainings nicht vorhanden waren, ohne vollständiges Neutraining.
- Hyperparameter-Sensitivität: Einbettungsdimension, Wanderungslänge, Anzahl der Wanderungen, Fenstergröße, p und q beeinflussen alle die Qualität der Einbettung und erfordern eine Abstimmung.
- Zufallswanderungen erfassen keine höherstufige Graphstruktur (z. B. Hyperkanten oder multirelationale Kanten) ohne Erweiterung.
- Die Leistung verschlechtert sich bei sehr kleinen Graphen (weniger als 50 Knoten), wo der Wanderungskorpus zu spärlich ist, um zuverlässige Statistiken zu lernen.
Die Bedingungen der Quelle ersetzen weder eine unabhängige wissenschaftliche Prüfung noch die Validierung durch eine Analyse-Engine.
Stärken
- Konvertiert relationale Graphdaten in Vektoren fester Länge, die mit jeder Standard-Pipeline für maschinelles Lernen kompatibel sind.
- Die p- und q-Parameter von Node2Vec ermöglichen es dem Analysten, die Balance zwischen Community-sensitiven und Rollen-sensitiven Embeddings abzustimmen.
- Kantengewichte können in die Wanderungswahrscheinlichkeiten einbezogen werden, wodurch die Stärke der Beziehung ohne zusätzliche Modellierungsschritte erfasst wird.
- Skaliert auf große Graphen durch effiziente Zufallswanderungs-Stichproben und das Skip-Gram-Trainingsverfahren.
Anwendungen
- Knotenklassifizierung in Zitationsnetzwerken, sozialen Plattformen oder biologischen Interaktionsgraphen.
- Link-Vorhersage – Identifizierung fehlender oder zukünftiger Kanten durch Vergleich der Ähnlichkeit von Knoten-Embeddings.
- Community-Erkennung durch Clustering von Knotenvektoren mit k-means oder hierarchischen Methoden.
- Anomalieerkennung – Knoten, deren Embeddings Ausreißer im Vektorraum sind, können ungewöhnliche strukturelle Rollen darstellen.
- Empfehlungssysteme, bei denen Benutzer und Elemente Knoten in einem bipartiten oder multiplexen Interaktionsgraphen sind.
So funktioniert es
So funktioniert es
Der Prozess beginnt mit einem Graphen G, in dem Knoten Entitäten sind und Kanten Beziehungen darstellen. Kanten können gerichtet oder ungerichtet sein und Gewichte tragen, die später die Wahrscheinlichkeit der Traversierung beeinflussen. Wenn Kantengewichte vorhanden sind, werden sie in die Wanderungswahrscheinlichkeiten einbezogen; wenn sie fehlen, erhalten alle Kanten das gleiche Gewicht. In dieser Phase wählt der Analyst auch die Algorithmusvariante – DeepWalk für uniforme Zufallswanderungen, Node2Vec für gewichtete Wanderungen, die durch die Parameter p (Return) und q (In-Out) gesteuert werden, oder LINE, wenn die Proximität erster und zweiter Ordnung separat gelernt werden soll. Die Wahl zwischen den Parameterregimen von Node2Vec wird durch die erwartete Netzwerkeigenschaft geleitet: Homophilie (ähnliche Knoten verbinden sich, daher wird Breitensuche bevorzugt, q < 1) oder strukturelle Äquivalenz (Knoten mit ähnlichen Rollen können weit voneinander entfernt sein, daher wird Tiefensuche bevorzugt, p < 1).
Ausgehend von jedem Knoten simuliert der Algorithmus eine Reihe von Zufallswanderungen fester Länge (typischerweise 30 Schritte) und wiederholt diese viele Male (typischerweise 200 Wanderungen pro Knoten). Jede Wanderung erzeugt eine Sequenz von Knotenidentifikatoren, analog zu einem Satz von Wörtern. In DeepWalk wird der nächste Knoten gleichmäßig aus den Nachbarn gewählt. In Node2Vec wird der nächste Knoten gemäß Übergangswahrscheinlichkeiten gewählt, die durch p und q gewichtet sind: die Rückkehr zum vorherigen Knoten wird mit 1/p bestraft, das Verbleiben in der gleichen Entfernung bleibt bei 1, und die Bewegung weiter weg wird durch 1/q gesteuert. Die Sammlung aller Wanderungen bildet ein Korpus von Knotensequenzen, der die Topologie des Graphen kodiert.
Das Korpus von Knotensequenzen wird in ein Skip-Gram-Modell (die gleiche Architektur wie Word2Vec) eingespeist. Für jeden Knoten in einer Wanderung sagt das Modell die umgebenden Kontextknoten innerhalb eines Fensters (typischerweise 10 Schritte) voraus. Durch stochastischen Gradientenabstieg lernt das Modell eine dichte Vektorrepräsentation fester Dimension – üblicherweise 64 oder 128 – für jeden Knoten, sodass Knoten, die in Wanderungen gemeinsam vorkommen, ähnliche Vektoren haben. Die Dimension ist ein Hyperparameter: größere Dimensionen erfassen mehr Struktur, erhöhen aber die Berechnung und das Risiko von Überanpassung bei kleinen Graphen.
Nach dem Training liefert das Modell einen Embedding-Vektor pro Knoten. Diese Vektoren werden als Merkmale für die Knotenklassifizierung (Einspeisung in eine logistische Regression oder einen neuronalen Klassifikator), Link-Vorhersage (Vergleich von Vektoren von Kandidatenknotenpaaren) oder Community-Erkennung (Clustering der Vektoren) verwendet. Die Embeddings sind transduktiv: sie sind für die während des Trainings gesehenen Knoten fixiert. Wenn neue Knoten nach dem Training eingebettet werden müssen, sollte stattdessen eine induktive Methode wie GraphSAGE verwendet werden, da ein Standard-Node2Vec- oder DeepWalk-Modell nicht auf ungesehene Knoten generalisieren kann, ohne neu trainiert zu werden.
Häufige Fallstricke
- Anwendung eines Node2Vec-Modells auf neue Knoten, die nicht im Trainingsgraphen enthalten waren – das Modell hat keinen Vektor für sie; verwenden Sie eine induktive Methode (z. B. GraphSAGE), wenn transduktive Einbettung nicht akzeptabel ist.
- Verwendung der Standardwerte p=1, q=1 (entspricht DeepWalk), ohne zu prüfen, ob das Netzwerk einem Homophilie- oder strukturellen Äquivalenzmuster folgt – die Abstimmung von p und q auf das erwartete Muster kann die Leistung nachgelagerter Aufgaben erheblich verbessern.
- Behandlung der Einbettungsdimension als feste Konstante: Bei kleinen Graphen kann eine Dimension von 64 oder 128 zu einer Überanpassung führen; beginnen Sie niedriger und validieren Sie anhand der nachgelagerten Aufgabe.
- Ignorieren der Mindestanforderung an die Stichprobe: Graphen mit weniger als 50 Knoten erzeugen Wanderungskorpora, die zu dünn sind, um zuverlässige Einbettungen zu trainieren.
Häufig gestellte Fragen
Was ist der Unterschied zwischen DeepWalk, Node2Vec und LINE?
DeepWalk verwendet uniforme Zufallswanderungen und das Word2Vec Skip-Gram-Modell – es ist die einfachste Baseline. Node2Vec fügt gewichtete Zufallswanderungen hinzu, die durch p und q gesteuert werden, wodurch der Analyst abstimmen kann, ob die Wanderung wie eine Breitensuche (Homophilie) oder eine Tiefensuche (strukturelle Äquivalenz) erkundet. LINE verwendet überhaupt keine Zufallswanderungen; es optimiert Ziele der ersten und zweiten Ordnung direkt auf der Kantenliste, was für sehr große Graphen skalierbarer ist, aber das wanderungsbasierte Nachbarschaftssignal opfert.
Wie wähle ich die Parameter p und q in Node2Vec?
p steuert die Wahrscheinlichkeit, zum vorherigen Knoten zurückzukehren (niedriges p = weniger Zurückverfolgung), und q steuert den Erkundungsradius (q < 1 begünstigt die Erkundung nach außen, q > 1 hält die Wanderung nahe der Quelle). Wenn Sie erwarten, dass Knoten in derselben Community ähnlich sind (Homophilie), setzen Sie q < 1, damit die Wanderung nach außen streift. Wenn Sie erwarten, dass Knoten mit derselben strukturellen Rolle ähnlich sind, auch wenn sie weit voneinander entfernt sind, setzen Sie p < 1, um die Tiefensuche zu fördern. Validieren Sie beide Regime für die nachgelagerte Aufgabe.
Kann ich neue Knoten nach dem Training einbetten, ohne das gesamte Modell neu zu trainieren?
Standard-Node2Vec und DeepWalk sind transduktiv: Die Embedding-Matrix deckt nur die während des Trainings gesehenen Knoten ab. Für induktive Generalisierung auf neue, bisher ungesehene Knoten verwenden Sie eine induktive Graph Neural Network-Methode wie GraphSAGE, die eine Aggregationsfunktion über Knotennachbarschaften lernt, die zu jedem Zeitpunkt der Inferenz auf jeden Knoten angewendet werden kann.
Wie viele Dimensionen sollte ich für das Embedding verwenden?
Die gängigsten Optionen sind 64 und 128, und diese funktionieren gut für mittlere bis große Graphen. Für kleine Graphen (50–200 Knoten) beginnen Sie mit einer niedrigeren Dimension (16 oder 32), um eine Überanpassung zu vermeiden, und bewerten Sie die Qualität des Embeddings, indem Sie die Leistung der nachgelagerten Aufgabe messen (z. B. Genauigkeit der Knotenklassifizierung) und nicht nur den Rekonstruktionsfehler.
Verwandte Methoden
Quellen
Grover, A. & Leskovec, J. (2016). Node2Vec: Scalable Feature Learning for Networks. Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), 855-864.
DOI-Referenz öffnenKopiert.Perozzi, B., Al-Rfou, R., & Skiena, S. (2014). DeepWalk: Online Learning of Social Representations. Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), 701-710.
DOI-Referenz öffnenKopiert.