Approximate neural subgraph counting for similar queries

Existing work on approximate subgraph counting mainly focuses on isolate-query settings, where queries are independent. However, in some scenarios, similar queries can be processed frequently due to user preferences or application requirements. The approximate subgraph counting problem in similar query scenarios has not been studied yet. In this paper, we study the approximate subgraph counting problem in similar query scenarios and propose a lightweight learning-based subgraph counting framework, SubMB, to solve this problem. SubMB can estimate the count for arbitrary-size similar query patterns effectively within polynomial time complexity, and avoids complicated computations on the data graph. SubMB adopts a multi-level substructure extraction method and an edge-based query transformation method to get information related to the count and uses a graph attention blocks estimator to estimate query counts. We conduct extensive experiments on 7 real-world datasets with varying sizes ranging from 10³ to 10⁶ to evaluate the effectiveness and efficiency of SubMB. The experimental results show that SubMB can reduce the q-error by 1-3 orders of magnitude on multiple percentiles (including the median, 75%, 85%, 90% percentile) and by 35%–72% on the max q-error compared to the baseline methods. In addition, SubMB can reduce the offline training time by 79%–98% compared to the state-of-the-art methods.