Weisfeiler and Leman Go Infinite: Spectral and Combinatorial Pre-Colorings

Abstract

The limit in the expressivity of Message Passing Graph Neural Networks (MPGNNs) has recently led to the development of end-to-end learning GNN architectures. These advanced GNNs usually generalize existing notions in the GNN architecture or suggest new ones that break the limit of the existing, relatively simple MPGNNs. In this paper, we focus on a different solution, the two-phase approach (or pre-coloring), which enables to use of the same simple MPGNNs while improving their expressivity. We prove that using pre-colorings could strictly increase the expressivity of MPGNNs ad infinitum. We also suggest new pre-coloring based on the spectral decomposition of the graph Laplacian and prove that it strictly improves the expressivity of standard MPGNNs. An extensive evaluation of the proposed method with different MPGNN models on various graph classification and node property prediction datasets consistently outperforms previous pre-coloring strategies. The code to reproduce our experiments is available at \url{https://github.com/TPFI22/Spectral-and-Combinatorial}.