A Practical, Progressively-Expressive GNN

Message passing neural networks (MPNNs) have become a dominant flavor of graph neural networks (GNNs) in recent years. Y et, MPNNs come with notable limitations; namely, they are at most as powerful as the 1-dimensional Weisfeiler-Leman (1-WL) test in distinguishing graphs in a graph isomorphism testing framework. To this end, researchers have drawn inspiration from the k -WL hierarchy to develop more expressive GNNs. However, current k -WL-equivalent GNNs are not practical for even small values of k, as k -WL becomes combinatorially more complex as k grows. At the same time, several works have found great empirical success in graph learning tasks without highly expressive models, implying that chasing expressiveness with a "coarse-grained ruler" of expressivity like k -WL is often unneeded in practical tasks. To truly understand the expressiveness-complexity tradeoff, one desires a more "fine-grained ruler, " which can more gradually increase expressiveness.