Weisfeiler-Leman at the margin: When more expressivity matters
Billy J. Franks Christopher Morris Ameya Velingker Floris Geerts
The Weisfeiler-Leman algorithm ($1$-WL) is a well-studied heuristic for the
graph isomorphism problem. Recently, the algorithm has played a prominent role
in understanding the expressive power of message-passing graph neural networks
(MPNNs) and being effective as a graph kernel. Despite its success, $1$-WL
faces challenges in distinguishing non-isomorphic graphs, leading to the
development of more expressive MPNN and kernel architectures. However, the
relationship between enhanced expressivity and improved generalization
performance remains unclear. Here, we show that an architecture's expressivity
offers limited insights into its generalization performance when viewed through
graph isomorphism. Moreover, we focus on augmenting $1$-WL and MPNNs with
subgraph information and employ classical margin theory to investigate the
conditions under which an architecture's increased expressivity aligns with
improved generalization performance. In addition, we show that gradient flow
pushes the MPNN's weights toward the maximum margin solution. Further, we
introduce variations of expressive $1$-WL-based kernel and MPNN architectures
with provable generalization properties. Our empirical study confirms the
validity of our theoretical findings.