GAP: Generalisierbarer Approximativer Graph-Partitionierungsrahmen

Die Graphpartitionierung ist das Problem, die Knoten eines Graphen in ausgewogene Partitionen zu teilen, während man die Anzahl der Kanten, die zwischen den Partitionen durchtrennt werden müssen, minimiert. Aufgrund ihrer kombinatorischen Natur wurden viele approximative Lösungen entwickelt, darunter Varianten von Multi-Level-Methoden und spektraler Clustering. Wir schlagen GAP vor, ein generalisierbares approximatives Partitionierungsframework, das einen tiefen Lernansatz zur Graphpartitionierung verfolgt. Wir definieren eine differenzierbare Verlustfunktion, die das Partitionierungsziel repräsentiert, und nutzen Backpropagation zur Optimierung der Netzwerkparameter. Im Gegensatz zu Baseline-Verfahren, die für jeden Graphen die Optimierung erneut durchführen müssen, ist GAP in der Lage zu generalisieren und ermöglicht es uns, Modelle zu trainieren, die bei der Inferenzzeit effektive Partitionen erzeugen können – sogar auf bisher nicht gesehenen Graphen. Da wir gleichzeitig die Darstellung des Graphen lernen und für die Verlustfunktion der Partitionierung optimieren, kann GAP leicht an verschiedene Graphstrukturen angepasst werden. Wir evaluieren die Leistungsfähigkeit von GAP anhand von Graphen unterschiedlicher Größen und Strukturen, einschließlich weit verbreiteter maschineller Lernmodelle (z.B. ResNet, VGG und Inception-V3), skalenfreien Graphen und zufälligen Graphen. Unsere Ergebnisse zeigen, dass GAP wettbewerbsfähige Partitionen erzeugt und bis zu 100-mal schneller als die Baseline-Verfahren ist sowie sich auf unbekannte Graphen überträgt.