On the Expressive Power of Geometric Graph Neural Networks | Chaitanya K. Joshi & Simon V. Mathis

Join the Learning on Graphs and Geometry Reading Group: https://hannes-stark.com/logag-reading-group Paper: "On the Expressive Power of Geometric Graph Neural Networks" https://arxiv.org/abs/2301.09308 Abstract: The expressive power of Graph Neural Networks (GNNs) has been studied extensively through the Weisfeiler-Leman (WL) graph isomorphism test. Yet, many graphs in science and engineering come embedded in Euclidean space with an additional notion of geometric isomorphism, which is not covered by the WL framework. In this work, we propose a geometric version of the WL test (GWL) for discriminating geometric graphs while respecting the underlying physical symmetries: permutations, rotation, reflection, and translation. We use GWL to characterise the expressive power of geometric GNNs that are invariant or equivariant to physical symmetries in terms of distinguishing geometric graphs. Our framework formalises how key design choices influence geometric GNN expressivity: (1) Invariant layers have limited expressivity as they cannot distinguish one-hop similar geometric graphs; (2) Equivariant layers distinguish a larger class of graphs by propagating geometric information beyond local neighbourhoods. Synthetic experiments supplement our theory and highlight the need for higher order order tensors and scalarisation in geometric GNNs. Authors: Chaitanya K. Joshi, Cristian Bodnar, Simon V. Mathis, Taco Cohen, Pietro Liò Speakers: Chaitanya K. Joshi - https://twitter.com/chaitjo Simon V. Mathis - https://twitter.com/SimMat20 Twitter Hannes: https://twitter.com/HannesStaerk Twitter Dominique: https://twitter.com/dom_beaini Twitter Valence Discovery: https://twitter.com/valence_ai Reading Group Slack: https://join.slack.com/t/logag/shared_invite/zt-u0mbo1ec-zElmvd1oSCXGjXvxLSokvg ~ Chapters 00:00 - Intro 03:14 - Types of GNN 4:28 - Key Takeaways 10:01 - Background: GNNs for Geometric Graphs 27:12 - Geometric Weisfeiler-Leman Test 55:47 - Synthetic Experiments on Geometric GNN Espressivity 01:05:50 - Conclusion and Summary 01:08:09 - Q+A