Do we need to Improve message passing? Improving graph neural networks with graph transformations

Abstract

Wir untersuchen Graph Neuronale Netzwerke (GNNs) mit geändertem Message Passing und schlagen neuartige Graphtransformationen vor, mit denen Standard Message Passing hochmoderne Expressivität und Vorhersageleistungen erreichen kann.Es ist bekannt, dass Graph Neuronale Netzwerke mit Message Passing (MPNNs) bei der Unterscheidung von Graphen eine begrenzte Expressivität haben. Das bedeutet, dass Paare von Graphen existieren, für die jedes MPNN das gleiche Ergebnis liefert. Dies schränkt die Funktionen ein, die MPNNs ausdrücken können. Außerdem können MPNNs viele Graphenstrukturen nicht erkennen: ein Beispiel dafür sind zyklische Subgraphen deren Anzahl MPNNs nicht zählen können. Allerdings können diese Strukturen wichtige Informationen beinhalten, zum Beispiel ist die Existenz von Zyklen in Molekülstrukturen wichtig, um Moleküleigenschaften vorherzusagen. Deshalb ist es sinnvoll GNNs zu entwicklen die expressiver als MPNNs sind. Wir definieren, dass ein Algorithmus A mindestens so expressiv wie Algorithmus B ist, wenn A jedes Paar von Graphen unterscheiden kann, das B unterscheiden kann. Es besteht ein Zusammenhang zwischen Universalität und Expressivität: wenn ein Algorithmus alle Graphen eines bestimmten Typs unterscheiden kann, dann ergibt die Kombination dieses Algorithmus mit einem Multilayer Perceptrons automatisch einen universellen Funktionsapproximator auf diesen Graphen. Um MPNNs expressiver zu machen ist es notwendig, eine verbesserte Form des Message Passings zu verwenden oder die Graphen zu modifizieren. Das Ändern von Message Passing ist sehr mächtig, erfordert aber erhebliche Änderungen an bestehenden Implementierungen und kann nicht ohne weiteres mit anderen Ansätzen kombiniert werden. Die Modifizierung der Graphen erfordert keine Änderungen am Lernalgorithmus und funktioniert direkt mit Standardimplementierungen. In dieser Arbeit untersuchen wir vier Varianten von GNNs. Drei GNNs die verbessertes Message Passing verwenden: (I) CW-Networks, (II) Equivariant Subgraph Aggregation Networks und (III) (local) δ-k-dimensional WL. Ein GNN welches als Anwendung einer Graphentransformation gesehen werden kann: (IV) MPNNs mit Homomorphismenszählung. Wir schlagen neuartige Graphentransformationen für (I), (II), (III) vor und vergleichen diese mit dem aktuellen Stand der Wissenschaft. Wir beweisen, dass die Kombination von Graphentransformation mit einem hinreichend expressiven Algorithmus zumindest so expressiv wie der dementsprechende GNN mit verbessertem Message Passing ist. Besonders interessant ist die Kombination mit einem MPNN das gleich expressiv wie der Weisfeiler-Leman Test ist: in diesem Fall erhält man ein GNN das zumindest so expressiv wie ein GNN mit verbessertem Message Passing ist, welches aber nur Standard Message Passing verwendet. Darüber hinaus zeigen wir empirisch, dass diese Transformationen konkurrenzfähige Ergebnisse auf Molekül Datensätzen liefern. Schließlich untersuchen wir Ähnlichkeiten zwischen (I) und (IV) in einer häufigen Situation im Zusammenhang mit Cliquen. Wir beweisen, dass in diesem Fall (I) mindestens so expressiv im Unterscheiden von Graphen wie (IV) ist.

We investigate graph neural networks (GNNs) with modified message passing and propose novel graph transformations that allow standard message passing to achieve state-of-the-art expressiveness and predictive performance. Message passing graph neural networks (MPNNs) are known to have limited expressiveness in distinguishing graphs. This means that there exist pairs of graphs for which any MPNN will return the same result. This restricts the functions MPNNs can express and implies that MPNNs are unable to detect many graph structures, for example cyclical subgraphs. However, these structures can contain important information: consider the task of learning properties of molecules, there the cycles in the molecular structure encode important information. Thus, MPNNs are not sufficiently expressive. Formally, we define an algorithm A to be at least as expressive as algorithm B if A can distinguish every pair of graphs that B can distinguish.There is a connection between universality and expressiveness: if an algorithm is able to distinguish all graphs of a certain type, then combining that algorithm with a multilayer perceptron automatically gives us a universal function approximator for these graphs. To make MPNNs more expressive, one can either use an improved variant of message passing or modify the graphs. Changing message passing is powerful but requires significant changes to existing implementations and cannot easily be combined with other approaches. Modifying the graphs requires no changes to the learning algorithm and works directly with off-the-shelf implementations. In this thesis, we investigate four graph neural networks that are based on MPNNs. Three GNNs that can be seen as modifying message passing: (I) CW Networks,(II) Equivariant Subgraph Aggregation Networks and (III) (local) δ-k-dimensional WL. One GNN that can be seen as applying a graph transformation: (IV) MPNNs with homomorphism counts. We propose novel graph transformations for (I), (II), (III) and compare them to the state-of-the-art. We prove that combining each of the graph transformations with a suitably expressive algorithm is at least as expressive as the corresponding GNN with modified message passing. By combining the graph transformation with an MPNN that is as expressive as the Weisfeiler-Leman test, one obtains a GNN that is as expressive as a GNN with modified message passing but without modifying message passing. Furthermore, we empirically demonstrate that these transformations lead to competitive results on molecular graph datasets. Finally, we investigate similarities between (I) and (IV) in a common situation relating to cliques. We prove that in this case (I) is at least as expressive as (IV) when it comes to distinguishing graphs.