Weisfeiler and Leman Go Loopy: A New Hierarchy for Graph Representational Learning

For example, in organic chemistry or bioinformatics, different types of cycles can impact We introduce r-loopy Weisfeiler-Leman (r-lWL), various chemical properties of the underlying molecules a novel hierarchy of graph isomorphism tests and (Deshpande et al., 2002; Koyutürk et al., 2004). Therefore, a corresponding GNN framework, r-lMPNN, that it is crucial to investigate whether GNNs can count certain can count cycles up to length r + 2. Most notably, substructures and to design architectures that surpass the we show that r-lWL can count homomorphisms limited power of MPNNs. of cactus graphs. This strictly extends classical Many models have been proposed to match or surpass the 1-WL, which can only count homomorphisms of expressive power of WL. Several draw inspiration from trees and, in fact, is incomparable to k-WL for any higher-order variants of the WL algorithm (Morris et al., fixed k. We empirically validate the expressive 2019), enabling them to count a broader range of substructures.