Equivariant Subgraph Aggregation Networks – Haggai Maron (NVIDIA Research)

On Sunday 12.12.2021, we will host Haggai Maron from NVIDIA Research.

Zoom:
https://us02web.zoom.us/j/85743049730?pwd=dVNRcVBJRlJxaTkrZzZkdSt1ajlUQT09

Meeting ID: 857 4304 9730
Passcode: 902259

Title: 

Equivariant Subgraph Aggregation Networks

Abstract:
Message-passing neural networks (MPNNs) are the leading architecture for deep learning on graph-structured data, in large part due to their simplicity and scalability. Unfortunately, it was shown that these architectures are limited in their expressive power. This talk will describe a novel framework called Equivariant Subgraph Aggregation Networks (ESAN), which addresses this issue. Our main observation is that while two graphs may not be distinguishable by an MPNN, they often contain distinguishable subgraphs. Hence, we propose to represent each graph as a set of subgraphs derived by predefined policies and to process the set of subgraphs using a suitable equivariant architecture. Theoretically, we develop novel variants of the 1-dimensional Weisfeiler-Leman (1-WL) test for graph isomorphism and prove lower bounds on the expressiveness of ESAN in terms of these new WL variants. We will also see that ESAN performs well on a variety of graph learning benchmarks, outperforming 1-WL bounded graph networks and several recent expressive architectures.

Joint work with Beatrice Bevilacqua, Fabrizio Frasca, Derek Lim, Balasubramaniam Srinivasan, Chen Cai, Gopinath Balamurugan, Michael M. Bronstein