# Towards Subgraph Isomorphism Counting with Graph Kernels

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 19 of its 55 references that are in the map.
- First posted on arXiv 13 May 2024.

## Builds on (most cited first, 19 of 19)

- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Transformer-XL: Attentive Language Models Beyond a Fixed-Length Context](https://mlsanity.com/paper/1901.02860/) (2019)
- [Modeling Relational Data with Graph Convolutional Networks](https://mlsanity.com/paper/1703.06103/) (2017)
- [Graph Convolutional Neural Networks for Web-Scale Recommender Systems](https://mlsanity.com/paper/1806.01973/) (2018)
- [Convolutional Neural Networks for Sentence Classification](https://mlsanity.com/paper/1408.5882/) (2014)
- [Composition-based Multi-Relational Graph Convolutional Networks](https://mlsanity.com/paper/1911.03082/) (2019)
- [Can Graph Neural Networks Count Substructures?](https://mlsanity.com/paper/2002.04025/) (2020)
- [On Valid Optimal Assignment Kernels and Applications to Graph Classification](https://mlsanity.com/paper/1606.01141/) (2016)
- [Neural Subgraph Matching](https://mlsanity.com/paper/2007.03092/) (2020)
- [Multi-Task Learning for Conversational Question Answering over a Large-Scale Knowledge Base](https://mlsanity.com/paper/1910.05069/) (2019)
- [Neural Subgraph Isomorphism Counting](https://mlsanity.com/paper/1912.11589/) (2019)
- [Deriving Neural Architectures from Sequence and Graph Kernels](https://mlsanity.com/paper/1705.09037/) (2017)
- [Learning to Count Isomorphisms with Graph Neural Networks](https://mlsanity.com/paper/2302.03266/) (2023)
- [Graph Convolutional Networks with Dual Message Passing for Subgraph Isomorphism Counting and Matching](https://mlsanity.com/paper/2112.08764/) (2021)
- [A Generalized Weisfeiler-Lehman Graph Kernel](https://mlsanity.com/paper/2101.08104/) (2021)
- [Path Sampling: A Fast and Provable Method for Estimating 4-Vertex Subgraph Counts](https://mlsanity.com/paper/1411.4942/) (2014)
- [Motivo: fast motif counting via succinct color coding and adaptive sampling](https://mlsanity.com/paper/1906.01599/) (2019)
- [Gradual Weisfeiler-Leman: Slow and Steady Wins the Race](https://mlsanity.com/paper/2209.09048/) (2022)

## Abstract (arXiv)

Subgraph isomorphism counting is known as #P-complete and requires exponential time to find the accurate solution. Utilizing representation learning has been shown as a promising direction to represent substructures and approximate the solution. Graph kernels that implicitly capture the correlations among substructures in diverse graphs have exhibited great discriminative power in graph classification, so we pioneeringly investigate their potential in counting subgraph isomorphisms and further explore the augmentation of kernel capability through various variants, including polynomial and Gaussian kernels. Through comprehensive analysis, we enhance the graph kernels by incorporating neighborhood information. Finally, we present the results of extensive experiments to demonstrate the effectiveness of the enhanced graph kernels and discuss promising directions for future research.