Weisfeiler and Leman Return with Graph Transformations

Abstract

We propose novel graph transformations that allow standard message passing to achieve state-of-the-art expressiveness and predictive performance. Message passing graph neural networks are known to have limited expressiveness in distinguishing graphs. To mitigate this, one can either change 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 graph requires no changes to the learning algorithm and works directly with off-the-shelf implementations. In this paper, we propose novel graph transformations and compare them to the state-of-the-art. We prove that they are at least as expressive as corresponding message passing algorithms when combined with the Weisfeiler-Leman test or a sufficiently powerful graph neural network. Furthermore, we empirically demonstrate that these transformations lead to competitive results on molecular graph datasets.