ASAP: Adaptive Structure Aware Pooling für die Lernung hierarchischer Graphendarstellungen

Graph Neural Networks (GNN) haben sich als effektiv erwiesen, um graphenstrukturierte Daten zu modellieren und Aufgaben wie Knotenklassifikation, Link-Vorhersage und Graph-Klassifikation zu lösen. In jüngster Zeit wurden Fortschritte bei der Definition des Pooling-Begriffs in Graphen erzielt, bei dem das Modell versucht, eine graphenbasierte Repräsentation durch Downsampling und Zusammenfassung der in den Knoten enthaltenen Informationen zu generieren. Bisherige Pooling-Methoden scheitern entweder daran, die Unterstruktur des Graphen effektiv zu erfassen, oder skaliert nicht gut auf große Graphen. In dieser Arbeit stellen wir ASAP (Adaptive Structure Aware Pooling) vor, eine sparsame und differenzierbare Pooling-Methode, die die Einschränkungen früherer Architekturen für Graph-Pooling adressiert. ASAP nutzt ein neuartiges Self-Attention-Netzwerk in Kombination mit einer modifizierten GNN-Formulierung, um die Bedeutung jedes Knotens innerhalb eines gegebenen Graphen zu erfassen. Zudem lernt es eine spärliche, weiche Cluster-Zuweisung für die Knoten auf jeder Ebene, um die Untergraphen effektiv zu poolen und den gepoolten Graphen zu bilden. Durch umfangreiche Experimente auf mehreren Datensätzen sowie theoretische Analysen begründen wir unsere Wahl der in ASAP verwendeten Komponenten. Unsere experimentellen Ergebnisse zeigen, dass die Kombination bestehender GNN-Architekturen mit ASAP führende Ergebnisse auf mehreren Benchmark-Aufgaben zur Graph-Klassifikation erzielt. Im Vergleich zur aktuellen state-of-the-art-Methode für sparsame hierarchische Pooling-Verfahren erreicht ASAP im Durchschnitt eine Verbesserung um 4 %.