Timezone: »

 
Poster
Understanding and Extending Subgraph GNNs by Rethinking Their Symmetries
Fabrizio Frasca · Beatrice Bevilacqua · Michael Bronstein · Haggai Maron

Thu Dec 01 02:00 PM -- 04:00 PM (PST) @ Hall J #939
in Poster Session 6 »

Subgraph GNNs are a recent class of expressive Graph Neural Networks (GNNs) which model graphs as collections of subgraphs. So far, the design space of possible Subgraph GNN architectures as well as their basic theoretical properties are still largely unexplored. In this paper, we study the most prominent form of subgraph methods, which employs node-based subgraph selection policies such as ego-networks or node marking and deletion. We address two central questions: (1) What is the upper-bound of the expressive power of these methods? and (2) What is the family of equivariant message passing layers on these sets of subgraphs?. Our first step in answering these questions is a novel symmetry analysis which shows that modelling the symmetries of node-based subgraph collections requires a significantly smaller symmetry group than the one adopted in previous works. This analysis is then used to establish a link between Subgraph GNNs and Invariant Graph Networks (IGNs). We answer the questions above by first bounding the expressive power of subgraph methods by 3-WL, and then proposing a general family of message-passing layers for subgraph methods that generalises all previous node-based Subgraph GNNs. Finally, we design a novel Subgraph GNN dubbed SUN, which theoretically unifies previous architectures while providing better empirical performance on multiple benchmarks.

Keywords: Equivariance · graph neural networks · subgraphs · Expressive Power · Weisfeiler-Leman

Author Information

Fabrizio Frasca (Imperial College London Twitter)
Beatrice Bevilacqua (Purdue University)
Michael Bronstein (USI)
Haggai Maron (NVIDIA Research)

I am a PhD student at the Department of Computer Science and Applied Mathematics at the Weizmann Institute of Science under the supervision of Prof. Yaron Lipman. My main fields of interest are machine learning, optimization and shape analysis. More specifically I am working on applying deep learning to irregular domains (e.g., graphs, point clouds, and surfaces) and graph/shape matching problems. I serve as a reviewer for NeurIPS, ICCV, SIGGRAPH, SIGGRAPH Asia, ACM TOG, JAIR, TVCG and SGP.

More from the Same Authors