Understanding and Extending Subgraph GNNs by Rethinking Their Symmetries
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.