Neues GNN-Modell liefert präzisere Graph-Edit-Distanz

In der Welt der Graphenvergleiche ist die Graph Edit Distance (GED) ein zentraler Maßstab, der die optimale Übereinstimmung zweier Graphen bestimmt. Da die exakte Berechnung von GED jedoch NP-schwer ist, greifen Forscher vermehrt auf Graph Neural Networks (GNN) zurück, um Annäherungen zu erzeugen. Traditionelle GNN-Ansätze konzentrieren sich dabei auf die Erzeugung von Knoteneinbettungen und aggregieren anschließend die Ähnlichkeiten einzelner Knoten, um die Gesamtsimilarität abzuschätzen.

Diese node‑zentrierte Methode steht jedoch im Widerspruch zu den Grundprinzipien von GED. Sie verpasst die globale Strukturkorrespondenz und führt zu fehlerhaften Kostenzuweisungen, die auf spurious node‑level Signalen beruhen. Um diese Schwächen zu beheben, wurde GCGSim entwickelt – ein GED‑konsistentes Lernframework, das sich auf graph‑level Matching und substructure‑level Edit Costs fokussiert.

GCGSim nutzt drei zentrale Innovationen: Erstens wird die Übereinstimmung auf Graphebene statt Knotebene durchgeführt, zweitens werden die Editkosten auf substructure‑Ebene berechnet und drittens werden die Substrukturen selbst disentangled und semantisch sinnvoll repräsentiert. In umfangreichen Experimenten auf vier Benchmark‑Datensätzen übertrifft GCGSim bestehende Methoden und erreicht damit einen neuen Stand der Technik.

Die Ergebnisse zeigen nicht nur eine höhere Genauigkeit bei der GED‑Schätzung, sondern auch, dass das Modell tatsächlich sinnvolle, voneinander getrennte Substruktur‑Darstellungen lernt – ein wichtiger Schritt hin zu transparenteren und nachvollziehbareren Graph‑Similarity‑Algorithmen.