DSCM: A Dominance-Based Subgraph Counting Method

Graphs are widely used to represent vertices and their relationships, with the subgraph counting problem being a crucial challenge in network analysis. Originating from subgraph matching, this problem aims to efficiently determine the number of subgraphs in a data graph that are isomorphic to a given query graph. Since this task is NP-hard, existing approaches are typically divided into exact and approximate methods. Exact methods compute the precise number of isomorphic subgraphs but incur prohibitive computational costs on large graphs. Approximate methods, often based on Graph Neural Networks (GNNs), estimate the subgraph count more efficiently but tend to suffer when there is a large size discrepancy between the data graph and the query graph, leading to inaccurate vertex matching. To address these limitations, we propose a domination-based subgraph counting method (DSCM), which improves vertex matching by using a vertex dominance embedding method. This approach, combined with an attention mechanism, accurately computes subgraph counts. Experimental results show that DSCM outperforms existing methods, providing an efficient solution for subgraph counting in large graphs.