SimGNN: Ein neuronales Netzansatz zur schnellen Berechnung von Graphenähnlichkeiten

Die Suche nach ähnlichen Graphen zählt zu den wichtigsten graphbasierten Anwendungen, wie zum Beispiel das Auffinden chemischer Verbindungen, die einer Abfrageverbindung am ähnlichsten sind. Die Berechnung der Graphähnlichkeit, einschließlich des Graph-Edit-Distances (GED) und des Maximum Common Subgraphs (MCS), ist die Kernoperation sowohl bei der Suche nach ähnlichen Graphen als auch bei vielen anderen Anwendungen, jedoch in der Praxis sehr aufwändig. Inspiriert durch den jüngsten Erfolg neuronaler Netzansätze in verschiedenen graphbasierten Anwendungen, wie Knoten- oder Graphklassifizierung, schlagen wir einen neuen Ansatz vor, der auf neuronale Netze basiert und dieses klassische und herausfordernde Problem der Graphähnlichkeit löst. Das Ziel ist es, die Rechenintensität zu reduzieren, während gleichzeitig eine gute Leistung gewährleistet wird.Der vorgeschlagene Ansatz, SimGNN genannt, kombiniert zwei Strategien. Erstens entwickeln wir eine lernfähige Einbettungsfunktion, die jeden Graphen in einen Vektor abbildet und so eine globale Zusammenfassung des Graphen bereitstellt. Es wird ein neues Aufmerksamheitsmechanismus vorgeschlagen, um wichtige Knoten im Hinblick auf ein spezifisches Ähnlichkeitsmaß hervorzuheben. Zweitens entwerfen wir eine Methode zur paarweisen Knotenvergleich, um die graphbasierten Einbettungen mit detaillierten knotenbasierten Informationen zu ergänzen. Unser Modell erzielt bessere Generalisierungsleistungen auf unbekannten Graphen und läuft im schlimmsten Fall quadratisch bezogen auf die Anzahl der Knoten in beiden Graphen.Unter Verwendung der Berechnung des GEDs als Beispiel zeigen experimentelle Ergebnisse auf drei realen Graphendatensätzen die Effektivität und Effizienz unseres Ansatzes. Insbesondere erreicht unser Modell kleinere Fehlerquoten und erhebliche Zeitersparnisse im Vergleich zu einer Reihe von Baseline-Methoden, darunter mehreren Approximationsalgorithmen für die GED-Berechnung sowie zahlreichen existierenden Modellen basierend auf graphneuronalen Netzen. Nach bestem Wissen sind wir unter den ersten, die neuronale Netze verwenden, um die Ähnlichkeit zwischen zwei Graphen explizit zu modellieren und damit eine neue Richtung für zukünftige Forschungen zur Berechnung von Graphähnlichkeiten und zur Suche nach ähnlichen Graphen aufzeigen.