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.

增强 Weisfeiler-Leman 算法和消息传递图神经网络的表达力的关系对于改进概括能力的条件是不明确的。通过引入子图信息和经典边界理论来探索这种表达力增强和概括能力改善的条件，并提出具有可证明概括性质的基于 $1$-WL 的核和消息传递图神经网络架构的变体。