DeSCo: Towards Generalizable and Scalable Deep Subgraph Counting
This addresses the challenge of scalable and generalizable subgraph counting for applications in network analysis, with incremental improvements in accuracy and efficiency.
The paper tackles the problem of subgraph counting in large graphs by introducing DeSCo, a neural pipeline that predicts both count and occurrence positions with a single training, achieving a 137x improvement in mean squared error over state-of-the-art neural methods while maintaining polynomial runtime.
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.