  Recently, subgraph GNNs have emerged as an important direction for developing
expressive graph neural networks (GNNs). While numerous architectures have been
proposed, so far there is still a limited understanding of how various design
paradigms differ in terms of expressive power, nor is it clear what design
principle achieves maximal expressiveness with minimal architectural
complexity. To address these fundamental questions, this paper conducts a
systematic study of general node-based subgraph GNNs through the lens of
Subgraph Weisfeiler-Lehman Tests (SWL). Our central result is to build a
complete hierarchy of SWL with strictly growing expressivity. Concretely, we
prove that any node-based subgraph GNN falls into one of the six SWL
equivalence classes, among which $\mathsf{SSWL}$ achieves the maximal
expressive power. We also study how these equivalence classes differ in terms
of their practical expressiveness such as encoding graph distance and
biconnectivity. Furthermore, we give a tight expressivity upper bound of all
SWL algorithms by establishing a close relation with localized versions of WL
and Folklore WL (FWL) tests. Our results provide insights into the power of
existing subgraph GNNs, guide the design of new architectures, and point out
their limitations by revealing an inherent gap with the 2-FWL test. Finally,
experiments demonstrate that $\mathsf{SSWL}$-inspired subgraph GNNs can
significantly outperform prior architectures on multiple benchmarks despite
great simplicity.
