  Message passing neural networks (MPNNs) have become a dominant flavor of
graph neural networks (GNNs) in recent years. Yet, MPNNs come with notable
limitations; namely, they are at most as powerful as the 1-dimensional
Weisfeiler-Leman (1-WL) test in distinguishing graphs in a graph isomorphism
testing frame-work. To this end, researchers have drawn inspiration from the
k-WL hierarchy to develop more expressive GNNs. However, current
k-WL-equivalent GNNs are not practical for even small values of k, as k-WL
becomes combinatorially more complex as k grows. At the same time, several
works have found great empirical success in graph learning tasks without highly
expressive models, implying that chasing expressiveness with a coarse-grained
ruler of expressivity like k-WL is often unneeded in practical tasks. To truly
understand the expressiveness-complexity tradeoff, one desires a more
fine-grained ruler, which can more gradually increase expressiveness. Our work
puts forth such a proposal: Namely, we first propose the (k, c)(<=)-SETWL
hierarchy with greatly reduced complexity from k-WL, achieved by moving from
k-tuples of nodes to sets with <=k nodes defined over <=c connected components
in the induced original graph. We show favorable theoretical results for this
model in relation to k-WL, and concretize it via (k, c)(<=)-SETGNN, which is as
expressive as (k, c)(<=)-SETWL. Our model is practical and
progressively-expressive, increasing in power with k and c. We demonstrate
effectiveness on several benchmark datasets, achieving several state-of-the-art
results with runtime and memory usage applicable to practical graphs. We open
source our implementation at https://github.com/LingxiaoShawn/KCSetGNN.
