Vorlagebasiertes Graph Neural Network mit optimalen Transportentfernungen

Aktuelle Architekturen von Graph Neural Networks (GNN) beruhen im Allgemeinen auf zwei zentralen Komponenten: der Einbettung von Knotenmerkmalen mittels Message Passing sowie der Aggregation durch eine spezialisierte Form von Pooling. Die strukturelle (oder topologische) Information wird in diesen beiden Schritten implizit berücksichtigt. In dieser Arbeit schlagen wir einen neuen Ansatz vor, bei dem Abstände zu lernbaren Graphen-Template-Mustern im Zentrum der Graphendarstellung stehen. Diese Abstands-Einbettung wird mittels einer optimalen Transport-Distanz, nämlich der gefügten Gromov-Wasserstein-(FGW)-Distanz, konstruiert, die sowohl Merkmals- als auch Strukturdissimilaritäten durch die Lösung eines weichen Graphen-Matching-Problems kodiert. Wir vermuten, dass der Vektor der FGW-Abstände zu einer Menge von Template-Graphen eine starke diskriminative Kraft besitzt, der anschließend einem nichtlinearen Klassifikator zur endgültigen Vorhersage zugeführt wird. Die Abstands-Einbettung kann als eine neue Schicht betrachtet werden und kann bestehende Message-Passing-Techniken nutzen, um sinnvolle Merkmalsrepräsentationen zu fördern. Interessanterweise wird in unserer Arbeit auch der optimale Satz von Template-Graphen end-to-end durch Differenzierung durch diese Schicht gelernt. Nach der Beschreibung des entsprechenden Lernverfahrens validieren wir unsere These empirisch an mehreren synthetischen und realen Graphen-Klassifikationsdatensätzen, wobei unsere Methode mit oder sogar besser als state-of-the-art-Ansätze basierend auf Kernen und GNNs abschneidet. Die Experimente ergänzen wir durch eine Ablationsstudie und eine Sensitivitätsanalyse hinsichtlich der Parameter.