  We introduce DeSCo, a scalable neural deep subgraph counting pipeline,
designed to accurately predict both the count and occurrence position of
queries on target graphs post single training. Firstly, DeSCo uses a novel
canonical partition and divides the large target graph into small neighborhood
graphs, greatly reducing the count variation while guaranteeing no missing or
double-counting. Secondly, neighborhood counting uses an expressive
subgraph-based heterogeneous graph neural network to accurately count in each
neighborhood. Finally, gossip propagation propagates neighborhood counts with
learnable gates to harness the inductive biases of motif counts. DeSCo is
evaluated on eight real-world datasets from various domains. It outperforms
state-of-the-art neural methods with 137x improvement in the mean squared error
of count prediction, while maintaining the polynomial runtime complexity. Our
open source project is at https://github.com/fuvty/DeSCo.
