Nachweislich leistungsstarke Graphennetze

Kürzlich wurde der Weisfeiler-Lehman (WL)-Graph-Isomorphie-Test verwendet, um die Ausdrucksstärke von Graph Neural Networks (GNN) zu messen. Es wurde gezeigt, dass die weit verbreiteten Message-Passing-GNN nicht zwischen Graphen unterscheiden können, die durch den 1-WL-Test nicht zu unterscheiden sind (Morris et al. 2018; Xu et al. 2019). Leider können viele einfache Graphinstanzen durch den 1-WL-Test nicht unterschieden werden.Im Streben nach ausdrucksstärkeren Graph-Lernmodellen bauen wir auf den jüngsten k-Ordnungs-invarianten und -äquivarianten Graph Neural Networks (Maron et al. 2019a,b) auf und präsentieren zwei Ergebnisse:Erstens zeigen wir, dass solche k-Ordnungs-Netze zwischen nicht-isomorphen Graphen so gut unterscheiden können wie die k-WL-Tests, die beweisbar stärker sind als der 1-WL-Test für (k > 2). Dies macht diese Modelle streng stärker als Message-Passing-Modelle. Allerdings geht die höhere Ausdrucksstärke dieser Modelle mit einem Rechenaufwand einher, der die Verarbeitung hochdimensionaler Tensoren erfordert.Zweitens, mit dem Ziel eines beweisbar stärkeren, einfachen und skalierbaren Modells, zeigen wir, dass ein reduziertes 2-Ordnungs-Netzwerk, das nur einen skalierten Identitätsoperator enthält und durch eine einzelne quadratische Operation (Matrixmultiplikation) ergänzt wird, eine beweisbare 3-WL-Ausdrucksstärke besitzt. Anders gesagt schlagen wir ein einfaches Modell vor, das Anwendungen des Standard-Multilayer Perceptrons (MLP) in der Merkmalsdimension und Matrixmultiplikation abwechseln lässt. Wir validieren dieses Modell durch die Präsentation von Stand-of-the-Art-Ergebnissen bei beliebten Graph-Klassifikations- und -Regressionaufgaben. Nach bestem Wissen ist dies das erste praktische invariant/äquivariante Modell mit garantierte 3-WL-Ausdrucksstärke, das streng stärker ist als Message-Passing-Modelle.