Neue Algorithmen für Graphenkomprimierung im Gromov‑Wasserstein‑Rahmen

In einer kürzlich veröffentlichten Arbeit auf arXiv wird ein neues Verfahren zur Graphenkomprimierung vorgestellt, das die Gromov‑Wasserstein‑Geometrie nutzt. Die Autoren präsentieren zwei effiziente Algorithmen, die die durch das Zusammenführen von Knotengruppen entstehende Verzerrung neu darstellen.

Der erste Ansatz, Greedy Pair Coarsening (GPC), arbeitet iterativ: Er verbindet jeweils das Knotengleichgewicht, das die lokale Verzerrung am wenigsten erhöht, bis die gewünschte Knotenzahl erreicht ist. Der zweite Ansatz, k‑means Greedy Pair Coarsening (KGPC), nutzt eine Clustering‑Strategie, die auf Paar‑Verzerrungsmetriken basiert, um ganze Cluster von Knoten gleichzeitig zu verschmelzen.

Die Autoren liefern mathematische Bedingungen, unter denen beide Verfahren optimale Komprimierungen garantieren. In umfangreichen Tests auf sechs großen Datensätzen sowie einer anschließenden Clustering‑Aufgabe zeigen die neuen Methoden eine deutlich bessere Leistung als bestehende Verfahren – sowohl hinsichtlich der Qualität der Komprimierung als auch der Flexibilität über verschiedene Parameterbereiche hinweg.