# Learning to Count Isomorphisms with Graph Neural Networks

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 37 of its 66 references that are in the map.
- First posted on arXiv 7 Feb 2023.

## Builds on (most cited first, 30 of 37)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [Empirical Evaluation of Gated Recurrent Neural Networks on Sequence Modeling](https://mlsanity.com/paper/1412.3555/) (2014)
- [FiLM: Visual Reasoning with a General Conditioning Layer](https://mlsanity.com/paper/1709.07871/) (2017)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [node2vec: Scalable Feature Learning for Networks](https://mlsanity.com/paper/1607.00653/) (2016)
- [Modeling Relational Data with Graph Convolutional Networks](https://mlsanity.com/paper/1703.06103/) (2017)
- [HyperNetworks](https://mlsanity.com/paper/1609.09106/) (2016)
- [Hierarchical Graph Representation Learning with Differentiable Pooling](https://mlsanity.com/paper/1806.08804/) (2018)
- [Heterogeneous Graph Attention Network](https://mlsanity.com/paper/1903.07293/) (2019)
- [LINE: Large-scale Information Network Embedding](https://mlsanity.com/paper/1503.03578/) (2015)
- [Object Detection with Deep Learning: A Review](https://mlsanity.com/paper/1807.05511/) (2018)
- [Self-Attention Graph Pooling](https://mlsanity.com/paper/1904.08082/) (2019)
- [Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting](https://mlsanity.com/paper/2006.09252/) (2020)
- [Can Graph Neural Networks Count Substructures?](https://mlsanity.com/paper/2002.04025/) (2020)
- [Graph Matching Networks for Learning the Similarity of Graph Structured Objects](https://mlsanity.com/paper/1904.12787/) (2019)
- [Learning Combinatorial Embedding Networks for Deep Graph Matching](https://mlsanity.com/paper/1904.00597/) (2019)
- [MotifNet: a motif-based Graph Convolutional Network for directed graphs](https://mlsanity.com/paper/1802.01572/) (2018)
- [Graph Few-shot Learning via Knowledge Transfer](https://mlsanity.com/paper/1910.03053/) (2019)
- [Learning-based Efficient Graph Similarity Computation via Multi-Scale Convolutional Set Matching](https://mlsanity.com/paper/1809.04440/) (2018)
- [EdgeNets:Edge Varying Graph Neural Networks](https://mlsanity.com/paper/2001.07620/) (2020)
- [Co-embedding of Nodes and Edges with Graph Neural Networks](https://mlsanity.com/paper/2010.13242/) (2020)
- [Neural Subgraph Isomorphism Counting](https://mlsanity.com/paper/1912.11589/) (2019)
- [Combinatorial Learning of Graph Edit Distance via Dynamic Embedding](https://mlsanity.com/paper/2011.15039/) (2020)
- [GLSearch: Maximum Common Subgraph Detection via Learning to Search](https://mlsanity.com/paper/2002.03129/) (2020)
- [Dual-Primal Graph Convolutional Networks](https://mlsanity.com/paper/1806.00770/) (2018)

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

- [GraphPrompt: Unifying Pre-Training and Downstream Tasks for Graph Neural Networks](https://mlsanity.com/paper/2302.08043/) (2023)
- [SAMGPT: Text-free Graph Foundation Model for Multi-domain Pre-training and Cross-domain Adaptation](https://mlsanity.com/paper/2502.05424/) (2025)
- [Generalized Graph Prompt: Toward a Unification of Pre-Training and Downstream Tasks on Graphs](https://mlsanity.com/paper/2311.15317/) (2023)
- [HGCLIP: Exploring Vision-Language Models with Graph Representations for Hierarchical Understanding](https://mlsanity.com/paper/2311.14064/) (2023)
- [A Survey of Imbalanced Learning on Graphs: Problems, Techniques, and Future Directions](https://mlsanity.com/paper/2308.13821/) (2023)
- [Node-Time Conditional Prompt Learning In Dynamic Graphs](https://mlsanity.com/paper/2405.13937/) (2024)
- [GCoT: Chain-of-Thought Prompt Learning for Graphs](https://mlsanity.com/paper/2502.08092/) (2025)
- [A Survey of Few-Shot Learning on Graphs: from Meta-Learning to Pre-Training and Prompt Learning](https://mlsanity.com/paper/2402.01440/) (2024)
- [Graph Neural Networks for Databases: A Survey](https://mlsanity.com/paper/2502.12908/) (2025)
- [Incomplete Graph Learning: A Comprehensive Survey](https://mlsanity.com/paper/2502.12412/) (2025)
- [Expressivity of Graph Neural Networks Through the Lens of Adversarial Robustness](https://mlsanity.com/paper/2308.08173/) (2023)
- [Towards Subgraph Isomorphism Counting with Graph Kernels](https://mlsanity.com/paper/2405.07497/) (2024)
- [Heterogeneous Graph Alignment for Joint Reasoning and Interpretability](https://mlsanity.com/paper/2601.22593/) (2026)

## Abstract (arXiv)

Subgraph isomorphism counting is an important problem on graphs, as many graph-based tasks exploit recurring subgraph patterns. Classical methods usually boil down to a backtracking framework that needs to navigate a huge search space with prohibitive computational costs. Some recent studies resort to graph neural networks (GNNs) to learn a low-dimensional representation for both the query and input graphs, in order to predict the number of subgraph isomorphisms on the input graph. However, typical GNNs employ a node-centric message passing scheme that receives and aggregates messages on nodes, which is inadequate in complex structure matching for isomorphism counting. Moreover, on an input graph, the space of possible query graphs is enormous, and different parts of the input graph will be triggered to match different queries. Thus, expecting a fixed representation of the input graph to match diversely structured query graphs is unrealistic. In this paper, we propose a novel GNN called Count-GNN for subgraph isomorphism counting, to deal with the above challenges. At the edge level, given that an edge is an atomic unit of encoding graph structures, we propose an edge-centric message passing scheme, where messages on edges are propagated and aggregated based on the edge adjacency to preserve fine-grained structural information. At the graph level, we modulate the input graph representation conditioned on the query, so that the input graph can be adapted to each query individually to improve their matching. Finally, we conduct extensive experiments on a number of benchmark datasets to demonstrate the superior performance of Count-GNN.