Hierarchische Repräsentationslernen in Graph Neural Networks mit Node Decimation Pooling

In Graph Neural Networks (GNNs) werden Pooling-Operatoren eingesetzt, um lokale Zusammenfassungen von Eingabegraphen zu berechnen, um deren globale Eigenschaften zu erfassen, und sie sind entscheidend für den Aufbau tiefer GNNs, die hierarchische Darstellungen lernen. In dieser Arbeit stellen wir Node Decimation Pooling (NDP) vor, einen Pooling-Operator für GNNs, der verdünnte Graphen generiert, während die Gesamttopologie des Graphen erhalten bleibt. Während des Trainings lernt das GNN neue Knotendarstellungen und passt diese an eine Pyramide verdünnter Graphen an, die im Vorverarbeitungsschritt offline berechnet wird. NDP besteht aus drei Schritten. Zunächst wählt ein Knoten-Entscheidungsverfahren die Knoten aus, die einer Seite der von einem spektralen Algorithmus identifizierten Partition entsprechen, wobei dieser Algorithmus eine Näherung der \maxcut{}-Lösung berechnet. Anschließend werden die ausgewählten Knoten mittels Kron-Reduktion miteinander verbunden, um den verdünnten Graphen zu bilden. Schließlich wird aufgrund der hohen Dichte des resultierenden Graphen eine Verdünnungsprozedur angewandt, bei der die Adjazenzmatrix des verdünnten Graphen so verarbeitet wird, dass die Rechenkosten im GNN reduziert werden. Insbesondere zeigen wir, dass viele Kanten entfernt werden können, ohne die Struktur des Graphen signifikant zu verändern. Experimentelle Ergebnisse belegen, dass NDP im Vergleich zu aktuellen State-of-the-Art-Pooling-Operatoren effizienter ist und gleichzeitig auf einer Vielzahl von Graphklassifizierungsaufgaben wettbewerbsfähige Leistung erzielt.