  Subgraph Graph Neural Networks (Subgraph GNNs) enhance the expressivity of
message-passing GNNs by representing graphs as sets of subgraphs. They have
shown impressive performance on several tasks, but their complexity limits
applications to larger graphs. Previous approaches suggested processing only
subsets of subgraphs, selected either randomly or via learnable sampling.
However, they make suboptimal subgraph selections or can only cope with very
small subset sizes, inevitably incurring performance degradation. This paper
introduces a new Subgraph GNNs framework to address these issues. We employ a
graph coarsening function to cluster nodes into super-nodes with induced
connectivity. The product between the coarsened and the original graph reveals
an implicit structure whereby subgraphs are associated with specific sets of
nodes. By running generalized message-passing on such graph product, our method
effectively implements an efficient, yet powerful Subgraph GNN. Controlling the
coarsening function enables meaningful selection of any number of subgraphs
while, contrary to previous methods, being fully compatible with standard
training techniques. Notably, we discover that the resulting node feature
tensor exhibits new, unexplored permutation symmetries. We leverage this
structure, characterize the associated linear equivariant layers and
incorporate them into the layers of our Subgraph GNN architecture. Extensive
experiments on multiple graph learning benchmarks demonstrate that our method
is significantly more flexible than previous approaches, as it can seamlessly
handle any number of subgraphs, while consistently outperforming baseline
approaches.
