On over-squashing and expressivity: can GNNs mix variables? From theory to physics-inspired solutions


I will discuss how Message Passing Neural Networks (MPNNs) model mixing among features in a graph. I will show that MPNNs need as many layers as the commute time between nodes to model strong mixing. This allows to derive a measure for over-squashing and to clarify how the latter limits the expressivity of MPNNs to learn functions with long-range interactions. I will then discuss a novel paradigm for message-passing that determines “when” messages are being propagated based on the geometry of the data and introduces a delay mechanism to greatly enhance the power of MPNNs to capture long-range interactions achieving superior performance than Graph-Transformers even remaining sub-quadratic.

Friday, October 20, 2023 15:00 Europe/Paris
GReTA seminar
Zoom registration: click here! Please consider joining the meeting already within the 15min prior to the start of the seminar to ensure your setup is functioning properly. You may connect with either the Zoom web or Zoom desktop clients.

Please note that the meeting will be recorded and live-streamed to YouTube:

Francesco Di Giovanni
Francesco Di Giovanni
Research Associate

I am currently a Research Associate at the University of Cambridge, working in Pietro Lio ’s group on Geometric Deep Learning and Graph Neural Networks. Previously, I was a postdoctoral ML Researcher at Twitter Cortex working with Michael Bronstein. I finished my PhD in Mathematics at UCL with a thesis on analysis of singularity formation of rotationally symmetric Ricci Flows. I am now interested in investigating Deep Learning through the lens of Differential Geometry and Physics, with emphasis on graph structured data.