WL meet VC
Jul 24, 2023
Speakers
Christopher Morris
Speaker Β· 0 followers
Floris Geerts
Speaker Β· 0 followers
Jan Tonshoff
Speaker Β· 0 followers
Martin Grohe
Speaker Β· 0 followers
About
Recently, many works studied the expressive power of graph neural networks (GNNs) by linking it to the 1-dimensional Weisfeiler-Leman algorithm (1-πΆπ«). Here, the 1-πΆπ« is a well-studied heuristic for the graph isomorphism problem, which iteratively colors or partitions a graph's vertex set. While this connection has led to significant advances in understanding and enhancing GNNs' expressive power, it does not provide insights into their generalization performance, i.e., their ability to make meaningful predictions beyond the training set. In this paper, we study GNNs' generalization ability through the lens of Vapnik-Chervonenkis (VC) dimension theory in two settings, focusing on graph-level predictions. First, when no upper bound on the graphs' order is known, we show that the bitlength of GNNs' weights tightly bounds their VC dimension. Further, we derive an upper bound for GNNs' VC dimension using the number of colors produced by the 1-πΆπ«. Secondly, when an upper bound on the graphs' order is known, we show a tight connection between the number of graphs distinguishable by the 1-πΆπ« and GNNs' VC dimension. Our empirical study confirms the validity of our theoretical findings.Recently, many works studied the expressive power of graph neural networks (GNNs) by linking it to the 1-dimensional Weisfeiler-Leman algorithm (1-πΆπ«). Here, the 1-πΆπ« is a well-studied heuristic for the graph isomorphism problem, which iteratively colors or partitions a graph's vertex set. While this connection has led to significant advances in understanding and enhancing GNNs' expressive power, it does not provide insights into their generalization performance, i.e., their ability to makeβ¦
Like the format? Trust SlidesLive to capture your next event!
Professional recording and live streaming, delivered globally.
Sharing
Recommended Videos
Presentations on similar topic, category or speaker
Adversarial robustness of amortized Bayesian inference
Watch later
Manuel Gloeckler, β¦
Spherical Fourier Neural Operators: Learning Stable Dynamics on the Sphere
Watch later
Boris Bonev, β¦
Learning Regions of Interest for Bayesian Optimization with Adaptive Level-Set Estimation
Watch later
Fengxue Zhang, β¦
Rethinking Explaining Graph Neural Networks via Non-parametric Subgraph Matching
Watch later
Fang Wu, β¦
