DeSCo: Towards Generalizable and Scalable Deep Subgraph Counting
Tianyu Fu, Chiyue Wei, Yu Wang, Rex Ying · 2024
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 analysis for social network and loop counting for money laundering detection. Recently, to address the exponential runtime complexity of scalable subgraph counting, neural methods are proposed. However, existing approaches fall short in three aspects. Firstly, the subgraph counts vary from zero to millions for different graphs, posing a much larger challenge than regular graph regression tasks. Secondly, current scalable graph neural networks have limited expressive power and fail to efficiently distinguish graphs for count prediction. Furthermore, existing neural approaches cannot predict query occurrence positions.