On the Performance of Message Passing Neural Networks in Standard Graph Datasets
1-WL Expressiveness Is (Almost) All You Need
It has been shown that a message passing neural networks (mpnns), a popular family of neural networks for graph-structured data, are at most as expressiveas the first-order weisfeiler-leman (1-wl) graph isomorphism test, which has motivated the development of more expressive architectures.In this work, we analyze if the limited expressiveness is actually a limiting factor for mpnnsand other first-order wl-based models in standard graph datasets.We find that the expressiveness of wl is sufficient to identify almost all graphs in most datasets.Moreover, we find that the classification accuracy upper boundsare often close to 100\%.Furthermore, we find that simple wl-based neuralnetworks and several mpnns can be fitted to several datasets.We conclude that the performance of wl/mpnns is not limited by their expressiveness in practice.
