LearnSC: An Efficient and Unified Learning-Based Framework for Subgraph Counting Problem

Graphs are valuable data structures used to represent complex relationships between entities in a wide range of applications, such as social networks and chemical reactions. Subgraph counting problem is a well-known hard problem, as its core subroutine, the subgraph matching, is NP-complete. In this work, we propose an efficient and unified deep learning-based solution framework LearnSC, which solves the subgraph counting problem approximately. This framework offers two key advantages: (i) it is a generic solution that is orthogonal to the existing techniques of learning-based solutions; and (ii) it is equipped with a suite of optimizations to significantly improve the accuracy of the estimated results. Our experimental results on 7 datasets demonstrate that our proposal is highly accurate, robust, and scalable, making it an excellent solution for subgraph counting problem among all statistics-based and learning-based competitors.