# Neural Subgraph Isomorphism Counting

arXiv: https://arxiv.org/abs/1912.11589 · HTML: https://mlsanity.com/paper/1912.11589/

## Key facts

- Cited by 27 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Dec 2019.

## Built on by (most cited first, 27 of 27)

- [Theory of Graph Neural Networks: Representation and Learning](https://mlsanity.com/paper/2204.07697/) (2022)
- [GREED: A Neural Framework for Learning Graph Distance Functions](https://mlsanity.com/paper/2112.13143/) (2021)
- [Algorithm and System Co-design for Efficient Subgraph-based Graph Representation Learning](https://mlsanity.com/paper/2202.13538/) (2022)
- [Complex Query Answering on Eventuality Knowledge Graph with Implicit Logical Constraints](https://mlsanity.com/paper/2305.19068/) (2023)
- [On Structural Expressive Power of Graph Transformers](https://mlsanity.com/paper/2305.13987/) (2023)
- [MentorGNN: Deriving Curriculum for Pre-Training GNNs](https://mlsanity.com/paper/2208.09905/) (2022)
- [Boosting Graph Structure Learning with Dummy Nodes](https://mlsanity.com/paper/2206.08561/) (2022)
- [Learning to Count Isomorphisms with Graph Neural Networks](https://mlsanity.com/paper/2302.03266/) (2023)
- [An Efficient Subgraph GNN with Provable Substructure Counting Power](https://mlsanity.com/paper/2303.10576/) (2023)
- [Graph Convolutional Networks with Dual Message Passing for Subgraph Isomorphism Counting and Matching](https://mlsanity.com/paper/2112.08764/) (2021)
- [Enhancing User Intent Capture in Session-Based Recommendation with Attribute Patterns](https://mlsanity.com/paper/2312.16199/) (2023)
- [SUREL+: Moving from Walks to Sets for Scalable Subgraph-based Graph Representation Learning](https://mlsanity.com/paper/2303.03379/) (2023)
- [Reinforcement Learning Based Query Vertex Ordering Model for Subgraph Matching](https://mlsanity.com/paper/2201.11251/) (2022)
- [Graph Neural Networks for Databases: A Survey](https://mlsanity.com/paper/2502.12908/) (2025)
- [Sub-GMN: The Neural Subgraph Matching Network Model](https://mlsanity.com/paper/2104.00186/) (2021)
- [Representation Learning for Frequent Subgraph Mining](https://mlsanity.com/paper/2402.14367/) (2024)
- [DeSCo: Towards Generalizable and Scalable Deep Subgraph Counting](https://mlsanity.com/paper/2308.08198/) (2023)
- [Towards Accurate Subgraph Similarity Computation via Neural Graph Pruning](https://mlsanity.com/paper/2210.10643/) (2022)
- [Reinforcement Learning Enhanced Weighted Sampling for Accurate Subgraph Counting on Fully Dynamic Graph Streams](https://mlsanity.com/paper/2211.06793/) (2022)
- [Interactive Visual Pattern Search on Graph Data via Graph Representation Learning](https://mlsanity.com/paper/2202.09459/) (2022)
- [Detecting Small Query Graphs in A Large Graph via Neural Subgraph Search](https://mlsanity.com/paper/2207.10305/) (2022)
- [Graph Self-Supervised Learning with Learnable Structural and Positional Encodings](https://mlsanity.com/paper/2502.16233/) (2025)
- [A Survey on Machine Learning Solutions for Graph Pattern Extraction](https://mlsanity.com/paper/2204.01057/) (2022)
- [Uncertainty-aware Efficient Subgraph Isomorphism using Graph Topology](https://mlsanity.com/paper/2209.09090/) (2022)
- [Towards Subgraph Isomorphism Counting with Graph Kernels](https://mlsanity.com/paper/2405.07497/) (2024)
- [BEACON: A Benchmark for Efficient and Accurate Counting of Subgraphs](https://mlsanity.com/paper/2504.10948/) (2025)
- [Target Circuit Matching in Large-Scale Netlists using GNN-Based Region Prediction](https://mlsanity.com/paper/2507.19518/) (2025)

## Abstract (arXiv)

In this paper, we study a new graph learning problem: learning to count subgraph isomorphisms. Different from other traditional graph learning problems such as node classification and link prediction, subgraph isomorphism counting is NP-complete and requires more global inference to oversee the whole graph. To make it scalable for large-scale graphs and patterns, we propose a learning framework which augments different representation learning architectures and iteratively attends pattern and target data graphs to memorize subgraph isomorphisms for the global counting. We develop both small graphs (<= 1,024 subgraph isomorphisms in each) and large graphs (<= 4,096 subgraph isomorphisms in each) sets to evaluate different models. A mutagenic compound dataset, MUTAG, is also used to evaluate neural models and demonstrate the success of transfer learning. While the learning based approach is inexact, we are able to generalize to count large patterns and data graphs in linear time compared to the exponential time of the original NP-complete problem. Experimental results show that learning based subgraph isomorphism counting can speed up the traditional algorithm, VF2, 10-1,000 times with acceptable errors. Domain adaptation based on fine-tuning also shows the usefulness of our approach in real-world applications.