  We investigate the enhancement of graph neural networks' (GNNs)
representation power through their ability in substructure counting. Recent
advances have seen the adoption of subgraph GNNs, which partition an input
graph into numerous subgraphs, subsequently applying GNNs to each to augment
the graph's overall representation. Despite their ability to identify various
substructures, subgraph GNNs are hindered by significant computational and
memory costs. In this paper, we tackle a critical question: Is it possible for
GNNs to count substructures both \textbf{efficiently} and \textbf{provably}?
Our approach begins with a theoretical demonstration that the distance to
rooted nodes in subgraphs is key to boosting the counting power of subgraph
GNNs. To avoid the need for repetitively applying GNN across all subgraphs, we
introduce precomputed structural embeddings that encapsulate this crucial
distance information. Experiments validate that our proposed model retains the
counting power of subgraph GNNs while achieving significantly faster
performance.
