# DeSCo: Towards Generalizable and Scalable Deep Subgraph Counting

arXiv: https://arxiv.org/abs/2308.08198 · HTML: https://mlsanity.com/paper/2308.08198/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 101 references that are in the map.
- First posted on arXiv 16 Aug 2023.

## Builds on (most cited first, 26 of 26)

- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks](https://mlsanity.com/paper/1810.02244/) (2018)
- [Hierarchical Graph Representation Learning with Differentiable Pooling](https://mlsanity.com/paper/1806.08804/) (2018)
- [Provably Powerful Graph Networks](https://mlsanity.com/paper/1905.11136/) (2019)
- [Revisiting Graph Neural Networks: All We Have is Low-Pass Filters](https://mlsanity.com/paper/1905.09550/) (2019)
- [Can Graph Neural Networks Count Substructures?](https://mlsanity.com/paper/2002.04025/) (2020)
- [Graph Neural Networks with Heterophily](https://mlsanity.com/paper/2009.13566/) (2020)
- [Identity-aware Graph Neural Networks](https://mlsanity.com/paper/2101.10320/) (2021)
- [Higher-order organization of complex networks](https://mlsanity.com/paper/1612.08447/) (2016)
- [Propagation Kernels](https://mlsanity.com/paper/1410.3314/) (2014)
- [k-hop Graph Neural Networks](https://mlsanity.com/paper/1907.06051/) (2019)
- [Neural Subgraph Isomorphism Counting](https://mlsanity.com/paper/1912.11589/) (2019)
- [Scalable motif-aware graph clustering](https://mlsanity.com/paper/1606.06235/) (2016)
- [Graph Convolutional Networks with Dual Message Passing for Subgraph Isomorphism Counting and Matching](https://mlsanity.com/paper/2112.08764/) (2021)
- [Testing for Global Network Structure Using Small Subgraph Statistics](https://mlsanity.com/paper/1710.00862/) (2017)
- [Path Sampling: A Fast and Provable Method for Estimating 4-Vertex Subgraph Counts](https://mlsanity.com/paper/1411.4942/) (2014)
- [ESCAPE: Efficiently Counting All 5-Vertex Subgraphs](https://mlsanity.com/paper/1610.09411/) (2016)
- [Motivo: fast motif counting via succinct color coding and adaptive sampling](https://mlsanity.com/paper/1906.01599/) (2019)
- [A Survey on Subgraph Counting: Concepts, Algorithms and Applications to Network Motifs and Graphlets](https://mlsanity.com/paper/1910.13011/) (2019)
- [Faster motif counting via succinct color coding and adaptive sampling](https://mlsanity.com/paper/2009.03052/) (2020)
- [GraphPi: High Performance Graph Pattern Matching through Effective Redundancy Elimination](https://mlsanity.com/paper/2009.10955/) (2020)
- [GraphZero: Breaking Symmetry for Efficient Graph Mining](https://mlsanity.com/paper/1911.12877/) (2019)
- [DwarvesGraph: A High-Performance Graph Mining System with Pattern Decomposition](https://mlsanity.com/paper/2008.09682/) (2020)

## Built on by (most cited first, 4 of 4)

- [Boosting Graph Pooling with Persistent Homology](https://mlsanity.com/paper/2402.16346/) (2024)
- [Towards A Universal Graph Structural Encoder](https://mlsanity.com/paper/2504.10917/) (2025)
- [Graph Neural Networks for Databases: A Survey](https://mlsanity.com/paper/2502.12908/) (2025)
- [Studying and Improving Graph Neural Network-based Motif Estimation](https://mlsanity.com/paper/2506.15709/) (2025)

## Abstract (arXiv)

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.