Subgraph counting is the problem of counting the occurrences of a given query
graph in a large target graph. Large-scale subgraph counting is useful in
various domains, such as motif counting for social network analysis and loop
counting for money laundering detection on transaction networks. Recently, to
address the exponential runtime complexity of scalable subgraph counting,
neural methods are proposed. However, existing neural counting approaches fall
short in three aspects. Firstly, the counts of the same query can vary from
zero to millions on different target graphs, posing a much larger challenge
than most graph regression tasks. Secondly, current scalable graph neural
networks have limited expressive power and fail to efficiently distinguish
graphs in count prediction. Furthermore, existing neural approaches cannot
predict the occurrence position of queries in the target graph.
Here we design DeSCo, a scalable neural deep subgraph counting pipeline,
which aims to accurately predict the query count and occurrence position on any
target graph after one-time training. Firstly, DeSCo uses a novel canonical
partition and divides the large target graph into small neighborhood graphs.
The technique greatly reduces the count variation while guaranteeing no missing
or double-counting. Secondly, neighborhood counting uses an expressive
subgraph-based heterogeneous graph neural network to accurately perform
counting 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.

设计了 DeSCo，一种可扩展的神经深度子图计数流水线，通过一次训练准确地预测任何目标图中查询计数和发生位置，在计数预测的均方误差方面，优于现有的神经方法，同时保持多项式运行时间复杂度。