Weisfeiler-Leman at the margin: When more expressivity matters
CoRR(2024)
摘要
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.
更多查看译文
AI 理解论文
溯源树
样例
生成溯源树,研究论文发展脉络
Chat Paper
正在生成论文摘要