# Fast, Accurate and Interpretable Graph Classification with Topological Kernels

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 37 references that are in the map.
- First posted on arXiv 22 Sep 2025.

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

- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Hierarchical Graph Representation Learning with Differentiable Pooling](https://mlsanity.com/paper/1806.08804/) (2018)
- [A Survey on Graph Kernels](https://mlsanity.com/paper/1903.11835/) (2019)
- [Graph Kernels: State-of-the-Art and Future Challenges](https://mlsanity.com/paper/2011.03854/) (2020)
- [Graph Kernels: A Survey](https://mlsanity.com/paper/1904.12218/) (2019)
- [Quantum algorithms for spectral sums](https://mlsanity.com/paper/2011.06475/) (2020)

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

- [Topology-Aware Multiscale Mixture of Experts for Efficient Molecular Property Prediction](https://mlsanity.com/paper/2601.12637/) (2026)

## Abstract (arXiv)

We introduce a novel class of explicit feature maps based on topological indices that represent each graph by a compact feature vector, enabling fast and interpretable graph classification. Using radial basis function kernels on these compact vectors, we define a measure of similarity between graphs. We perform evaluation on standard molecular datasets and observe that classification accuracies based on single topological-index feature vectors underperform compared to state-of-the-art substructure-based kernels. However, we achieve significantly faster Gram matrix evaluation -- up to 20× faster -- compared to the Weisfeiler--Lehman subtree kernel. To enhance performance, we propose two extensions: 1) concatenating multiple topological indices into an Extended Feature Vector (EFV), and 2) Linear Combination of Topological Kernels (LCTK) by linearly combining Radial Basis Function kernels computed on feature vectors of individual topological graph indices. These extensions deliver up to 12% percent accuracy gains across all the molecular datasets. A complexity analysis highlights the potential for exponential quantum speedup for some of the vector components. Our results indicate that LCTK and EFV offer a favourable trade-off between accuracy and efficiency, making them strong candidates for practical graph learning applications.