Die Überwindung der Ausdrucksrestriktionen von Graph Neural Networks

Kürzlich wurde der Weisfeiler-Lehman-(WL)-Isomorphietest verwendet, um die Ausdrucksstärke von Graph Neural Networks (GNNs) zu messen. Dabei zeigte sich, dass die Neighborhood-Aggregation-GNNs höchstens so mächtig wie der 1-WL-Test bei der Unterscheidung von Graphstrukturen sind. Es wurden auch Verbesserungen vorgeschlagen, die sich am $k$-WL-Test ($k>1$) orientieren. Allerdings sind die Aggregatoren in diesen GNNs weit davon entfernt, injektiv zu sein, wie es vom WL-Test verlangt wird, und leiden unter einer schwachen Unterscheidungsstärke, was sie zu Ausdrucksengpässen macht. In dieser Arbeit verbessern wir die Ausdrucksstärke durch das Erkunden mächtiger Aggregatoren. Wir formulieren die Aggregation neu mit der entsprechenden Aggregationskoeffizientenmatrix und analysieren dann systematisch die Anforderungen an diese Matrix für den Bau stärkerer und sogar injektiver Aggregatoren. Dies kann auch als Strategie zur Erhaltung des Rangs der verborgenen Merkmale angesehen werden und impliziert, dass grundlegende Aggregatoren einem Sonderfall von Rangabbildungen niedrigen Rangs entsprechen. Wir zeigen zudem die Notwendigkeit, nichtlineare Einheiten vor der Aggregation anzuwenden, was sich von den meisten aggregationsbasierten GNNs unterscheidet. Auf Basis unserer theoretischen Analyse haben wir zwei GNN-Layer entwickelt: ExpandingConv und CombConv. Experimentelle Ergebnisse zeigen, dass unsere Modelle die Leistung erheblich steigern, insbesondere bei großen und dicht verbundenen Graphen.