mlsanityData to 14 Oct 2026

Towards Subgraph Isomorphism Counting with Graph Kernels

arXiv 2405.07497 ↗First posted 13 May 2024cs.LGcited by 0

Not on the map. Why?

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.

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

19 of 55 references.

References · 19

  1. 2018How Powerful are Graph Neural Networks?cited by 4,393
  2. 2017Neural Message Passing for Quantum Chemistrycited by 3,487
  3. 2019Transformer-XL: Attentive Language Models Beyond a Fixed-Length Contextcited by 1,850
  4. 2017Modeling Relational Data with Graph Convolutional Networkscited by 1,694
  5. 2018Graph Convolutional Neural Networks for Web-Scale Recommender Systemscited by 1,138
  6. 2014Convolutional Neural Networks for Sentence Classificationcited by 1,127
  7. 2019Composition-based Multi-Relational Graph Convolutional Networkscited by 396
  8. 2020Can Graph Neural Networks Count Substructures?cited by 236
  9. 2016On Valid Optimal Assignment Kernels and Applications to Graph Classificationcited by 49
  10. 2020Neural Subgraph Matchingcited by 47
  11. 2019Multi-Task Learning for Conversational Question Answering over a Large-Scale Knowledge Basecited by 33
  12. 2019Neural Subgraph Isomorphism Countingcited by 27
7 more
  1. 2017Deriving Neural Architectures from Sequence and Graph Kernelscited by 23
  2. 2023Learning to Count Isomorphisms with Graph Neural Networkscited by 13
  3. 2021Graph Convolutional Networks with Dual Message Passing for Subgraph Isomorphism Counting and Matchingcited by 11
  4. 2021A Generalized Weisfeiler-Lehman Graph Kernelcited by 9
  5. 2014Path Sampling: A Fast and Provable Method for Estimating 4-Vertex Subgraph Countscited by 8
  6. 2019Motivo: fast motif counting via succinct color coding and adaptive samplingcited by 8
  7. 2022Gradual Weisfeiler-Leman: Slow and Steady Wins the Racecited by 5

Built on by

Not cited yet.