A Neural Subgraph Counting Method Based on Matching Matrix
摘要
Subgraph counting aims to compute the number of subgraphs in a data graph \( G \) that match a given query graph \( q \) , which has been applied in various fields such as bioinformatics, data mining, and social network analysis. Early methods fundamentally rely on enumerating all possible subgraphs, but they face high computational costs because enumerating all possible subgraphs is an NP-complete problem. To reduce complexity, the approximate method has gained attention, as in many cases, approximate counts are sufficient for decision-making or identifying trends. Recently, researchers have begun applying GNNs to approximate subgraph counting tasks, yet existing GNN-based methods suffer from inefficiencies caused by unpromising data vertices and limited use of the matching information between query and data vertices. To address these challenges, we propose a Neural Subgraph Counting method based on Matching Matrix, namely MMNSC, which consists of two key components: (1) Candidates Extraction, which retrieves candidate substructures from data graph using a new filtering method, and (2) Matching Matrix Estimator, a learning-based estimator that generates a matching matrix between query graph and data graph. Through experiments on five real-world data graphs, MMNSC demonstrates superior performance over existing state-of-the-art methods.