  While message passing Graph Neural Networks (GNNs) have become increasingly
popular architectures for learning with graphs, recent works have revealed
important shortcomings in their expressive power. In response, several
higher-order GNNs have been proposed that substantially increase the expressive
power, albeit at a large computational cost. Motivated by this gap, we explore
alternative strategies and lower bounds. In particular, we analyze a new
recursive pooling technique of local neighborhoods that allows different
tradeoffs of computational cost and expressive power. First, we prove that this
model can count subgraphs of size $k$, and thereby overcomes a known limitation
of low-order GNNs. Second, we show how recursive pooling can exploit sparsity
to reduce the computational complexity compared to the existing higher-order
GNNs. More generally, we provide a (near) matching information-theoretic lower
bound for counting subgraphs with graph representations that pool over
representations of derived (sub-)graphs. We also discuss lower bounds on time
complexity.
