Message Passing on the Edge: Towards Scalable and Expressive GNNs

Graph learning, and in particular message-passing graph neural networks (GNNs), have emerged as a fundamental tool across the sciences (Scarselli et al., 2009; Kipf & Welling, 2017; Wu et al., 2019). A major factor in the wide applicability of GNNs is the robust theoretical framework that grounds their study in principled comparisons between architectures. Core to this framework is the characterization of the expressive power of GNNs in terms of the Weisfeiler-Leman (1WL) test, a central notion in the theoretical study of graph similarity (Morris et al., 2019; Xu et al., 2019). Owing to this connection, alternative, yet equally insightful, characterizations of GNN expressive power have been developed--such as via finite-variable fragments of counting logics (Cai et al., 1992) or homomorphism counts from classes of graphs of bounded treewidth (Dvor ak, 2010; Dell et al., 2018). While these perspectives enrich our understanding of GNN capabilities, they also make clear that 1WL-based GNNs remain limited in important ways. To highlight the necessity for more expressive tests than 1WL, an illustrative limitation of 1WL-based GNNs is their inability to detect small motifs or count triangles (Chen et al., 2020; Arvind et al., 2020; Lanzinger & Barcel o, 2024). The higher-order WL hierarchy offers a systematic remedy: properties that elude 1WL are often captured at some higher level, i.e., by kWL for some k > 1. Yet this increase in expressive power comes at a steep computational cost.