1-WL Expressiveness Is (Almost) All You Need
This work addresses the practical relevance of expressiveness limitations for graph neural networks, suggesting that incremental improvements may not be necessary for many real-world datasets.
The authors investigated whether the limited expressiveness of message passing neural networks (MPNNs) and Weisfeiler-Leman (WL)-based models is a practical bottleneck in standard graph datasets, finding that WL expressiveness is sufficient to identify almost all graphs and classification accuracy upper bounds are often close to 100%.
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 expressive as 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 MPNNs and other WL-based models in standard graph datasets. Interestingly, 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 bounds are often close to 100\%. Furthermore, we find that simple WL-based neural networks and several MPNNs can be fitted to several datasets. In sum, we conclude that the performance of WL/MPNNs is not limited by their expressiveness in practice.