Extending the Design Space of Graph Neural Networks by Rethinking Folklore Weisfeiler-Lehman

Message passing neural networks (MPNNs) have emerged as the most popular framework of graph neural networks (GNNs) in recent years. However, their expressive power is limited by the 1-dimensional Weisfeiler-Lehman (1-WL) test. Some works are inspired by k -WL/FWL (Folklore WL) and design the corresponding neural versions. Despite the high expressive power, there are serious limitations in this line of research. In particular, (1) k -WL/FWL requires at least O(n k) space complexity, which is impractical for large graphs even when k 3; (2) The design space of k -WL/FWL is rigid, with the only adjustable hyper-parameter being k .