Genaueres Lernen von Graphendarstellungen mit Graphen-Multiset-Pooling

Graph Neural Networks werden weitgehend zur Modellierung graphenförmiger Daten eingesetzt und erzielen beeindruckende Ergebnisse bei Aufgaben der Knotenklassifikation und der Link-Vorhersage. Dennoch erfordert die Erzeugung einer genauen Darstellung eines Graphen eine Pooling-Funktion, die eine Menge von Knotendarstellungen in eine kompakte Form abbildet. Eine einfache Summierung oder Durchschnittsbildung über alle Knotendarstellungen berücksichtigt alle Knotenmerkmale gleichwertig, ohne deren Aufgabenrelevanz oder etwaige strukturelle Abhängigkeiten zu berücksichtigen. Im Gegensatz dazu können kürzlich vorgeschlagene hierarchische Graph-Pooling-Methoden für zwei verschiedene Graphen dieselbe Darstellung erzeugen, die sich jedoch bereits im Weisfeiler-Lehman-Test unterscheiden, da sie die Informationen aus den Knotenmerkmalen suboptimal bewahren. Um diese Beschränkungen bestehender Graph-Pooling-Methoden zu überwinden, formulieren wir das Graph-Pooling-Problem zunächst als ein Multiset-Encoding-Problem unter Einbeziehung zusätzlicher Informationen über die Graphenstruktur und schlagen einen Graph Multiset Transformer (GMT) vor – eine auf Multi-Head-Attention basierende globale Pooling-Schicht, die die Wechselwirkungen zwischen Knoten gemäß ihren strukturellen Abhängigkeiten erfasst. Wir zeigen, dass GMT sowohl Injektivität als auch Permutationsinvarianz erfüllt, wodurch es mindestens so leistungsfähig ist wie der Weisfeiler-Lehman-Graph-Isomorphismus-Test. Darüber hinaus lässt sich unser Ansatz problemlos auf frühere Knoten-Clustering-Ansätze zur hierarchischen Graph-Pooling erweitern. Unsere experimentellen Ergebnisse zeigen, dass GMT state-of-the-art-Graph-Pooling-Methoden bei graphenklassifizierenden Benchmarks erheblich übertrifft, wobei gleichzeitig eine hohe Speicher- und Zeiteffizienz erreicht wird. Zudem erzielt GMT noch deutlich größere Leistungssteigerungen bei Aufgaben der Graphenrekonstruktion und -generierung.